X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/1b923f193392e3ce847882c24a128eff4bee9992..f4dd79b2c3181cb26ec94555b62ed77dcb0a4200:/sdd.tex diff --git a/sdd.tex b/sdd.tex index 0bd7629..f86c544 100644 --- 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 -$\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 -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}$ @@ -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 -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 @@ -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). \] -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 @@ -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 -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. -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)$ @@ -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} -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 -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} - \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}% @@ -104,37 +102,15 @@ de ce document. \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}% +\caption{Graphes d'itérations de fonctions booléennes dans $\Bool^2$} +\label{fig:xplgraphIter} \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$. +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: @@ -178,7 +158,7 @@ est possible. \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}% @@ -186,7 +166,7 @@ est possible. \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}% @@ -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$. -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}).