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