sdd.tex

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