-\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}).
-
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
\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:
\[
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=
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}
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 s'il existe $x \in \Delta f(x)$ tel que $y = \overline{x}^i$.
+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$.
+
\item Le \emph{graphe des itérations généralisées} de $f$, noté $\textsc{gig}(f)$
est le graphe orienté de $\Bool^{\mathsf{N}}$ qui contient un arc $x \rightarrow y$ si
et seulement s'il existe un ensemble $I\subseteq \Delta f(x)$ tel que
-\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{minipage}{0.33\textwidth}
+ \begin{minipage}{0.3\textwidth}
\begin{center}
\includegraphics[scale=0.4]{fsig}
\end{center}
\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}
\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}
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}
\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.
-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}
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}.
\begin{theorem}
Si $f_i$ ne dépend pas de $x_j$, alors pour tout $x\in [{\mathsf{N}}]$,
-$f_i(\overline{x}^j)$ est égal à $f_i(x)$, \textit{i.e},
+$f_i(\overline{x}^j)$ est égal à $f_i(x)$, \textit{i.e.},
$f'_{ij}(x)=0$. Ainsi $B(f)_{ij}$ est nulle. La réciproque est aussi vraie.
\end{theorem}
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}}$.
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{minipage}{0.90\textwidth}
+ \begin{minipage}{0.65\textwidth}
+ \begin{scriptsize}
\begin{center}
$
\left(
\right)
$
\end{center}
- \end{minipage}
+ \end{scriptsize}
+ \end{minipage}
\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) =
\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
$[{\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
-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
-$1$ à ${\mathsf{N}}$ revient indéfiniment.
+$1$ à ${\mathsf{N}}$ revient infiniment.
\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.
-\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.
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}.
-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)$)
