15TSI.tex

   1 On reprend ici le même plan que dans la section précédente.
   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 généralisées aux itérations parallèles}
   8
   9 Dans le schéma généralisé, à la  $t^{\textrm{ème}}$ itération,
  10 c'est l'ensemble
  11 des $s_{t}^{\textrm{ème}}$ éléments (inclus dans $[n]$) qui
  12 sont  mis à jour (c.f. équation~(\ref{eq:schema:generalise})).
  13 On redéfinit la fonction la fonction
  14   $F_f:  \Bool^{\mathsf{N}} \times \mathcal{P}(\{1, \ldots, \mathsf{N}\})
  15   \rightarrow \Bool^{\mathsf{N}}$  par
  16   \[
  17   F_f(x,s)_i=\left\{
  18     \begin{array}{l}
  19       f_i(x) \textrm{ si $i \in s$;}\\
  20       x_i \textrm{ sinon.}
  21     \end{array}\right.
  22   \]
  23
  24 Dans ce schéma d'itérations généralisées,
  25 pour une configuration initiale
  26 $x^0\in\Bool^{\mathsf{N}}$ et une stratégie $S = \left(s_t\right)_{t \in  \mathds{N}}
  27 \in \mathcal{P}(\{1, \ldots, {\mathsf{N}}\})^{\Nats}$,
  28 les
  29 configurations $x^t$ sont définies par la récurrence
  30 \begin{equation}\label{eq:asyn}
  31     x^{t+1}=F_f(s_t,x^t).
  32   \end{equation}
  33   Soit alors $G_f$ une fonction de $\Bool^{\mathsf{N}}  \times  \mathcal{P}(\{1, \ldots, {\mathsf{N}}\})^{\Nats}$
  34   dans lui-même définie par
  35   \[
  36   G_f(S,x)=(\sigma(S),F_f(s_0,x)),
  37   \]
  38   où la fonction $\sigma$ est définit comme à la section précédente.
  39   A nouveau, les itérations généralisées
  40   de $f$ induites par $x^0$ et la  stratégie $S$.
  41   décrivent la même orbite que les
  42   itérations parallèles de $G_f$ depuis un point initial
  43   $X^0=(x^0,S)$
  44
  45
  46
  47 %%%%%%%%%%%%%%%%%%%%
  48 On peut alors construire l'espace
  49 $\mathcal{X} = \Bool^{\mathsf{N}} \times
  50 \mathcal{P}(\{1, \ldots, {\mathsf{N}}\})^{\Nats}$
  51
  52 \subsection{Une métrique pour $\mathcal{X}$}
  53
  54 Cette nouvelle distance va comparer des ensembles.
  55 On rappelle pour quelques notions ensemblistes.
  56 Pour $A$ et $B$ deux ensembles de l'univers $\Omega$,
  57 on rappelle la définition de l'opérateur
  58 de \emph{différence ensembliste} symétrique :
  59 \[
  60 A \Delta B = (A \cap \overline{B}) \cup (\overline{A} \cap B)
  61 \]
  62 où $\overline{B}$ désigne le complémentaire de $B$ dans $\Omega$.
  63
  64 On considère l'espace $\mathcal{X}=\mathcal{P}(\{1, \ldots, {\mathsf{N}}\})^{\Nats}\times
  65 \Bool^{\mathsf{N}}$ et
  66 on définit la distance $d$ entre les points $X=(S,x)$ et
  67 $X'=(S',x')$ 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}^{\mathsf{N}} |x_i-x'_i|}\\[5mm]
  73 \displaystyle{d_S(S,S')=\frac{9}{{\mathsf{N}}}\sum_{t\in\Nats}\frac{|S_t \Delta S'_t|}{10^{t+1}}}.
  74 \end{array}
  75 \right.\,.
  76 \]
  77
  78 La fonction $d$ est une somme de deux fonctions.
  79 La fonction $d_H$ est la distance de Hamming; il est aussi établi que la
  80 somme de deux distances est une distance.
  81 Ainsi, pour montrer que $d$ est aussi une distance, il suffit
  82 de montrer que $d_S$ en une aussi, ce qui est fait en annexe~\ref{anx:distance:generalise}.
  83
  84 La section suivante caractérise les fonctions $f$ qui sont
  85 chaotiques pour le schéma généralisées.
  86
  87
  88 \subsection{Caractérisation des fonctions chaotiques
  89 pour le schéma généralisé}
  90 On a les théorèmes suivants dont les preuves sont données en
  91 annexe~\ref{anx:chaos:generalise}.
  92
  93 \begin{theorem} $G_f$  est transitive si et seulement si
  94  $\Gamma(f)$ est fortement connexe.
  95 \end{theorem}
  96
  97 \begin{theorem}
  98 \label{Prop: T est dans R} $\mathcal{T} \subset \mathcal{R}$.
  99 \end{theorem}
 100
 101
 102 \begin{theorem}%[Characterization of $\mathcal{C}$]
 103 \label{Th:CaracIC}
 104 Soit $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$. La fonction $G_f$ est chaotique
 105 si et seulement si $\Gamma(f)$ est fortement connexe.
 106 \end{theorem}
 107
 108
 109
 110
 111
 112
 113
 114
 115