X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/dd837d463f86ebb399eb1cac274139e98815fdd1..ab1271f8b9509a86f3434c2389be47fe3a1c4d04:/12TIPE.tex?ds=inline diff --git a/12TIPE.tex b/12TIPE.tex index 4cbc26d..4bcec9f 100644 --- a/12TIPE.tex +++ b/12TIPE.tex @@ -8,19 +8,21 @@ $\Bool^{{\mathsf{N}}}$ dans lui-même. 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. +composant (entre 1 et $\mathsf{N}$) est mis à jour. 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 peut définir -la fonction $F_{f_u}: \Bool^{\mathsf{N}} \times \llbracket1;\mathsf{N}\rrbracket$ +de $[\mathsf{N}]$), on peut définir +la fonction $F_{f_u}: \Bool^{\mathsf{N}} \times [\mathsf{N}]$ vers $\Bool^\mathsf{N}$ par -\[ + +\begin{equation} F_{f_u}(x,i)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_\mathsf{N}). -\] +\label{eq:iterations:unaires} +\end{equation} 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$ +[\mathsf{N}]^\Nats$, les configurations $x^t$ sont définies par la récurrence \begin{equation}\label{eq:asyn} x^{t+1}=F_{f_u}(x^t,s_t). @@ -29,8 +31,8 @@ x^{t+1}=F_{f_u}(x^t,s_t). On peut alors construire l'espace $\mathcal{X}_u = -\Bool^{{\mathsf{N}}} \times \llbracket1;{\mathsf{N}}\rrbracket^{\Nats}$ -et la fonction d'iteration $G_{f_u}$ définie de +\Bool^{{\mathsf{N}}} \times [{\mathsf{N}}]^{\Nats}$ +et la fonction d'itération $G_{f_u}$ définie de $\mathcal{X}_u$ dans lui-même par \begin{equation} @@ -39,8 +41,8 @@ G_{f_u}(x,s)=(F_{f_u}(x,s_0),\sigma(s)). \end{equation} Dans cette définition, la fonction -$\sigma: \llbracket1;{\mathsf{N}}\rrbracket^{\Nats} \longrightarrow - \llbracket1;{\mathsf{N}}\rrbracket^{\Nats} +$\sigma: [{\mathsf{N}}]^{\Nats} \longrightarrow + [{\mathsf{N}}]^{\Nats} $ décale la stratégie fournie en argument d'un élément vers la gauche en supprimant @@ -52,14 +54,14 @@ $$ 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_u}$ dans $\mathcal{X}_u$. +parallèles de la fonction $G_{f_u}$ dans $\mathcal{X}_u$. La section suivante introduit une métrique sur $\mathcal{X}_u$. \subsection{Une métrique pour $\mathcal{X}_u$} Sur $\mathcal{X}_u$, on définit la distance $d$ entre les points $X=(x,s)$ et $X'=(x',s')$ de $\mathcal{X}_u$ par -\[ +\begin{equation} d(X,X')= d_H(x,x')+d_S(s,s'),~\textrm{où}~ \left\{ \begin{array}{l} @@ -67,7 +69,8 @@ d(X,X')= d_H(x,x')+d_S(s,s'),~\textrm{où}~ \displaystyle{d_S(s,s')=\frac{9}{n}\sum_{t\in\Nats}\frac{|s_t-s'_t|}{10^{t+1}}}. \end{array} \right.\,. -\] +\end{equation} + 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 @@ -92,34 +95,34 @@ apporte une réponse à cette question. chaotiques $G_{f_u}$ sur $\mathcal{X}_u$} -On peut tout d'abord démontrer que pour toute fonction booléenne $f$, -$G_{f_u}$ est continue sur $\mathcal{X}_u$ (cf annexe~\ref{anx:cont}). +% On peut tout d'abord démontrer que pour toute fonction booléenne $f$, +% $G_{f_u}$ est continue sur $\mathcal{X}_u$ (cf annexe~\ref{anx:cont}). -Pour charactérister les fonctions rendant chaotiques dans $\mathcal{X}_u$ les itérations de $G_{f_u}$ -on se focalise donc que sur la régularité et sur la transitivité de $G_{f_u}$. +Pour caractériser les fonctions rendant chaotiques dans $\mathcal{X}_u$ les itérations de $G_{f_u}$ +on se focalise donc sur la régularité et sur la transitivité de $G_{f_u}$. 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_u} \textrm{ est transitive} \right\}$, -\item $\mathcal{R} = \left\{f : \mathds{B}^n \to -\mathds{B}^n \big/ G_{f_u} \textrm{ est régulière} \right\}$, -\item $\mathcal{C} = \left\{f : \mathds{B}^n \to -\mathds{B}^n \big/ G_{f_u} \textrm{ est chaotique} \right\}$. +\item $\mathcal{T} = \left\{f : \mathds{B}^{\mathsf{N}} \to +\mathds{B}^{\mathsf{N}} \textrm{ t. q. } G_{f_u} \textrm{ est transitive} \right\}$, +\item $\mathcal{R} = \left\{f : \mathds{B}^{\mathsf{N}} \to +\mathds{B}^{\mathsf{N}} \textrm{ t. q. } G_{f_u} \textrm{ est régulière} \right\}$, +\item $\mathcal{C} = \left\{f : \mathds{B}^{\mathsf{N}} \to +\mathds{B}^{\mathsf{N}} \textrm{ t. q. } G_{f_u} \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}. +On énonce les théorèmes successifs suivants dont les preuves sont données +dans~\cite{guyeuxphd}. \begin{theorem} $G_{f_u}$ est transitive si et seulement si $\textsc{giu}(f)$ est fortement connexe. \end{theorem} \begin{theorem} -\label{Prop: T est dans R} $\mathcal{T} \subset \mathcal{R}$. +\label{Prop: T est dans R:u} $\mathcal{T} \subset \mathcal{R}$. \end{theorem} On peut conclure que $\mathcal{C} = \mathcal{R} \cap \mathcal{T} @@ -127,7 +130,7 @@ On peut conclure que $\mathcal{C} = \mathcal{R} \cap \mathcal{T} \begin{theorem}%[Characterization of $\mathcal{C}$] \label{Th:CaracIC} -Soit $f:\Bool^n\to\Bool^n$. La fonction $G_{f_u}$ est chaotique +Soit $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$. La fonction $G_{f_u}$ est chaotique si et seulement si $\textsc{giu}(f)$ est fortement connexe. \end{theorem}