-La première section rappelle ce que sont les systèmes dynamiques chaotiques.
-\section{Systèmes dynamiques chaotiques selon Devaney}
-\label{subsec:Devaney}
-Dans cette partie, les définitions fondamentales liées au chaos
-dans les systèmes booléens sont rappelées.
-
-
-Soit un espace topologique $(\mathcal{X},\tau)$ et une fonction continue $f :
-\mathcal{X} \rightarrow \mathcal{X}$.
-
-
-
-
-\begin{Def}[Chaos selon Devaney~\cite{Devaney}]
-La fonction $f$ \emph{chaotique} sur $(\mathcal{X},\tau)$
-si elles est régulière et topologiquement transitive.
-\end{Def}
-
-
-
-\begin{Def}[Transitivite topologique]
-La fonction $f$ est dite \emph{topologiquement transitive} si,
-pour chaque paire d'ensembles ouverts
-$U,V \subset \mathcal{X}$,
-il existe $k>0$ tel que $f^k(U) \cap V \neq
-\varnothing$.
-\end{Def}
-
-\begin{Def}[Point périodique]
- Un point $P \in \mathcal{X}$ est dit \emph{périodique} de période $t$ pour
- une fonction $k$ si $t$ est un entier naturel non nul tel que $k^t(P) = P$ et
- pour tout $n$, $0 < n \le t-1$, on a $k^n(P) \neq P$.
- Par la suite, $\emph{Per(k)}$ dénote l'ensemble des points périodiques de
- $k$ dans $\mathcal{X}$ de période quelconque.
-\end{Def}
-
-
-
-\begin{Def}[Régularité]
-La fonction $f$ est dite \emph{régulière}
-sur $(\mathcal{X}, \tau)$ si l'ensemble des points périodiques
- de $f$ is dense in $\mathcal{X}$:
-pour chaque point $x \in \mathcal{X}$, chaque voisin
-de $x$ contient au moins un point périodique
-(sans que la période soit nécessairement constante).
-\end{Def}
-
-
-
-
-
-
-
-
-
-La propriété de chaos est souvent associée à la notion de
-\og sensibilité aux conditions initiales\fg{}, notion définie elle
-sur un espace métrique $(\mathcal{X},d)$ par:
-
-
-\begin{Def}[Forte sensibilité aux conditions initiales]
-Une fonction $k$ définie sur $(\mathcal{X},\tau)$
-est \emph{fortement sensible aux conditions initiales}
-s'il existe une valeur $\epsilon> 0$ telle que
-pour tout $X \in \mathcal{X}$ et pour tout
- $\delta > 0$, il existe $Y \in \mathcal{X}$ et
-$t \in \Nats$ qui vérifient $d(X,Y) < \delta$ et
-$d(k^t(X) , k^t(Y)) > \epsilon$.
-
-La constante $\delta$ est appelée \emph{constante de sensibilité} de $f$.
-\end{Def}
-
-John Banks et ses collègues ont cependant
-démontré que la sensibilité aux conditions initiales est une conséquence
-de la régularité et de la transitivité topologique~\cite{Banks92}.
-
-
-
-\section{Schéma unaire}
Soit ${\mathsf{N}}$ un entier naturel et $f$ une fonction de
$\Bool^{{\mathsf{N}}}$ dans lui-même.
-\section{Schéma généralisé}
+
--- /dev/null
+On reprend ici le même plan que dans la section précédente.
+
+Soit ${\mathsf{N}}$ un entier naturel et $f$ une fonction de
+$\Bool^{{\mathsf{N}}}$ dans lui-même.
+
+
+\subsection{Des itérations généralisées aux itérations parallèles}
+
+Dans le schéma généralisé, à la $t^{\textrm{ème}}$ itération,
+c'est l'ensemble
+des $s_{t}^{\textrm{ème}}$ éléments (inclus dans $[n]$) qui
+sont mis à jour (c.f. équation~(\ref{eq:schema:generalise})).
+On redéfinit la fonction la fonction
+ $F_f: \Bool^{\mathsf{N}} \times \mathcal{P}(\{1, \ldots, \mathsf{N}\})
+ \rightarrow \Bool^{\mathsf{N}}$ par
+ \[
+ F_f(x,s)_i=\left\{
+ \begin{array}{l}
+ f_i(x) \textrm{ si $i \in s$;}\\
+ x_i \textrm{ sinon.}
+ \end{array}\right.
+ \]
+
+Dans ce schéma d'itérations généralisées,
+pour une configuration initiale
+$x^0\in\Bool^{\mathsf{N}}$ et une stratégie $S = \left(s_t\right)_{t \in \mathds{N}}
+\in \mathcal{P}(\{1, \ldots, {\mathsf{N}}\})^{\Nats}$,
+les
+configurations $x^t$ sont définies par la récurrence
+\begin{equation}\label{eq:asyn}
+ x^{t+1}=F_f(s_t,x^t).
+ \end{equation}
+ Soit alors $G_f$ une fonction de $\Bool^{\mathsf{N}} \times \mathcal{P}(\{1, \ldots, {\mathsf{N}}\})^{\Nats}$
+ dans lui-même définie par
+ \[
+ G_f(S,x)=(\sigma(S),F_f(s_0,x)),
+ \]
+ où la fonction $\sigma$ est définit comme à la section précédente.
+ A nouveau, les itérations généralisées
+ de $f$ induites par $x^0$ et la stratégie $S$.
+ décrivent la même orbite que les
+ itérations parallèles de $G_f$ depuis un point initial
+ $X^0=(x^0,S)$
+
+
+
+%%%%%%%%%%%%%%%%%%%%
+On peut alors construire l'espace
+$\mathcal{X} = \Bool^{\mathsf{N}} \times
+\mathcal{P}(\{1, \ldots, {\mathsf{N}}\})^{\Nats}$
+
+\subsection{Une métrique pour $\mathcal{X}$}
+
+Cette nouvelle distance va comparer des ensembles.
+On rappelle pour quelques notions ensemblistes.
+Pour $A$ et $B$ deux ensembles de l'univers $\Omega$,
+on rappelle la définition de l'opérateur
+de \emph{différence ensembliste} symétrique :
+\[
+A \Delta B = (A \cap \overline{B}) \cup (\overline{A} \cap B)
+\]
+où $\overline{B}$ désigne le complémentaire de $B$ dans $\Omega$.
+
+On considère l'espace $\mathcal{X}=\mathcal{P}(\{1, \ldots, {\mathsf{N}}\})^{\Nats}\times
+\Bool^{\mathsf{N}}$ et
+on définit la distance $d$ entre les points $X=(S,x)$ et
+$X'=(S',x')$ de $\mathcal{X}$ par
+\[
+d(X,X')= d_H(x,x')+d_S(S,S'),~\textrm{où}~
+\left\{
+\begin{array}{l}
+\displaystyle{d_H(x,x')=\sum_{i=1}^{\mathsf{N}} |x_i-x'_i|}\\[5mm]
+\displaystyle{d_S(S,S')=\frac{9}{{\mathsf{N}}}\sum_{t\in\Nats}\frac{|S_t \Delta S'_t|}{10^{t+1}}}.
+\end{array}
+\right.\,.
+\]
+
+La fonction $d$ est une somme de deux fonctions.
+La fonction $d_H$ est la distance de Hamming; il est aussi établi que la
+somme de deux distances est une distance.
+Ainsi, pour montrer que $d$ est aussi une distance, il suffit
+de montrer que $d_S$ en une aussi, ce qui est fait en annexe~\ref{anx:distance:generalise}.
+
+La section suivante caractérise les fonctions $f$ qui sont
+chaotiques pour le schéma généralisées.
+
+
+\subsection{Caractérisation des fonctions chaotiques
+pour le schéma généralisé}
+On a les théorèmes suivants dont les preuves sont données en
+annexe~\ref{anx:chaos:generalise}.
+
+\begin{theorem} $G_f$ est transitive si et seulement si
+ $\Gamma(f)$ est fortement connexe.
+\end{theorem}
+
+\begin{theorem}
+\label{Prop: T est dans R} $\mathcal{T} \subset \mathcal{R}$.
+\end{theorem}
+
+
+\begin{theorem}%[Characterization of $\mathcal{C}$]
+\label{Th:CaracIC}
+Soit $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$. La fonction $G_f$ est chaotique
+si et seulement si $\Gamma(f)$ est fortement connexe.
+\end{theorem}
+
+
+
+
+
+
+
+
+
--- /dev/null
+
+Commençons par caractériser l'ensemble $\mathcal{T}$ des fonctions transitives:
+
+\begin{theorem} $G_f$ est transitive si et seulement si
+ $\Gamma(f)$ est fortement connexe.
+\end{theorem}
+
+\begin{Proof}
+
+$\Longleftarrow$ Supposons que $\Gamma(f)$ soit fortement connexe.
+Soient $(x,S)$ et $(x',S')$ deux points de $\mathcal{X}$ et $\varepsilon >0$.
+On construit la stratégie $\tilde S$ telle que la distance
+entre $(x,\tilde S)$ et $(x,S)$ est inférieure à
+$\varepsilon$ et telle que les itérations parallèles de $G_f$ depuis
+$(x,\tilde S)$ mènent au point $(x',S')$.
+
+Pour cela, on pose $t_1 =-\lfloor\log_{10}(\varepsilon)\rfloor$ et $x''$ la
+configuration de $\Bool^{\mathsf{N}}$ obtenue depuis $(x,S)$
+après $t_1$ itérations
+parallèles de $G_f$.
+Comme $\Gamma(f)$ est fortement connexe, il existe une
+stratégie $S''$ et un entier $t_2$ tels que $x'$ est atteint depuis
+$(x'',S'')$ après $t_2$ itérations de $G_f$.
+
+Considérons à présent la stratégie
+$\tilde S=(s_0,\dots,s_{t_1-1},s''_0,\dots,s''_{t_2-1},s'_0,s'_1,s'_2,s'_3\dots)$.
+Il est évident que $(x',s')$ est atteint depuis $(x,\tilde S)$ après
+$t_1+t_2$ itérations parallèles de $G_f$. Puisque
+$\tilde s_t=s_t$ pour $t<t_1$, grâce au choix de $t_1$,
+on a $d((x,S),(x,\tilde S))<\epsilon$.
+Par conséquent, $G_f$ est transitive.
+
+$\Longrightarrow$ Démontrons la contraposée.
+Si $\Gamma(f)$ n'est pas fortement connexe, alors
+il existe deux configurations $x$ et $x'$ telles qu'aucun chemin de
+$\Gamma(f)$ ne mène de $x$ à $x'$.
+Soient $S$ et $S'$ deux stratégies et $\varepsilon \in ]0;1[$.
+Alors, pour tout $(x'',S'')$ tel que
+$d((x'',S''),(x,S))<\varepsilon$ on a $x''$ qui est égal à $x$.
+Comme il n'existe aucun chemin de $\Gamma(f)$
+qui mène de $x$ à $x'$,
+les itérations de $G_f$ à partir de
+$(x'',S'') = (x,S'')$ ne peuvent atteindre que des points
+$(x''',S''')$ de $\mathcal{X}$ tels que $x''' \neq x'$,
+et donc ne peuvent pas atteindre $(x',S')$.
+On peut remarquer que, du fait que $x''' \neq x'$,
+elles n'atteignent que des points de $\mathcal{X}$
+dont la distance à $(x',S')$ est supérieure à 1.
+Pour tout entier naturel $t$, on a
+$G_f^t(x'',S'') \neq (x',S')$.
+Ainsi $G_f$ n'est pas transitive et
+par contraposée, on a la démonstration souhaitée.
+\end{Proof}
+
+
+Prouvons à présent le théorème suivant:
+
+\begin{theorem}
+\label{Prop: T est dans R} $\mathcal{T} \subset \mathcal{R}$.
+\end{theorem}
+
+
+\begin{Proof}
+Soit $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$ telle que $G_f$ est transitive (\textit{i.e.}
+$f$ appartient à $\mathcal{T}$).
+Soit $(x,S) \in\mathcal{X}$ et $\varepsilon >0$. Pour
+prouver que $f$ appartient à $\mathcal{R}$, il suffit de prouver
+qu'il existe une stratégie $\tilde S$ telle que la distance entre
+$(x,\tilde S)$ et $(x,S)$ est inférieure à $\varepsilon$ et telle que
+$(x,\tilde S)$ est un point périodique.
+
+Soit $t_1=-\lfloor \log_{10}(\varepsilon)\rfloor$ et soit $x'$ la
+configuration obtenue après $t_1$ itérations de $G_f$ depuis $(x,S)$.
+D'après la proposition précédente, $\Gamma(f)$ est fortement connexe.
+Ainsi, il existe une stratégie $S'$ et un nombre $t_2\in\Nats$ tels
+que $x$ est atteint depuis $(x',S')$ après $t_2$ itérations de $G_f$.
+
+Soit alors la stratégie $\tilde S$ qui alterne les $t_1$ premiers termes
+de $S$ avec les $t_2$ premiers termes de $S'$.
+Ainsi $\tilde S$ est définie par
+\begin{equation*}
+(s_0,\dots,s_{t_1-1},s'_0,\dots,s'_{t_2-1},s_0,\dots,s_{t_1-1},s'_0,\dots,s'_{t_2-1},s_0,\dots).
+\end{equation*}
+Il est évident que $(x,\tilde S)$ s'obtient à partir de $(x,\tilde S)$ après
+$t_1+t_2$ itérations parallèles de $G_f$. Ainsi $(x,\tilde S)$ est un point
+périodique. Puisque $\tilde s_t$ est égal à $s_t$ pour $t<t_1$, d'après le
+choix de $t_1$, on a $d((x,S),(x,\tilde S))<\epsilon$.
+\end{Proof}
+
+On peut conclure que $\mathcal{C} = \mathcal{R} \cap \mathcal{T}
+= \mathcal{T}$. On a alors la caractérisation suivante:
+
+\begin{theorem}%[Characterization of $\mathcal{C}$]
+\label{Th:CaracIC}
+Soit $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$. La fonction $G_f$ est chaotique
+si et seulement si $\Gamma(f)$ est fortement connexe.
+\end{theorem}
\begin{Proof}
$\Longleftarrow$ Supposons que $\Gamma(f)$ soit fortement connexe.
-Soient $(S,x)$ et $(S',x')$ deux points de $\mathcal{X}$ et $\varepsilon >0$.
+Soient $(x,S)$ et $(x',S')$ deux points de $\mathcal{X}$ et $\varepsilon >0$.
On construit la stratégie $\tilde S$ telle que la distance
-entre $(\tilde S,x)$ et $(S,x)$ est inférieure à
+entre $(x,\tilde S)$ et $(x,S)$ est inférieure à
$\varepsilon$ et telle que les itérations parallèles de $G_f$ depuis
-$(\tilde S,x)$ mènent au point $(S',x')$.
+$(x,\tilde S)$ mènent au point $(x',S')$.
Pour cela, on pose $t_1 =-\lfloor\log_{10}(\varepsilon)\rfloor$ et $x''$ la
-configuration de $\Bool^n$ obtenue depuis $(S,x)$ après $t_1$ itérations
+configuration de $\Bool^{\mathsf{N}}$ obtenue depuis $(x,S)$ après $t_1$
+itérations
parallèles de $G_f$.
Comme $\Gamma(f)$ est fortement connexe, il existe une
stratégie $S''$ et un entier $t_2$ tels que $x'$ est atteint depuis
-$(S'',x'')$ après $t_2$ itérations de $G_f$.
+$(x'',S'')$ après $t_2$ itérations de $G_f$.
Considérons à présent la stratégie
$\tilde S=(s_0,\dots,s_{t_1-1},s''_0,\dots,s''_{t_2-1},s'_0,s'_1,s'_2,s'_3\dots)$.
-Il est évident que $(s',x')$ est atteint depuis $(\tilde S,x)$ après
+Il est évident que $(x',s')$ est atteint depuis $(x,\tilde S)$ après
$t_1+t_2$ itérations parallèles de $G_f$. Puisque
$\tilde s_t=s_t$ pour $t<t_1$, grâce au choix de $t_1$,
-on a $d((S,x),(\tilde
-S,x))<\epsilon$.
+on a $d((x,S),(x,\tilde S))<\epsilon$.
Par conséquent, $G_f$ est transitive.
$\Longrightarrow$ Démontrons la contraposée.
il existe deux configurations $x$ et $x'$ telles qu'aucun chemin de
$\Gamma(f)$ ne mène de $x$ à $x'$.
Soient $S$ et $S'$ deux stratégies et $\varepsilon \in ]0;1[$.
-Alors, pour tout $(S'',x'')$ tel que
-$d((S'',x''),(S,x))<\varepsilon$ on a $x''$ qui est égal à $x$.
+Alors, pour tout $(x'',S'')$ tel que
+$d((x'',S''),(x,S))<\varepsilon$ on a $x''$ qui est égal à $x$.
Comme il n'existe aucun chemin de $\Gamma(f)$
qui mène de $x$ à $x'$,
les itérations de $G_f$ à partir de
-$(S'', x'') = (S'', x)$ ne peuvent atteindre que des points
-$(S''', x''')$ de $\mathcal{X}$ tels que $x''' \neq x'$,
-et donc ne peuvent pas atteindre $(S', x')$.
+$(x'',S'') = (x,S'')$ ne peuvent atteindre que des points
+$(x''',S''')$ de $\mathcal{X}$ tels que $x''' \neq x'$,
+et donc ne peuvent pas atteindre $(x',S')$.
On peut remarquer que, du fait que $x''' \neq x'$,
elles n'atteignent que des points de $\mathcal{X}$
-dont la distance à $(S', x')$ est supérieure à 1.
+dont la distance à $(x',S')$ est supérieure à 1.
Pour tout entier naturel $t$, on a
-$G_f^t(S'',x'') \neq (S',x')$.
+$G_f^t(x'',S'') \neq (x',S')$.
Ainsi $G_f$ n'est pas transitive et
par contraposée, on a la démonstration souhaitée.
\end{Proof}
\begin{Proof}
-Soit $f:\Bool^n\to\Bool^n$ telle que $G_f$ est transitive (\textit{i.e.}
+Soit $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$ telle que $G_f$ est transitive (\textit{i.e.}
$f$ appartient à $\mathcal{T}$).
-Soit $(S,x) \in\mathcal{X}$ et $\varepsilon >0$. Pour
+Soit $(x,S) \in\mathcal{X}$ et $\varepsilon >0$. Pour
prouver que $f$ appartient à $\mathcal{R}$, il suffit de prouver
qu'il existe une stratégie $\tilde S$ telle que la distance entre
-$(\tilde S,x)$ et $(S,x)$ est inférieure à $\varepsilon$ et telle que
-$(\tilde S,x)$ est un point périodique.
+$(x,\tilde S)$ et $(x,S)$ est inférieure à $\varepsilon$ et telle que
+$(x,\tilde S)$ est un point périodique.
Soit $t_1=-\lfloor \log_{10}(\varepsilon)\rfloor$ et soit $x'$ la
-configuration obtenue après $t_1$ itérations de $G_f$ depuis $(S,x)$.
+configuration obtenue après $t_1$ itérations de $G_f$ depuis $(x,S)$.
D'après la proposition précédente, $\Gamma(f)$ est fortement connexe.
Ainsi, il existe une stratégie $S'$ et un nombre $t_2\in\Nats$ tels
-que $x$ est atteint depuis $(S',x')$ après $t_2$ itérations de $G_f$.
+que $x$ est atteint depuis $(x',S')$ après $t_2$ itérations de $G_f$.
Soit alors la stratégie $\tilde S$ qui alterne les $t_1$ premiers termes
de $S$ avec les $t_2$ premiers termes de $S'$.
\begin{equation*}
(s_0,\dots,s_{t_1-1},s'_0,\dots,s'_{t_2-1},s_0,\dots,s_{t_1-1},s'_0,\dots,s'_{t_2-1},s_0,\dots).
\end{equation*}
-Il est évident que $(\tilde S,x)$ s'obtient à partir de $(\tilde S,x)$ après
-$t_1+t_2$ itérations parallèles de $G_f$. Ainsi $(\tilde S,x)$ est un point
+Il est évident que $(x,\tilde S)$ s'obtient à partir de $(x,\tilde S)$ après
+$t_1+t_2$ itérations parallèles de $G_f$. Ainsi $(x,\tilde S)$ est un point
périodique. Puisque $\tilde s_t$ est égal à $s_t$ pour $t<t_1$, d'après le
-choix de $t_1$, on a $d((S,x),(\tilde S,x))<\epsilon$.
+choix de $t_1$, on a $d((x,S),(x,\tilde S))<\epsilon$.
\end{Proof}
On peut conclure que $\mathcal{C} = \mathcal{R} \cap \mathcal{T}
\begin{theorem}%[Characterization of $\mathcal{C}$]
\label{Th:CaracIC}
-Soit $f:\Bool^n\to\Bool^n$. La fonction $G_f$ est chaotique
+Soit $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$. La fonction $G_f$ est chaotique
si et seulement si $\Gamma(f)$ est fortement connexe.
\end{theorem}
--- /dev/null
+
+Dans cette partie, les définitions fondamentales liées au chaos
+dans les systèmes booléens sont rappelées.
+
+
+
+Soit un espace topologique $(\mathcal{X},\tau)$ et une fonction continue $f :
+\mathcal{X} \rightarrow \mathcal{X}$.
+
+
+
+
+\begin{Def}[Chaos selon Devaney~\cite{Devaney}]
+La fonction $f$ \emph{chaotique} sur $(\mathcal{X},\tau)$
+si elles est régulière et topologiquement transitive.
+\end{Def}
+
+
+
+\begin{Def}[Transitivite topologique]
+La fonction $f$ est dite \emph{topologiquement transitive} si,
+pour chaque paire d'ensembles ouverts
+$U,V \subset \mathcal{X}$,
+il existe $k>0$ tel que $f^k(U) \cap V \neq
+\varnothing$.
+\end{Def}
+
+\begin{Def}[Point périodique]
+ Un point $P \in \mathcal{X}$ est dit \emph{périodique} de période $t$ pour
+ une fonction $k$ si $t$ est un entier naturel non nul tel que $k^t(P) = P$ et
+ pour tout $n$, $0 < n \le t-1$, on a $k^n(P) \neq P$.
+ Par la suite, $\emph{Per(k)}$ dénote l'ensemble des points périodiques de
+ $k$ dans $\mathcal{X}$ de période quelconque.
+\end{Def}
+
+
+
+\begin{Def}[Régularité]
+La fonction $f$ est dite \emph{régulière}
+sur $(\mathcal{X}, \tau)$ si l'ensemble des points périodiques
+ de $f$ is dense in $\mathcal{X}$:
+pour chaque point $x \in \mathcal{X}$, chaque voisin
+de $x$ contient au moins un point périodique
+(sans que la période soit nécessairement constante).
+\end{Def}
+
+
+
+
+
+
+
+
+
+La propriété de chaos est souvent associée à la notion de
+\og sensibilité aux conditions initiales\fg{}, notion définie elle
+sur un espace métrique $(\mathcal{X},d)$ par:
+
+
+\begin{Def}[Forte sensibilité aux conditions initiales]
+Une fonction $k$ définie sur $(\mathcal{X},\tau)$
+est \emph{fortement sensible aux conditions initiales}
+s'il existe une valeur $\epsilon> 0$ telle que
+pour tout $X \in \mathcal{X}$ et pour tout
+ $\delta > 0$, il existe $Y \in \mathcal{X}$ et
+$t \in \Nats$ qui vérifient $d(X,Y) < \delta$ et
+$d(k^t(X) , k^t(Y)) > \epsilon$.
+
+La constante $\delta$ est appelée \emph{constante de sensibilité} de $f$.
+\end{Def}
+
+John Banks et ses collègues ont cependant
+démontré que la sensibilité aux conditions initiales est une conséquence
+de la régularité et de la transitivité topologique~\cite{Banks92}.
+
+
+
+
+
+
+
+
+
+
+
\chapter{Characterisation des systèmes
discrets chaotiques}
+
+La première section rappelle ce que sont les systèmes dynamiques chaotiques.
Dire que cette caractérisation dépend du type de stratégie : unaire (TIPE),
généralisée (TSI). Pour chacune d'elle,
on introduit une distance différente.
On montre qu'on a des résultats similaires.
+\section{Systèmes dynamiques chaotiques selon Devaney}
+\label{subsec:Devaney}
+\input{devaney}
+
+\section{Schéma unaire}
\input{12TIPE}
+\section{Schéma généralisé}
+\input{15TSI}
générer des fonctions vérifiant ceci (TIPE12 juste sur le résultat d'adrien).
\input{annexecontinuite.tex}
+
+
\section{Caractérisation des fonctions $f$ rendant chaotique $G_f$ dans $(\mathcal{X},d)$}\label{anx:chaos:unaire}
\input{caracunaire.tex}
+\section{Preuve que $d$ est une distance sur $\mathcal{X}$}\label{anx:distance:generalise}
+\input{preuveDistanceGeneralisee}
+
+\section{Caractérisation des fonctions $f$ rendant chaotique $G_f$ dans $(\mathcal{X},d)$}\label{anx:chaos:generalise}
+\input{caracgeneralise.tex}
--- /dev/null
+Pour $S,S' \in \mathcal{P}(\{1, \ldots, {\mathsf{N}}\})$,
+on définit
+\[
+\displaystyle{d_S(S,S')=\frac{9}{{\mathsf{N}}}\sum_{t\in\Nats}\frac{|S_t \Delta S'_t|}{10^{t+1}}}.
+\]
+Montrons que $d_S$ est une distance sur $\mathcal{P}(\{1, \ldots, {\mathsf{N}}\})$.
+
+
+
+Soit $S$, $S'$ et $S''$ trois parties de $[{\mathsf{N}}]$.
+\begin{itemize}
+\item De manière évidente, $d_s(S,S')$ est positive ou bien nulle si
+ et seulement si $S$ et $S'$ sont égales.
+\item Comme la différence symétrique est commutative, la valeur de
+ $d_S(S,S')$ est égale à celle de $d_S(S',S)$.
+\item On a enfin la succession d'éléments suivants:
+ $$
+ \begin{array}{rcl}
+ S \Delta S' & = & (S \cap \overline{S'}) \cup (\overline{S} \cap S')\\
+ & = & (S \cap \overline{S'} \cap S'' ) \cup (S \cap \overline{S'} \cap \overline{S''} ) \cup (\overline{S} \cap S'\cap S'') \cup (\overline{S} \cap S'\cap \overline{S''})\\
+ & \subseteq & (S \cap \overline{S'} \cap S'' ) \cup (S \cap \overline{S'} \cap \overline{S''} ) \cup (\overline{S} \cap S'\cap S'') \cup (\overline{S} \cap S'\cap \overline{S''}) \cup \\
+ & & (\overline{S} \cap \overline{S'} \cap S'') \cup (S \cap S' \cap \overline{S''} ) \cup (\overline{S} \cap \overline{S'} \cap S'') \cup (S \cap S' \cap \overline{S''})\\
+ & = & (\overline{S'} \cap S'' ) \cup (S \cap \overline{S''} ) \cup (\overline{S} \cap S'') \cup (S'\cap \overline{S''}) \\
+ & = & (S \Delta S'') \cup (S'' \Delta S')
+ \end{array}
+ $$
+ On en déduit ainsi que
+$|S \Delta S'| \le |S \Delta S''| + |S'' \Delta S'|$ et donc que
+l'égalité triangulaire $d_S(S,S') \le d_S(S,S'') + d_S(S'',S')$ est établie.
+\end{itemize}
+
+
+
unaire de négation \og $\overline{\mathstrut\enskip}$ \fg{}.
-Soit $n$ un entier naturel.
-On introduit quelques notations à propos d'éléments de $\Bool^n$.
-L'ensemble $\{1,\dots, n\}$ sera par la suite noté $[n]$.
+Soit ${\mathsf{N}}$ un entier naturel.
+On introduit quelques notations à propos d'éléments de $\Bool^{\mathsf{N}}$.
+L'ensemble $\{1,\dots, {\mathsf{N}}\}$ sera par la suite noté $[{\mathsf{N}}]$.
Le $i^{\textrm{ème}}$ composant d'un élément
-$x \in \Bool^n$ s'écrit $x_i$.
-Si l'ensemble $I$ est une partie de $[n]$, alors
-$\overline{x}^I$ est l'élément $y\in \Bool^n$
+$x \in \Bool^{\mathsf{N}}$ s'écrit $x_i$.
+Si l'ensemble $I$ est une partie de $[{\mathsf{N}}]$, alors
+$\overline{x}^I$ est l'élément $y\in \Bool^{\mathsf{N}}$
tel que $y_i = 1 - x_i$ si $i\in I$ et
$y_i = x_i$ sinon.
-On considère les deux abréviations $\overline{x}$ pour $\overline{x}^{[n]}$
+On considère les deux abréviations $\overline{x}$ pour $\overline{x}^{[{\mathsf{N}}]}$
(chaque composant de $\overline{x}$ est nié:
c'est une négation composante à composante)
-et $\overline{x}^i$ pour $\overline{x}^{\{i\}}$ pour $i \in [n]$
+et $\overline{x}^i$ pour $\overline{x}^{\{i\}}$ pour $i \in [{\mathsf{N}}]$
(seul $x_i$ est nié dans $\overline{x}$).
-Pour tout $x$ et $y$ dans $\Bool^n$, l'ensemble
-$\Delta(x, y)$, contient les $i \in [n]$
+Pour tout $x$ et $y$ dans $\Bool^{\mathsf{N}}$, l'ensemble
+$\Delta(x, y)$, contient les $i \in [{\mathsf{N}}]$
tels que $x_i \neq y_i$.
-Soit enfin $f : \Bool^n \rightarrow \Bool^n$. Son $i^{\textrm{ème}}$ composant
-est nommé $f_i$ qui est une fonction de $\Bool^n$ dans $\Bool$.
+Soit enfin $f : \Bool^n \rightarrow \Bool^{\mathsf{N}}$. Son $i^{\textrm{ème}}$ composant
+est nommé $f_i$ qui est une fonction de $\Bool^{\mathsf{N}}$ dans $\Bool$.
Pour chaque
-$x$ dans $\Bool^n$, l'ensemble
+$x$ dans $\Bool^{\mathsf{N}}$, l'ensemble
$\Delta f(x)$ est défini par $\Delta f(x) = \Delta(x,f(x))$.
On peut admettre que $f (x) = \overline{x}^{\Delta f(x)}$ .
\begin{xpl}\label{xpl:1}
-On considère $n= 3$ et $f:\Bool^3 \rightarrow \Bool^3$ telle que
+On considère ${\mathsf{N}}= 3$ et $f:\Bool^3 \rightarrow \Bool^3$ telle que
$f(x)=(f_1(x),f_2(x),f_3(x))$ avec
$$\begin{array}{rcl}
f_1(x_1, x_2, x_3) &=& (\overline{x_1} + \overline{x_2}).x_3 \textrm{, }\\
Un réseau booléen est
défini à partir d'une fonction booléenne:
\[
-f:\Bool^n\to\Bool^n,\qquad x=(x_1,\dots,x_n)\mapsto f(x)=(f_1(x),\dots,f_n(x)),
+f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}},\qquad x=(x_1,\dots,x_{\mathsf{N}})\mapsto f(x)=(f_1(x),\dots,f_{\mathsf{N}}(x)),
\]
-et un {\emph{schéma itératif}} ou encore \emph{mode de mise à jour}. À partir d'une configuration initiale $x^0\in\Bool^n$, la suite $(x^{t})^{t
+et un {\emph{schéma itératif}} ou encore \emph{mode de mise à jour}. À partir d'une configuration initiale $x^0\in\Bool^{\mathsf{N}}$, la suite $(x^{t})^{t
\in \Nats}$ des configurations du système est construite selon l'un des
schémas suivants :
\begin{itemize}
\item \textbf{Schéma parallèle synchrone :} basé sur la relation de récurrence
- $x^{t+1}=f(x^t)$. Tous les $x_i$, $1 \le i \le n$, sont ainsi mis à jour à
+ $x^{t+1}=f(x^t)$. Tous les $x_i$, $1 \le i \le {\mathsf{N}}$, sont ainsi mis à jour à
chaque itération en utilisant l'état global précédent du système $x^t$.
\item \textbf{Schéma unaire :} ce schéma est parfois
qualifié de chaotique
dans la littérature.
Il consiste à modifier la valeur
- d'un unique élément $i$, $1 \le i \le n$, à
+ d'un unique élément $i$, $1 \le i \le {\mathsf{N}}$, à
chaque itération. Le choix de l'élément qui est modifié à chaque itération est
défini par une suite
$S = \left(s^t\right)^{t \in \mathds{N}}$ qui est une séquence
- d'indices dans $[n]$. Cette suite est appelée \emph{stratégie unaire}.
- Il est basé sur la relation définie pour tout $i \in [n]$ par
- $$
+ d'indices dans $[{\mathsf{N}}]$. Cette suite est appelée \emph{stratégie unaire}.
+ Il est basé sur la relation définie pour tout $i \in [{\mathsf{N}}]$ par
+
+\begin{equation}
x^{t+1}_i=
\left\{ \begin{array}{l}
f_i(x^t) \textrm{ si } i=s^t, \\
x^t_i\textrm{ sinon.}
\end{array}
- \right.$$
+ \right.
+\label{eq:schema:unaire}
+\end{equation}
\item \textbf{Schéma généralisé:} dans ce schéma, ce sont les valeurs
- d'un ensemble d'éléments de $[n]$ qui sont modifiées à chaque itération.
+ d'un ensemble d'éléments de $[{\mathsf{N}}]$ qui sont modifiées à chaque itération.
Dans le cas particulier où c'est la valeur d'un singleton
- $\{k\}$, $1 \le k \le n$, qui est modifiée à
+ $\{k\}$, $1 \le k \le {\mathsf{N}}$, qui est modifiée à
chaque itération, on retrouve le
mode unaire. Dans le second cas particulier où ce sont les valeurs de
- tous les éléments de $\{1, \ldots, n\}$ qui sont modifiées
+ tous les éléments de $\{1, \ldots, {\mathsf{N}}\}$ qui sont modifiées
à chaque itération, on retrouve le mode
parallèle. Ce mode généralise donc les deux modes précédents.
Plus formellement, à la $t^{\textrm{ème}}$
itération, seuls les éléments de la partie
- $s^{t} \in \mathcal{P}([n])$ sont mis à
+ $s^{t} \in \mathcal{P}([{\mathsf{N}}])$ sont mis à
jour. La suite $S = \left(s^t\right)^{t \in \mathds{N}}$ est une séquence
de sous-ensembles
- de $[n]$ appelée \emph{stratégie généralisée}.
- Il est basé sur la relation définie pour tout $i \in [n]$ par
- $$
+ de $[{\mathsf{N}}]$ appelée \emph{stratégie généralisée}.
+ Il est basé sur la relation définie pour tout $i \in [{\mathsf{N}}]$ par
+ \begin{equation}
x^{t+1}_i=
\left\{ \begin{array}{l}
f_i(x^t) \textrm{ si } i \in s^t, \\
x^t_i\textrm{ sinon.}
\end{array}
- \right.$$
+ \right.
+\label{eq:schema:generalise}
+\end{equation}
+
-Pour un entier naturel $n$ et une
-fonction $f : B^n \rightarrow B^n$, plusieurs évolutions sont possibles
+Pour un entier naturel ${\mathsf{N}}$ et une
+fonction $f : B^{\mathsf{N}} \rightarrow B^{\mathsf{N}}$, plusieurs évolutions sont possibles
en fonction du schéma itératif retenu.
Celles-ci sont représentées par un graphe orienté dont les noeuds
-sont les éléments de $\Bool^n$ (voir \textsc{Figure}~\ref{fig:xpl:graphs}).
+sont les éléments de $\Bool^{\mathsf{N}}$ (voir \textsc{Figure}~\ref{fig:xpl:graphs}).
\begin{itemize}
\item Le \emph{graphe des itérations synchrones} de $f$, noté $\textsc{gis}(f)$
-est le graphe orienté de $\Bool^n$ qui contient un arc $x \rightarrow y$ si
+est le graphe orienté de $\Bool^{\mathsf{N}}$ qui contient un arc $x \rightarrow y$ si
et seulement si $y=f(x)$.
\item Le \emph{graphe des itérations unaires} de $f$, noté $\textsc{giu}(f)$
-est le graphe orienté de $\Bool^n$ qui contient un arc $x \rightarrow y$ si
+est le graphe orienté de $\Bool^{\mathsf{N}}$ qui contient un arc $x \rightarrow y$ si
et seulement s'il existe $x \in \Delta f(x)$ tel que $y = \overline{x}^i$.
\item Le \emph{graphe des itérations généralisées} de $f$, noté $\textsc{gig}(f)$
-est le graphe orienté de $\Bool^n$ qui contient un arc $x \rightarrow y$ si
+est le graphe orienté de $\Bool^{\mathsf{N}}$ qui contient un arc $x \rightarrow y$ si
et seulement s'il existe un ensemble $I\subseteq \Delta f(x)$ tel que
$y = \overline{x}^I$. On peut remarquer que ce graphe contient comme
sous-graphe à la fois celui des itérations synchrones et celui
\subsection{Attracteurs}
On dit que le point
-$x \in \Bool^n$ est un \emph{point fixe} de $f$ si $x = f (x)$.
+$x \in \Bool^{\mathsf{N}}$ est un \emph{point fixe} de $f$ si $x = f (x)$.
Les points fixes sont particulièrement intéressants car ils correspondent
aux états stables:
dans chaque graphe d'itérations, le point $x$ est un point fixe
-Soit $\Gamma$ un graphe d'itérations (synchrones, unaires ou généralisées)
+Soit un graphe d'itérations (synchrones, unaires ou généralisées)
de $f$.
-Les \emph{attracteurs} de $\Gamma$ sont les
+Les \emph{attracteurs} de ce graphe sont les
plus petits sous-ensembles (au sens de l'inclusion) non vides
-$A \subseteq \Bool^n$ tels que pour tout arc
-$x \rightarrow y$ de $\Gamma$, si $x$ est un élément de $A$, alors
+$A \subseteq \Bool^{\mathsf{N}}$ tels que pour tout arc
+$x \rightarrow y$, si $x$ est un élément de $A$, alors
$y$ aussi.
Un attracteur qui contient au moins deux éléments est dit \emph{cyclique}.
On en déduit qu'un attracteur cyclique ne contient pas de point fixe.
\begin{theorem}\label{Prop:attracteur}
Le point $x$ est un point fixe si et seulement si
-$\{x\}$ est un attracteur de $\Gamma$.
-En d'autres termes, les attracteurs non cycliques de $\Gamma$
+$\{x\}$ est un attracteur du graphe d'itération (synchrone, unaire, généralisé).
+En d'autres termes, les attracteurs non cycliques de celui-ci
sont les points fixes de $f$.
-Ainsi pour chaque $x\in \Bool^n$, il existe au moins un chemin
+Ainsi pour chaque $x\in \Bool^{\mathsf{N}}$, il existe au moins un chemin
depuis $x$ qui atteint un attracteur.
-Ainsi $\Gamma$ contient toujours au moins un attracteur.
+Ainsi tout graphe d'itérations contient toujours au moins un attracteur.
\end{theorem}
système peuvent être mémorisées
dans la {\emph{matrice jacobienne discrète}} $f'$.
Celle-ci est définie comme étant la fonction qui à chaque
-configuration $x\in\Bool^n$ associe la matrice de taille
+configuration $x\in\Bool^{\mathsf{N}}$ associe la matrice de taille
$n\times n$ telle que
\begin{equation}
f'(x)=(f'_{ij}(x)),\qquad
dans $\Z$.
Lorsqu'on supprime les signes dans la matrice jacobienne discrète,
on obtient une matrice notée $B(f)$ aussi de taille
-$n\times n$.
+${\mathsf{N}}\times {\mathsf{N}}$.
Celle-ci mémorise uniquement
l'existence d'une dépendance de tel élément vis à vis de
tel élément.
\emph{matrice d'incidence}.
\begin{theorem}
-Si $f_i$ ne dépend pas de $x_j$, alors pour tout $x\in [n]$,
+Si $f_i$ ne dépend pas de $x_j$, alors pour tout $x\in [{\mathsf{N}}]$,
$f_i(\overline{x}^j)$ est égal à $f_i(x)$, \textit{i.e},
$f'_{ij}(x)=0$. Ainsi $B(f)_{ij}$ est nulle. La réciproque est aussi vraie.
\end{theorem}
En outre, les interactions peuvent se représenter à l'aide d'un
graphe $\Gamma(f)$ orienté et signé défini ainsi:
-l'ensemble des sommets est
-$[n]$ et il existe un arc de $j$ à $i$ de signe
+l'ensemble des sommet %s est
+$[{\mathsf{N}}]$ et il existe un arc de $j$ à $i$ de signe
$s\in\{-1,1\}$, noté $(j,s,i)$, si $f_{ij}(x)=s$ pour au moins
-un $x\in\Bool^n$.
+un $x\in\Bool^{\mathsf{N}}$.
On note que la présence de
deux arcs de signes opposés entre deux sommets donnés
\subsection{Conditions de convergence}\label{sec:Robert:async}
Parmi les itérations unaires caractérisées par leurs stratégies
-$S=(s^t)^{t \in \Nats}$ d'éléments appartenant à $[n]$,
+$S=(s^t)^{t \in \Nats}$ d'éléments appartenant à $[{\mathsf{N}}]$,
sont jugées intéressantes
celles qui activent au moins une fois
-chacun des $i\in[n]$. Dans le cas contraire, un élément n'est jamais modifié.
+chacun des $i\in[{\mathsf{N}}]$. Dans le cas contraire, un élément n'est jamais modifié.
Plus formellement, une séquence finie $S=(s^t)^{t \in \Nats}$
-est dite \emph{complète} relativement à $[n]$ si
-tout indice de $[n]$
+est dite \emph{complète} relativement à $[{\mathsf{N}}]$ si
+tout indice de $[{\mathsf{N}}]$
s'y retrouve au moins une fois.
Parmi toutes les stratégies unaires de
-$[n]^{\Nats}$, on qualifie de:
+$[{\mathsf{N}}]^{\Nats}$, on qualifie de:
\begin{itemize}
\item \emph{périodiques} celles
qui sont constituées par une répétition indéfinie
-d'une même séquence $S$ complète relativement à $[n]$.
+d'une même séquence $S$ complète relativement à $[{\mathsf{N}}]$.
En particulier toute séquence périodique est complète.
\item \emph{pseudo-périodiques} celles
qui sont constituées par une succession indéfinie de séquences
(de longueur éventuellement variable non supposée bornée) complètes.
Autrement dit dans chaque stratégie pseudo-périodique, chaque indice de
-$1$ à $n$ revient indéfiniment.
+$1$ à ${\mathsf{N}}$ revient indéfiniment.
\end{itemize}
\begin{theorem}\label{Th:conv:GIU}
Si le graphe $\Gamma(f)$ n'a pas de cycle et si la stratégie unaire est
pseudo-périodique, alors tout chemin de $\textsc{giu}(f)$ atteint
-l'unique point fixe $\zeta$ en au plus $n$ pseudo-périodes.
+l'unique point fixe $\zeta$ en au plus ${\mathsf{N}}$ pseudo-périodes.
\end{theorem}
Le qualificatif \emph{pseudo-périodique} peut aisément
s'étendre aux stratégies généralisées comme suit.
Lorsqu'une stratégie généralisée est constituée d'une
-succession indéfinie de séquences de parties de $[n]$
-dont l'union est $[n]$, cette stratégie est {pseudo-périodique}.
+succession indéfinie de séquences de parties de $[{\mathsf{N}}]$
+dont l'union est $[{\mathsf{N}}]$, cette stratégie est {pseudo-périodique}.
J. Bahi~\cite{Bah00} a démontré le théorème suivant:
\begin{theorem}\label{Th:Bahi}
