[hdrcouchot.git] / 12TIPE.tex

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é}