-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.
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}}$
+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$
+de $\llbracket 1;\mathsf{N} \rrbracket$), on peut définir
+la fonction $F_{f_u}: \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}).
+F_{f_u}(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).
+\begin{equation}\label{eq:asyn}
+x^{t+1}=F_{f_u}(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} =
+$\mathcal{X}_u =
\Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}$
-et la fonction d'iteration $G_f$ définie de
-$\mathcal{X}$
+et la fonction d'iteration $G_{f_u}$ définie de
+$\mathcal{X}_u$
dans lui-même par
-\[
-G_f(x,s)=(F_f(x,s_0),\sigma(s)).
-\]
+\begin{equation}
+G_{f_u}(x,s)=(F_{f_u}(x,s_0),\sigma(s)).
+\label{eq:sch:unaire}
+\end{equation}
Dans cette définition, la fonction
$\sigma: \llbracket1;{\mathsf{N}}\rrbracket^{\Nats} \longrightarrow
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}$.
+parallèles de la fonctions $G_{f_u}$ dans $\mathcal{X}_u$.
+La section suivante introduit une métrique sur $\mathcal{X}_u$.
-\subsection{Une métrique pour $\mathcal{X}$}
-Sur $\mathcal{X}$,
+\subsection{Une métrique pour $\mathcal{X}_u$}
+Sur $\mathcal{X}_u$,
on définit la distance $d$ entre les points $X=(x,s)$ et
-$X'=(x',s')$ de $\mathcal{X}$ par
+$X'=(x',s')$ de $\mathcal{X}_u$ par
\[
d(X,X')= d_H(x,x')+d_S(s,s'),~\textrm{où}~
\left\{
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.
+Se pose la question de caractériser les fonctions $f$ telles que
+les itérations de $G_{f_u}$ associées à leurs itérations unaires
+sont chaotiques dans $\mathcal{X}_u$. La section suivante
+apporte une réponse à cette question.
-\subsection{Caractérisation des fonctions chaotiques
-pour le schéma unaire}
+\subsection{Caractérisation des fonctions rendant
+chaotiques $G_{f_u}$ sur $\mathcal{X}_u$}
+
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}).
+$G_{f_u}$ est continue sur $\mathcal{X}_u$ (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$.
-
+Pour charactérister les fonctions rendant chaotiques dans $\mathcal{X}_u$ les itérations de $G_{f_u}$
+on se focalise donc que sur la régularité et sur la transitivité de $G_{f_u}$.
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\}$,
+\mathds{B}^n \big/ G_{f_u} \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\}$,
+\mathds{B}^n \big/ G_{f_u} \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\}$.
+\mathds{B}^n \big/ G_{f_u} \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.
+\begin{theorem} $G_{f_u}$ est transitive si et seulement si
+ $\textsc{giu}(f)$ est fortement connexe.
\end{theorem}
\begin{theorem}
\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.
+Soit $f:\Bool^n\to\Bool^n$. La fonction $G_{f_u}$ est chaotique
+si et seulement si $\textsc{giu}(f)$ est fortement connexe.
\end{theorem}
-\section{Schéma généralisé}
+
