reprise chap 1

diff --git a/annexePreuveMixage.tex b/annexePreuveMixage.tex
index 4757b0b68d5c5c0073db472a783b7fdda715ad5c..d4087d42d45e028686c795b2cf5b056815b0d194 100644 (file)
--- a/annexePreuveMixage.tex
+++ b/annexePreuveMixage.tex
@@ -1,103 +1,105 @@
-
-Let  us introduce an  ordering $\preceq$  between classes.   Formally, \class{p}
-$\preceq$   \class{q}   if   there    exists   a   path   of   length   $\alpha$
-($0<\alpha<|\mathcal{K}|$)  from  an  element  of  \class{p} to  an  element  of
-\class{q}.  One can  remark that if \class{p}$\preceq$\class{q}, then  it is not
-possible to also have \class{q}$\preceq$\class{p}.
-
-% \begin{lemma}
-%   The relation $ \preceq$ is a partial order
-%   \begin{Proof}
-%     Reflexivity is established  since for any $p_0 \in [p]$  there exists a path
-%     of length  0 from  $p_0$ to $p_0$.
-%     For antisymmetry, suppose  there exists two classes $[p]$ and 
-%     $[q]$ such that $[p] \preceq [q]$ and $[q] \preceq [p]$.
-%     There exists then $p_0,p'_0 \in [p]$, $q_0, q'_0 \in [q]$ with paths 
-%     from $p_0$ to $q_0$ and from $q'_0$  to $p_0$.
-%     Thus, elements $p_0$, $p'_0$, $q_0$ and $q'_0$ belong to the same 
-%     strongly connected component and then
-%     $[p]$ = $[q]$.  Transitivity is obviously established.
-%   \end{Proof}
-% \end{lemma}
+Introduisons tout d'abord une relation d'ordre 
+$\preceq$  entre les  classes d'équivalences.   
+Formellement, \class{p}
+$\preceq$   \class{q}   
+s'il existe un chemin de longueur   $\alpha$
+($0<\alpha<|\mathcal{K}|$)  entre un élément le la classe
+\class{p} vers un élément  de
+\class{q}.  
+On remarque que si la  \class{p}$\preceq$\class{q}, 
+il n'est alors pas possible que  \class{q}$\preceq$\class{p}.

 
 \begin{lemma}
 
 \begin{lemma}

-  There exists a renaming process  method that assigns new identifier numbers to
-  processes  $i\in$ \class{p}  and $j  \in$ \class{q}  s.t. $i  \le  j$ provided
+  Il existe un processus de renommage qui effecte un nouvel identifiant aux
+  élément  $i\in$ \class{p}  et $j  \in$ \class{q}  tel que 
+  $i  \le  j$ si et seulement si

   \class{p} $\preceq$ \class{q}.
   \begin{Proof}
   \class{p} $\preceq$ \class{q}.
   \begin{Proof}

-    % We first  define a renaming process  method and later show  that it fulfills
-    % the requirements.

     
     

