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 $[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 pour 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 d(X,X')= d_H(x,x')+d_S(S,S'),~\textrm{où}~
  67 \left\{
  68 \begin{array}{l}
  69 \displaystyle{d_H(x,x')=\sum_{i=1}^{\mathsf{N}} |x_i-x'_i|}\\[5mm]
  70 \displaystyle{d_S(S,S')=\frac{9}{{\mathsf{N}}}\sum_{t\in\Nats}\frac{|S_t \Delta S'_t|}{10^{t+1}}}.
  71 \end{array}
  72 \right.\,.
  73 \]
  74
  75 La fonction $d$ est une somme de deux fonctions.
  76 La fonction $d_H$ est la distance de Hamming; il est aussi établi que la
  77 somme de deux distances est une distance.
  78 Ainsi, pour montrer que $d$ est aussi une distance, il suffit
  79 de montrer que $d_S$ en une aussi, ce qui est fait en annexe~\ref{anx:distance:generalise}.
  80
  81 La section suivante caractérise les fonctions $f$ qui sont
  82 chaotiques pour le schéma généralisées.
  83
  84 \subsection{Caractérisation des fonctions rendant
  85 chaotiques $G_{f_g}$ sur $\mathcal{X}_g$}
  86 On reprend les définitions des ensembles $\mathcal{T}$, $\mathcal{R}$ et $\mathcal{C}$
  87 en les adaptant à  $G_{f_g}$.
  88 On a les théorèmes suivants dont les preuves sont données en
  89 annexe~\ref{anx:chaos:generalise}.
  90
  91 \begin{theorem} $G_{f_g}$  est transitive si et seulement si
  92  $\textsc{gig}(f)$ est fortement connexe.
  93 \end{theorem}
  94
  95 \begin{theorem}
  96 \label{Prop: T est dans R:g} $\mathcal{T} \subset \mathcal{R}$.
  97 \end{theorem}
  98
  99
 100 \begin{theorem}%[Characterization of $\mathcal{C}$]
 101 \label{Th:CaracIC:g}
 102 Soit $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$. La fonction $G_{f_g}$ est chaotique
 103 si et seulement si $\textsc{gig}(f)$ est fortement connexe.
 104 \end{theorem}
 105
 106
 107
 108
 109
 110
 111
 112
 113