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   Ce schéma 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$ 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
 204 \begin{figure}[ht]
 205   \begin{center}
 206     \subfigure[$\textsc{gis}(f)$]{
 207       \begin{minipage}{0.3\textwidth}
 208         \begin{center}
 209           \includegraphics[scale=0.4]{fsig}
 210         \end{center}
 211       \end{minipage}
 212       \label{fig:fsig}
 213     }
 214     \subfigure[$\textsc{giu}(f)$]{
 215       \begin{minipage}{0.3\textwidth}
 216         \begin{center}
 217           \includegraphics[scale=0.4]{faig}
 218         \end{center}
 219       \end{minipage}
 220       \label{fig:faig}
 221     }
 222     \subfigure[$\textsc{gig}(f)$]{
 223       \begin{minipage}{0.3\textwidth}
 224         \begin{center}
 225           \includegraphics[scale=0.4]{fgig}
 226         \end{center}
 227       \end{minipage}
 228       \label{fig:fgig}
 229     }
 230   \end{center}
 231   \caption{Graphes des itérations de la fonction
 232 $f:\Bool^3 \rightarrow \Bool^3$ telle que
 233 $(x_1, x_2, x_3) \mapsto
 234 ((\overline{x_1} + \overline{x_2}).x_3,
 235 x_1.x_3,
 236 x_1 + x_2 + x_3)$.\label{fig:xpl:graphs}
 237 On remarque le cycle $((101,111),(111,011),(011,101))$
 238  à la \textsc{Figure}~(\ref{fig:fsig}).}
 239 \end{figure}
 240
 241 \begin{xpl}
 242 On reprend notre exemple illustratif
 243 détaillé à la page~\pageref{xpl:1} avec sa table
 244 d'images (\textsc{Table}~\ref{table:xpl:images}).
 245 La \textsc{Figure}~\ref{fig:xpl:graphs} donne les trois graphes d'itérations
 246 associés à $f$.
 247 \end{xpl}
 248
 249
 250 \subsection{Attracteurs}
 251
 252 On dit que le point
 253 $x \in \Bool^{\mathsf{N}}$ est un \emph{point fixe} de $f$ si  $x = f (x)$.
 254 Les points fixes sont particulièrement intéressants car ils correspondent
 255 aux états stables:
 256 dans chaque graphe d'itérations, le point $x$ est un point fixe
 257 si et seulement si il est son seul successeur.
 258
 259
 260
 261 Soit un graphe d'itérations (synchrones, unaires ou généralisées)
 262 de $f$.
 263 Les \emph{attracteurs}  de ce graphe sont les
 264 plus petits sous-ensembles (au sens de l'inclusion) non vides
 265 $A \subseteq \Bool^{\mathsf{N}}$ tels que pour tout arc
 266 $x \rightarrow y$, si $x$ est un élément de $A$, alors
 267 $y$ aussi.
 268 Un attracteur qui contient au moins deux éléments  est dit \emph{cyclique}.
 269 On en déduit qu'un attracteur cyclique ne contient pas de point fixe.
 270 En d'autres termes, lorsqu'un système entre dans un attracteur cyclique,
 271 il ne peut pas atteindre un point fixe.
 272
 273
 274 On a la proposition suivante:
 275
 276
 277 \begin{theorem}\label{Prop:attracteur}
 278 La configuration $x$ est un point fixe si et seulement si
 279 $\{x\}$ est un attracteur du graphe d'itérations (synchrone, unaire, généralisé).
 280 En d'autres termes, les attracteurs non cycliques de celui-ci
 281 sont les points fixes de $f$.
 282 Ainsi pour chaque $x\in \Bool^{\mathsf{N}}$, il existe au moins un chemin
 283 depuis $x$ qui atteint un attracteur.
 284 Tout graphe d'itérations contient donc toujours au moins un attracteur.
 285 \end{theorem}
 286
 287
 288
 289 \begin{xpl}
 290 Les attracteurs de $\textsc{giu}(f)$ et de $\textsc{gig}(f)$ sont
 291 le point fixe $000$ et l'attracteur cyclique
 292 $\{001, 101,111, 011  \}$.
 293 Les attracteurs de $\textsc{gis}(f)$ sont le point fixe $000$
 294 et l'attracteur cyclique $\{011, 101, 111\}$.
 295 \end{xpl}
 296
 297 \subsection{Graphe d'interaction}
 298 Les interactions entre les composants du
 299 système peuvent être mémorisées
 300 dans la {\emph{matrice jacobienne discrète}} $f'$.
 301 Celle-ci est définie comme étant la fonction  qui  à chaque
 302 configuration $x\in\Bool^{\mathsf{N}}$ associe la matrice de taille
 303 $n\times n$ telle que
 304 \begin{equation}
 305 f'(x)=(f'_{ij}(x)),\qquad
 306 f'_{ij}(x)=\frac{f_i(\overline{x}^j){-}f_i(x)}{\overline{x_j}{-}x_j}\qquad (i,j\in[n]).
 307 \label{eq:jacobienne}
 308 \end{equation}
 309 On note que dans l'équation donnant la valeur de $f'_{ij}(x)$,
 310 les termes $f_i(\overline{x}^j)$, $f_i(x)$,
 311 $\overline{x}^j_j$ et $x_j$ sont considérés comme des entiers naturels
 312 égaux à $0$ ou à $1$ et que la différence est effectuée
 313  dans $\Z$.
 314 Lorsqu'on supprime les signes dans la matrice jacobienne discrète,
 315 on obtient une matrice notée $B(f)$ aussi de taille
 316 ${\mathsf{N}}\times {\mathsf{N}}$.
 317 Celle-ci mémorise uniquement
 318 l'existence d'une dépendance de tel élément vis à vis de
 319  tel élément.
 320 Elle ne mémorise pas \emph{comment}  les éléments dépendent
 321 les uns par rapport aux autres. Cette matrice est nommée
 322 \emph{matrice d'incidence}.
 323
 324 \begin{theorem}
 325 Si $f_i$ ne dépend pas de $x_j$, alors pour tout $x\in [{\mathsf{N}}]$,
 326 $f_i(\overline{x}^j)$ est égal à  $f_i(x)$, \textit{i.e.},
 327 $f'_{ij}(x)=0$. Ainsi $B(f)_{ij}$ est nulle. La réciproque est aussi vraie.
 328 \end{theorem}
 329
 330
 331
 332
 333 En outre, les interactions peuvent se  représenter à l'aide d'un
 334 graphe $\Gamma(f)$ orienté et signé défini ainsi:
 335 l'ensemble des sommets est
 336 $[{\mathsf{N}}]$ et il existe un arc de $j$ à $i$ de signe
 337  $s\in\{-1,1\}$, noté $(j,s,i)$, si $f_{ij}(x)=s$ pour au moins
 338 un $x\in\Bool^{\mathsf{N}}$.
 339
 340 On note que la présence de
 341 deux arcs de signes opposés entre deux sommets donnés
 342 est possible.
 343 % Dans la suite, le graphe signé $G$ sera qualifié de
 344 % \emph{simple} si, pour chaque  $i$, $j$ dans $[n]$,
 345 % il existe au plus un arc de $j$ à $i$ dans $G$.
 346 Un cycle \emph{positif} (resp. négatif) de $G$
 347 est un cycle \emph{élémentaire} qui contient un nombre
 348 pair (resp. impair) d'arcs négatifs.
 349 La \emph{longueur}
 350 d'un cycle est le nombre d'arcs qu'il contient.
 351
 352 \begin{xpl}
 353 Pour exprimer la jacobienne discrète de la fonction donnée en exemple,
 354 pour chaque $i$, $j$ dans
 355 $[3]$ on exprime
 356 $f'_{ij}(x)=
 357 \frac
 358 {f_i(\overline{x}^j){-}f_i(x)}
 359 {\overline{x_j}{-}x_j}$
 360 d'après l'équation~(\ref{eq:jacobienne}).
 361 % Ainsi
 362 % $$
 363 % f'_{12} (x_1,x_2,x_3)=
 364 % \frac
 365 % { ((\overline{x_1} + \overline{\overline{x_2}}).x_3)
 366 % {-}
 367 % ((\overline{x_1} + \overline{x_2}).x_3)
 368 % }
 369 % {\overline{x_2}{-}x_2} =  \frac{
 370 % ((\overline{x_1} + x_2).x_3)
 371 % {-}
 372 % ((\overline{x_1} + \overline{x_2}).x_3)
 373 % }{\overline{x_2}{-}x_2} .
 374 % $$
 375 % Évaluons cette fonction de $\Bool^3$ dans $\Z$ en construisant le tableau de toutes ses valeurs.
 376 % $$
 377 % \begin{array}{|c|c|c|c|c|c|c|c|}
 378 % \hline
 379 % x_1 &   x_2 &  x_3 &
 380 % (\overline{x_1} + {x_2}).x_3 & (\overline{x_1} + \overline{x_2}).x_3 &
 381 % (\overline{x_1} + {x_2}).x_3 {-} (\overline{x_1} + \overline{x_2}).x_3 & \overline{x_2} {-} x_2  &
 382 % f'_{12} (x_1,x_2,x_3)\\
 383 % \hline
 384 % 0   &  0    &  0   &  0  & 0 & 0 & 1   & 0 \\\hline
 385 % 0   &  0    &  1   &  1  & 1 & 0 & 1   & 0 \\\hline
 386 % 0   &  1    &  0   &  0  & 0 & 0 & -1  & 0 \\\hline
 387 % 0   &  1    &  1   &  1  & 1 & 0 & -1  & 0 \\\hline
 388 % 1   &  0    &  0   &  0  & 0 & 0 & 1   & 0 \\\hline
 389 % 1   &  0    &  1   &  0  & 1 & -1 & 1   & -1 \\\hline
 390 % 1   &  1    &  0   &  0  & 0 & 0 & -1  & 0 \\\hline
 391 % 1   &  1    &  1   &  1  & 0 & 1& -1  & -1 \\\hline
 392 % \end{array}
 393 % $$
 394 % La seule valeur de $f'_{12}$ qui n'est pas nulle est -1, qui est négative.
 395 % Le graphe d'interaction contiendra ainsi un arc négatif entre le n{\oe}ud 2 et le n{\oe}ud 1.
 396 La \textsc{Figure}~(\ref{fig:f:jacobienne}) explicite la matrice jacobienne discrète de cette fonction.
 397
 398 Le graphe d'interaction de $f$ s'en déduit directement. Il est donné à la
 399 \textsc{Figure}~(\ref{fig:f:interaction}).
 400 Il possède
 401 un cycle négatif de longueur 1 et
 402 un cycle négatif de longueur 3.
 403 Concernant les cycles positifs, il en possède
 404 un de longueur 1,
 405 deux de longueur 2
 406 et un de longueur 3.
 407
 408 La matrice d'incidence peut se déduire de la matrice d'interaction en supprimant les signes ou bien
 409 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)$
 410 est égale à $1~1~1$. De manière similaire,  $f_2$ (resp. $f_3$) dépend  de
 411 $x_1$ et  de $x_3$
 412 (resp. dépend de $x_1$, $x_2$ et $x_3$).
 413 Ainsi la seconde ligne (resp. la troisième ligne) de $B(f)$ est $1~0~1$ (resp. est $1~1~1$).
 414 La \textsc{Figure}~(\ref{fig:f:incidence}) donne la matrice d'incidence complète.
 415
 416 \begin{figure}[ht]
 417   \begin{center}
 418      \subfigure[Matrice jacobienne]{
 419        \begin{minipage}{0.65\textwidth}
 420          \begin{scriptsize}
 421          \begin{center}
 422         $
 423         \left(
 424           \begin{array}{ccc}
 425             \frac{
 426               ((x_1 + \overline{x_2}).x_3)
 427               {-}
 428               ((\overline{x_1} + \overline{x_2}).x_3)
 429             }{\overline{x_1}{-}x_1}
 430             &
 431             \frac{
 432               ((\overline{x_1} + x_2).x_3)
 433               {-}
 434               ((\overline{x_1} + \overline{x_2}).x_3)
 435             }{\overline{x_2}{-}x_2}
 436             &
 437             \frac{
 438               ((\overline{x_1} + \overline{x_2}).\overline{x_3})
 439               {-}
 440               ((\overline{x_1} + \overline{x_2}).x_3)
 441             }{\overline{x_3}{-}x_3}
 442 \\
 443 \\
 444             \frac{\overline{x_1}.x_3 {-} x_1.x_3}{\overline{x_1}{-}x_1}
 445              & 0 &
 446 \frac{{x_1}.\overline{x_3} {-} x_1.x_3}{\overline{x_3}{-}x_3}
 447  \\
 448 \\
 449             \frac{(\overline{x_1}+x_2+x_3){-}(x_1+x_2+x_3)}{\overline{x_1}{-}{x_1}} &
 450             \frac{(x_1+\overline{x_2}+x_3){-}(x_1+x_2+x_3)}{\overline{x_2}{-}{x_2}} &
 451             \frac{(x_1+x_2+\overline{x_3}){-}(x_1+x_2+x_3)}{\overline{x_3}{-}{x_3}}
 452           \end{array}
 453         \right)
 454         $
 455          \end{center}
 456        \end{scriptsize}
 457      \end{minipage}
 458        \label{fig:f:jacobienne}
 459      }
 460      \subfigure[Matrice d'incidence]{
 461        \begin{minipage}{0.25\textwidth}
 462         \begin{center}
 463           $
 464           B(f) =
 465           \left(
 466             \begin{array}{ccc}
 467               1 & 1 & 1 \\
 468               1 & 0 & 1 \\
 469               1 & 1 & 1
 470             \end{array}
 471           \right)
 472           $
 473         \end{center}
 474         \label{fig:f:incidence}
 475     \end{minipage}
 476   }
 477
 478     ~
 479     \subfigure[Graphe d'interaction]{
 480       \begin{minipage}{0.45\textwidth}
 481       \begin{center}
 482         \includegraphics[scale=0.5]{gf}
 483       \end{center}
 484       \label{fig:f:interaction}
 485     \end{minipage}
 486     }
 487 \end{center}
 488 \caption{Représentations des dépendances entre les éléments
 489 de la fonction
 490 $f:\Bool^3 \rightarrow \Bool^3$ telle que
 491 $(x_1, x_2, x_3) \mapsto
 492 ((\overline{x_1} + \overline{x_2}).x_3,
 493 x_1.x_3,
 494 x_1 + x_2 + x_3)$}
 495 \end{figure}
 496 \end{xpl}
 497
 498
 499
 500
 501 Soit $P$ une suite d'arcs de $\Gamma(f)$ de la forme
 502 \[
 503 (i_1,s_1,i_2),(i_2,s_2,i_3),\ldots,(i_r,s_r,i_{r+1}).
 504 \]
 505 Alors, $P$ est dit un chemin de $\Gamma(f)$ de longueur $r$ et de signe
 506 $\Pi_{i=1}^{r}s_i$ et  $i_{r+1}$ est dit accessible depuis
 507 $i_1$.
 508 $P$ est un {\emph{circuit}} si $i_{r+1}=i_1$ et si les sommets
 509 $i_1$,\ldots $i_r$ sont deux à deux disjoints.
 510 Un sommet $i$ de $\Gamma(f)$ a une {\emph{boucle}}
 511 positive (resp. négative) , si $\Gamma(f)$ a un
 512 arc positif (resp. un arc négatif) de $i$ vers lui-même.
 513
 514
 515
 516 \subsection{Conditions de convergence}\label{sec:Robert:async}
 517
 518 Parmi les itérations unaires caractérisées par leurs stratégies
 519 $S=(s^t)^{t \in \Nats}$ d'éléments appartenant à $[{\mathsf{N}}]$,
 520 sont jugées intéressantes
 521 celles qui activent au moins une fois
 522 chacun des $i\in[{\mathsf{N}}]$. Dans le cas contraire, un élément n'est jamais modifié.
 523
 524 Plus formellement, une séquence finie $S=(s^t)^{t \in \Nats}$
 525 est dite \emph{complète} relativement à $[{\mathsf{N}}]$ si
 526 tout indice de $[{\mathsf{N}}]$
 527 s'y retrouve au moins une fois.
 528
 529 Parmi toutes les stratégies unaires de
 530 $[{\mathsf{N}}]^{\Nats}$, on qualifie de:
 531 \begin{itemize}
 532 \item \emph{périodiques} celles
 533 qui sont constituées par une répétition infinie
 534 d'une même séquence $S$ complète relativement à $[{\mathsf{N}}]$.
 535 En particulier toute séquence périodique est complète.
 536 \item \emph{pseudo-périodiques} celles
 537 qui sont constituées par une succession infinie de séquences
 538 (de longueur éventuellement variable non supposée bornée) complètes.
 539 Autrement dit dans chaque stratégie pseudo-périodique, chaque indice de
 540 $1$ à ${\mathsf{N}}$ revient infiniment.
 541 \end{itemize}
 542
 543
 544 On a le théorème suivant de convergence
 545 dans le mode des itérations unaires.
 546
 547 \begin{theorem}[~\cite{Rob95}]\label{Th:conv:GIU}
 548 Si le graphe $\Gamma(f)$ n'a pas de cycle et si la stratégie unaire est
 549 pseudo-périodique, alors tout chemin de $\textsc{giu}(f)$ atteint
 550 l'unique point fixe $\zeta$ en au plus ${\mathsf{N}}$ pseudo-périodes.
 551 \end{theorem}
 552
 553 Le qualificatif \emph{pseudo-périodique} peut aisément
 554 s'étendre aux stratégies généralisées comme suit.
 555 Lorsqu'une stratégie généralisée est constituée d'une
 556 succession infinie de séquences de parties de $[{\mathsf{N}}]$
 557 dont l'union est $[{\mathsf{N}}]$, cette stratégie est {pseudo-périodique}.
 558 On a le théorème suivant.
 559
 560 \begin{theorem}[~\cite{Bah00}]\label{Th:Bahi}
 561 Si le graphe $\Gamma(f)$ n'a pas de cycle et si la stratégie généralisée
 562 est pseudo-périodique alors
 563 tout chemin de $\textsc{gig}(f)$ (et donc de $\textsc{giu}(f)$)
 564 finit par atteindre
 565 l'unique point fixe $\zeta$.
 566 \end{theorem}
 567
 568 % \section{Distance sur l'espace $\llbracket 1;n\rrbracket^{\Nats}\times \Bool^n$}\label{sub:metric}
 569 % On considère l'espace $\mathcal{X}=\llbracket 1;n\rrbracket^{\Nats}\times
 570 % \Bool^n$ et
 571 % on définit la distance $d$ entre les points $X=(s,x)$ et
 572 % $X'=(s',x')$ de $\mathcal{X}$ par
 573 % \[
 574 % d(X,X')= d_H(x,x')+d_S(s,s'),~\textrm{où}~
 575 % \left\{
 576 % \begin{array}{l}
 577 % \displaystyle{d_H(x,x')=\sum_{i=1}^n |x_i-x'_i|}\\[5mm]
 578 % \displaystyle{d_S(s,s')=\frac{9}{n}\sum_{t\in\Nats}\frac{|s_t-s'_t|}{10^{t+1}}}.
 579 % \end{array}
 580 % \right.\,.
 581 % \]
 582 % On note que dans le calcul de $d_H(x,x')$--
 583 % appelée \gls{distanceHamming} (cf. glossaire) entre $x$ et $x'$--
 584 % les termes $x_i$ et $x'_i$ sont considérés comme des entiers naturels
 585 % égaux à $0$ ou à $1$ et que le calcul est effectué dans $\Z$.
 586 % De plus, la \gls{partieentiere} (cf. glossaire)
 587 % $\lfloor d(X,X')\rfloor$ est égale à $d_H(x,x')$ soit la distance
 588 % de Hamming entre $x$ et $x'$.
 589 % %D'autre part, $d(X,X')-\lfloor d(X,X')\rfloor=d_S(s,s')$
 590 % %mesure la différence entre $s$ et $s'$.
 591 % On remarque que la partie décimale est inférieure à $10^{-l}$ si
 592 % et seulement si les $l$ premiers termes des deux stratégies sont égaux.
 593 % De plus, si la
 594 % $(l+1)^{\textrm{ème}}$ décimale
 595 % de $d_S(s,s')$
 596 % n'est pas nulle, alors $s_l$ est différent de  $s'_l$.
 597
 598 % On a  démontré que pour toute fonction booléenne $f$,
 599 % $G_f$ est continue sur $\mathcal{X}$ (cf annexe~\ref{anx:cont}).
 600