[hdrcouchot.git] / sdd.tex

\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 
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}
  \begin{center}
    \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{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 
système peuvent être mémorisées 
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)$, 
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: 
l'ensemble des sommets est 
$\llbracket1;n\rrbracket$ 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}
  \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
\[
(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
$\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 
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 a  démontré que pour toute fonction booléenne $f$, 
$G_f$ est continue sur $\mathcal{X}$ (cf annexe~\ref{anx:cont}).