reprise chap 1

[hdrcouchot.git] / sdd.tex

diff --git a/sdd.tex b/sdd.tex
index 37552951ecc85d033d2eddf4a966a7f12fcc59af..530ef34b28ed4a106d881c14f565dcb137195e05 100644 (file)
--- a/sdd.tex
+++ b/sdd.tex
@@ -119,18 +119,26 @@ schémas suivants :
 \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 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}. 
   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
 \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


@@ -146,6 +154,17 @@ schémas suivants :
   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}.
   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}
 
 
   \end{itemize}
 
 


@@ -168,7 +187,7 @@ sont les éléments de $\Bool^n$ (voir \textsc{Figure}~\ref{fig:xpl:graphs}).
 \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 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)$
 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)$


@@ -200,7 +219,7 @@ associés à $f$.
       \end{minipage}
       \label{fig:fsig}
     }
       \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}
       \begin{minipage}{0.33\textwidth}
         \begin{center}
           \includegraphics[scale=0.4]{faig}


@@ -237,9 +256,6 @@ 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.
 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.

 
 
 
 
 
 


@@ -272,7 +288,7 @@ Ainsi $\Gamma$ contient toujours au moins un attracteur.
 
 
 \begin{xpl}
 
 
 \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$
 le point fixe $000$ et l'attracteur cyclique 
 $\{001, 101,111, 011  \}$. 
 Les attracteurs de $\textsc{gis}(f)$ sont le point fixe $000$


@@ -316,7 +332,7 @@ $f'_{ij}(x)=0$. Ainsi $B(f)_{ij}$ est nulle. La réciproque est aussi vraie.
 
 
 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 
 $[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
 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


@@ -400,7 +416,7 @@ La \textsc{Figure}~(\ref{fig:f:incidence}) donne la matrice d'incidence complèt
 
 \begin{figure}[ht]
   \begin{center}
 
 \begin{figure}[ht]
   \begin{center}

-     \subfigure[Matrice jacobienne de $f$.]{
+     \subfigure[Matrice jacobienne]{

        \begin{minipage}{0.90\textwidth}
          \begin{center}
         $
        \begin{minipage}{0.90\textwidth}
          \begin{center}
         $


@@ -440,8 +456,8 @@ La \textsc{Figure}~(\ref{fig:f:incidence}) donne la matrice d'incidence complèt
        \end{minipage}
        \label{fig:f:jacobienne}
      } 
        \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}
       \begin{minipage}{0.45\textwidth}
       \begin{center}
         \includegraphics[scale=0.5]{gf}


@@ -450,7 +466,7 @@ La \textsc{Figure}~(\ref{fig:f:incidence}) donne la matrice d'incidence complèt
     \end{minipage}
     }
     
     \end{minipage}
     }
     

-    \subfigure[Matrice d'incidence de $f$.]{
+    \subfigure[Matrice d'incidence]{

       \begin{minipage}{0.45\textwidth}
         \begin{center}
           $
       \begin{minipage}{0.45\textwidth}
         \begin{center}
           $


@@ -468,24 +484,30 @@ La \textsc{Figure}~(\ref{fig:f:incidence}) donne la matrice d'incidence complèt
     \end{minipage}
   }
 \end{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}
 
 
 
 
 \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}).
 \]
 \[
 (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.
 
 


@@ -522,9 +544,9 @@ François Robert~\cite{Rob95}
 a énoncé en 1995 le théorème suivant de convergence 
 dans le mode des itérations unaires.
 
 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}
 
 l'unique point fixe $\zeta$ en au plus $n$ pseudo-périodes.
 \end{theorem}
 


@@ -536,9 +558,10 @@ 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}
 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
 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}
 
 l'unique point fixe $\zeta$. 
 \end{theorem}