\item \textbf{Schéma parallèle synchrone :} basé sur la relation de récurrence
$x^{t+1}=f(x^t)$. Tous les $x_i$, $1 \le i \le n$, sont ainsi mis à jour à
chaque itération en utilisant l'état global précédent du système $x^t$.
-\item \textbf{Schéma unaire :} cette terminologie a plusieurs
- interprétations
- dans la littérature, mais celle que nous
- retenons ici consiste à modifier la valeur
+\item \textbf{Schéma unaire :} ce schéma est parfois
+ qualifié de chaotique
+ dans la littérature.
+ Il consiste à modifier la valeur
d'un unique élément $i$, $1 \le i \le n$, à
chaque itération. Le choix de l'élément qui est modifié à chaque itération est
défini par une suite
$S = \left(s^t\right)^{t \in \mathds{N}}$ qui est une séquence
d'indices dans $[n]$. Cette suite est appelée \emph{stratégie unaire}.
-% Lorsque cette suite est strictement cyclique (sans
- % occurrences multiples dans le motif) sur l'ensemble des éléments $\{1,\ldots
- % n\}$, alors on retrouve le comportement du mode séquentiel synchrone.
+ Il est basé sur la relation définie pour tout $i \in [n]$ par
+ $$
+ x^{t+1}_i=
+ \left\{ \begin{array}{l}
+ f_i(x^t) \textrm{ si } i=s^t, \\
+ x^t_i\textrm{ sinon.}
+ \end{array}
+ \right.$$
+
+
+
\item \textbf{Schéma généralisé:} dans ce schéma, ce sont les valeurs
d'un ensemble d'éléments de $[n]$ qui sont modifiées à chaque itération.
Dans le cas particulier où c'est la valeur d'un singleton
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}
\item Le \emph{graphe des itérations synchrones} de $f$, noté $\textsc{gis}(f)$
est le graphe orienté de $\Bool^n$ qui contient un arc $x \rightarrow y$ si
et seulement si $y=f(x)$.
-\item Le \emph{graphe des itérations unaires} de $f$, noté $\textsc{gia}(f)$
+\item Le \emph{graphe des itérations unaires} de $f$, noté $\textsc{giu}(f)$
est le graphe orienté de $\Bool^n$ qui contient un arc $x \rightarrow y$ si
et seulement s'il existe $x \in \Delta f(x)$ tel que $y = \overline{x}^i$.
\item Le \emph{graphe des itérations généralisées} de $f$, noté $\textsc{gig}(f)$
\end{minipage}
\label{fig:fsig}
}
- \subfigure[$\textsc{gia}(f)$]{
+ \subfigure[$\textsc{giu}(f)$]{
\begin{minipage}{0.33\textwidth}
\begin{center}
\includegraphics[scale=0.4]{faig}
aux états stables:
dans chaque graphe d'itérations, le point $x$ est un point fixe
si et seulement si il est son seul successeur.
-Dans le contexte des réseaux de régulation de gènes,
-ces points fixes correspondent aux configurations stables pour l'expression de
-gènes.
\begin{xpl}
-Les attracteurs de $\textsc{gia}(f)$ et de $\textsc{gig}(f)$ sont
+Les attracteurs de $\textsc{giu}(f)$ et de $\textsc{gig}(f)$ sont
le point fixe $000$ et l'attracteur cyclique
$\{001, 101,111, 011 \}$.
Les attracteurs de $\textsc{gis}(f)$ sont le point fixe $000$
En outre, les interactions peuvent se représenter à l'aide d'un
-graphe $G(f)$ orienté et signé défini ainsi:
+graphe $\Gamma(f)$ orienté et signé défini ainsi:
l'ensemble des sommets est
$[n]$ et il existe un arc de $j$ à $i$ de signe
$s\in\{-1,1\}$, noté $(j,s,i)$, si $f_{ij}(x)=s$ pour au moins
\begin{figure}[ht]
\begin{center}
- \subfigure[Matrice jacobienne de $f$.]{
+ \subfigure[Matrice jacobienne]{
\begin{minipage}{0.90\textwidth}
\begin{center}
$
\end{minipage}
\label{fig:f:jacobienne}
}
-
- \subfigure[Graphe d'interaction de $f$.]{
+ ~
+ \subfigure[Graphe d'interaction]{
\begin{minipage}{0.45\textwidth}
\begin{center}
\includegraphics[scale=0.5]{gf}
\end{minipage}
}
- \subfigure[Matrice d'incidence de $f$.]{
+ \subfigure[Matrice d'incidence]{
\begin{minipage}{0.45\textwidth}
\begin{center}
$
\end{minipage}
}
\end{center}
-\caption{Représentations des dépendances entre les éléments de la fonction $f$ de l'exemple illustratif.}
+\caption{Représentations des dépendances entre les éléments
+de la fonction
+$f:\Bool^3 \rightarrow \Bool^3$ telle que
+$(x_1, x_2, x_3) \mapsto
+((\overline{x_1} + \overline{x_2}).x_3,
+x_1.x_3,
+x_1 + x_2 + x_3)$}
\end{figure}
\end{xpl}
-Soit $P$ une suite d'arcs de $G(f)$ de la forme
+Soit $P$ une suite d'arcs de $\Gamma(f)$ de la forme
\[
(i_1,s_1,i_2),(i_2,s_2,i_3),\ldots,(i_r,s_r,i_{r+1}).
\]
-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.
a énoncé en 1995 le théorème suivant de convergence
dans le mode des itérations unaires.
-\begin{theorem}\label{Th:conv:GIA}
-Si le graphe $G(f)$ n'a pas de cycle et si la stratégie unaire est
-pseudo-périodique, alors tout chemin de $\textsc{GIA}(f)$ atteint
+\begin{theorem}\label{Th:conv:GIU}
+Si le graphe $\Gamma(f)$ n'a pas de cycle et si la stratégie unaire est
+pseudo-périodique, alors tout chemin de $\textsc{giu}(f)$ atteint
l'unique point fixe $\zeta$ en au plus $n$ pseudo-périodes.
\end{theorem}
J. Bahi~\cite{Bah00} a démontré le théorème suivant:
\begin{theorem}\label{Th:Bahi}
-Si le graphe $G(f)$ n'a pas de cycle et si la stratégie généralisée
+Si le graphe $\Gamma(f)$ n'a pas de cycle et si la stratégie généralisée
est pseudo-périodique alors
-tout chemin de $\textsc{gig}(f)$ finit par atteindre
+tout chemin de $\textsc{gig}(f)$ (et donc de $\textsc{giu}(f)$)
+finit par atteindre
l'unique point fixe $\zeta$.
\end{theorem}
