une version de plus

[hdrcouchot.git] / 12TIPE.tex

diff --git a/12TIPE.tex b/12TIPE.tex
index 41714377514f1417622db475e6a9e74181842b08..4bcec9fbdc58def6a2740728b1d72efa55c19ba0 100644 (file)
--- a/12TIPE.tex
+++ b/12TIPE.tex
@@ -1,84 +1,5 @@
-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.
 
 Soit ${\mathsf{N}}$ un entier naturel et $f$ une fonction de 
 $\Bool^{{\mathsf{N}}}$ dans lui-même.
 


@@ -87,44 +8,41 @@ $\Bool^{{\mathsf{N}}}$ dans lui-même.
 
 Dans le schéma unaire, à la  $t^{\textrm{ème}}$ itération, 
 seul le  $s_{t}^{\textrm{è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}}$ 
+composant (entre 1 et $\mathsf{N}$) est mis à jour.
+Pour une stratégie $s = \left(s_t\right)_{t \in \mathds{N}}$ 

 (\textit{i.e.}, une séquence d'indices
 (\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 $[\mathsf{N}]$), on peut définir
+la fonction $F_{f_u}: \Bool^{\mathsf{N}} \times [\mathsf{N}]$

 vers $\Bool^\mathsf{N}$ par 
 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}).
-\]
+
+\begin{equation}
+F_{f_u}(x,i)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_\mathsf{N}).
+\label{eq:iterations:unaires}
+\end{equation}

 
 Dans le schéma des itérations unaires pour une configuration initiale
 $x^0\in\Bool^\mathsf{N}$ et une stratégie $s\in
 
 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$
+[\mathsf{N}]^\Nats$, les configurations $x^t$

 sont définies par la récurrence
 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}
 
 \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 
 
 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}$ 
+$\mathcal{X}_u =
+\Bool^{{\mathsf{N}}} \times [{\mathsf{N}}]^{\Nats}$ 
+et la fonction d'itération $G_{f_u}$ définie  de 
+$\mathcal{X}_u$ 

 dans lui-même par 
 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 
 
 Dans cette définition, la fonction 

-$\sigma: \llbracket1;{\mathsf{N}}\rrbracket^{\Nats} \longrightarrow
- \llbracket1;{\mathsf{N}}\rrbracket^{\Nats} 
+$\sigma: [{\mathsf{N}}]^{\Nats} \longrightarrow
+ [{\mathsf{N}}]^{\Nats} 

 $
 décale
 la stratégie fournie en argument d'un élément vers la gauche en supprimant 
 $
 décale
 la stratégie fournie en argument d'un élément vers la gauche en supprimant 


@@ -136,15 +54,14 @@ $$
 
 Ainsi, effectuer des itérations unaires sur la fonction 
 $f$ selon une stratégie $s$ revient à effectuer des itérations
 
 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 fonction $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
 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 
+\begin{equation}

 d(X,X')= d_H(x,x')+d_S(s,s'),~\textrm{où}~
 \left\{
 \begin{array}{l}
 d(X,X')= d_H(x,x')+d_S(s,s'),~\textrm{où}~
 \left\{
 \begin{array}{l}


@@ -152,7 +69,8 @@ d(X,X')= d_H(x,x')+d_S(s,s'),~\textrm{où}~
 \displaystyle{d_S(s,s')=\frac{9}{n}\sum_{t\in\Nats}\frac{|s_t-s'_t|}{10^{t+1}}}.
 \end{array}
 \right.\,.
 \displaystyle{d_S(s,s')=\frac{9}{n}\sum_{t\in\Nats}\frac{|s_t-s'_t|}{10^{t+1}}}.
 \end{array}
 \right.\,.

-\]
+\end{equation}
+

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


@@ -167,44 +85,44 @@ $(l+1)^{\textrm{ème}}$ décimale
 de $d_S(s,s')$ 
 n'est pas nulle, alors $s_l$ est différent de  $s'_l$. 
 
 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}).   

 
 

-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$.
- 
+% On peut tout d'abord démontrer que pour toute fonction booléenne $f$, 
+% $G_{f_u}$ est continue sur $\mathcal{X}_u$ (cf annexe~\ref{anx:cont}).   
+
+Pour caractériser les fonctions rendant chaotiques dans $\mathcal{X}_u$ les itérations de $G_{f_u}$ 
+on se focalise donc 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}
 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\}$.
+\item   $\mathcal{T}   =    \left\{f   :   \mathds{B}^{\mathsf{N}}   \to
+\mathds{B}^{\mathsf{N}} \textrm{ t. q. } G_{f_u} \textrm{ est transitive} \right\}$,
+\item   $\mathcal{R}   =    \left\{f   :   \mathds{B}^{\mathsf{N}}   \to
+\mathds{B}^{\mathsf{N}} \textrm{ t. q. } G_{f_u} \textrm{ est régulière} \right\}$,
+\item   $\mathcal{C}   =    \left\{f   :   \mathds{B}^{\mathsf{N}}   \to
+\mathds{B}^{\mathsf{N}}  \textrm{ t. q. }  G_{f_u}  \textrm{  est chaotique} \right\}$.

 \end{itemize}
 
 
 \end{itemize}
 
 

-On énnonce les théorèmes successifs suivants.
-Leur preuve est donnée en annexe~\ref{anx:chaos:unaire}.
+On énonce les théorèmes successifs suivants dont les preuves sont données 
+dans~\cite{guyeuxphd}.

 
 

-\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}
 \end{theorem}
 
 \begin{theorem}

-\label{Prop: T est dans R} $\mathcal{T} \subset \mathcal{R}$.
+\label{Prop: T est dans R:u} $\mathcal{T} \subset \mathcal{R}$.

 \end{theorem}
 
 On peut conclure  que $\mathcal{C} = \mathcal{R} \cap \mathcal{T}
 \end{theorem}
 
 On peut conclure  que $\mathcal{C} = \mathcal{R} \cap \mathcal{T}


@@ -212,8 +130,8 @@ On peut conclure  que $\mathcal{C} = \mathcal{R} \cap \mathcal{T}
 
 \begin{theorem}%[Characterization of $\mathcal{C}$]
 \label{Th:CaracIC}  
 
 \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^{\mathsf{N}}\to\Bool^{\mathsf{N}}$. La fonction $G_{f_u}$ est chaotique  
+si et seulement si $\textsc{giu}(f)$ est fortement connexe.

 \end{theorem}
 
 
 \end{theorem}
 
 


@@ -221,6 +139,6 @@ si et seulement si $\Gamma(f)$ est fortement connexe.
 
 
 
 
 
 

-\section{Schéma généralisé}
+