X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/251b65007a909068d3344bd82b7c5ec0ffb0a21a..148e6fe3fc164ce0c37454354e0815c398cdea62:/sdd.tex diff --git a/sdd.tex b/sdd.tex index 770d1a2..530ef34 100644 --- a/sdd.tex +++ b/sdd.tex @@ -1,235 +1,600 @@ - - \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}).