]> AND Private Git Repository - hdrcouchot.git/blob - sdd.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
ajout de quelques tex
[hdrcouchot.git] / 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