X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/7b2f06062fc54db047de438cda35671608a1dc89..refs/heads/master:/sdd.tex?ds=sidebyside diff --git a/sdd.tex b/sdd.tex index 83bee06..7a31f0d 100644 --- 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$. -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 @@ -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} -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: \[ @@ -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}. - 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= @@ -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}. - 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} @@ -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$ 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$. @@ -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{minipage}{0.33\textwidth} + \begin{minipage}{0.3\textwidth} \begin{center} \includegraphics[scale=0.4]{fsig} \end{center} @@ -228,7 +212,7 @@ associés à $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} @@ -236,7 +220,7 @@ associés à $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} @@ -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} + +\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} @@ -284,13 +275,13 @@ On a la proposition suivante: \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} @@ -326,13 +317,13 @@ ${\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. -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} @@ -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: -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}}$. @@ -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. -\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( @@ -461,21 +453,12 @@ La \textsc{Figure}~(\ref{fig:f:incidence}) donne la matrice d'incidence complèt \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) = @@ -491,6 +474,16 @@ La \textsc{Figure}~(\ref{fig:f:incidence}) donne la matrice d'incidence complèt \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 @@ -537,22 +530,21 @@ Parmi toutes les stratégies unaires de $[{\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. @@ -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 -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)$)