15TSI.tex

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