From: couchot Date: Thu, 21 May 2015 12:22:48 +0000 (+0200) Subject: nouveaux tex X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/commitdiff_plain/e9bdff7e28e4cda1ffb71158afdcf44e3d656b6c?hp=148e6fe3fc164ce0c37454354e0815c398cdea62 nouveaux tex --- diff --git a/12TIPE.tex b/12TIPE.tex new file mode 100644 index 0000000..4171437 --- /dev/null +++ b/12TIPE.tex @@ -0,0 +1,226 @@ +La première section rappelle ce que sont les systèmes dynamiques chaotiques. + +\section{Systèmes dynamiques chaotiques selon Devaney} +\label{subsec:Devaney} +Dans cette partie, les définitions fondamentales liées au chaos +dans les systèmes booléens sont rappelées. + + + +Soit un espace topologique $(\mathcal{X},\tau)$ et une fonction continue $f : +\mathcal{X} \rightarrow \mathcal{X}$. + + + + +\begin{Def}[Chaos selon Devaney~\cite{Devaney}] +La fonction $f$ \emph{chaotique} sur $(\mathcal{X},\tau)$ +si elles est régulière et topologiquement transitive. +\end{Def} + + + +\begin{Def}[Transitivite topologique] +La fonction $f$ est dite \emph{topologiquement transitive} si, +pour chaque paire d'ensembles ouverts +$U,V \subset \mathcal{X}$, +il existe $k>0$ tel que $f^k(U) \cap V \neq +\varnothing$. +\end{Def} + +\begin{Def}[Point périodique] + Un point $P \in \mathcal{X}$ est dit \emph{périodique} de période $t$ pour + une fonction $k$ si $t$ est un entier naturel non nul tel que $k^t(P) = P$ et + pour tout $n$, $0 < n \le t-1$, on a $k^n(P) \neq P$. + Par la suite, $\emph{Per(k)}$ dénote l'ensemble des points périodiques de + $k$ dans $\mathcal{X}$ de période quelconque. +\end{Def} + + + +\begin{Def}[Régularité] +La fonction $f$ est dite \emph{régulière} +sur $(\mathcal{X}, \tau)$ si l'ensemble des points périodiques + de $f$ is dense in $\mathcal{X}$: +pour chaque point $x \in \mathcal{X}$, chaque voisin +de $x$ contient au moins un point périodique +(sans que la période soit nécessairement constante). +\end{Def} + + + + + + + + + +La propriété de chaos est souvent associée à la notion de +\og sensibilité aux conditions initiales\fg{}, notion définie elle +sur un espace métrique $(\mathcal{X},d)$ par: + + +\begin{Def}[Forte sensibilité aux conditions initiales] +Une fonction $k$ définie sur $(\mathcal{X},\tau)$ +est \emph{fortement sensible aux conditions initiales} +s'il existe une valeur $\epsilon> 0$ telle que +pour tout $X \in \mathcal{X}$ et pour tout + $\delta > 0$, il existe $Y \in \mathcal{X}$ et +$t \in \Nats$ qui vérifient $d(X,Y) < \delta$ et +$d(k^t(X) , k^t(Y)) > \epsilon$. + +La constante $\delta$ est appelée \emph{constante de sensibilité} de $f$. +\end{Def} + +John Banks et ses collègues ont cependant +démontré que la sensibilité aux conditions initiales est une conséquence +de la régularité et de la transitivité topologique~\cite{Banks92}. + + + +\section{Schéma unaire} +Soit ${\mathsf{N}}$ un entier naturel et $f$ une fonction de +$\Bool^{{\mathsf{N}}}$ dans lui-même. + + +\subsection{Des itérations unaires aux itérations parallèles} + +Dans le schéma unaire, à la $t^{\textrm{ème}}$ itération, +seul le $s_{t}^{\textrm{ème}}$ +composant (entre 1 et $n$) est mis à jour. + +Formellement, pour une stratégie $s = \left(s_t\right)_{t \in \mathds{N}}$ +(\textit{i.e.}, une séquence d'indices +de $\llbracket 1;\mathsf{N} \rrbracket$), on définit +la fonction $F_f: \Bool^{\mathsf{N}} \times \llbracket1;\mathsf{N}\rrbracket$ +vers $\Bool^\mathsf{N}$ par +\[ +F_f(x,i)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_\mathsf{N}). +\] + +Dans le schéma des itérations unaires pour une configuration initiale +$x^0\in\Bool^\mathsf{N}$ et une stratégie $s\in +\llbracket1;\mathsf{N}\rrbracket^\Nats$, les configurations $x^t$ +sont définies par la récurrence +x\begin{equation}\label{eq:asyn} +x^{t+1}=F_f(x^t,s_t). +\end{equation} + +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 +$s$. + + +On peut alors construire l'espace +$\mathcal{X} = +\Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}$ +et la fonction d'iteration $G_f$ définie de +$\mathcal{X}$ +dans lui-même par +\[ +G_f(x,s)=(F_f(x,s_0),\sigma(s)). +\] + +Dans cette définition, la fonction +$\sigma: \llbracket1;{\mathsf{N}}\rrbracket^{\Nats} \longrightarrow + \llbracket1;{\mathsf{N}}\rrbracket^{\Nats} +$ +décale +la stratégie fournie en argument d'un élément vers la gauche en supprimant +l'élément de tête. Ceci se formalise par +$$ +\sigma((u^k)_{k \in \Nats}) = (u^{k+1})_{k \in \Nats}. +$$ + + +Ainsi, effectuer des itérations unaires sur la fonction +$f$ selon une stratégie $s$ revient à effectuer des itérations +parallèles de la fonctions $G_f$ dans $\mathcal{X}$. + +La section suivante introduit une métrique sur $\mathcal{X}$. + +\subsection{Une métrique pour $\mathcal{X}$} +Sur $\mathcal{X}$, +on définit la distance $d$ entre les points $X=(x,s)$ et +$X'=(x',s')$ 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 distance de Hamming 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 partie entière +$\lfloor d(X,X')\rfloor$ est égale à $d_H(x,x')$ soit la distance +de Hamming entre $x$ et $x'$. +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$. + +La section fournit quelques résultats de caractérisation de fonctions +chaotiques pour le schéma unaire. + + +\subsection{Caractérisation des fonctions chaotiques +pour le schéma unaire} + +On peut tout d'abord démontrer que pour toute fonction booléenne $f$, +$G_f$ est continue sur $\mathcal{X}$ (cf annexe~\ref{anx:cont}). + +Pour charactérister les fonctions rendant chaotiques dans $ +\mathcal{X}$ les itérations de $G_f$ +on se focalise donc que sur la régularité et +sur la transitivité de $G_f$. + +Ceci se réalise en établissant les relations d'inclusion entre +les ensembles $\mathcal{T}$ des fonctions topologiquement transitives, +$\mathcal{R}$ des fonctions régulières +et $\mathcal{C}$ des fonctions chaotiques définis respectivement ci-dessous: +\begin{itemize} +\item $\mathcal{T} = \left\{f : \mathds{B}^n \to +\mathds{B}^n \big/ G_f \textrm{ est transitive} \right\}$, +\item $\mathcal{R} = \left\{f : \mathds{B}^n \to +\mathds{B}^n \big/ G_f \textrm{ est régulière} \right\}$, +\item $\mathcal{C} = \left\{f : \mathds{B}^n \to +\mathds{B}^n \big/ G_f \textrm{ est chaotique} \right\}$. +\end{itemize} + + +On énnonce les théorèmes successifs suivants. +Leur preuve est donnée en annexe~\ref{anx:chaos:unaire}. + +\begin{theorem} $G_f$ est transitive si et seulement si + $\Gamma(f)$ est fortement connexe. +\end{theorem} + +\begin{theorem} +\label{Prop: T est dans R} $\mathcal{T} \subset \mathcal{R}$. +\end{theorem} + +On peut conclure que $\mathcal{C} = \mathcal{R} \cap \mathcal{T} += \mathcal{T}$. On a alors la caractérisation suivante: + +\begin{theorem}%[Characterization of $\mathcal{C}$] +\label{Th:CaracIC} +Soit $f:\Bool^n\to\Bool^n$. La fonction $G_f$ est chaotique +si et seulement si $\Gamma(f)$ est fortement connexe. +\end{theorem} + + + + + + +\section{Schéma généralisé} + + diff --git a/caracunaire.tex b/caracunaire.tex new file mode 100644 index 0000000..7f3fbc4 --- /dev/null +++ b/caracunaire.tex @@ -0,0 +1,101 @@ +On prouve les théorèmes suivants + + +\begin{theorem} $G_f$ est transitive si et seulement si + $\Gamma(f)$ est fortement connexe. +\end{theorem} + + + + +\begin{Proof} + +$\Longleftarrow$ Supposons que $\Gamma(f)$ soit fortement connexe. +Soient $(S,x)$ et $(S',x')$ deux points de $\mathcal{X}$ et $\varepsilon >0$. +On construit la stratégie $\tilde S$ telle que la distance +entre $(\tilde S,x)$ et $(S,x)$ est inférieure à +$\varepsilon$ et telle que les itérations parallèles de $G_f$ depuis +$(\tilde S,x)$ mènent au point $(S',x')$. + +Pour cela, on pose $t_1 =-\lfloor\log_{10}(\varepsilon)\rfloor$ et $x''$ la +configuration de $\Bool^n$ obtenue depuis $(S,x)$ après $t_1$ itérations +parallèles de $G_f$. +Comme $\Gamma(f)$ est fortement connexe, il existe une +stratégie $S''$ et un entier $t_2$ tels que $x'$ est atteint depuis +$(S'',x'')$ après $t_2$ itérations de $G_f$. + +Considérons à présent la stratégie +$\tilde S=(s_0,\dots,s_{t_1-1},s''_0,\dots,s''_{t_2-1},s'_0,s'_1,s'_2,s'_3\dots)$. +Il est évident que $(s',x')$ est atteint depuis $(\tilde S,x)$ après +$t_1+t_2$ itérations parallèles de $G_f$. Puisque +$\tilde s_t=s_t$ pour $t0$. Pour +prouver que $f$ appartient à $\mathcal{R}$, il suffit de prouver +qu'il existe une stratégie $\tilde S$ telle que la distance entre +$(\tilde S,x)$ et $(S,x)$ est inférieure à $\varepsilon$ et telle que +$(\tilde S,x)$ est un point périodique. + +Soit $t_1=-\lfloor \log_{10}(\varepsilon)\rfloor$ et soit $x'$ la +configuration obtenue après $t_1$ itérations de $G_f$ depuis $(S,x)$. +D'après la proposition précédente, $\Gamma(f)$ est fortement connexe. +Ainsi, il existe une stratégie $S'$ et un nombre $t_2\in\Nats$ tels +que $x$ est atteint depuis $(S',x')$ après $t_2$ itérations de $G_f$. + +Soit alors la stratégie $\tilde S$ qui alterne les $t_1$ premiers termes +de $S$ avec les $t_2$ premiers termes de $S'$. +Ainsi $\tilde S$ est définie par +\begin{equation*} +(s_0,\dots,s_{t_1-1},s'_0,\dots,s'_{t_2-1},s_0,\dots,s_{t_1-1},s'_0,\dots,s'_{t_2-1},s_0,\dots). +\end{equation*} +Il est évident que $(\tilde S,x)$ s'obtient à partir de $(\tilde S,x)$ après +$t_1+t_2$ itérations parallèles de $G_f$. Ainsi $(\tilde S,x)$ est un point +périodique. Puisque $\tilde s_t$ est égal à $s_t$ pour $t