X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/1b923f193392e3ce847882c24a128eff4bee9992..f0130c1c75d237435f0071124c85e58df03b6fe9:/sdd.tex?ds=sidebyside

diff --git a/sdd.tex b/sdd.tex
index 0bd7629..355e33c 100644
--- a/sdd.tex
+++ b/sdd.tex
@@ -1,255 +1,608 @@
 
+\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}).
+
+
+
+
+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 ${\mathsf{N}}$ un entier naturel.
+On introduit quelques notations Ã  propos d'Ã©lÃ©ments de $\Bool^{\mathsf{N}}$. 
+L'ensemble $\{1,\dots, {\mathsf{N}}\}$ sera par la suite notÃ© $[{\mathsf{N}}]$.
+Le $i^{\textrm{Ã¨me}}$ composant d'un Ã©lÃ©ment 
+$x \in \Bool^{\mathsf{N}}$ s'Ã©crit  $x_i$.
+Si l'ensemble $I$ est une partie de $[{\mathsf{N}}]$, alors 
+$\overline{x}^I$ est l'Ã©lÃ©ment $y\in  \Bool^{\mathsf{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}^{[{\mathsf{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 [{\mathsf{N}}]$
+(seul $x_i$ est niÃ© dans $\overline{x}$).
+Pour tout $x$ et  $y$ dans  $\Bool^{\mathsf{N}}$, l'ensemble 
+$\Delta(x, y)$,  contient les $i \in [{\mathsf{N}}]$
+tels que $x_i \neq y_i$.
+Soit enfin $f : \Bool^n \rightarrow \Bool^{\mathsf{N}}$. Son $i^{\textrm{Ã¨me}}$ composant
+est nommÃ© $f_i$ qui est une fonction de $\Bool^{\mathsf{N}}$ dans $\Bool$.
+Pour chaque 
+$x$ dans $\Bool^{\mathsf{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 ${\mathsf{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^{\mathsf{N}}\to\Bool^{\mathsf{N}},\qquad x=(x_1,\dots,x_{\mathsf{N}})\mapsto f(x)=(f_1(x),\dots,f_{\mathsf{N}}(x)),
+\]
+et un  {\emph{schÃ©ma itÃ©ratif}} ou  encore \emph{mode de  mise Ã  jour}. Ã  partir d'une configuration initiale $x^0\in\Bool^{\mathsf{N}}$,  la suite $(x^{t})^{t
+  \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 {\mathsf{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  {\mathsf{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 $[{\mathsf{N}}]$. Cette suite est appelÃ©e \emph{stratÃ©gie unaire}. 
+  Il est basÃ© sur la relation dÃ©finie pour tout $i \in [{\mathsf{N}}]$ par
+  
+\begin{equation}
+  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.
+\label{eq:schema:unaire}
+\end{equation}
 
 
-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.
 
+\item \textbf{SchÃ©ma gÃ©nÃ©ralisÃ©:}  dans ce schÃ©ma, ce sont les valeurs  
+  d'un ensemble d'Ã©lÃ©ments de $[{\mathsf{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 {\mathsf{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,  {\mathsf{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}([{\mathsf{N}}])$ sont mis Ã 
+  jour.  La  suite $S  = \left(s^t\right)^{t \in  \mathds{N}}$ est  une sÃ©quence
+  de sous-ensembles 
+  de   $[{\mathsf{N}}]$   appelÃ©e   \emph{stratÃ©gie gÃ©nÃ©ralisÃ©e}.
+  Il est basÃ© sur la relation dÃ©finie pour tout $i \in [{\mathsf{N}}]$ par
+  \begin{equation}
+  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.
+\label{eq:schema:generalise}
+\end{equation}
 
 
 
 
-\section{SystÃ¨me dynamique boolÃ©en}\label{sub:sdd}
+  \end{itemize}
 
-Soit $n$ un entier naturel. Un systÃ¨me dynamique 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 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}%
-  \begin{center}
-    \includegraphics[height=4cm]{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}%
-\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 
-systÃ¨me peuvent Ãªtre mÃ©morisÃ©es 
-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)$, 
-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$.
+La section suivante dÃ©taille comment reprÃ©senter graphiquement les Ã©volutions de tels rÃ©seaux.
+\subsection{Graphes des itÃ©rations}
 
-En outre, les interactions peuvent se  reprÃ©senter Ã  l'aide d'un 
-graphe $G(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
- $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.
 
 
+Pour un entier naturel ${\mathsf{N}}$ et une 
+fonction $f : B^{\mathsf{N}} \rightarrow B^{\mathsf{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^{\mathsf{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^{\mathsf{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^{\mathsf{N}}$ qui contient un arc $x \rightarrow y$ pour $x \neq$ si 
+et seulement s'il existe $i \in \Delta f(x)$ tel que $y = \overline{x}^i$.
+Si $\Delta f(x)$ est vide, on ajoute l'arc $x \rightarrow x$.
 
-\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}
-  \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}%
+\item Le \emph{graphe des itÃ©rations gÃ©nÃ©ralisÃ©es} de $f$, notÃ© $\textsc{gig}(f)$
+est le graphe orientÃ© de $\Bool^{\mathsf{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}
+    \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{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^{\mathsf{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 un graphe d'itÃ©rations (synchrones, unaires ou gÃ©nÃ©ralisÃ©es)
+de $f$. 
+Les \emph{attracteurs}  de ce graphe sont les 
+plus petits sous-ensembles (au sens de l'inclusion) non vides
+$A \subseteq \Bool^{\mathsf{N}}$ tels que pour tout arc
+$x \rightarrow y$, 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 du graphe d'itÃ©ration (synchrone, unaire, gÃ©nÃ©ralisÃ©).
+En d'autres termes, les attracteurs non cycliques de celui-ci 
+sont les points fixes de $f$.
+Ainsi pour chaque $x\in \Bool^{\mathsf{N}}$, il existe au moins un chemin 
+depuis $x$ qui atteint un attracteur.
+Ainsi tout graphe d'itÃ©rations 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'$.
+Celle-ci est dÃ©finie comme Ã©tant la fonction  qui  Ã  chaque 
+configuration $x\in\Bool^{\mathsf{N}}$ associe la matrice de taille 
+$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 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 
+${\mathsf{N}}\times {\mathsf{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 [{\mathsf{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 $\Gamma(f)$ orientÃ© et signÃ© dÃ©fini ainsi: 
+l'ensemble des sommet %s est 
+$[{\mathsf{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^{\mathsf{N}}$. 
 
-Soit $P$ une suite d'arcs de $G(f)$ de la forme
+On note que la prÃ©sence de 
+deux arcs de signes opposÃ©s entre deux sommets donnÃ©s 
+est possible.
+% 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}
+     \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 Ã  $[{\mathsf{N}}]$,
+sont jugÃ©es intÃ©ressantes 
+celles qui activent au moins une fois
+chacun des $i\in[{\mathsf{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 Ã  $[{\mathsf{N}}]$ si 
+tout indice de $[{\mathsf{N}}]$
+s'y retrouve au moins une fois.
+
+Parmi toutes les stratÃ©gies unaires de 
+$[{\mathsf{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 Ã  $[{\mathsf{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$ Ã  ${\mathsf{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 ${\mathsf{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 $[{\mathsf{N}}]$ 
+dont l'union est $[{\mathsf{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}).   
 
