ajout de l'état de l'art PRBG chaotique

[hdrcouchot.git] / sdd.tex

diff --git a/sdd.tex b/sdd.tex
index 355e33c119cc87c89289384c67b69d505cdadf4d..7a31f0d8468e34704c691a750b8d1e4214ba58e5 100644 (file)
--- a/sdd.tex
+++ b/sdd.tex
@@ -1,17 +1,7 @@
 
 

-\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}).
-

 
 
 
 
 
 


@@ -40,7 +30,7 @@ et $\overline{x}^i$ pour $\overline{x}^{\{i\}}$ pour $i \in [{\mathsf{N}}]$
 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$.
 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
+Soit enfin $f : \Bool^{\mathsf{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 
 est nommé $f_i$ qui est une fonction de $\Bool^{\mathsf{N}}$ dans $\Bool$.
 Pour chaque 
 $x$ dans $\Bool^{\mathsf{N}}$, l'ensemble 


@@ -105,8 +95,8 @@ Pour $x=(0,1,0)$ les assertions suivantes se déduisent directement du tableau:
 \end{xpl}
 
 \subsection{Réseau booléen}
 \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).
+Soit ${\mathsf{N}}$ un entier naturel représentant le nombre 
+d'éléments étudiés.

 Un réseau booléen  est 
 défini à partir d'une fonction booléenne:
 \[
 Un réseau booléen  est 
 défini à partir d'une fonction booléenne:
 \[


@@ -128,7 +118,7 @@ schémas suivants :
   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}. 
   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
+  Ce mode est défini pour tout $i \in [{\mathsf{N}}]$ par

   
 \begin{equation}
   x^{t+1}_i=
   
 \begin{equation}
   x^{t+1}_i=


@@ -157,7 +147,7 @@ schémas suivants :
   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}.
   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
+  Ce schéma est basé sur la relation définie pour tout $i \in [{\mathsf{N}}]$ par

   \begin{equation}
   x^{t+1}_i=
   \left\{ \begin{array}{l}
   \begin{equation}
   x^{t+1}_i=
   \left\{ \begin{array}{l}


@@ -194,7 +184,7 @@ sont les éléments de $\Bool^{\mathsf{N}}$ (voir \textsc{Figure}~\ref{fig:xpl:g
 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$ 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 
+est le graphe orienté de $\Bool^{\mathsf{N}}$ qui contient un arc $x \rightarrow y$ 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$.
 
 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$.
 


@@ -210,17 +200,11 @@ des itérations unaires.
 
 
 
 
 
 

-\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{figure}[ht]

   \begin{center}
     \subfigure[$\textsc{gis}(f)$]{
   \begin{center}
     \subfigure[$\textsc{gis}(f)$]{

-      \begin{minipage}{0.33\textwidth}
+      \begin{minipage}{0.3\textwidth}

         \begin{center}
           \includegraphics[scale=0.4]{fsig}
         \end{center}
         \begin{center}
           \includegraphics[scale=0.4]{fsig}
         \end{center}


@@ -228,7 +212,7 @@ associés à $f$.
       \label{fig:fsig}
     }
     \subfigure[$\textsc{giu}(f)$]{
       \label{fig:fsig}
     }
     \subfigure[$\textsc{giu}(f)$]{

-      \begin{minipage}{0.33\textwidth}
+      \begin{minipage}{0.3\textwidth}

         \begin{center}
           \includegraphics[scale=0.4]{faig}
         \end{center}
         \begin{center}
           \includegraphics[scale=0.4]{faig}
         \end{center}


@@ -236,7 +220,7 @@ associés à $f$.
       \label{fig:faig}
     }   
     \subfigure[$\textsc{gig}(f)$]{
       \label{fig:faig}
     }   
     \subfigure[$\textsc{gig}(f)$]{

-      \begin{minipage}{0.33\textwidth}
+      \begin{minipage}{0.3\textwidth}

         \begin{center}
           \includegraphics[scale=0.4]{fgig}
         \end{center}
         \begin{center}
           \includegraphics[scale=0.4]{fgig}
         \end{center}


@@ -253,6 +237,13 @@ 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}
 On remarque le cycle $((101,111),(111,011),(011,101))$ 
  à la \textsc{Figure}~(\ref{fig:fsig}).}
 \end{figure}

+
+\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$.

 \end{xpl} 
 
 
 \end{xpl} 
 
 


@@ -284,13 +275,13 @@ On a la proposition suivante:
 
 
 \begin{theorem}\label{Prop:attracteur}
 
 
 \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é).
+La configuration $x$ est un point fixe si et seulement si 
+$\{x\}$ est un attracteur du graphe d'itérations (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.
 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.
+Tout graphe d'itérations contient donc toujours au moins un attracteur.

 \end{theorem}
 
 
 \end{theorem}
 
 


@@ -326,7 +317,7 @@ ${\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.
 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 
+Elle ne mémorise pas \emph{comment}  les éléments dépendent

 les uns par rapport aux autres. Cette matrice est nommée 
 \emph{matrice d'incidence}.  
 
 les uns par rapport aux autres. Cette matrice est nommée 
 \emph{matrice d'incidence}.  
 


@@ -341,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 
 graphe $\Gamma(f)$ orienté et signé défini ainsi: 
 
 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 
+l'ensemble des sommets 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}}$. 
 $[{\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}}$. 


@@ -422,10 +413,11 @@ $x_1$ et  de $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. 
 
 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{figure}[ht]

   \begin{center}
      \subfigure[Matrice jacobienne]{
   \begin{center}
      \subfigure[Matrice jacobienne]{

-       \begin{minipage}{0.90\textwidth}
+       \begin{minipage}{0.65\textwidth}
+         \begin{scriptsize}

          \begin{center}
         $
         \left(
          \begin{center}
         $
         \left(


@@ -461,21 +453,12 @@ La \textsc{Figure}~(\ref{fig:f:incidence}) donne la matrice d'incidence complèt
         \right)
         $
          \end{center}
         \right)
         $
          \end{center}

-       \end{minipage}
+       \end{scriptsize}
+     \end{minipage}

        \label{fig:f:jacobienne}
      } 
        \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}
+     \subfigure[Matrice d'incidence]{
+       \begin{minipage}{0.25\textwidth}

         \begin{center}
           $
           B(f) =
         \begin{center}
           $
           B(f) =


@@ -491,6 +474,16 @@ La \textsc{Figure}~(\ref{fig:f:incidence}) donne la matrice d'incidence complèt
         \label{fig:f:incidence}
     \end{minipage}
   }
         \label{fig:f:incidence}
     \end{minipage}
   }

+
+    ~ 
+    \subfigure[Graphe d'interaction]{
+      \begin{minipage}{0.45\textwidth}
+      \begin{center}
+        \includegraphics[scale=0.5]{gf}
+      \end{center}
+      \label{fig:f:interaction}
+    \end{minipage}
+    }

 \end{center}  
 \caption{Représentations des dépendances entre les éléments 
 de la fonction 
 \end{center}  
 \caption{Représentations des dépendances entre les éléments 
 de la fonction 


@@ -537,22 +530,21 @@ Parmi toutes les stratégies unaires de
 $[{\mathsf{N}}]^{\Nats}$, on qualifie de:
 \begin{itemize}
 \item \emph{périodiques} celles 
 $[{\mathsf{N}}]^{\Nats}$, on qualifie de:
 \begin{itemize}
 \item \emph{périodiques} celles 

-qui sont constituées par une répétition indéfinie 
+qui sont constituées par une répétition infinie 

 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 
 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 
+qui sont constituées par une succession infinie 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
 (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.
+$1$ à ${\mathsf{N}}$ revient infiniment.

 \end{itemize}
 
 
 \end{itemize}
 
 

-François Robert~\cite{Rob95}
-a énoncé en 1995 le théorème suivant de convergence 
+On a le théorème suivant de convergence 

 dans le mode des itérations unaires.
 
 dans le mode des itérations unaires.
 

-\begin{theorem}\label{Th:conv:GIU}
+\begin{theorem}[~\cite{Rob95}]\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.
 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.


@@ -561,11 +553,11 @@ l'unique point fixe $\zeta$ en au plus ${\mathsf{N}}$ pseudo-périodes.
 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 
 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}}]$ 
+succession infinie de séquences de parties de $[{\mathsf{N}}]$ 

 dont l'union est $[{\mathsf{N}}]$, cette stratégie est {pseudo-périodique}.
 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:
+On a le théorème suivant.

 
 

-\begin{theorem}\label{Th:Bahi}
+\begin{theorem}[~\cite{Bah00}]\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)$) 
 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)$)