-    First  of   all,  let  \class{p_1},   \ldots,  \class{p_l}  be   classes  of
-    $n_1$,\ldots,  $n_l$  elements respectively  that  do  not  depend on  other
-    classes.   Elements of  \class{p_1} are  renamed by  $1$, \ldots,  $n_1$ and
-    elements   of  \class{p_i},   $2  \le   i  \le   l$  are   renamed   by  $1+
-    \Sigma_{k=1}^{i-1}  n_k$, \ldots, $\Sigma_{k=1}^{i}  n_k$.  We  now consider
-    the  classes \class{p_1},  \ldots, \class{p_{l'}}  whose elements  have been
-    renamed and let $m$ be the maximum index of elements of \class{p_1}, \ldots,
-    \class{p_{l'}}.  Given  another class \class{p} that  exclusively depends on
-    some \class{p_i}, $1 \le i \le l'$ and that contains $k$ elements.  Elements
-    of \class{p} are then renamed by $m+1$, \ldots, $m+k$.
-% In the end for remaining classes, i.e. those which do not depend on anything,
-% elements are arbitrarily numbered. 
-    This renaming  process method has then  been applied on  $l'+1$ classes.  It
-    ends since it  decreases the number of elements to  assign a number.  Notice
-    that this process is not determinist.
+    Tout d'abord,  soit  \class{p_1},   \ldots,  \class{p_l}  des   classes 
+    contenant respectivement $n_1$,\ldots,  $n_l$  éléments respectively
+    qui ne dépendent d'aucune autre classe.  
+    Les éléments de  \class{p_1} sont renommés par $1$, \ldots,  $n_1$,
+    les elements  de \class{p_i},   $2  \le   i  \le   l$  sont renommés par 
+    $1+
+    \Sigma_{k=1}^{i-1}  n_k$, \ldots, $\Sigma_{k=1}^{i}  n_k$. 
+    On considère maintenant les classes \class{p_1},  \ldots, \class{p_{l'}} 
+    dont les éléments ont été renommés et soit 
+    $m$ le plus grand indice des elements de \class{p_1}, \ldots,
+    \class{p_{l'}}.
+    Soit une autre classe \class{p} qui dépend exclusivement d'une classe 
+    \class{p_i}, $1 \le i \le l'$ et qui contient $k$ elements. 
+    Les éléments de \class{p} sont renommés par  $m+1$, \ldots, $m+k$.
+    Ce processus a été appliqué sur  $l'+1$ classes. Il se termine 
+    puisqu'il diminue le nombre d'elements auquel il reste 
+    à affecter un numéro. 

 
 

-    We  are then  ready to  prove that  this renaming  method  verifies property
-    expressed in the lemma.  The proof is done by induction on the length $l$ of
-    the longest dependency path between classes.
+    Il reste à montrer que cette méthode de renommage vérifie la propriété 
+    énoncée dans le lemme.
+    Cette preuve se fait par induction sur la taille  $l$
+    du plus grand chemin de dépendance entre les classes.

 
 

-    First, if \class{p} $\preceq$ \class{q} and \class{q} immediately depends on
-    \class{p},  \textit{i.e.} the  longest path  from elements  of  \class{p} to
-    elements of \class{q} has length 1.  Due to the renaming method, all element
-    numbers of \class{q}  are greater than the ones of  \class{p} and the result
-    is established.   Let \class{p} and  \class{q} s.t.  the  longest dependency
-    path from \class{p}  to \class{q} has length $l+1$.   Then there exists some
-    \class{q'} s.t.  \class{q} immediately depends on \class{q'} and the longest
-    dependency path from \class{p} and  \class{q'} has length $l$.  We have then
-    \class{q'}  $\preceq$ \class{q}  and  then for  all  $k$, $j$  s.t. $k  \in$
-    \class{q'}  and $j  \in$  \class{q},  $k \le  j$.   By induction  hypothesis
-    \class{p}  $\preceq$ \class{q'}  and  then for  all  $i$, $k$  s.t. $i  \in$
-    \class{p} and $k \in$ \class{q'}, $i \le k$ and the result is established.
+    Tout d'abord, si \class{p} $\preceq$ \class{q} et \class{q} 
+    dépend immédiatement de 
+    \class{p},  \textit{i.e.} 
+    le chemin le plus long entre les éléments de   \class{p} et les 
+    elements de \class{q} est de longueur 1.  
+    En raison de la méthode renommage, chaque numéro d'élément
+    \class{q}  est plus grand que tous ceux de  \class{p} et la preuve est 
+    établie.
+    Soit \class{p} et  \class{q} tels que le plus long chemin de dépendance 
+    entre \class{p} et  \class{q} a une longueur de $l+1$.   
+    Il existe alors une classe 
+    \class{q'} telle que \class{q} 
+    dépend immédiatement de  \class{q'} et le chemin de dépendance le
+    plus long entre \class{p} et  \class{q'} a pour longueur $l$. 
+    On a ainsi
+    \class{q'}  $\preceq$ \class{q}  
+    et pour tout  $k$, $j$  tels que $k  \in$
+    \class{q'} et $j  \in$  \class{q},  $k \le  j$.
+    Par hypothèse d'induction, 
+    \class{p}  $\preceq$ \class{q'}  et pour chaque  $i$, $k$  tels que $i  \in$
+    \class{p} et  $k \in$ \class{q'}, $i \le k$
+    et le résultat est établi.

   \end{Proof}
 \end{lemma}
 
   \end{Proof}
 \end{lemma}
 

-It can  be noticed that  the renaming process  is inspired from  \emph{graphs by
-  layer} of Golès and Salinas~\cite{GS08}. It ensures that identifier numbers of
-a layer are greater than all the identifier numbers of any lower layers.
+On peut remarquer que ce processus de renommage est inspiré des \emph{graphes 
+  par couches } de Golès et Salinas~\cite{GS08}.

 
 

-\begin{xpl}
-  We  have \class{1}  $=\{1,2\}$, \class{3}  $=\{3\}$ and  \class{4} $=\{4,5\}$.
-  Processes numbers are already compliant with the order $\preceq$.
-\end{xpl}
+% \begin{xpl}
+%   We  have \class{1}  $=\{1,2\}$, \class{3}  $=\{3\}$ and  \class{4} $=\{4,5\}$.
+%   Processes numbers are already compliant with the order $\preceq$.
+% \end{xpl}

 
 \begin{Proof}[of Theorem~\ref{th:cvg}]
 
 
 \begin{Proof}[of Theorem~\ref{th:cvg}]
 

-  % Since $\preceq$ is a partial order,  [[JFC citer un theoreme qui dit cela ou
-  % le prouver]]  there exists  a renaming process  that assigns  new identifier
-  % number to processes $i\in [p]$ and $j  \in [q]$ s.t. $i \le j$ provided $[p]
-  % \preceq [q]$.
-  % % $i \in [p]$ and $j \in [q]$.
-
-  The  rest of  the proof  is done  by  induction on  the class  index.  Let  us
-  consider  the first class  \class{b_1} with  $n_1$ elements  \textit{i.e.} the
-  class with the smallest identifiers.
+  Le reste de la preuve est fait par induction sur le numéro de classe. 
+  Considérons la première  classe \class{b_1} de $n_1$ éléments 
+  \textit{i.e.} la classe avec le plus petit identifiant.

 
 

-  By theorem hypotheses, %following the strategy $(S^t)$,
-  synchronous  iterations converge  to the  fixed point  in a  finite  number of
-  iterations. %pseudo periods. % [[JFC : borner m1/n1]].
-  So, all  \emph{source classes}  (independant from any  other class)  will also
-  converge in mixed mode.  Let us suppose now that mixed iterations with uniform
-  delays converge for classes \class{b_1},  \ldots, \class{b_k} in a time $t_k$.
-  By  construction, \class{b_{k+1}}  only depends  on some  \class{b_1}, \ldots,
-  \class{b_k} and \class{b_{k+1}}.  There  exists then a sufficiently large time
-  $t_0$  s.t.  $D^{t_0}_{p_{k+1}p_j}$  is  greater  or equal  to  $t_k$ for  any
-  $p_{k+1} \in$ \class{b_{k+1}} and $p_j \in$ \class{b_j}, $1 \le j \le k$.
+  D'après les hypothèses du  théorème, %following the strategy $(S^t)$,
+  les itérations synchrones convergent vers un point fixe en un nombre 
+  fini d'itérations. %pseudo periods. % [[JFC : borner m1/n1]].
+  Ainsi toutes les  \emph{classes sources} 
+  (indépendantes de toutes les  autres classes) vont aussi converger 
+  dans le mode mixe. 
+  On peut ainsi  supposer que le  mode d'itération mixe avec délais 
+  uniformes fait converger les classes \class{b_1},  \ldots, \class{b_k}
+  en  un temps $t_k$.
+  Par construction, la classe \class{b_{k+1}}  dépend uniquement 
+  de certaines classes de  \class{b_1}, \ldots,
+  \class{b_k} et éventuellement d'elle-même.
+  Il existe un nombre d'iteration suffisamment grand 
+  $t_0$  tel que  $D^{t_0}_{p_{k+1}p_j}$  est suppérieur ou égal à   $t_k$ 
+  pour chaque 
+  $p_{k+1} \in$ \class{b_{k+1}} et $p_j \in$ \class{b_j}, $1 \le j \le k$.

 
 

-  We are  then left with  synchronous iterations of elements  of \class{b_{k+1}}
-  starting with configurations  where all the elements of  \class{b_j}, $1 \le j
-  \le k$, have constant values.  By theorem hypotheses, it converges.
+  Il nous reste donc des itérations synchronous entre les 
+  elements  of \class{b_{k+1}} en démarant dans des configurations
+  où tous les éléments de  \class{b_j}, $1 \le j
+  \le k$, on des valeurs constantes.  
+  D'après les hypothèses du théorème, cela converge.

 \end{Proof}
 
 
 \end{Proof}
 
 

diff --git a/main.pdf b/main.pdf
index 5ee54b773f66abdba39983cc386dbb88660d4309..b01f58d828c72e1efe2a214393bc4e2eba5c88c5 100644 (file)
Binary files a/main.pdf and b/main.pdf differ

diff --git a/main.tex b/main.tex
index c16595e1021448ae0d1d8b2bf9e38216e02b5a83..ce52fff00982717267270d1e020566c5e2f7786d 100644 (file)
--- a/main.tex
+++ b/main.tex
@@ -183,19 +183,29 @@ de l'asynchronisme en terme de vitesse de convergence.
 
 \chapter{Preuves sur les SDD}
 
 
 \chapter{Preuves sur les SDD}
 

-\section{Théorème~\ref{th:Adrien}}\label{anx:sccg}
-\input{annexesccg}
+\section{Convergence du mode mixe}\label{anx:mix}
+\input{annexePreuveMixage}
+
+
+\section{Correction et complétude de la 
+  vérification de convergence par SPIN}\label{anx:promela}
+\input{annexePromelaProof}
+
+
+
+\chapter{Preuves sur les systèmes chaotiques}
+

 
 \section{Continuité de $G_f$ dans $(\mathcal{X},d)$}\label{anx:cont}
 \input{annexecontinuite.tex}
 
 
 
 \section{Continuité de $G_f$ dans $(\mathcal{X},d)$}\label{anx:cont}
 \input{annexecontinuite.tex}
 
 

-\section{Convergence du mode mixe}\label{anx:mix}
-\input{annexePreuveMixage}
+
+\section{Théorème~\ref{th:Adrien}}\label{anx:sccg}
+\input{annexesccg}
+

 
 
 
 

-\section{Correction et complétude de la vérification de convergence par SPIN}\label{anx:promela}
-\input{annexePromelaProof}

 
 \backmatter
 
 
 \backmatter
 

diff --git a/mixage.tex b/mixage.tex
index d5f1981d43478f293e5ea98fdf53ca9b1e274a02..a71a36d25735bb68daecf2a65e16e2dbe0a5d1fb 100644 (file)
--- a/mixage.tex
+++ b/mixage.tex
@@ -3,7 +3,7 @@ Pour être exécuté,
 le mode des itérations généralisées nécessite que chaque élément 
 connaisse la valeur de chaque autre élément dont il dépend.
 Pratiquement, cela se réalise en diffusant les valeurs des éléments de 
 le mode des itérations généralisées nécessite que chaque élément 
 connaisse la valeur de chaque autre élément dont il dépend.
 Pratiquement, cela se réalise en diffusant les valeurs des éléments de 

-proche en proche à tous les composants.
+proche en proche à tous les composants avant chaque itération.

 Dans le mode généralisé 
 \emph{asynchrone}, le composant n'attend pas: il met à jour sa 
 valeur avec les dernières valeurs dont il dispose, même si celles-ci 
 Dans le mode généralisé 
 \emph{asynchrone}, le composant n'attend pas: il met à jour sa 
 valeur avec les dernières valeurs dont il dispose, même si celles-ci 


@@ -54,7 +54,7 @@ souvent.
 Dans le mode asynchrone, a chaque itération $t$, chaque composant peut
 mettre à jour son état en 
 fonction des dernières valeurs qu'il connaît des autre composants.
 Dans le mode asynchrone, a chaque itération $t$, chaque composant peut
 mettre à jour son état en 
 fonction des dernières valeurs qu'il connaît des autre composants.

-Obtenir où non les valeurs les plus à jours dépend du temps de calcul et 
+Obtenir ou non les valeurs les plus à jours dépend du temps de calcul et 

 du temps d'acheminement de celles-ci. On parle de latence, de délai.
 
 Formalisons le mode les itérations asynchrone.
 du temps d'acheminement de celles-ci. On parle de latence, de délai.
 
 Formalisons le mode les itérations asynchrone.


@@ -65,7 +65,7 @@ dont chaque élément $D_{ij}^{t}$ représente la date (inférieure ou égale à
 disponible au composant $i$. 
 On considère que le délai entre l'émission par $j$ et la réception par $i$, 
 défini par $\delta_{ij}^t  = t  - D_{ij}^{t}$ est borné par une constante $\delta_0$ pour tous les $i$, $j$.
 disponible au composant $i$. 
 On considère que le délai entre l'émission par $j$ et la réception par $i$, 
 défini par $\delta_{ij}^t  = t  - D_{ij}^{t}$ est borné par une constante $\delta_0$ pour tous les $i$, $j$.

-Le \emph{mode des itérations généralisées sans attente} 
+Le \emph{mode des itérations généralisées asynchrone} 

 est défini pour chaque  $i
 \in \{1,\ldots,n\}$ et chaque  $t=0,1,2,...$ par:
 
 est défini pour chaque  $i
 \in \{1,\ldots,n\}$ et chaque  $t=0,1,2,...$ par:
 


@@ -74,7 +74,7 @@ est défini pour chaque  $i
   x^{t+1}_i= \left\{
     \begin{array}{l}
       f_i( x_1^{D_{i1}^t},\ldots, x_{n}^{D_{i{n}}^t})
   x^{t+1}_i= \left\{
     \begin{array}{l}
       f_i( x_1^{D_{i1}^t},\ldots, x_{n}^{D_{i{n}}^t})

-      \textrm{ if } \textit{bin}(s^t)[i] = 1\\ 
+      \textrm{ si } \textit{bin}(s^t)[i] = 1\\ 

       x^{t}_i  \textrm{ sinon }
     \end{array} 
   \right.
       x^{t}_i  \textrm{ sinon }
     \end{array} 
   \right.


@@ -99,20 +99,20 @@ $(D^{(t)})^{t  \in \Nats}$, alors les itérations de  $f$ sont
 \emph{universellement convergentes}.
 
 
 \emph{universellement convergentes}.
 
 

-\subsection{Exemple jouet}
-On considère cinq éléments prenant à valeurs dans $\Bool$. 
+\begin{xpl}
+On considère cinq éléments à valeurs dans $\Bool$. 

 Une configuration dans $\Bool^5$ est représentée par un entier entre 
 Une configuration dans $\Bool^5$ est représentée par un entier entre 

-0 et 31. La~\Fig{fig:mix:map} donne la fonction définissant la dynamique du 
-système. La~\Fig{fig:mix:xplgraph} donne le graphe d'interaction associé à cette fonction.
+0 et 31. 
+La~\Fig{fig:mix:map} donne la fonction définissant la dynamique du 
+système et son graphe d'interaction.

 On note que le graphe d'interaction contient cinq cycles. Les résultats 
 connus~\cite{Bah00} de conditions suffisantes établissant la convergence
 du système pour les itérations généralisées sont
 basés sur l'absence de cycles. Ils ne peuvent donc pas être appliqués ici.
 
 \begin{figure}[ht]
 On note que le graphe d'interaction contient cinq cycles. Les résultats 
 connus~\cite{Bah00} de conditions suffisantes établissant la convergence
 du système pour les itérations généralisées sont
 basés sur l'absence de cycles. Ils ne peuvent donc pas être appliqués ici.
 
 \begin{figure}[ht]

-\begin{minipage}[b]{0.55\linewidth}
-  \centering
-  $ f(x)= \left \{
+  \begin{center}
+    $$ f(x)= \left \{

     \begin{array}{lll}
       f_1(x_1,x_2,x_3,x_4,x_5) & = & x_1.\overline{x_2} + \overline{x_1}.x_2 \\
       f_2(x_1,x_2,x_3,x_4,x_5) & = & \overline{x_1 + x_2}  \\
     \begin{array}{lll}
       f_1(x_1,x_2,x_3,x_4,x_5) & = & x_1.\overline{x_2} + \overline{x_1}.x_2 \\
       f_2(x_1,x_2,x_3,x_4,x_5) & = & \overline{x_1 + x_2}  \\


@@ -120,48 +120,47 @@ basés sur l'absence de cycles. Ils ne peuvent donc pas être appliqués ici.
       f_4(x_1,x_2,x_3,x_4,x_5) & = & x_5  \\
       f_5(x_1,x_2,x_3,x_4,x_5) & = & \overline{x_3} + x_4
     \end{array}
       f_4(x_1,x_2,x_3,x_4,x_5) & = & x_5  \\
       f_5(x_1,x_2,x_3,x_4,x_5) & = & \overline{x_3} + x_4
     \end{array}

-  \right.  $
-\caption{Fonction $f$ de l'exemple jouet.}
-\label{fig:mix:map}
-\end{minipage}\hfill
-\begin{minipage}[b]{.40\linewidth}
-  \begin{center}
-    \includegraphics[scale=0.55]{xplgraphmix}
+  \right.
+  $$
+  
+  \includegraphics[scale=0.55]{xplgraphmix}

   \end{center}
   \end{center}

-  \caption{Graphe d'interaction associé à $f$.}
-  \label{fig:mix:xplgraph}
-\end{minipage}
+  \caption{Définition de $f:\Bool^5 \rightarrow \Bool^5$ et son graphe d'interaction}
+  \label{fig:mix:map}

 \end{figure}
 
 
 \begin{figure}
 \end{figure}
 
 
 \begin{figure}

-\begin{minipage}{0.56\linewidth}
-  \includegraphics[scale=0.55]{para_iterate_dec}
-  \caption{Itérations parallèles de $f$.}\label{fig:mix:xplparaFig}
-\end{minipage}
-\hfill
-\begin{minipage}{0.39\linewidth}
-  \includegraphics[scale=0.55]{chao_iterate_excerpt}
-  \caption{Extrait d'itérations chaotiques.}
-  \label{fig:mix:xplchaoFig}
-\end{minipage}
+  \begin{center}
+    \subfigure[Itérations synchrones de $f$.]{
+        \includegraphics[scale=0.50]{para_iterate_dec}
+        \label{fig:mix:xplparaFig}
+    }
+    \subfigure[Extrait des itérations unaires.]{
+        \includegraphics[scale=0.49]{chao_iterate_excerpt}
+        \label{fig:mix:xplchaoFig}
+    }
+    \end{center}
+ \caption{Graphes des itérations de $f$ définie à la figure~\ref{fig:mix:map}}

 \end{figure}
 \end{figure}

+\end{xpl}
+

 
 Dans ce qui suit, les  configurations  sont représentées à l'aide d'entiers 
 
 Dans ce qui suit, les  configurations  sont représentées à l'aide d'entiers 

-plutôt que nombres binaires. Le graphe des itérations parallèles est donné 
+plutôt que nombres binaires. Le graphe des itérations synchrones est donné 

 en~\Fig{fig:mix:xplparaFig}. Depuis n'importe quelle configuration, on constate 
 qu'il converge vers le point fixe correspondant à l'entier 19.
 en~\Fig{fig:mix:xplparaFig}. Depuis n'importe quelle configuration, on constate 
 qu'il converge vers le point fixe correspondant à l'entier 19.

-Un extrait du graphe des itérations chaotiques est donné à 
+Un extrait du graphe des itérations unaires est donné à 

 la~\Fig{fig:mix:xplchaoFig}. Les libellés des arcs correspondent aux éléments 
 la~\Fig{fig:mix:xplchaoFig}. Les libellés des arcs correspondent aux éléments 

-activés. Les itérations chaotiques ne convergent pas pour la stratégie 
+activés. Les itérations unaires ne convergent pas pour la stratégie 

 pseudo périodique donnée à l'équation~\Equ{eq:pseudo}:
 le système peut infiniment boucler entre 11 et 3, entre 15 et 7.   
 
 pseudo périodique donnée à l'équation~\Equ{eq:pseudo}:
 le système peut infiniment boucler entre 11 et 3, entre 15 et 7.   
 

-Comme les itérations chaotiques ne convergent pas pour certaines stratégies,
+Comme les itérations unaires ne convergent pas pour certaines stratégies,

 les itérations asynchrones basées sur les même stratégies peuvent ne pas 
 converger aussi. Cependant, même si l'on considère que tous les composants 
 sont activés à chaque itération, c'est à dire si $s^t$ est 
 les itérations asynchrones basées sur les même stratégies peuvent ne pas 
 converger aussi. Cependant, même si l'on considère que tous les composants 
 sont activés à chaque itération, c'est à dire si $s^t$ est 

-constamment égal à $2^n-1$, le délais peut introduire de la divergence.
+constamment égal à $2^n-1$, le délai peut introduire de la divergence.

 On considère par exemple la matrice $D^t$ dont chaque élément vaut  $t$
 sauf $D^t_{12}$  qui vaut $t-1$ si $t$  est impair. 
 On a ainsi $x^{t+1}= f(x^{t})$ si $t$ est pair et  
 On considère par exemple la matrice $D^t$ dont chaque élément vaut  $t$
 sauf $D^t_{12}$  qui vaut $t-1$ si $t$  est impair. 
 On a ainsi $x^{t+1}= f(x^{t})$ si $t$ est pair et  


@@ -206,7 +205,7 @@ Les itérations mixes d'un système discret suit l'équation \Equ{eq:async} où
 de plus   $bin(s^t)[i]=bin(s^t)[j]$ et $D_{ij}^t=D_{ji}^t=t$ si $i \eqNode j$.
 \end{Def}
 
 de plus   $bin(s^t)[i]=bin(s^t)[j]$ et $D_{ij}^t=D_{ji}^t=t$ si $i \eqNode j$.
 \end{Def}
 

-Dans ce contexte, il n'y a plus de délais entre deux noeuds de la même CFC
+Dans ce contexte, il n'y a plus de délai entre deux noeuds de la même CFC

 et leurs mises à jour sont synchronisées.
 Cependant, pour $p_0$ et $p_1$ dans la même  classe \class{p}, 
 et $q$ dans une autre classe \class{q}, ce  mode opératoire autorise
 et leurs mises à jour sont synchronisées.
 Cependant, pour $p_0$ et $p_1$ dans la même  classe \class{p}, 
 et $q$ dans une autre classe \class{q}, ce  mode opératoire autorise


@@ -224,12 +223,6 @@ Pour gommer cette distinction, on définit le mode suivant:
      \bigwedge_{p_k \in  \class{p}, q_k \in \class{q} } 
      D_{p_{k}q_{k}}^{t}  =   d_{pq}^t    
   \end{equation*}
      \bigwedge_{p_k \in  \class{p}, q_k \in \class{q} } 
      D_{p_{k}q_{k}}^{t}  =   d_{pq}^t    
   \end{equation*}

-  % Je me demande si cette formalisation n'a pas un souci par rapport à une
-  % formalisation avec un seul q ?! (car deux éléments supposent qu'ils sont distincts)
-  % car si on a deux éléments dans chaque classe, on peut alors avoir deux
-  % groupes de délais : supposons (a,b) dans p et (c,d) dans q
-  % a,c et b,d sont égaux et a,d et b,c sont égaux mais rien n'implique que a,c et
-  % a,d soient égaux !!!

 \end{Def}
 
 On a alors le théorème suivant.
 \end{Def}
 
 On a alors le théorème suivant.


@@ -252,7 +245,7 @@ La preuve de ce théorème est donnée en section~\ref{anx:mix}.
 Cette section donne des bornes supérieures et inférieures des durées 
 globales de convergence pour les modes synchrones, mixes et asynchrones.
 Pour simplifier le discours, on considère que les itérations 
 Cette section donne des bornes supérieures et inférieures des durées 
 globales de convergence pour les modes synchrones, mixes et asynchrones.
 Pour simplifier le discours, on considère que les itérations 

-convergent en in $I$ étapes dans le mode synchrone et que le graphe 
+convergent en $I$ étapes dans le mode synchrone et que le graphe 

 d'interaction ne contient qu'une seule composante connexe.
 Les durées de convergence prennent en compte les temps de calcul et les temps 
 de communication, ce depuis l'initialisation et jusqu'à la stabilisation.
 d'interaction ne contient qu'une seule composante connexe.
 Les durées de convergence prennent en compte les temps de calcul et les temps 
 de communication, ce depuis l'initialisation et jusqu'à la stabilisation.


@@ -265,11 +258,13 @@ un entier $\delta_0$ tel que $0 \le t-D_{ij}^t \le \delta_0$ est établi
 pour tout couple de n{\oe}uds $(i,j)$. 
 Les notations utilisées sont les suivantes:
 \begin{description}
 pour tout couple de n{\oe}uds $(i,j)$. 
 Les notations utilisées sont les suivantes:
 \begin{description}

-\item [Taille pour coder l'information:] elle représente le nombre de nécessaire de bits 
+\item [Taille pour coder l'information] elle représente le nombre 
+  de bits
+  nécessaires 

   pour représenter  l'état courant du composant $i$ et est notée $\textit{cs}_i$;
   pour représenter  l'état courant du composant $i$ et est notée $\textit{cs}_i$;

-\item [Temps de calcul:] le composant $i$ a besoins de  $\textit{cp}_i$ unités de temps 
+\item [Temps de calcul] le composant $i$ a besoins de  $\textit{cp}_i$ unités de temps 

   pour faire une mise à jour locale de son état;
   pour faire une mise à jour locale de son état;

-\item   [Temps de communication:] On utilise le modèle classique de communication 
+\item   [Temps de communication] on utilise le modèle classique de communication 

   $\beta+L\tau$  où $L$ est le nombre de bits  transférés. 
   On définit  $\beta_{ij}$ et  $\tau_{ij}$ comme la latence et la bande passante du lien 
   entre  $i$ et $j$.
   $\beta+L\tau$  où $L$ est le nombre de bits  transférés. 
   On définit  $\beta_{ij}$ et  $\tau_{ij}$ comme la latence et la bande passante du lien 
   entre  $i$ et $j$.


@@ -299,7 +294,7 @@ graphe d'interaction, le temps global de convergence est
   Intuitivement la convergence se propage selon les dépendances internes au système:
   un n{\oe}uds se stabilise lorsque ceux dont il dépend sont eux aussi stables.
   Cette stabilisation progressive est illustrée à la \Fig{fig:evalsync} qui
   Intuitivement la convergence se propage selon les dépendances internes au système:
   un n{\oe}uds se stabilise lorsque ceux dont il dépend sont eux aussi stables.
   Cette stabilisation progressive est illustrée à la \Fig{fig:evalsync} qui

-  représente des exécutions parallèles dans le cas d'une initialisation avec la 
+  représente des exécutions synchrones dans le cas d'une initialisation avec la 

   valeur (00100).
   Dans cette figure et les suivantes, les blocs doublement hachurés
   indiquent la stabilisation du composant.
   valeur (00100).
   Dans cette figure et les suivantes, les blocs doublement hachurés
   indiquent la stabilisation du composant.


@@ -309,7 +304,7 @@ graphe d'interaction, le temps global de convergence est
   \centering
   \begin{minipage}{1\linewidth}
     \includegraphics[scale=0.4]{eval_sync}
   \centering
   \begin{minipage}{1\linewidth}
     \includegraphics[scale=0.4]{eval_sync}

-    \caption{Itérations parallèles}
+    \caption{Itérations synchrones}

     \label{fig:evalsync}
   \end{minipage}
   
     \label{fig:evalsync}
   \end{minipage}
   


@@ -390,38 +385,14 @@ graphe d'interaction, le temps global de convergence est
 \subsection{le mode mixe}
 \label{sec:evalmixed}
 
 \subsection{le mode mixe}
 \label{sec:evalmixed}
 

-% As  detailed  in Sect.~\ref{sec:mdn},  the  mixed  case asynchronously  combines
-% subsets of synchronized components  (the different classes). The double interest
-% of  that  approach is  to  ensure  the convergence  of  the  system while  using
-% asynchronism.
-
-% The  part  of  asynchronism often  reduces  the  global  execution time  as  the
-% communications  between  subgroups are  implicitly  overlapped by  computations.
-% However, the iterative scheme is no more the same as the synchronous one and its
-% number of  iterations to reach  the convergence will  be greater or  equal.
-
-% Le nombre d'itérations requises pour obtenir la convergence en mode mixe 
-% dépend des arangements entre les délais de communication et les durées de 
-% calcul. 
-
-% number directly  depends on the arrangement  of delays during  the execution and
-% then on the communication times. But  it also depends on the evolution functions
-% which influence  the way each  part of the  system stabilizes itself.  
-% In fact,  according to its evolution  function, a component may  reach its fixed
-% point  state even  with  a part  of its  input  data not  recently updated.   In
-% addition, as  mentioned earlier, the  set of components  in any system  does not
-% stabilize at the same time and there is often a propagation of the stabilization
-% through the system.
-% Also, the  previously mentioned phenomenon of  stabilization propagation through
-% the system is still present in mixed mode.

 
 On considère $|\mathcal{K}|$  classes de composants synchronisés.
 
 On considère $|\mathcal{K}|$  classes de composants synchronisés.

-(comme donné  en équation~(\ref{eq:I}).
+(comme donné  en équation~(\ref{eq:I})).

 Soit $I_k$ le nombre d'itérations suffisants pour que la classe 
 Soit $I_k$ le nombre d'itérations suffisants pour que la classe 

-$k  \in \mathcal{K}$ se stabilise 
+$\class{k}  \in \mathcal{K}$ se stabilise 

 sachant  toutes ses dépendances ont déjà convergé. 
 sachant  toutes ses dépendances ont déjà convergé. 

-Ainsi $I$ vaut $\sum_{k \in \mathcal{K}} I_k$.
-La borne inférieur pour la durée de convergence des itérations asynchrones est 
+Ainsi $I$ vaut $\sum_{\class{k} \in \mathcal{K}} I_k$.
+La borne inférieure pour la durée de convergence des itérations asynchrones est 

 \begin{equation}
   \label{eq:mixtelow}
   T(\textit{Mixed})\ge \sum_{k\in \mathcal{K}} I_k(\max_{l\in k}\textit{cp}_{l})
 \begin{equation}
   \label{eq:mixtelow}
   T(\textit{Mixed})\ge \sum_{k\in \mathcal{K}} I_k(\max_{l\in k}\textit{cp}_{l})


@@ -446,7 +417,7 @@ ascendants pour converger. On a dans ce cas:
   Une exécution du mode mixe est donnée à la~\Fig{fig:evalmixte}.
   On peut constater que le temps d'exécution peut être  
   plus petit que pour le 
   Une exécution du mode mixe est donnée à la~\Fig{fig:evalmixte}.
   On peut constater que le temps d'exécution peut être  
   plus petit que pour le 

-  mode parallèle.
+  mode synchrone.

 \end{xpl}
 
 \subsection{Le mode généralisé asynchrone}
 \end{xpl}
 
 \subsection{Le mode généralisé asynchrone}


@@ -467,11 +438,12 @@ La borne supérieure quant à elle est donnée par:
   \label{eq:asyncup}
   T(\textit{Async})\le\sum_{i=1}^{n}\left(I_i\times \textit{cp}_{i}+\max_{1\le k \le n}B_{ki}(\beta_{ik}+\textit{cs}_{i}\tau_{ik})\right)
 \end{equation}
   \label{eq:asyncup}
   T(\textit{Async})\le\sum_{i=1}^{n}\left(I_i\times \textit{cp}_{i}+\max_{1\le k \le n}B_{ki}(\beta_{ik}+\textit{cs}_{i}\tau_{ik})\right)
 \end{equation}

-et apparaît lorsque chaque élément dépend des autres et que les calcules 
+et apparaît lorsque chaque élément dépend des autres et que les calculs 

 ne recouvrent nullement les communications.
 
 \begin{xpl}
 ne recouvrent nullement les communications.
 
 \begin{xpl}

-  La \Fig{fig:evalasync} présente un exemple d'exécution du mode asynchrone.
+  La \Fig{fig:evalasync} présente un exemple d'exécution du mode généralisé 
+  asynchrone.

   Certaines communications issues de l'élément $4$ n'ont pas été représentées
   pour des raisons de clarté.
   On constate que le temps global de convergence est plus petit que celui des
   Certaines communications issues de l'élément $4$ n'ont pas été représentées
   pour des raisons de clarté.
   On constate que le temps global de convergence est plus petit que celui des


@@ -500,6 +472,6 @@ ne recouvrent nullement les communications.
 %%% Local Variables: 
 %%% mode: latex
 %%% TeX-master: "main"
 %%% Local Variables: 
 %%% mode: latex
 %%% TeX-master: "main"

-%%% ispell-dictionary: "american"
+%%% ispell-dictionary: "french"

 %%% mode: flyspell
 %%% End: 
 %%% mode: flyspell
 %%% End: 

diff --git a/sdd.tex b/sdd.tex
index 37552951ecc85d033d2eddf4a966a7f12fcc59af..530ef34b28ed4a106d881c14f565dcb137195e05 100644 (file)
--- a/sdd.tex
+++ b/sdd.tex
@@ -119,18 +119,26 @@ schémas suivants :
 \item \textbf{Schéma parallèle  synchrone :} basé sur la  relation de récurrence
   $x^{t+1}=f(x^t)$. Tous  les $x_i$, $1 \le  i \le n$,  sont ainsi mis à  jour à
   chaque itération en utilisant l'état global précédent du système $x^t$.
 \item \textbf{Schéma parallèle  synchrone :} basé sur la  relation de récurrence
   $x^{t+1}=f(x^t)$. Tous  les $x_i$, $1 \le  i \le n$,  sont ainsi mis à  jour à
   chaque itération en utilisant l'état global précédent du système $x^t$.

-\item \textbf{Schéma  unaire :} cette terminologie  a plusieurs 
-  interprétations
-  dans  la littérature,  mais celle  que  nous
-  retenons ici  consiste à modifier la valeur 
+\item \textbf{Schéma  unaire :} ce schéma  est parfois 
+  qualifié de chaotique 
+  dans  la littérature. 
+  Il  consiste à modifier la valeur 

   d'un unique élément $i$,  $1 \le i \le  n$, à
   chaque itération. Le choix de l'élément qui est modifié à chaque itération est
   défini  par une  suite 
   $S  = \left(s^t\right)^{t \in  \mathds{N}}$ qui est  une séquence
   d'indices dans $[n]$. Cette suite est appelée \emph{stratégie unaire}. 
   d'un unique élément $i$,  $1 \le i \le  n$, à
   chaque itération. Le choix de l'élément qui est modifié à chaque itération est
   défini  par une  suite 
   $S  = \left(s^t\right)^{t \in  \mathds{N}}$ qui est  une séquence
   d'indices dans $[n]$. Cette suite est appelée \emph{stratégie unaire}. 

-%  Lorsque  cette  suite est  strictement cyclique  (sans
-  % occurrences multiples  dans le motif) sur l'ensemble  des éléments $\{1,\ldots
-  % n\}$, alors on retrouve le comportement du mode séquentiel synchrone.
+  Il est basé sur la relation définie pour tout $i \in [n]$ par
+  $$
+  x^{t+1}_i=
+  \left\{ \begin{array}{l}
+      f_i(x^t) \textrm{ si } i=s^t, \\
+      x^t_i\textrm{ sinon.}
+    \end{array}
+  \right.$$
+
+
+

 \item \textbf{Schéma généralisé:}  dans ce schéma, ce sont les valeurs  
   d'un ensemble d'éléments de $[n]$ qui sont modifiées à  chaque  itération.
   Dans  le  cas  particulier où  c'est la valeur d'un  singleton
 \item \textbf{Schéma généralisé:}  dans ce schéma, ce sont les valeurs  
   d'un ensemble d'éléments de $[n]$ qui sont modifiées à  chaque  itération.
   Dans  le  cas  particulier où  c'est la valeur d'un  singleton


@@ -146,6 +154,17 @@ schémas suivants :
   jour.  La  suite $S  = \left(s^t\right)^{t \in  \mathds{N}}$ est  une séquence
   de sous-ensembles 
   de   $[n]$   appelée   \emph{stratégie généralisée}.
   jour.  La  suite $S  = \left(s^t\right)^{t \in  \mathds{N}}$ est  une séquence
   de sous-ensembles 
   de   $[n]$   appelée   \emph{stratégie généralisée}.

+  Il est basé sur la relation définie pour tout $i \in [n]$ par
+  $$
+  x^{t+1}_i=
+  \left\{ \begin{array}{l}
+      f_i(x^t) \textrm{ si } i \in s^t, \\
+      x^t_i\textrm{ sinon.}
+    \end{array}
+  \right.$$
+
+
+

   \end{itemize}
 
 
   \end{itemize}
 
 


@@ -168,7 +187,7 @@ sont les éléments de $\Bool^n$ (voir \textsc{Figure}~\ref{fig:xpl:graphs}).
 \item Le \emph{graphe des itérations synchrones} de $f$, noté $\textsc{gis}(f)$ 
 est le graphe orienté de $\Bool^n$ qui contient un arc $x \rightarrow y$ si 
 et seulement si $y=f(x)$.
 \item Le \emph{graphe des itérations synchrones} de $f$, noté $\textsc{gis}(f)$ 
 est le graphe orienté de $\Bool^n$ qui contient un arc $x \rightarrow y$ si 
 et seulement si $y=f(x)$.

-\item Le \emph{graphe des itérations unaires} de $f$, noté $\textsc{gia}(f)$
+\item Le \emph{graphe des itérations unaires} de $f$, noté $\textsc{giu}(f)$

 est le graphe orienté de $\Bool^n$ qui contient un arc $x \rightarrow y$ si 
 et seulement s'il existe $x \in \Delta f(x)$ tel que $y = \overline{x}^i$.
 \item Le \emph{graphe des itérations généralisées} de $f$, noté $\textsc{gig}(f)$
 est le graphe orienté de $\Bool^n$ qui contient un arc $x \rightarrow y$ si 
 et seulement s'il existe $x \in \Delta f(x)$ tel que $y = \overline{x}^i$.
 \item Le \emph{graphe des itérations généralisées} de $f$, noté $\textsc{gig}(f)$


@@ -200,7 +219,7 @@ associés à $f$.
       \end{minipage}
       \label{fig:fsig}
     }
       \end{minipage}
       \label{fig:fsig}
     }

-    \subfigure[$\textsc{gia}(f)$]{
+    \subfigure[$\textsc{giu}(f)$]{

       \begin{minipage}{0.33\textwidth}
         \begin{center}
           \includegraphics[scale=0.4]{faig}
       \begin{minipage}{0.33\textwidth}
         \begin{center}
           \includegraphics[scale=0.4]{faig}


@@ -237,9 +256,6 @@ Les points fixes sont particulièrement intéressants car ils correspondent
 aux états stables:
 dans chaque graphe d'itérations, le point $x$ est un point fixe 
 si et seulement si il est son seul successeur.
 aux états stables:
 dans chaque graphe d'itérations, le point $x$ est un point fixe 
 si et seulement si il est son seul successeur.

-Dans le contexte des réseaux de régulation de gènes,
-ces points fixes correspondent aux configurations stables pour l'expression de
-gènes.

 
 
 
 
 
 


@@ -272,7 +288,7 @@ Ainsi $\Gamma$ contient toujours au moins un attracteur.
 
 
 \begin{xpl}
 
 
 \begin{xpl}

-Les attracteurs de $\textsc{gia}(f)$ et de $\textsc{gig}(f)$ sont 
+Les attracteurs de $\textsc{giu}(f)$ et de $\textsc{gig}(f)$ sont 

 le point fixe $000$ et l'attracteur cyclique 
 $\{001, 101,111, 011  \}$. 
 Les attracteurs de $\textsc{gis}(f)$ sont le point fixe $000$
 le point fixe $000$ et l'attracteur cyclique 
 $\{001, 101,111, 011  \}$. 
 Les attracteurs de $\textsc{gis}(f)$ sont le point fixe $000$


@@ -316,7 +332,7 @@ $f'_{ij}(x)=0$. Ainsi $B(f)_{ij}$ est nulle. La réciproque est aussi vraie.
 
 
 En outre, les interactions peuvent se  représenter à l'aide d'un 
 
 
 En outre, les interactions peuvent se  représenter à l'aide d'un 

-graphe $G(f)$ orienté et signé défini ainsi: 
+graphe $\Gamma(f)$ orienté et signé défini ainsi: 

 l'ensemble des sommets est 
 $[n]$ et il existe un arc de $j$ à $i$ de signe
  $s\in\{-1,1\}$, noté $(j,s,i)$, si $f_{ij}(x)=s$ pour au moins
 l'ensemble des sommets est 
 $[n]$ et il existe un arc de $j$ à $i$ de signe
  $s\in\{-1,1\}$, noté $(j,s,i)$, si $f_{ij}(x)=s$ pour au moins


@@ -400,7 +416,7 @@ La \textsc{Figure}~(\ref{fig:f:incidence}) donne la matrice d'incidence complèt
 
 \begin{figure}[ht]
   \begin{center}
 
 \begin{figure}[ht]
   \begin{center}

-     \subfigure[Matrice jacobienne de $f$.]{
+     \subfigure[Matrice jacobienne]{

        \begin{minipage}{0.90\textwidth}
          \begin{center}
         $
        \begin{minipage}{0.90\textwidth}
          \begin{center}
         $


@@ -440,8 +456,8 @@ La \textsc{Figure}~(\ref{fig:f:incidence}) donne la matrice d'incidence complèt
        \end{minipage}
        \label{fig:f:jacobienne}
      } 
        \end{minipage}
        \label{fig:f:jacobienne}
      } 

-     
-    \subfigure[Graphe d'interaction de $f$.]{
+    ~ 
+    \subfigure[Graphe d'interaction]{

       \begin{minipage}{0.45\textwidth}
       \begin{center}
         \includegraphics[scale=0.5]{gf}
       \begin{minipage}{0.45\textwidth}
       \begin{center}
         \includegraphics[scale=0.5]{gf}


@@ -450,7 +466,7 @@ La \textsc{Figure}~(\ref{fig:f:incidence}) donne la matrice d'incidence complèt
     \end{minipage}
     }
     
     \end{minipage}
     }
     

-    \subfigure[Matrice d'incidence de $f$.]{
+    \subfigure[Matrice d'incidence]{

       \begin{minipage}{0.45\textwidth}
         \begin{center}
           $
       \begin{minipage}{0.45\textwidth}
         \begin{center}
           $


@@ -468,24 +484,30 @@ La \textsc{Figure}~(\ref{fig:f:incidence}) donne la matrice d'incidence complèt
     \end{minipage}
   }
 \end{center}  
     \end{minipage}
   }
 \end{center}  

-\caption{Représentations des dépendances entre les éléments de la fonction $f$ de l'exemple illustratif.}
+\caption{Représentations des dépendances entre les éléments 
+de la fonction 
+$f:\Bool^3 \rightarrow \Bool^3$ telle que  
+$(x_1, x_2, x_3) \mapsto 
+((\overline{x_1} + \overline{x_2}).x_3,
+x_1.x_3,
+x_1 + x_2 + x_3)$}

 \end{figure}
 \end{xpl}
 
 
 
 
 \end{figure}
 \end{xpl}
 
 
 
 

-Soit $P$ une suite d'arcs de $G(f)$ de la forme
+Soit $P$ une suite d'arcs de $\Gamma(f)$ de la forme

 \[
 (i_1,s_1,i_2),(i_2,s_2,i_3),\ldots,(i_r,s_r,i_{r+1}).
 \]
 \[
 (i_1,s_1,i_2),(i_2,s_2,i_3),\ldots,(i_r,s_r,i_{r+1}).
 \]

-Alors, $P$ est dit un chemin de $G(f)$ de longueur $r$ et de signe
+Alors, $P$ est dit un chemin de $\Gamma(f)$ de longueur $r$ et de signe

 $\Pi_{i=1}^{r}s_i$ et  $i_{r+1}$ est dit accessible depuis
 $i_1$. 
 $P$ est un {\emph{circuit}} si $i_{r+1}=i_1$ et si les sommets
 $i_1$,\ldots $i_r$ sont deux à deux disjoints.
 $\Pi_{i=1}^{r}s_i$ et  $i_{r+1}$ est dit accessible depuis
 $i_1$. 
 $P$ est un {\emph{circuit}} si $i_{r+1}=i_1$ et si les sommets
 $i_1$,\ldots $i_r$ sont deux à deux disjoints.

-Un sommet $i$ de $G(f)$ a une {\emph{boucle}} 
-positive (resp. négative) , si $G(f)$ a un 
+Un sommet $i$ de $\Gamma(f)$ a une {\emph{boucle}} 
+positive (resp. négative) , si $\Gamma(f)$ a un 

 arc positif (resp. un arc négatif) de $i$ vers lui-même.
 
 
 arc positif (resp. un arc négatif) de $i$ vers lui-même.
 
 


@@ -522,9 +544,9 @@ François Robert~\cite{Rob95}
 a énoncé en 1995 le théorème suivant de convergence 
 dans le mode des itérations unaires.
 
 a énoncé en 1995 le théorème suivant de convergence 
 dans le mode des itérations unaires.
 

-\begin{theorem}\label{Th:conv:GIA}
-Si le graphe $G(f)$ n'a pas de cycle et si la stratégie unaire est
-pseudo-périodique, alors tout chemin de $\textsc{GIA}(f)$ atteint 
+\begin{theorem}\label{Th:conv:GIU}
+Si le graphe $\Gamma(f)$ n'a pas de cycle et si la stratégie unaire est
+pseudo-périodique, alors tout chemin de $\textsc{giu}(f)$ atteint 

 l'unique point fixe $\zeta$ en au plus $n$ pseudo-périodes.
 \end{theorem}
 
 l'unique point fixe $\zeta$ en au plus $n$ pseudo-périodes.
 \end{theorem}
 


@@ -536,9 +558,10 @@ dont l'union est $[n]$, cette stratégie est {pseudo-périodique}.
 J. Bahi~\cite{Bah00} a démontré le théorème suivant:
 
 \begin{theorem}\label{Th:Bahi}
 J. Bahi~\cite{Bah00} a démontré le théorème suivant:
 
 \begin{theorem}\label{Th:Bahi}

-Si le graphe $G(f)$ n'a pas de cycle et si la stratégie généralisée
+Si le graphe $\Gamma(f)$ n'a pas de cycle et si la stratégie généralisée

 est pseudo-périodique alors
 est pseudo-périodique alors

-tout chemin de $\textsc{gig}(f)$ finit par atteindre
+tout chemin de $\textsc{gig}(f)$ (et donc de $\textsc{giu}(f)$) 
+finit par atteindre

 l'unique point fixe $\zeta$. 
 \end{theorem}
 
 l'unique point fixe $\zeta$. 
 \end{theorem}