--- /dev/null
+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.
+
+
+\subsection{Des itérations unaires aux itérations parallèles}
+
+Dans le schéma unaire, à la $t^{\textrm{ème}}$ itération,
+seul le $s_{t}^{\textrm{ème}}$
+composant (entre 1 et $n$) est mis à jour.
+
+Formellement, pour une stratégie $s = \left(s_t\right)_{t \in \mathds{N}}$
+(\textit{i.e.}, une séquence d'indices
+de $\llbracket 1;\mathsf{N} \rrbracket$), on définit
+la fonction $F_f: \Bool^{\mathsf{N}} \times \llbracket1;\mathsf{N}\rrbracket$
+vers $\Bool^\mathsf{N}$ par
+\[
+F_f(x,i)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_\mathsf{N}).
+\]
+
+Dans le schéma des itérations unaires pour une configuration initiale
+$x^0\in\Bool^\mathsf{N}$ et une stratégie $s\in
+\llbracket1;\mathsf{N}\rrbracket^\Nats$, les configurations $x^t$
+sont définies par la récurrence
+x\begin{equation}\label{eq:asyn}
+x^{t+1}=F_f(x^t,s_t).
+\end{equation}
+
+Les itérations parallèles de $G_f$ depuis un point initial
+$X^0=(s,x^0)$ décrivent la même orbite que les
+itérations asynchrones de $f$ induites par $x^0$ et la stratégie
+$s$.
+
+
+On peut alors construire l'espace
+$\mathcal{X} =
+\Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}$
+et la fonction d'iteration $G_f$ définie de
+$\mathcal{X}$
+dans lui-même par
+\[
+G_f(x,s)=(F_f(x,s_0),\sigma(s)).
+\]
+
+Dans cette définition, la fonction
+$\sigma: \llbracket1;{\mathsf{N}}\rrbracket^{\Nats} \longrightarrow
+ \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}
+$
+décale
+la stratégie fournie en argument d'un élément vers la gauche en supprimant
+l'élément de tête. Ceci se formalise par
+$$
+\sigma((u^k)_{k \in \Nats}) = (u^{k+1})_{k \in \Nats}.
+$$
+
+
+Ainsi, effectuer des itérations unaires sur la fonction
+$f$ selon une stratégie $s$ revient à effectuer des itérations
+parallèles de la fonctions $G_f$ dans $\mathcal{X}$.
+
+La section suivante introduit une métrique sur $\mathcal{X}$.
+
+\subsection{Une métrique pour $\mathcal{X}$}
+Sur $\mathcal{X}$,
+on définit la distance $d$ entre les points $X=(x,s)$ et
+$X'=(x',s')$ 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}^n |x_i-x'_i|}\\[5mm]
+\displaystyle{d_S(s,s')=\frac{9}{n}\sum_{t\in\Nats}\frac{|s_t-s'_t|}{10^{t+1}}}.
+\end{array}
+\right.\,.
+\]
+On note que dans le calcul de $d_H(x,x')$--
+appelée distance de Hamming entre $x$ et $x'$--
+les termes $x_i$ et $x'_i$ sont considérés comme des entiers naturels
+égaux à $0$ ou à $1$ et que le calcul est effectué dans $\Z$.
+De plus, la partie entière
+$\lfloor d(X,X')\rfloor$ est égale à $d_H(x,x')$ soit la distance
+de Hamming entre $x$ et $x'$.
+On remarque que la partie décimale est inférieure à $10^{-l}$ si
+et seulement si les $l$ premiers termes des deux stratégies sont égaux.
+De plus, si la
+$(l+1)^{\textrm{ème}}$ décimale
+de $d_S(s,s')$
+n'est pas nulle, alors $s_l$ est différent de $s'_l$.
+
+La section fournit quelques résultats de caractérisation de fonctions
+chaotiques pour le schéma unaire.
+
+
+\subsection{Caractérisation des fonctions chaotiques
+pour le schéma unaire}
+
+On peut tout d'abord démontrer que pour toute fonction booléenne $f$,
+$G_f$ est continue sur $\mathcal{X}$ (cf annexe~\ref{anx:cont}).
+
+Pour charactérister les fonctions rendant chaotiques dans $
+\mathcal{X}$ les itérations de $G_f$
+on se focalise donc que sur la régularité et
+sur la transitivité de $G_f$.
+
+Ceci se réalise en établissant les relations d'inclusion entre
+les ensembles $\mathcal{T}$ des fonctions topologiquement transitives,
+$\mathcal{R}$ des fonctions régulières
+et $\mathcal{C}$ des fonctions chaotiques définis respectivement ci-dessous:
+\begin{itemize}
+\item $\mathcal{T} = \left\{f : \mathds{B}^n \to
+\mathds{B}^n \big/ G_f \textrm{ est transitive} \right\}$,
+\item $\mathcal{R} = \left\{f : \mathds{B}^n \to
+\mathds{B}^n \big/ G_f \textrm{ est régulière} \right\}$,
+\item $\mathcal{C} = \left\{f : \mathds{B}^n \to
+\mathds{B}^n \big/ G_f \textrm{ est chaotique} \right\}$.
+\end{itemize}
+
+
+On énnonce les théorèmes successifs suivants.
+Leur preuve est donnée en annexe~\ref{anx:chaos:unaire}.
+
+\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}
+
+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^n\to\Bool^n$. La fonction $G_f$ est chaotique
+si et seulement si $\Gamma(f)$ est fortement connexe.
+\end{theorem}
+
+
+
+
+
+
+\section{Schéma généralisé}
+
+
--- /dev/null
+On prouve les théorèmes suivants
+
+
+\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 $(S,x)$ et $(S',x')$ 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 à
+$\varepsilon$ et telle que les itérations parallèles de $G_f$ depuis
+$(\tilde S,x)$ mènent au point $(S',x')$.
+
+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
+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$.
+
+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
+$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$.
+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 $(S'',x'')$ tel que
+$d((S'',x''),(S,x))<\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')$.
+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.
+Pour tout entier naturel $t$, on a
+$G_f^t(S'',x'') \neq (S',x')$.
+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^n\to\Bool^n$ telle que $G_f$ est transitive (\textit{i.e.}
+$f$ appartient à $\mathcal{T}$).
+Soit $(S,x) \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.
+
+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)$.
+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$.
+
+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 $(\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
+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$.
+\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^n\to\Bool^n$. La fonction $G_f$ est chaotique
+si et seulement si $\Gamma(f)$ est fortement connexe.
+\end{theorem}
+
