t

[hdrcouchot.git] / sdd.tex

diff --git a/sdd.tex b/sdd.tex
index 0bd7629f2613a94d737b0a7b52b0ca71f949cc14..530ef34b28ed4a106d881c14f565dcb137195e05 100644 (file)
--- a/sdd.tex
+++ b/sdd.tex
@@ -1,255 +1,600 @@
 
 

-
-

 \JFC{Chapeau chapitre à faire}
 
 
 
 \JFC{Chapeau chapitre à faire}
 
 
 

-Cette section énonce quelques notions suffisantes 
-à la compréhension de ce document.
-Elle commence par formaliser ce que sont les systèmes dynamiques booléens 
-(section \ref{sub:sdd}) 
-et montre comment en extraire leur graphe d'itérations (section~\ref{sub:grIter})
-et d'interactions (section~\ref{sub:sdd:inter}). 
-Elle se termine en définissant une distance sur l'espace 
-$\llbracket 1;n\rrbracket^{\Nats}\times \Bool^n$ (section~\ref{sub:metric})
-qui permet ensuite (section~\ref{sec:charac}) d'établir la chaoticité des 
-systèmes dynamiques booléens.
-
-
-
-
-
-\section{Système dynamique booléen}\label{sub:sdd}
-
-Soit $n$ un entier naturel. Un système dynamique booléen est 
+% Cette section énonce quelques notions suffisantes 
+% à la compréhension de ce document.
+% Elle commence par formaliser ce que sont les systèmes dynamiques booléens 
+% (section \ref{sub:sdd}) 
+% et montre comment en extraire leur graphe d'itérations (section~\ref{sub:grIter})
+% et d'interactions (section~\ref{sub:sdd:inter}). 
+% Elle se termine en définissant une distance sur l'espace 
+% $\llbracket 1;n\rrbracket^{\Nats}\times \Bool^n$ (section~\ref{sub:metric}).
+
+
+
+
+On considère l'espace booléen 
+$\Bool=\{0,1\}$
+muni des opérateurs binaires 
+de disjonction \og +\fg{},
+de conjonction \og . \fg{} et
+unaire de négation \og $\overline{\mathstrut\enskip}$ \fg{}.
+
+
+Soit $n$ un entier naturel.
+On introduit quelques notations à propos d'éléments de $\Bool^n$. 
+L'ensemble $\{1,\dots, n\}$ sera par la suite noté $[n]$.
+Le $i^{\textrm{ème}}$ composant d'un élément 
+$x \in \Bool^n$ s'écrit  $x_i$.
+Si l'ensemble $I$ est une partie de $[n]$, alors 
+$\overline{x}^I$ est l'élément $y\in  \Bool^n$
+tel que $y_i = 1 - x_i$ si $i\in I$ et  
+$y_i = x_i$ sinon. 
+On considère les deux abréviations $\overline{x}$ pour $\overline{x}^{[n]}$ 
+(chaque composant de $\overline{x}$ est nié:
+c'est une négation composante à composante)
+et $\overline{x}^i$ pour $\overline{x}^{\{i\}}$ pour $i \in [n]$
+(seul $x_i$ est nié dans $\overline{x}$).
+Pour tout $x$ et  $y$ dans  $\Bool^n$, l'ensemble 
+$\Delta(x, y)$,  contient les $i \in [n]$
+tels que $x_i \neq y_i$.
+Soit enfin $f : \Bool^n \rightarrow \Bool^n$. Son $i^{\textrm{ème}}$ composant
+est nommé $f_i$ qui est une fonction de $\Bool^n$ dans $\Bool$.
+Pour chaque 
+$x$ dans $\Bool^n$, l'ensemble 
+$\Delta f(x)$ est défini par $\Delta f(x) = \Delta(x,f(x))$.
+On peut admettre que $f (x) = \overline{x}^{\Delta f(x)}$ .
+
+\begin{xpl}\label{xpl:1}
+On considère $n= 3$ et $f:\Bool^3 \rightarrow \Bool^3$ telle que
+$f(x)=(f_1(x),f_2(x),f_3(x))$ avec  
+$$\begin{array}{rcl}
+f_1(x_1, x_2, x_3) &=& (\overline{x_1} + \overline{x_2}).x_3 \textrm{, }\\
+f_2(x_1, x_2, x_3) &= &x_1.x_3 \textrm{ et }\\
+f_3(x_1, x_2, x_3) &=& x_1 + x_2 + x_3.
+\end{array}
+$$
+
+\begin{table}[ht]
+$$
+\begin{array}{|l|l|l||c|c|c|}
+\hline
+\multicolumn{3}{|c||}{x} & 
+\multicolumn{3}{|c|}{f(x)} \\
+\hline
+x_1 & x_2 & x_3 & 
+f_1(x) & f_2(x) & f_3(x) \\
+\hline
+0& 0 & 0 & 0 & 0  & 0 \\
+\hline 
+0& 0 & 1 & 1 &  0 & 1\\
+\hline 
+0& 1 & 0 & 0 & 0& 1\\
+\hline 
+0& 1 & 1 & 1 & 0& 1\\
+\hline 
+1& 0 & 0 & 0 & 0& 1\\
+\hline 
+1& 0 & 1 & 1 & 1& 1\\
+\hline 
+1& 1 & 0 & 0 & 0& 1\\
+\hline 
+1& 1 & 1 & 0 & 1& 1\\
+\hline 
+\end{array}
+$$
+\caption{Images de 
+$(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)$ \label{table:xpl:images}}
+\end{table}
+
+La \textsc{Table}~\ref{table:xpl:images} donne l'image de chaque élément
+$x \in \Bool^3$.
+Pour $x=(0,1,0)$ les assertions suivantes se déduisent directement du tableau:
+\begin{itemize}
+\item $f(x)=(0,0,1)$;
+\item pour $I=\{1,3\}$, $\overline{x}^{I} = (1,1,1)$ et 
+  $\overline{x} = (1,0,1)$; 
+\item $\Delta(x,f(x)) = \{2,3\}$.
+\end{itemize}
+
+\end{xpl}
+
+\subsection{Réseau booléen}
+Soit $n$ un entier naturel représentant le nombre 
+d'éléments étudiés (gènes, protéines,\ldots).
+Un réseau booléen  est 

 défini à partir d'une fonction booléenne:
 \[
 f:\Bool^n\to\Bool^n,\qquad x=(x_1,\dots,x_n)\mapsto f(x)=(f_1(x),\dots,f_n(x)),
 \]
 défini à partir d'une fonction booléenne:
 \[
 f:\Bool^n\to\Bool^n,\qquad x=(x_1,\dots,x_n)\mapsto f(x)=(f_1(x),\dots,f_n(x)),
 \]

-et un {\emph{schéma des itérations}} qui peuvent être 
-parallèles, séquentielles ou asynchrones \ldots 
-Le schéma des itérations parallèles est défini comme suit:
-à partir d'une configuration initiale $x^0\in\Bool^n$, la suite 
-$(x^{t})^{t \in \Nats}$ 
-des configurations du système est construite à partir de 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. 
-Le  schéma qui ne modifie qu'un élément
-$i$, $1 \le i \le n$ à chaque itération 
-est le schéma \emph{asynchrone}. 
-Plus formellement, à la  $t^{\textrm{ème}}$ itération, seul le  $s_{t}^{\textrm{ème}}$ 
-composant (entre 1 et $n$) est mis à jour.
-La suite $s = \left(s_t\right)_{t \in \mathds{N}}$ est une séquence d'indices
-de $\llbracket 1;n \rrbracket$ appelée \emph{stratégie}. Formellement, dans 
-ce mode opératoire,
-soit $F_f: \llbracket1;n\rrbracket\times \Bool^{n}$ vers $\Bool^n$ définie par 
-\[
-F_f(i,x)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_n).
-\]
-
-Dans le schéma des itérations asynchrones pour une configuration initiale
-$x^0\in\Bool^n$ et une stratégie $s\in
-\llbracket1;n\rrbracket^\Nats$, les configurations $x^t$
-sont définies par la récurrence
-\begin{equation}\label{eq:asyn}
-x^{t+1}=F_f(s_t,x^t).
-\end{equation}
-
-Soit alors $G_f$ une fonction de $\llbracket1;n\rrbracket^\Nats\times\Bool^n$ 
-dans lui même définie par 
-\[
-G_f(s,x)=(\sigma(s),F_f(s_0,x)),
-\] 
-où $\forall t\in\Nats,\sigma(s)_t=s_{t+1}$.
-En d'autres termes la fonction $\sigma$ décale
-la stratégie fournie en argument d'un élément vers la gauche en supprimant 
-l'élément de tête. 
-Les itérations parallèles de $G_f$ depuis un point initial
-$X^0=(s,x^0)$ décrivent la même orbite que les  
-itérations asynchrones de $f$ induites par $x^0$ et la  stratégie
-$s$.
-
-\section{Graphe d'itérations}\label{sub:grIter}
-
-Soit $f$ une fonction de $\Bool^n$ dans lui-même. 
-Le {\emph{graphe des itérations asynchrones}} associé à $f$ est le 
-graphe orienté $\Gamma(f)$ défini ainsi: 
-l'ensemble de ses sommets est $\Bool^n$ et pour chaque $x\in\Bool^n$ et  
-$i\in \llbracket1;n\rrbracket$, le graphe $\Gamma(f)$ 
-contient un arc de $x$ vers $F_f(i,x)$. 
-La relation entre $\Gamma(f)$ et $G_f$ est claire: il  existe un 
-chemin  de $x$ à  $x'$ dans $\Gamma(f)$ si et seulement s'il existe une 
-stratégie  $s$ telle que les itérations  parallèles $G_f$ à partir 
-du point $(s,x)$ mènent au point $x'$.
-
-
-Dans ce qui suit, et par souci de concision, le terme \emph{graphe des itérations}
-est une abréviation de  graphe des itérations asynchrones.
-La figure~\ref{fig:xplgraphIter} donne deux exemples de graphes d'itérations 
-pour les fonctions $g$ et $h$ définies dans $\Bool^2$ qui sont reprises tout au long 
-de ce document. 
-
-
-
-\begin{figure}%
-\centering
-\begin{minipage}{0.40\textwidth}
-  \begin{center}
-    \includegraphics[height=4cm]{images/g.pdf}
-  \end{center}
-\caption{$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $}%
-\label{fig:g:iter}%
-\end{minipage}
-\qquad
-\begin{minipage}{0.40\textwidth}%
+et un  {\emph{schéma itératif}} ou  encore \emph{mode de  mise à jour}. À  partir d'une configuration initiale $x^0\in\Bool^n$,  la suite $(x^{t})^{t
+  \in  \Nats}$ des  configurations  du  système est  construite  selon l'un  des
+schémas suivants :
+\begin{itemize}
+\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 :} 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}. 
+  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
+  $\{k\}$, $1 \le k  \le n$, qui est modifiée à
+  chaque  itération, on retrouve le
+  mode unaire. Dans le second cas particulier où ce sont les valeurs de 
+  tous les éléments de $\{1, \ldots,  n\}$ qui sont  modifiées
+  à chaque  itération, on retrouve  le mode
+  parallèle.  Ce mode généralise donc les deux modes précédents.  
+  Plus formellement,  à  la  $t^{\textrm{ème}}$
+  itération, seuls les éléments de la partie 
+  $s^{t} \in \mathcal{P}([n])$ sont mis à
+  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}
+
+
+ 
+ 
+
+La section suivante détaille comment représenter graphiquement les évolutions de tels réseaux.
+\subsection{Graphes des itérations}
+
+
+
+Pour un entier naturel $n$ et une 
+fonction $f : B^n \rightarrow B^n$, plusieurs évolutions sont possibles
+en fonction du schéma itératif retenu. 
+Celles-ci sont représentées par un graphe orienté dont les noeuds 
+sont les éléments de $\Bool^n$ (voir \textsc{Figure}~\ref{fig:xpl:graphs}).
+
+
+\begin{itemize}
+\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{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 un ensemble $I\subseteq \Delta f(x)$ tel que 
+$y = \overline{x}^I$. On peut remarquer que ce graphe contient comme 
+sous-graphe à la fois celui des itérations synchrones et celui 
+des itérations unaires.
+
+
+\end{itemize}
+
+
+
+\begin{xpl}
+On reprend notre exemple illustratif
+détaillé à la page~\pageref{xpl:1} avec sa table
+d'images (\textsc{Table}~\ref{table:xpl:images}).
+La \textsc{Figure}~\ref{fig:xpl:graphs} donne les trois graphes d'itérations 
+associés à $f$.
+
+\begin{figure}[ht]

   \begin{center}
   \begin{center}

-    \includegraphics[height=4cm]{images/h.pdf}
+    \subfigure[$\textsc{gis}(f)$]{
+      \begin{minipage}{0.33\textwidth}
+        \begin{center}
+          \includegraphics[scale=0.4]{fsig}
+        \end{center}
+      \end{minipage}
+      \label{fig:fsig}
+    }
+    \subfigure[$\textsc{giu}(f)$]{
+      \begin{minipage}{0.33\textwidth}
+        \begin{center}
+          \includegraphics[scale=0.4]{faig}
+        \end{center}
+      \end{minipage}
+      \label{fig:faig}
+    }   
+    \subfigure[$\textsc{gig}(f)$]{
+      \begin{minipage}{0.33\textwidth}
+        \begin{center}
+          \includegraphics[scale=0.4]{fgig}
+        \end{center}
+      \end{minipage}
+      \label{fig:fgig}
+    }

   \end{center}
   \end{center}

-\caption{$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$}%
-\label{fig:h:iter}%
-\end{minipage}%
-\end{figure}%
-
-% \begin{figure}%[t]
-%   \begin{center}
-%     \subfloat[$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $]{
-%       \begin{minipage}{0.40\textwidth}
-%         \begin{center}
-%           \includegraphics[height=4cm]{images/g.pdf}
-%         \end{center}
-%       \end{minipage}
-%       \label{fig:g:iter}
-%     }
-%     \subfloat[$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$]{
-%       \begin{minipage}{0.40\textwidth}
-%         \begin{center}
-%           \includegraphics[height=4cm]{images/h.pdf}
-%         \end{center}
-%       \end{minipage}
-%       \label{fig:h:iter}
-%     }    \end{center}
-%     \caption{Graphes d'itérations de fonctions booléennes dans $\Bool^2$}
-%     \label{fig:xplgraphIter}
-%   \end{figure}
-
-
-
-
-
-
-
-\section{Graphe d'interactions}\label{sub:sdd:inter}
-
-Pour $x\in\Bool^n$ et $i\in\llbracket 1;n\rrbracket$, on nomme  
-$\overline{x}^i$ la configuration obtenue en niant le 
-$i^{\textrm{ème}}$ composant de $x$. En d'autres termes
-$\overline{x}^i=(x_1,\dots,\overline{x_i},\dots,x_n)$.
-Des interactions entre les composants du 
+  \caption{Graphes des itérations 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)$.\label{fig:xpl:graphs}
+On remarque le cycle $((101,111),(111,011),(011,101))$ 
+ à la \textsc{Figure}~(\ref{fig:fsig}).}
+\end{figure}
+\end{xpl} 
+
+
+\subsection{Attracteurs}
+
+On dit que le point 
+$x \in \Bool^n$ est un \emph{point fixe} de $f$ si  $x = f (x)$.
+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.
+
+
+
+Soit $\Gamma$ un graphe d'itérations (synchrones, unaires ou généralisées)
+de $f$. 
+Les \emph{attracteurs}  de $\Gamma$ sont les 
+plus petits sous-ensembles (au sens de l'inclusion) non vides
+$A \subseteq \Bool^n$ tels que pour tout arc
+$x \rightarrow y$ de $\Gamma$, si $x$ est un élément de $A$, alors 
+$y$ aussi.
+Un attracteur qui contient au moins deux éléments  est dit \emph{cyclique}.
+On en déduit qu'un attracteur cyclique ne contient pas de point fixe.
+En d'autres termes, lorsqu'un système entre dans un attracteur cyclique, 
+il ne peut pas atteindre un point fixe.
+
+
+On a la proposition suivante:
+
+
+\begin{theorem}\label{Prop:attracteur}
+Le point $x$ est un point fixe si et seulement si 
+$\{x\}$ est un attracteur de $\Gamma$.
+En d'autres termes, les attracteurs non cycliques de $\Gamma$ 
+sont les points fixes de $f$.
+Ainsi pour chaque $x\in \Bool^n$, il existe au moins un chemin 
+depuis $x$ qui atteint un attracteur.
+Ainsi $\Gamma$ contient toujours au moins un attracteur.
+\end{theorem}
+
+
+
+\begin{xpl}
+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$
+et l'attracteur cyclique $\{011, 101, 111\}$.
+\end{xpl}
+
+\subsection{Graphe d'interaction}
+Les interactions entre les composants du 

 système peuvent être mémorisées 
 système peuvent être mémorisées 

-dans la {\emph{matrice Jacobienne discrète}} $f'$.
+dans la {\emph{matrice jacobienne discrète}} $f'$.

 Celle-ci est définie comme étant la fonction  qui  à chaque 
 configuration $x\in\Bool^n$ associe la matrice de taille 
 Celle-ci est définie comme étant la fonction  qui  à chaque 
 configuration $x\in\Bool^n$ associe la matrice de taille 

-$n\times n$ 
-\[
-f'(x)=(f_{ij}(x)),\qquad 
-f_{ij}(x)=\frac{f_i(\overline{x}^j)-f_i(x)}{\overline{x}^j_j-x_j}\qquad (i,j\in\llbracket1;n\rrbracket).
-\]
-On note que dans l'équation donnant la valeur de $f_{ij}(x)$, 
+$n\times n$ telle que 
+\begin{equation}
+f'(x)=(f'_{ij}(x)),\qquad 
+f'_{ij}(x)=\frac{f_i(\overline{x}^j){-}f_i(x)}{\overline{x_j}{-}x_j}\qquad (i,j\in[n]).
+\label{eq:jacobienne}
+\end{equation}
+On note que dans l'équation donnant la valeur de $f'_{ij}(x)$, 

 les termes $f_i(\overline{x}^j)$, $f_i(x)$, 
 $\overline{x}^j_j$ et $x_j$ sont considérés comme des entiers naturels 
 les termes $f_i(\overline{x}^j)$, $f_i(x)$, 
 $\overline{x}^j_j$ et $x_j$ sont considérés comme des entiers naturels 

-égaux à $0$ ou à $1$ et que le calcul est effectué dans $\Z$.
+égaux à $0$ ou à $1$ et que la différence est effectuée
+ dans $\Z$.
+Lorsqu'on supprime les signes dans la matrice jacobienne discrète, 
+on obtient une matrice notée $B(f)$ aussi de taille 
+$n\times n$.
+Celle-ci mémorise uniquement 
+l'existence d'une dépendance de tel élément vis à vis de 
+ tel élément.
+Elle ne mémorise pas \emph{comment} dépendent les éléments 
+les uns par rapport aux autres. Cette matrice est nommée 
+\emph{matrice d'incidence}.  
+
+\begin{theorem}
+Si $f_i$ ne dépend pas de $x_j$, alors pour tout $x\in [n]$, 
+$f_i(\overline{x}^j)$ est égal à  $f_i(x)$, \textit{i.e}, 
+$f'_{ij}(x)=0$. Ainsi $B(f)_{ij}$ est nulle. La réciproque est aussi vraie.
+\end{theorem} 
+
+
+

 
 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 
 l'ensemble des sommets est 

-$\llbracket1;n\rrbracket$ et il existe un arc de $j$ à $i$ de signe
+$[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
 un $x\in\Bool^n$. 
  $s\in\{-1,1\}$, noté $(j,s,i)$, si $f_{ij}(x)=s$ pour au moins
 un $x\in\Bool^n$. 

+

 On note que la présence de 
 deux arcs de signes opposés entre deux sommets donnés 
 est possible.
 On note que la présence de 
 deux arcs de signes opposés entre deux sommets donnés 
 est possible.

-
-
-
-
-
-\begin{figure}%
-\centering
-\begin{minipage}{0.40\textwidth}
-  \begin{center}
-    \includegraphics[height=3cm]{images/gp.pdf}
-  \end{center}
-\caption{$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $}%
-\label{fig:g:inter}%
-\end{minipage}
-\qquad
-\begin{minipage}{0.40\textwidth}
+% Dans la suite, le graphe signé $G$ sera qualifié de 
+% \emph{simple} si, pour chaque  $i$, $j$ dans $[n]$,
+% il existe au plus un arc de $j$ à $i$ dans $G$.
+Un cycle \emph{positif} (resp. négatif) de $G$
+est un cycle \emph{élémentaire} qui contient un nombre 
+pair (resp. impair) d'arcs négatifs. 
+La \emph{longueur}
+d'un cycle est le nombre d'arcs qu'il contient.
+
+\begin{xpl}
+Pour exprimer la jacobienne discrète de la fonction donnée en exemple,
+pour chaque $i$, $j$ dans
+$[3]$ on exprime 
+$f'_{ij}(x)=
+\frac
+{f_i(\overline{x}^j){-}f_i(x)}
+{\overline{x_j}{-}x_j}$
+d'après l'équation~(\ref{eq:jacobienne}).
+% Ainsi 
+% $$
+% f'_{12} (x_1,x_2,x_3)=  
+% \frac
+% { ((\overline{x_1} + \overline{\overline{x_2}}).x_3)
+% {-}  
+% ((\overline{x_1} + \overline{x_2}).x_3) 
+% }
+% {\overline{x_2}{-}x_2} =  \frac{   
+% ((\overline{x_1} + x_2).x_3)
+% {-}  
+% ((\overline{x_1} + \overline{x_2}).x_3) 
+% }{\overline{x_2}{-}x_2} .
+% $$
+% Évaluons cette fonction de $\Bool^3$ dans $\Z$ en construisant le tableau de toutes ses valeurs.
+% $$
+% \begin{array}{|c|c|c|c|c|c|c|c|}
+% \hline
+% x_1 &   x_2 &  x_3 &  
+% (\overline{x_1} + {x_2}).x_3 & (\overline{x_1} + \overline{x_2}).x_3 &   
+% (\overline{x_1} + {x_2}).x_3 {-} (\overline{x_1} + \overline{x_2}).x_3 & \overline{x_2} {-} x_2  &  
+% f'_{12} (x_1,x_2,x_3)\\
+% \hline
+% 0   &  0    &  0   &  0  & 0 & 0 & 1   & 0 \\\hline
+% 0   &  0    &  1   &  1  & 1 & 0 & 1   & 0 \\\hline
+% 0   &  1    &  0   &  0  & 0 & 0 & -1  & 0 \\\hline
+% 0   &  1    &  1   &  1  & 1 & 0 & -1  & 0 \\\hline
+% 1   &  0    &  0   &  0  & 0 & 0 & 1   & 0 \\\hline
+% 1   &  0    &  1   &  0  & 1 & -1 & 1   & -1 \\\hline
+% 1   &  1    &  0   &  0  & 0 & 0 & -1  & 0 \\\hline
+% 1   &  1    &  1   &  1  & 0 & 1& -1  & -1 \\\hline
+% \end{array}
+% $$
+% La seule valeur de $f'_{12}$ qui n'est pas nulle est -1, qui est négative.
+% Le graphe d'interaction contiendra ainsi un arc négatif entre le n{\oe}ud 2 et le n{\oe}ud 1.
+La \textsc{Figure}~(\ref{fig:f:jacobienne}) explicite la matrice jacobienne discrète de cette fonction.
+
+Le graphe d'interaction de $f$ s'en déduit directement. Il est donné à la 
+\textsc{Figure}~(\ref{fig:f:interaction}). 
+Il possède 
+un cycle négatif de longueur 1 et 
+un cycle négatif de longueur 3. 
+Concernant les cycles positifs, il en possède 
+un de longueur 1, 
+deux de longueur 2 
+et un de longueur 3.
+
+La matrice d'incidence peut se déduire de la matrice d'interaction en supprimant les signes ou bien 
+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)$ 
+est égale à $1~1~1$. De manière similaire,  $f_2$ (resp. $f_3$) dépend  de 
+$x_1$ et  de $x_3$ 
+(resp. dépend de $x_1$, $x_2$ et $x_3$).
+Ainsi la seconde ligne (resp. la troisième ligne) de $B(f)$ est $1~0~1$ (resp. est $1~1~1$). 
+La \textsc{Figure}~(\ref{fig:f:incidence}) donne la matrice d'incidence complète. 
+
+\begin{figure}[ht]

   \begin{center}
   \begin{center}

-    \includegraphics[height=3cm]{images/hp.pdf}
-  \end{center}
-\caption{$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$}%
-\label{fig:h:inter}%
-\end{minipage}%
-\caption{Graphes d'interactions de fonctions booléennes dans $\Bool^2$}
-\label{fig:xplgraphInter}
-\end{figure}%
-
-
-
-
-
-
-
-
-
-Soit $P$ une suite d'arcs de $G(f)$ de la forme
+     \subfigure[Matrice jacobienne]{
+       \begin{minipage}{0.90\textwidth}
+         \begin{center}
+        $
+        \left(
+          \begin{array}{ccc}
+            \frac{   
+              ((x_1 + \overline{x_2}).x_3)
+              {-}  
+              ((\overline{x_1} + \overline{x_2}).x_3) 
+            }{\overline{x_1}{-}x_1}
+            &
+            \frac{   
+              ((\overline{x_1} + x_2).x_3)
+              {-}  
+              ((\overline{x_1} + \overline{x_2}).x_3) 
+            }{\overline{x_2}{-}x_2}
+            &
+            \frac{   
+              ((\overline{x_1} + \overline{x_2}).\overline{x_3})
+              {-}  
+              ((\overline{x_1} + \overline{x_2}).x_3) 
+            }{\overline{x_3}{-}x_3} 
+\\
+\\
+            \frac{\overline{x_1}.x_3 {-} x_1.x_3}{\overline{x_1}{-}x_1}
+             & 0 & 
+\frac{{x_1}.\overline{x_3} {-} x_1.x_3}{\overline{x_3}{-}x_3}
+ \\
+\\
+            \frac{(\overline{x_1}+x_2+x_3){-}(x_1+x_2+x_3)}{\overline{x_1}{-}{x_1}} &
+            \frac{(x_1+\overline{x_2}+x_3){-}(x_1+x_2+x_3)}{\overline{x_2}{-}{x_2}} &
+            \frac{(x_1+x_2+\overline{x_3}){-}(x_1+x_2+x_3)}{\overline{x_3}{-}{x_3}} 
+          \end{array}
+        \right)
+        $
+         \end{center}
+       \end{minipage}
+       \label{fig:f:jacobienne}
+     } 
+    ~ 
+    \subfigure[Graphe d'interaction]{
+      \begin{minipage}{0.45\textwidth}
+      \begin{center}
+        \includegraphics[scale=0.5]{gf}
+      \end{center}
+      \label{fig:f:interaction}
+    \end{minipage}
+    }
+    
+    \subfigure[Matrice d'incidence]{
+      \begin{minipage}{0.45\textwidth}
+        \begin{center}
+          $
+          B(f) =
+          \left(
+            \begin{array}{ccc}
+              1 & 1 & 1 \\
+              1 & 0 & 1 \\
+              1 & 1 & 1 
+            \end{array}
+          \right)
+          $
+        \end{center}
+        \label{fig:f:incidence}
+    \end{minipage}
+  }
+\end{center}  
+\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}
+
+
+
+
+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.
 
 
 

-
-
-\section{Distance sur l'espace $\llbracket 1;n\rrbracket^{\Nats}\times \Bool^n$}\label{sub:metric}
-On considère l'espace $\mathcal{X}=\llbracket 1;n\rrbracket^{\Nats}\times
-\Bool^n$ et
-on définit la distance $d$ entre les points $X=(s,x)$ et
-$X'=(s',x')$ de $\mathcal{X}$ par 
-\[
-d(X,X')= d_H(x,x')+d_S(s,s'),~\textrm{où}~
-\left\{
-\begin{array}{l}
-\displaystyle{d_H(x,x')=\sum_{i=1}^n |x_i-x'_i|}\\[5mm] 
-\displaystyle{d_S(s,s')=\frac{9}{n}\sum_{t\in\Nats}\frac{|s_t-s'_t|}{10^{t+1}}}.
-\end{array}
-\right.\,.
-\]
-On note que dans le calcul de $d_H(x,x')$-- 
-appelée \gls{distanceHamming} (cf. glossaire) entre $x$ et $x'$-- 
-les termes $x_i$ et $x'_i$ sont considérés comme des entiers naturels 
-égaux à $0$ ou à $1$ et que le calcul est effectué dans $\Z$.
-De plus, la \gls{partieentiere} (cf. glossaire) 
-$\lfloor d(X,X')\rfloor$ est égale à $d_H(x,x')$ soit la distance 
-de Hamming entre $x$ et $x'$. 
-%D'autre part, $d(X,X')-\lfloor d(X,X')\rfloor=d_S(s,s')$ 
-%mesure la différence entre $s$ et $s'$.
-On remarque que la partie décimale est inférieure à $10^{-l}$ si
-et seulement si les $l$ premiers termes des deux stratégies sont égaux. 
-De plus, si la 
-$(l+1)^{\textrm{ème}}$ décimale  
-de $d_S(s,s')$ 
-n'est pas nulle, alors $s_l$ est différent de  $s'_l$. 
-
-On peut démontrer que pour toute fonction booléenne $f$, 
-$G_f$ est continue sur $\mathcal{X}$ (cf annexe~\ref{anx:cont}).   
+\subsection{Conditions de convergence}\label{sec:Robert:async}
+
+Parmi les itérations unaires caractérisées par leurs stratégies
+$S=(s^t)^{t \in \Nats}$ d'éléments appartenant à $[n]$,
+sont jugées intéressantes 
+celles qui activent au moins une fois
+chacun des $i\in[n]$. Dans le cas contraire, un élément n'est jamais modifié. 
+
+Plus formellement, une séquence finie $S=(s^t)^{t \in \Nats}$
+est dite \emph{complète} relativement à $[n]$ si 
+tout indice de $[n]$
+s'y retrouve au moins une fois.
+
+Parmi toutes les stratégies unaires de 
+$[n]^{\Nats}$, on qualifie de:
+\begin{itemize}
+\item \emph{périodiques} celles 
+qui sont constituées par une répétition indéfinie 
+d'une même séquence $S$ complète relativement à $[n]$.
+En particulier toute séquence périodique est complète.
+\item \emph{pseudo-périodiques} celles 
+qui sont constituées par une succession indéfinie de séquences 
+(de longueur éventuellement variable non supposée bornée) complètes.
+Autrement dit dans chaque stratégie pseudo-périodique, chaque indice de
+$1$ à $n$ revient indéfiniment.
+\end{itemize}
+
+
+François Robert~\cite{Rob95}
+a énoncé en 1995 le théorème suivant de convergence 
+dans le mode des itérations unaires.
+
+\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}
+
+Le qualificatif \emph{pseudo-périodique} peut aisément 
+s'étendre aux stratégies généralisées comme suit.
+Lorsqu'une stratégie généralisée est constituée d'une 
+succession indéfinie de séquences de parties de $[n]$ 
+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}
+Si le graphe $\Gamma(f)$ n'a pas de cycle et si la stratégie généralisée
+est pseudo-périodique alors
+tout chemin de $\textsc{gig}(f)$ (et donc de $\textsc{giu}(f)$) 
+finit par atteindre
+l'unique point fixe $\zeta$. 
+\end{theorem}
+
+% \section{Distance sur l'espace $\llbracket 1;n\rrbracket^{\Nats}\times \Bool^n$}\label{sub:metric}
+% On considère l'espace $\mathcal{X}=\llbracket 1;n\rrbracket^{\Nats}\times
+% \Bool^n$ et
+% on définit la distance $d$ entre les points $X=(s,x)$ et
+% $X'=(s',x')$ de $\mathcal{X}$ par 
+% \[
+% d(X,X')= d_H(x,x')+d_S(s,s'),~\textrm{où}~
+% \left\{
+% \begin{array}{l}
+% \displaystyle{d_H(x,x')=\sum_{i=1}^n |x_i-x'_i|}\\[5mm] 
+% \displaystyle{d_S(s,s')=\frac{9}{n}\sum_{t\in\Nats}\frac{|s_t-s'_t|}{10^{t+1}}}.
+% \end{array}
+% \right.\,.
+% \]
+% On note que dans le calcul de $d_H(x,x')$-- 
+% appelée \gls{distanceHamming} (cf. glossaire) entre $x$ et $x'$-- 
+% les termes $x_i$ et $x'_i$ sont considérés comme des entiers naturels 
+% égaux à $0$ ou à $1$ et que le calcul est effectué dans $\Z$.
+% De plus, la \gls{partieentiere} (cf. glossaire) 
+% $\lfloor d(X,X')\rfloor$ est égale à $d_H(x,x')$ soit la distance 
+% de Hamming entre $x$ et $x'$. 
+% %D'autre part, $d(X,X')-\lfloor d(X,X')\rfloor=d_S(s,s')$ 
+% %mesure la différence entre $s$ et $s'$.
+% On remarque que la partie décimale est inférieure à $10^{-l}$ si
+% et seulement si les $l$ premiers termes des deux stratégies sont égaux. 
+% De plus, si la 
+% $(l+1)^{\textrm{ème}}$ décimale  
+% de $d_S(s,s')$ 
+% n'est pas nulle, alors $s_l$ est différent de  $s'_l$. 
+
+% On a  démontré que pour toute fonction booléenne $f$, 
+% $G_f$ est continue sur $\mathcal{X}$ (cf annexe~\ref{anx:cont}).