debut mixage

[hdrcouchot.git] / sdd.tex

diff --git a/sdd.tex b/sdd.tex
index 0bd7629f2613a94d737b0a7b52b0ca71f949cc14..f86c5448c5d0e9a87f4eb12ad69d568afae11b58 100644 (file)
--- a/sdd.tex
+++ b/sdd.tex
@@ -12,9 +12,8 @@ Elle commence par formaliser ce que sont les systèmes dynamiques booléens
 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 
 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.
+$\llbracket 1;n\rrbracket^{\Nats}\times \Bool^n$ (section~\ref{sub:metric}).
+

 
 
 
 
 
 


@@ -28,7 +27,7 @@ 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 
 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 
+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}$ 
 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}$ 


@@ -37,7 +36,7 @@ $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 
 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}. 
+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
 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


@@ -48,7 +47,7 @@ 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).
 \]
 
 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
+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
 $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


@@ -67,13 +66,13 @@ 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  
 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
+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. 
 $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 
+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)$ 
 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)$ 


@@ -85,10 +84,9 @@ 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}
 
 
 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.
+est une abréviation de  graphe des itérations chaotiques.

 La figure~\ref{fig:xplgraphIter} donne deux exemples de graphes d'itérations 
 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. 
+pour les fonctions $g$ et $h$ définies dans $\Bool^2$ qui seront reprises dans la suite.

 
 
 
 
 
 


@@ -96,7 +94,7 @@ de ce document.
 \centering
 \begin{minipage}{0.40\textwidth}
   \begin{center}
 \centering
 \begin{minipage}{0.40\textwidth}
   \begin{center}

-    \includegraphics[height=4cm]{images/g.pdf}
+    \includegraphics[scale=0.4]{images/g.pdf}

   \end{center}
 \caption{$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $}%
 \label{fig:g:iter}%
   \end{center}
 \caption{$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $}%
 \label{fig:g:iter}%


@@ -104,37 +102,15 @@ de ce document.
 \qquad
 \begin{minipage}{0.40\textwidth}%
   \begin{center}
 \qquad
 \begin{minipage}{0.40\textwidth}%
   \begin{center}

-    \includegraphics[height=4cm]{images/h.pdf}
+    \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}%
   \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}%
 
 \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}
-
-
-

 
 
 
 
 
 


@@ -159,6 +135,10 @@ 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$.
 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.
+

 
 En outre, les interactions peuvent se  représenter à l'aide d'un 
 graphe $G(f)$ orienté et signé défini ainsi: 
 
 En outre, les interactions peuvent se  représenter à l'aide d'un 
 graphe $G(f)$ orienté et signé défini ainsi: 


@@ -178,7 +158,7 @@ est possible.
 \centering
 \begin{minipage}{0.40\textwidth}
   \begin{center}
 \centering
 \begin{minipage}{0.40\textwidth}
   \begin{center}

-    \includegraphics[height=3cm]{images/gp.pdf}
+    \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{center}
 \caption{$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $}%
 \label{fig:g:inter}%


@@ -186,7 +166,7 @@ est possible.
 \qquad
 \begin{minipage}{0.40\textwidth}
   \begin{center}
 \qquad
 \begin{minipage}{0.40\textwidth}
   \begin{center}

-    \includegraphics[height=3cm]{images/hp.pdf}
+    \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{center}
 \caption{$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$}%
 \label{fig:h:inter}%


@@ -250,6 +230,6 @@ $(l+1)^{\textrm{ème}}$ décimale
 de $d_S(s,s')$ 
 n'est pas nulle, alors $s_l$ est différent de  $s'_l$. 
 
 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$, 
+On a  démontré que pour toute fonction booléenne $f$, 

 $G_f$ est continue sur $\mathcal{X}$ (cf annexe~\ref{anx:cont}).   
 
 $G_f$ est continue sur $\mathcal{X}$ (cf annexe~\ref{anx:cont}).