12TIPE.tex

   1
   2
   3 Soit ${\mathsf{N}}$ un entier naturel et $f$ une fonction de
   4 $\Bool^{{\mathsf{N}}}$ dans lui-même.
   5
   6
   7 \subsection{Des itérations unaires aux itérations parallèles}
   8
   9 Dans le schéma unaire, à la  $t^{\textrm{ème}}$ itération,
  10 seul le  $s_{t}^{\textrm{ème}}$
  11 composant (entre 1 et $\mathsf{N}$) est mis à jour.
  12 Pour une stratégie $s = \left(s_t\right)_{t \in \mathds{N}}$
  13 (\textit{i.e.}, une séquence d'indices
  14 de $[\mathsf{N}]$), on peut définir
  15 la fonction $F_{f_u}: \Bool^{\mathsf{N}} \times [\mathsf{N}]$
  16 vers $\Bool^\mathsf{N}$ par
  17
  18 \begin{equation}
  19 F_{f_u}(x,i)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_\mathsf{N}).
  20 \label{eq:iterations:unaires}
  21 \end{equation}
  22
  23 Dans le schéma des itérations unaires pour une configuration initiale
  24 $x^0\in\Bool^\mathsf{N}$ et une stratégie $s\in
  25 [\mathsf{N}]^\Nats$, les configurations $x^t$
  26 sont définies par la récurrence
  27 \begin{equation}\label{eq:asyn}
  28 x^{t+1}=F_{f_u}(x^t,s_t).
  29 \end{equation}
  30
  31
  32 On peut alors construire l'espace
  33 $\mathcal{X}_u =
  34 \Bool^{{\mathsf{N}}} \times [{\mathsf{N}}]^{\Nats}$
  35 et la fonction d'itération $G_{f_u}$ définie  de
  36 $\mathcal{X}_u$
  37 dans lui-même par
  38 \begin{equation}
  39 G_{f_u}(x,s)=(F_{f_u}(x,s_0),\sigma(s)).
  40 \label{eq:sch:unaire}
  41 \end{equation}
  42
  43 Dans cette définition, la fonction
  44 $\sigma: [{\mathsf{N}}]^{\Nats} \longrightarrow
  45  [{\mathsf{N}}]^{\Nats}
  46 $
  47 décale
  48 la stratégie fournie en argument d'un élément vers la gauche en supprimant
  49 l'élément de tête. Ceci se formalise par
  50 $$
  51 \sigma((u^k)_{k \in \Nats}) =  (u^{k+1})_{k \in \Nats}.
  52 $$
  53
  54
  55 Ainsi, effectuer des itérations unaires sur la fonction
  56 $f$ selon une stratégie $s$ revient à effectuer des itérations
  57 parallèles de la fonction $G_{f_u}$ dans  $\mathcal{X}_u$.
  58 La section suivante introduit une métrique sur $\mathcal{X}_u$.
  59
  60 \subsection{Une métrique pour $\mathcal{X}_u$}
  61 Sur $\mathcal{X}_u$,
  62 on définit la distance $d$ entre les points $X=(x,s)$ et
  63 $X'=(x',s')$ de $\mathcal{X}_u$ par
  64 \begin{equation}
  65 d(X,X')= d_H(x,x')+d_S(s,s'),~\textrm{où}~
  66 \left\{
  67 \begin{array}{l}
  68 \displaystyle{d_H(x,x')=\sum_{i=1}^n |x_i-x'_i|}\\[5mm]
  69 \displaystyle{d_S(s,s')=\frac{9}{n}\sum_{t\in\Nats}\frac{|s_t-s'_t|}{10^{t+1}}}.
  70 \end{array}
  71 \right.\,.
  72 \end{equation}
  73
  74 On note que dans le calcul de $d_H(x,x')$--
  75 appelée distance de Hamming entre $x$ et $x'$--
  76 les termes $x_i$ et $x'_i$ sont considérés comme des entiers naturels
  77 égaux à $0$ ou à $1$ et que le calcul est effectué dans $\Z$.
  78 De plus, la partie entière
  79 $\lfloor d(X,X')\rfloor$ est égale à $d_H(x,x')$ soit la distance
  80 de Hamming entre $x$ et $x'$.
  81 On remarque que la partie décimale est inférieure à $10^{-l}$ si
  82 et seulement si les $l$ premiers termes des deux stratégies sont égaux.
  83 De plus, si la
  84 $(l+1)^{\textrm{ème}}$ décimale
  85 de $d_S(s,s')$
  86 n'est pas nulle, alors $s_l$ est différent de  $s'_l$.
  87
  88 Se pose la question de caractériser les fonctions $f$ telles que
  89 les itérations de $G_{f_u}$ associées à leurs itérations unaires
  90 sont chaotiques dans $\mathcal{X}_u$. La section suivante
  91 apporte une réponse à cette question.
  92
  93
  94 \subsection{Caractérisation des fonctions rendant
  95 chaotiques $G_{f_u}$ sur $\mathcal{X}_u$}
  96
  97
  98 % On peut tout d'abord démontrer que pour toute fonction booléenne $f$,
  99 % $G_{f_u}$ est continue sur $\mathcal{X}_u$ (cf annexe~\ref{anx:cont}).
 100
 101 Pour caractériser les fonctions rendant chaotiques dans $\mathcal{X}_u$ les itérations de $G_{f_u}$
 102 on se focalise donc sur la régularité et sur la transitivité de $G_{f_u}$.
 103 Ceci se réalise en établissant les relations d'inclusion entre
 104 les ensembles $\mathcal{T}$ des fonctions topologiquement transitives,
 105 $\mathcal{R}$ des fonctions régulières
 106 et $\mathcal{C}$ des fonctions chaotiques définis respectivement ci-dessous:
 107 \begin{itemize}
 108 \item   $\mathcal{T}   =    \left\{f   :   \mathds{B}^{\mathsf{N}}   \to
 109 \mathds{B}^{\mathsf{N}} \textrm{ t. q. } G_{f_u} \textrm{ est transitive} \right\}$,
 110 \item   $\mathcal{R}   =    \left\{f   :   \mathds{B}^{\mathsf{N}}   \to
 111 \mathds{B}^{\mathsf{N}} \textrm{ t. q. } G_{f_u} \textrm{ est régulière} \right\}$,
 112 \item   $\mathcal{C}   =    \left\{f   :   \mathds{B}^{\mathsf{N}}   \to
 113 \mathds{B}^{\mathsf{N}}  \textrm{ t. q. }  G_{f_u}  \textrm{  est chaotique} \right\}$.
 114 \end{itemize}
 115
 116
 117 On énonce les théorèmes successifs suivants dont les preuves sont données
 118 dans~\cite{guyeuxphd}.
 119
 120 \begin{theorem} $G_{f_u}$  est transitive si et seulement si
 121  $\textsc{giu}(f)$ est fortement connexe.
 122 \end{theorem}
 123
 124 \begin{theorem}
 125 \label{Prop: T est dans R:u} $\mathcal{T} \subset \mathcal{R}$.
 126 \end{theorem}
 127
 128 On peut conclure  que $\mathcal{C} = \mathcal{R} \cap \mathcal{T}
 129 = \mathcal{T}$. On a alors la  caractérisation suivante:
 130
 131 \begin{theorem}%[Characterization of $\mathcal{C}$]
 132 \label{Th:CaracIC}
 133 Soit $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$. La fonction $G_{f_u}$ est chaotique
 134 si et seulement si $\textsc{giu}(f)$ est fortement connexe.
 135 \end{theorem}
 136
 137
 138
 139
 140
 141
 142
 143
 144