-
-
\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}).
-
-
-
-
-
-
-\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)),
\]
-et un {\emph{schéma des itérations}} qui peuvent être
-parallèles, séquentielles, chaotiques, 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{chaotique}.
-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 chaotiques 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 chaotiques 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 chaotiques}} 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 chaotiques.
-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 seront reprises dans la suite.
-
-
-
-\begin{figure}%
-\centering
-\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}
- \includegraphics[scale=0.4]{images/g.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}
-\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}%
- \begin{center}
- \includegraphics[scale=0.4]{images/h.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:iter}%
-\end{minipage}%
-\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
-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
-$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
-égaux à $0$ ou à $1$ et que le calcul est effectué dans $\Z$.
-On a le lien suivant avec la \emph{matrice d'adjacence} $A$ de $f$ dans $\Bool^{n^2}$:
-le booléen $A_{ij}$ vaut 1 si et seulement s'il existe $x\in \Bool^{n}$ tel que
-$f_{ij}(x)$ est différent de 0.
+é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
-graphe $G(f)$ orienté et signé défini ainsi:
+graphe $\Gamma(f)$ orienté et signé défini ainsi:
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$.
+
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}
+% 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}
- \includegraphics[scale=0.4]{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}
- \begin{center}
- \includegraphics[scale=0.4]{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}).
\]
-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.
-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.
-
-
-\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}).
