sdd.tex

   1
   2
   3
   4
   5
   6
   7
   8 On considère l'espace booléen
   9 $\Bool=\{0,1\}$
  10 muni des opérateurs binaires
  11 de disjonction \og +\fg{},
  12 de conjonction \og . \fg{} et
  13 unaire de négation \og $\overline{\mathstrut\enskip}$ \fg{}.
  14
  15
  16 Soit ${\mathsf{N}}$ un entier naturel.
  17 On introduit quelques notations à propos d'éléments de $\Bool^{\mathsf{N}}$.
  18 L'ensemble $\{1,\dots, {\mathsf{N}}\}$ sera par la suite noté $[{\mathsf{N}}]$.
  19 Le $i^{\textrm{ème}}$ composant d'un élément
  20 $x \in \Bool^{\mathsf{N}}$ s'écrit  $x_i$.
  21 Si l'ensemble $I$ est une partie de $[{\mathsf{N}}]$, alors
  22 $\overline{x}^I$ est l'élément $y\in  \Bool^{\mathsf{N}}$
  23 tel que $y_i = 1 - x_i$ si $i\in I$ et
  24 $y_i = x_i$ sinon.
  25 On considère les deux abréviations $\overline{x}$ pour $\overline{x}^{[{\mathsf{N}}]}$
  26 (chaque composant de $\overline{x}$ est nié:
  27 c'est une négation composante à composante)
  28 et $\overline{x}^i$ pour $\overline{x}^{\{i\}}$ pour $i \in [{\mathsf{N}}]$
  29 (seul $x_i$ est nié dans $\overline{x}$).
  30 Pour tout $x$ et  $y$ dans  $\Bool^{\mathsf{N}}$, l'ensemble
  31 $\Delta(x, y)$,  contient les $i \in [{\mathsf{N}}]$
  32 tels que $x_i \neq y_i$.
  33 Soit enfin $f : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$. Son $i^{\textrm{ème}}$ composant
  34 est nommé $f_i$ qui est une fonction de $\Bool^{\mathsf{N}}$ dans $\Bool$.
  35 Pour chaque
  36 $x$ dans $\Bool^{\mathsf{N}}$, l'ensemble
  37 $\Delta f(x)$ est défini par $\Delta f(x) = \Delta(x,f(x))$.
  38 On peut admettre que $f (x) = \overline{x}^{\Delta f(x)}$ .
  39
  40 \begin{xpl}\label{xpl:1}
  41 On considère ${\mathsf{N}}= 3$ et $f:\Bool^3 \rightarrow \Bool^3$ telle que
  42 $f(x)=(f_1(x),f_2(x),f_3(x))$ avec
  43 $$\begin{array}{rcl}
  44 f_1(x_1, x_2, x_3) &=& (\overline{x_1} + \overline{x_2}).x_3 \textrm{, }\\
  45 f_2(x_1, x_2, x_3) &= &x_1.x_3 \textrm{ et }\\
  46 f_3(x_1, x_2, x_3) &=& x_1 + x_2 + x_3.
  47 \end{array}
  48 $$
  49
  50 \begin{table}[ht]
  51 $$
  52 \begin{array}{|l|l|l||c|c|c|}
  53 \hline
  54 \multicolumn{3}{|c||}{x} &
  55 \multicolumn{3}{|c|}{f(x)} \\
  56 \hline
  57 x_1 & x_2 & x_3 &
  58 f_1(x) & f_2(x) & f_3(x) \\
  59 \hline
  60 0& 0 & 0 & 0 & 0  & 0 \\
  61 \hline
  62 0& 0 & 1 & 1 &  0 & 1\\
  63 \hline
  64 0& 1 & 0 & 0 & 0& 1\\
  65 \hline
  66 0& 1 & 1 & 1 & 0& 1\\
  67 \hline
  68 1& 0 & 0 & 0 & 0& 1\\
  69 \hline
  70 1& 0 & 1 & 1 & 1& 1\\
  71 \hline
  72 1& 1 & 0 & 0 & 0& 1\\
  73 \hline
  74 1& 1 & 1 & 0 & 1& 1\\
  75 \hline
  76 \end{array}
  77 $$
  78 \caption{Images de
  79 $(x_1, x_2, x_3) \mapsto
  80 ((\overline{x_1} + \overline{x_2}).x_3,
  81 x_1.x_3,
  82 x_1 + x_2 + x_3)$ \label{table:xpl:images}}
  83 \end{table}
  84
  85 La \textsc{Table}~\ref{table:xpl:images} donne l'image de chaque élément
  86 $x \in \Bool^3$.
  87 Pour $x=(0,1,0)$ les assertions suivantes se déduisent directement du tableau:
  88 \begin{itemize}
  89 \item $f(x)=(0,0,1)$;
  90 \item pour $I=\{1,3\}$, $\overline{x}^{I} = (1,1,1)$ et
  91   $\overline{x} = (1,0,1)$;
  92 \item $\Delta(x,f(x)) = \{2,3\}$.
  93 \end{itemize}
  94
  95 \end{xpl}
  96
  97 \subsection{Réseau booléen}
  98 Soit ${\mathsf{N}}$ un entier naturel représentant le nombre
  99 d'éléments étudiés.
 100 Un réseau booléen  est
 101 défini à partir d'une fonction booléenne:
 102 \[
 103 f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}},\qquad x=(x_1,\dots,x_{\mathsf{N}})\mapsto f(x)=(f_1(x),\dots,f_{\mathsf{N}}(x)),
 104 \]
 105 et un  {\emph{schéma itératif}} ou  encore \emph{mode de  mise à jour}. À  partir d'une configuration initiale $x^0\in\Bool^{\mathsf{N}}$,  la suite $(x^{t})^{t
 106   \in  \Nats}$ des  configurations  du  système est  construite  selon l'un  des
 107 schémas suivants :
 108 \begin{itemize}
 109 \item \textbf{Schéma parallèle  synchrone :} basé sur la  relation de récurrence
 110   $x^{t+1}=f(x^t)$. Tous  les $x_i$, $1 \le  i \le {\mathsf{N}}$,  sont ainsi mis à  jour à
 111   chaque itération en utilisant l'état global précédent du système $x^t$.
 112 \item \textbf{Schéma  unaire :} ce schéma  est parfois
 113   qualifié de chaotique
 114   dans  la littérature.
 115   Il  consiste à modifier la valeur
 116   d'un unique élément $i$,  $1 \le i \le  {\mathsf{N}}$, à
 117   chaque itération. Le choix de l'élément qui est modifié à chaque itération est
 118   défini  par une  suite
 119   $S  = \left(s^t\right)^{t \in  \mathds{N}}$ qui est  une séquence
 120   d'indices dans $[{\mathsf{N}}]$. Cette suite est appelée \emph{stratégie unaire}.
 121   Ce mode est défini pour tout $i \in [{\mathsf{N}}]$ par
 122
 123 \begin{equation}
 124   x^{t+1}_i=
 125   \left\{ \begin{array}{l}
 126       f_i(x^t) \textrm{ si } i=s^t, \\
 127       x^t_i\textrm{ sinon.}
 128     \end{array}
 129   \right.
 130 \label{eq:schema:unaire}
 131 \end{equation}
 132
 133
 134
 135 \item \textbf{Schéma généralisé:}  dans ce schéma, ce sont les valeurs
 136   d'un ensemble d'éléments de $[{\mathsf{N}}]$ qui sont modifiées à  chaque  itération.
 137   Dans  le  cas  particulier où  c'est la valeur d'un  singleton
 138   $\{k\}$, $1 \le k  \le {\mathsf{N}}$, qui est modifiée à
 139   chaque  itération, on retrouve le
 140   mode unaire. Dans le second cas particulier où ce sont les valeurs de
 141   tous les éléments de $\{1, \ldots,  {\mathsf{N}}\}$ qui sont  modifiées
 142   à chaque  itération, on retrouve  le mode
 143   parallèle.  Ce mode généralise donc les deux modes précédents.
 144   Plus formellement,  à  la  $t^{\textrm{ème}}$
 145   itération, seuls les éléments de la partie
 146   $s^{t} \in \mathcal{P}([{\mathsf{N}}])$ sont mis à
 147   jour.  La  suite $S  = \left(s^t\right)^{t \in  \mathds{N}}$ est  une séquence
 148   de sous-ensembles
 149   de   $[{\mathsf{N}}]$   appelée   \emph{stratégie généralisée}.
 150   Il est basé sur la relation définie pour tout $i \in [{\mathsf{N}}]$ par
 151   \begin{equation}
 152   x^{t+1}_i=
 153   \left\{ \begin{array}{l}
 154       f_i(x^t) \textrm{ si } i \in s^t, \\
 155       x^t_i\textrm{ sinon.}
 156     \end{array}
 157   \right.
 158 \label{eq:schema:generalise}
 159 \end{equation}
 160
 161
 162
 163
 164   \end{itemize}
 165
 166
 167
 168
 169
 170 La section suivante détaille comment représenter graphiquement les évolutions de tels réseaux.
 171 \subsection{Graphes des itérations}
 172
 173
 174
 175 Pour un entier naturel ${\mathsf{N}}$ et une
 176 fonction $f : B^{\mathsf{N}} \rightarrow B^{\mathsf{N}}$, plusieurs évolutions sont possibles
 177 en fonction du schéma itératif retenu.
 178 Celles-ci sont représentées par un graphe orienté dont les noeuds
 179 sont les éléments de $\Bool^{\mathsf{N}}$ (voir \textsc{Figure}~\ref{fig:xpl:graphs}).
 180
 181
 182 \begin{itemize}
 183 \item Le \emph{graphe des itérations synchrones} de $f$, noté $\textsc{gis}(f)$
 184 est le graphe orienté de $\Bool^{\mathsf{N}}$ qui contient un arc $x \rightarrow y$ si
 185 et seulement si $y=f(x)$.
 186 \item Le \emph{graphe des itérations unaires} de $f$, noté $\textsc{giu}(f)$
 187 est le graphe orienté de $\Bool^{\mathsf{N}}$ qui contient un arc $x \rightarrow y$ pour $x \neq$ si
 188 et seulement s'il existe $i \in \Delta f(x)$ tel que $y = \overline{x}^i$.
 189 Si $\Delta f(x)$ est vide, on ajoute l'arc $x \rightarrow x$.
 190
 191 \item Le \emph{graphe des itérations généralisées} de $f$, noté $\textsc{gig}(f)$
 192 est le graphe orienté de $\Bool^{\mathsf{N}}$ qui contient un arc $x \rightarrow y$ si
 193 et seulement s'il existe un ensemble $I\subseteq \Delta f(x)$ tel que
 194 $y = \overline{x}^I$. On peut remarquer que ce graphe contient comme
 195 sous-graphe à la fois celui des itérations synchrones et celui
 196 des itérations unaires.
 197
 198
 199 \end{itemize}
 200
 201
 202
 203 \begin{xpl}
 204 On reprend notre exemple illustratif
 205 détaillé à la page~\pageref{xpl:1} avec sa table
 206 d'images (\textsc{Table}~\ref{table:xpl:images}).
 207 La \textsc{Figure}~\ref{fig:xpl:graphs} donne les trois graphes d'itérations
 208 associés à $f$.
 209
 210 \begin{figure}%[ht]
 211   \begin{center}
 212     \subfigure[$\textsc{gis}(f)$]{
 213       \begin{minipage}{0.33\textwidth}
 214         \begin{center}
 215           \includegraphics[scale=0.4]{fsig}
 216         \end{center}
 217       \end{minipage}
 218       \label{fig:fsig}
 219     }
 220     \subfigure[$\textsc{giu}(f)$]{
 221       \begin{minipage}{0.33\textwidth}
 222         \begin{center}
 223           \includegraphics[scale=0.4]{faig}
 224         \end{center}
 225       \end{minipage}
 226       \label{fig:faig}
 227     }
 228     \subfigure[$\textsc{gig}(f)$]{
 229       \begin{minipage}{0.33\textwidth}
 230         \begin{center}
 231           \includegraphics[scale=0.4]{fgig}
 232         \end{center}
 233       \end{minipage}
 234       \label{fig:fgig}
 235     }
 236   \end{center}
 237   \caption{Graphes des itérations de la fonction
 238 $f:\Bool^3 \rightarrow \Bool^3$ telle que
 239 $(x_1, x_2, x_3) \mapsto
 240 ((\overline{x_1} + \overline{x_2}).x_3,
 241 x_1.x_3,
 242 x_1 + x_2 + x_3)$.\label{fig:xpl:graphs}
 243 On remarque le cycle $((101,111),(111,011),(011,101))$
 244  à la \textsc{Figure}~(\ref{fig:fsig}).}
 245 \end{figure}
 246 \end{xpl}
 247
 248
 249 \subsection{Attracteurs}
 250
 251 On dit que le point
 252 $x \in \Bool^{\mathsf{N}}$ est un \emph{point fixe} de $f$ si  $x = f (x)$.
 253 Les points fixes sont particulièrement intéressants car ils correspondent
 254 aux états stables:
 255 dans chaque graphe d'itérations, le point $x$ est un point fixe
 256 si et seulement si il est son seul successeur.
 257
 258
 259
 260 Soit un graphe d'itérations (synchrones, unaires ou généralisées)
 261 de $f$.
 262 Les \emph{attracteurs}  de ce graphe sont les
 263 plus petits sous-ensembles (au sens de l'inclusion) non vides
 264 $A \subseteq \Bool^{\mathsf{N}}$ tels que pour tout arc
 265 $x \rightarrow y$, si $x$ est un élément de $A$, alors
 266 $y$ aussi.
 267 Un attracteur qui contient au moins deux éléments  est dit \emph{cyclique}.
 268 On en déduit qu'un attracteur cyclique ne contient pas de point fixe.
 269 En d'autres termes, lorsqu'un système entre dans un attracteur cyclique,
 270 il ne peut pas atteindre un point fixe.
 271
 272
 273 On a la proposition suivante:
 274
 275
 276 \begin{theorem}\label{Prop:attracteur}
 277 La configuration $x$ est un point fixe si et seulement si
 278 $\{x\}$ est un attracteur du graphe d'itération (synchrone, unaire, généralisé).
 279 En d'autres termes, les attracteurs non cycliques de celui-ci
 280 sont les points fixes de $f$.
 281 Ainsi pour chaque $x\in \Bool^{\mathsf{N}}$, il existe au moins un chemin
 282 depuis $x$ qui atteint un attracteur.
 283 Ainsi tout graphe d'itérations contient toujours au moins un attracteur.
 284 \end{theorem}
 285
 286
 287
 288 \begin{xpl}
 289 Les attracteurs de $\textsc{giu}(f)$ et de $\textsc{gig}(f)$ sont
 290 le point fixe $000$ et l'attracteur cyclique
 291 $\{001, 101,111, 011  \}$.
 292 Les attracteurs de $\textsc{gis}(f)$ sont le point fixe $000$
 293 et l'attracteur cyclique $\{011, 101, 111\}$.
 294 \end{xpl}
 295
 296 \subsection{Graphe d'interaction}
 297 Les interactions entre les composants du
 298 système peuvent être mémorisées
 299 dans la {\emph{matrice jacobienne discrète}} $f'$.
 300 Celle-ci est définie comme étant la fonction  qui  à chaque
 301 configuration $x\in\Bool^{\mathsf{N}}$ associe la matrice de taille
 302 $n\times n$ telle que
 303 \begin{equation}
 304 f'(x)=(f'_{ij}(x)),\qquad
 305 f'_{ij}(x)=\frac{f_i(\overline{x}^j){-}f_i(x)}{\overline{x_j}{-}x_j}\qquad (i,j\in[n]).
 306 \label{eq:jacobienne}
 307 \end{equation}
 308 On note que dans l'équation donnant la valeur de $f'_{ij}(x)$,
 309 les termes $f_i(\overline{x}^j)$, $f_i(x)$,
 310 $\overline{x}^j_j$ et $x_j$ sont considérés comme des entiers naturels
 311 égaux à $0$ ou à $1$ et que la différence est effectuée
 312  dans $\Z$.
 313 Lorsqu'on supprime les signes dans la matrice jacobienne discrète,
 314 on obtient une matrice notée $B(f)$ aussi de taille
 315 ${\mathsf{N}}\times {\mathsf{N}}$.
 316 Celle-ci mémorise uniquement
 317 l'existence d'une dépendance de tel élément vis à vis de
 318  tel élément.
 319 Elle ne mémorise pas \emph{comment} dépendent les éléments
 320 les uns par rapport aux autres. Cette matrice est nommée
 321 \emph{matrice d'incidence}.
 322
 323 \begin{theorem}
 324 Si $f_i$ ne dépend pas de $x_j$, alors pour tout $x\in [{\mathsf{N}}]$,
 325 $f_i(\overline{x}^j)$ est égal à  $f_i(x)$, \textit{i.e.},
 326 $f'_{ij}(x)=0$. Ainsi $B(f)_{ij}$ est nulle. La réciproque est aussi vraie.
 327 \end{theorem}
 328
 329
 330
 331
 332 En outre, les interactions peuvent se  représenter à l'aide d'un
 333 graphe $\Gamma(f)$ orienté et signé défini ainsi:
 334 l'ensemble des sommets est
 335 $[{\mathsf{N}}]$ et il existe un arc de $j$ à $i$ de signe
 336  $s\in\{-1,1\}$, noté $(j,s,i)$, si $f_{ij}(x)=s$ pour au moins
 337 un $x\in\Bool^{\mathsf{N}}$.
 338
 339 On note que la présence de
 340 deux arcs de signes opposés entre deux sommets donnés
 341 est possible.
 342 % Dans la suite, le graphe signé $G$ sera qualifié de
 343 % \emph{simple} si, pour chaque  $i$, $j$ dans $[n]$,
 344 % il existe au plus un arc de $j$ à $i$ dans $G$.
 345 Un cycle \emph{positif} (resp. négatif) de $G$
 346 est un cycle \emph{élémentaire} qui contient un nombre
 347 pair (resp. impair) d'arcs négatifs.
 348 La \emph{longueur}
 349 d'un cycle est le nombre d'arcs qu'il contient.
 350
 351 \begin{xpl}
 352 Pour exprimer la jacobienne discrète de la fonction donnée en exemple,
 353 pour chaque $i$, $j$ dans
 354 $[3]$ on exprime
 355 $f'_{ij}(x)=
 356 \frac
 357 {f_i(\overline{x}^j){-}f_i(x)}
 358 {\overline{x_j}{-}x_j}$
 359 d'après l'équation~(\ref{eq:jacobienne}).
 360 % Ainsi
 361 % $$
 362 % f'_{12} (x_1,x_2,x_3)=
 363 % \frac
 364 % { ((\overline{x_1} + \overline{\overline{x_2}}).x_3)
 365 % {-}
 366 % ((\overline{x_1} + \overline{x_2}).x_3)
 367 % }
 368 % {\overline{x_2}{-}x_2} =  \frac{
 369 % ((\overline{x_1} + x_2).x_3)
 370 % {-}
 371 % ((\overline{x_1} + \overline{x_2}).x_3)
 372 % }{\overline{x_2}{-}x_2} .
 373 % $$
 374 % Évaluons cette fonction de $\Bool^3$ dans $\Z$ en construisant le tableau de toutes ses valeurs.
 375 % $$
 376 % \begin{array}{|c|c|c|c|c|c|c|c|}
 377 % \hline
 378 % x_1 &   x_2 &  x_3 &
 379 % (\overline{x_1} + {x_2}).x_3 & (\overline{x_1} + \overline{x_2}).x_3 &
 380 % (\overline{x_1} + {x_2}).x_3 {-} (\overline{x_1} + \overline{x_2}).x_3 & \overline{x_2} {-} x_2  &
 381 % f'_{12} (x_1,x_2,x_3)\\
 382 % \hline
 383 % 0   &  0    &  0   &  0  & 0 & 0 & 1   & 0 \\\hline
 384 % 0   &  0    &  1   &  1  & 1 & 0 & 1   & 0 \\\hline
 385 % 0   &  1    &  0   &  0  & 0 & 0 & -1  & 0 \\\hline
 386 % 0   &  1    &  1   &  1  & 1 & 0 & -1  & 0 \\\hline
 387 % 1   &  0    &  0   &  0  & 0 & 0 & 1   & 0 \\\hline
 388 % 1   &  0    &  1   &  0  & 1 & -1 & 1   & -1 \\\hline
 389 % 1   &  1    &  0   &  0  & 0 & 0 & -1  & 0 \\\hline
 390 % 1   &  1    &  1   &  1  & 0 & 1& -1  & -1 \\\hline
 391 % \end{array}
 392 % $$
 393 % La seule valeur de $f'_{12}$ qui n'est pas nulle est -1, qui est négative.
 394 % Le graphe d'interaction contiendra ainsi un arc négatif entre le n{\oe}ud 2 et le n{\oe}ud 1.
 395 La \textsc{Figure}~(\ref{fig:f:jacobienne}) explicite la matrice jacobienne discrète de cette fonction.
 396
 397 Le graphe d'interaction de $f$ s'en déduit directement. Il est donné à la
 398 \textsc{Figure}~(\ref{fig:f:interaction}).
 399 Il possède
 400 un cycle négatif de longueur 1 et
 401 un cycle négatif de longueur 3.
 402 Concernant les cycles positifs, il en possède
 403 un de longueur 1,
 404 deux de longueur 2
 405 et un de longueur 3.
 406
 407 La matrice d'incidence peut se déduire de la matrice d'interaction en supprimant les signes ou bien
 408 en constatant que $f_1$ dépend des trois éléments $x_1$, $x_2$ et $x_3$ et donc que la première ligne de $B(f)$
 409 est égale à $1~1~1$. De manière similaire,  $f_2$ (resp. $f_3$) dépend  de
 410 $x_1$ et  de $x_3$
 411 (resp. dépend de $x_1$, $x_2$ et $x_3$).
 412 Ainsi la seconde ligne (resp. la troisième ligne) de $B(f)$ est $1~0~1$ (resp. est $1~1~1$).
 413 La \textsc{Figure}~(\ref{fig:f:incidence}) donne la matrice d'incidence complète.
 414
 415 \begin{figure}%[ht]
 416   \begin{center}
 417      \subfigure[Matrice jacobienne]{
 418        \begin{minipage}{0.90\textwidth}
 419          \begin{center}
 420         $
 421         \left(
 422           \begin{array}{ccc}
 423             \frac{
 424               ((x_1 + \overline{x_2}).x_3)
 425               {-}
 426               ((\overline{x_1} + \overline{x_2}).x_3)
 427             }{\overline{x_1}{-}x_1}
 428             &
 429             \frac{
 430               ((\overline{x_1} + x_2).x_3)
 431               {-}
 432               ((\overline{x_1} + \overline{x_2}).x_3)
 433             }{\overline{x_2}{-}x_2}
 434             &
 435             \frac{
 436               ((\overline{x_1} + \overline{x_2}).\overline{x_3})
 437               {-}
 438               ((\overline{x_1} + \overline{x_2}).x_3)
 439             }{\overline{x_3}{-}x_3}
 440 \\
 441 \\
 442             \frac{\overline{x_1}.x_3 {-} x_1.x_3}{\overline{x_1}{-}x_1}
 443              & 0 &
 444 \frac{{x_1}.\overline{x_3} {-} x_1.x_3}{\overline{x_3}{-}x_3}
 445  \\
 446 \\
 447             \frac{(\overline{x_1}+x_2+x_3){-}(x_1+x_2+x_3)}{\overline{x_1}{-}{x_1}} &
 448             \frac{(x_1+\overline{x_2}+x_3){-}(x_1+x_2+x_3)}{\overline{x_2}{-}{x_2}} &
 449             \frac{(x_1+x_2+\overline{x_3}){-}(x_1+x_2+x_3)}{\overline{x_3}{-}{x_3}}
 450           \end{array}
 451         \right)
 452         $
 453          \end{center}
 454        \end{minipage}
 455        \label{fig:f:jacobienne}
 456      }
 457     ~
 458     \subfigure[Graphe d'interaction]{
 459       \begin{minipage}{0.45\textwidth}
 460       \begin{center}
 461         \includegraphics[scale=0.5]{gf}
 462       \end{center}
 463       \label{fig:f:interaction}
 464     \end{minipage}
 465     }
 466
 467     \subfigure[Matrice d'incidence]{
 468       \begin{minipage}{0.45\textwidth}
 469         \begin{center}
 470           $
 471           B(f) =
 472           \left(
 473             \begin{array}{ccc}
 474               1 & 1 & 1 \\
 475               1 & 0 & 1 \\
 476               1 & 1 & 1
 477             \end{array}
 478           \right)
 479           $
 480         \end{center}
 481         \label{fig:f:incidence}
 482     \end{minipage}
 483   }
 484 \end{center}
 485 \caption{Représentations des dépendances entre les éléments
 486 de la fonction
 487 $f:\Bool^3 \rightarrow \Bool^3$ telle que
 488 $(x_1, x_2, x_3) \mapsto
 489 ((\overline{x_1} + \overline{x_2}).x_3,
 490 x_1.x_3,
 491 x_1 + x_2 + x_3)$}
 492 \end{figure}
 493 \end{xpl}
 494
 495
 496
 497
 498 Soit $P$ une suite d'arcs de $\Gamma(f)$ de la forme
 499 \[
 500 (i_1,s_1,i_2),(i_2,s_2,i_3),\ldots,(i_r,s_r,i_{r+1}).
 501 \]
 502 Alors, $P$ est dit un chemin de $\Gamma(f)$ de longueur $r$ et de signe
 503 $\Pi_{i=1}^{r}s_i$ et  $i_{r+1}$ est dit accessible depuis
 504 $i_1$.
 505 $P$ est un {\emph{circuit}} si $i_{r+1}=i_1$ et si les sommets
 506 $i_1$,\ldots $i_r$ sont deux à deux disjoints.
 507 Un sommet $i$ de $\Gamma(f)$ a une {\emph{boucle}}
 508 positive (resp. négative) , si $\Gamma(f)$ a un
 509 arc positif (resp. un arc négatif) de $i$ vers lui-même.
 510
 511
 512
 513 \subsection{Conditions de convergence}\label{sec:Robert:async}
 514
 515 Parmi les itérations unaires caractérisées par leurs stratégies
 516 $S=(s^t)^{t \in \Nats}$ d'éléments appartenant à $[{\mathsf{N}}]$,
 517 sont jugées intéressantes
 518 celles qui activent au moins une fois
 519 chacun des $i\in[{\mathsf{N}}]$. Dans le cas contraire, un élément n'est jamais modifié.
 520
 521 Plus formellement, une séquence finie $S=(s^t)^{t \in \Nats}$
 522 est dite \emph{complète} relativement à $[{\mathsf{N}}]$ si
 523 tout indice de $[{\mathsf{N}}]$
 524 s'y retrouve au moins une fois.
 525
 526 Parmi toutes les stratégies unaires de
 527 $[{\mathsf{N}}]^{\Nats}$, on qualifie de:
 528 \begin{itemize}
 529 \item \emph{périodiques} celles
 530 qui sont constituées par une répétition infinie
 531 d'une même séquence $S$ complète relativement à $[{\mathsf{N}}]$.
 532 En particulier toute séquence périodique est complète.
 533 \item \emph{pseudo-périodiques} celles
 534 qui sont constituées par une succession infinie de séquences
 535 (de longueur éventuellement variable non supposée bornée) complètes.
 536 Autrement dit dans chaque stratégie pseudo-périodique, chaque indice de
 537 $1$ à ${\mathsf{N}}$ revient infiniment.
 538 \end{itemize}
 539
 540
 541 On a le théorème suivant de convergence
 542 dans le mode des itérations unaires.
 543
 544 \begin{theorem}[~\cite{Rob95}]\label{Th:conv:GIU}
 545 Si le graphe $\Gamma(f)$ n'a pas de cycle et si la stratégie unaire est
 546 pseudo-périodique, alors tout chemin de $\textsc{giu}(f)$ atteint
 547 l'unique point fixe $\zeta$ en au plus ${\mathsf{N}}$ pseudo-périodes.
 548 \end{theorem}
 549
 550 Le qualificatif \emph{pseudo-périodique} peut aisément
 551 s'étendre aux stratégies généralisées comme suit.
 552 Lorsqu'une stratégie généralisée est constituée d'une
 553 succession infinie de séquences de parties de $[{\mathsf{N}}]$
 554 dont l'union est $[{\mathsf{N}}]$, cette stratégie est {pseudo-périodique}.
 555 On a le théorème suivant.
 556
 557 \begin{theorem}[~\cite{Bah00}]\label{Th:Bahi}
 558 Si le graphe $\Gamma(f)$ n'a pas de cycle et si la stratégie généralisée
 559 est pseudo-périodique alors
 560 tout chemin de $\textsc{gig}(f)$ (et donc de $\textsc{giu}(f)$)
 561 finit par atteindre
 562 l'unique point fixe $\zeta$.
 563 \end{theorem}
 564
 565 % \section{Distance sur l'espace $\llbracket 1;n\rrbracket^{\Nats}\times \Bool^n$}\label{sub:metric}
 566 % On considère l'espace $\mathcal{X}=\llbracket 1;n\rrbracket^{\Nats}\times
 567 % \Bool^n$ et
 568 % on définit la distance $d$ entre les points $X=(s,x)$ et
 569 % $X'=(s',x')$ de $\mathcal{X}$ par
 570 % \[
 571 % d(X,X')= d_H(x,x')+d_S(s,s'),~\textrm{où}~
 572 % \left\{
 573 % \begin{array}{l}
 574 % \displaystyle{d_H(x,x')=\sum_{i=1}^n |x_i-x'_i|}\\[5mm]
 575 % \displaystyle{d_S(s,s')=\frac{9}{n}\sum_{t\in\Nats}\frac{|s_t-s'_t|}{10^{t+1}}}.
 576 % \end{array}
 577 % \right.\,.
 578 % \]
 579 % On note que dans le calcul de $d_H(x,x')$--
 580 % appelée \gls{distanceHamming} (cf. glossaire) entre $x$ et $x'$--
 581 % les termes $x_i$ et $x'_i$ sont considérés comme des entiers naturels
 582 % égaux à $0$ ou à $1$ et que le calcul est effectué dans $\Z$.
 583 % De plus, la \gls{partieentiere} (cf. glossaire)
 584 % $\lfloor d(X,X')\rfloor$ est égale à $d_H(x,x')$ soit la distance
 585 % de Hamming entre $x$ et $x'$.
 586 % %D'autre part, $d(X,X')-\lfloor d(X,X')\rfloor=d_S(s,s')$
 587 % %mesure la différence entre $s$ et $s'$.
 588 % On remarque que la partie décimale est inférieure à $10^{-l}$ si
 589 % et seulement si les $l$ premiers termes des deux stratégies sont égaux.
 590 % De plus, si la
 591 % $(l+1)^{\textrm{ème}}$ décimale
 592 % de $d_S(s,s')$
 593 % n'est pas nulle, alors $s_l$ est différent de  $s'_l$.
 594
 595 % On a  démontré que pour toute fonction booléenne $f$,
 596 % $G_f$ est continue sur $\mathcal{X}$ (cf annexe~\ref{anx:cont}).
 597