X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/e9bdff7e28e4cda1ffb71158afdcf44e3d656b6c..1ba923d87cf3028fb3f60f0b411e155f48767aeb:/caracunaire.tex diff --git a/caracunaire.tex b/caracunaire.tex index 7f3fbc4..1111939 100644 --- a/caracunaire.tex +++ b/caracunaire.tex @@ -1,8 +1,8 @@ On prouve les théorèmes suivants -\begin{theorem} $G_f$ est transitive si et seulement si - $\Gamma(f)$ est fortement connexe. +\begin{theorem} $G_{f_u}$ est transitive si et seulement si + $\textsc{giu}(f)$ est fortement connexe. \end{theorem} @@ -10,48 +10,48 @@ On prouve les théorèmes suivants \begin{Proof} -$\Longleftarrow$ Supposons que $\Gamma(f)$ soit fortement connexe. -Soient $(S,x)$ et $(S',x')$ deux points de $\mathcal{X}$ et $\varepsilon >0$. +$\Longleftarrow$ Supposons que $\textsc{giu}(f)$ soit fortement connexe. +Soient $(x,S)$ et $(x',S')$ deux points de $\mathcal{X}_u$ 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')$. +entre $(x,\tilde S)$ et $(x,S)$ est inférieure à +$\varepsilon$ et telle que les itérations parallèles de $G_{f_u}$ depuis +$(x,\tilde S)$ mènent au point $(x',S')$. 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 +configuration de $\Bool^{\mathsf{N}}$ obtenue depuis $(x,S)$ après $t_1$ +itérations +parallèles de $G_{f_u}$. +Comme $\textsc{giu}(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$. +$(x'',S'')$ après $t_2$ itérations de $G_{f_u}$. 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 +Il est évident que $(x',s')$ est atteint depuis $(x,\tilde S)$ après +$t_1+t_2$ itérations parallèles de $G_{f_u}$. Puisque $\tilde s_t=s_t$ pour $t<t_1$, grâce au choix de $t_1$, -on a $d((S,x),(\tilde -S,x))<\epsilon$. -Par conséquent, $G_f$ est transitive. +on a $d((x,S),(x,\tilde S))<\epsilon$. +Par conséquent, $G_{f_u}$ est transitive. $\Longrightarrow$ Démontrons la contraposée. -Si $\Gamma(f)$ n'est pas fortement connexe, alors +Si $\textsc{giu}(f)$ n'est pas fortement connexe, alors il existe deux configurations $x$ et $x'$ telles qu'aucun chemin de -$\Gamma(f)$ ne mène de $x$ à $x'$. +$\textsc{giu}(f)$ ne mène de $x$ à $x'$. Soient $S$ et $S'$ deux stratégies et $\varepsilon \in ]0;1[$. -Alors, pour tout $(S'',x'')$ tel que -$d((S'',x''),(S,x))<\varepsilon$ on a $x''$ qui est égal à $x$. -Comme il n'existe aucun chemin de $\Gamma(f)$ +Alors, pour tout $(x'',S'')$ tel que +$d((x'',S''),(x,S))<\varepsilon$ on a $x''$ qui est égal à $x$. +Comme il n'existe aucun chemin de $\textsc{giu}(f)$ qui mène de $x$ à $x'$, -les itérations de $G_f$ à partir de -$(S'', x'') = (S'', x)$ ne peuvent atteindre que des points -$(S''', x''')$ de $\mathcal{X}$ tels que $x''' \neq x'$, -et donc ne peuvent pas atteindre $(S', x')$. +les itérations de $G_{f_u}$ à partir de +$(x'',S'') = (x,S'')$ ne peuvent atteindre que des points +$(x''',S''')$ de $\mathcal{X}_u$ tels que $x''' \neq x'$, +et donc ne peuvent pas atteindre $(x',S')$. On peut remarquer que, du fait que $x''' \neq x'$, -elles n'atteignent que des points de $\mathcal{X}$ -dont la distance à $(S', x')$ est supérieure à 1. +elles n'atteignent que des points de $\mathcal{X}_u$ +dont la distance à $(x',S')$ est supérieure à 1. Pour tout entier naturel $t$, on a -$G_f^t(S'',x'') \neq (S',x')$. -Ainsi $G_f$ n'est pas transitive et +$G_{f_u}^t(x'',S'') \neq (x',S')$. +Ainsi $G_{f_u}$ n'est pas transitive et par contraposée, on a la démonstration souhaitée. \end{Proof} @@ -64,19 +64,19 @@ Prouvons à présent le théorème suivant: \begin{Proof} -Soit $f:\Bool^n\to\Bool^n$ telle que $G_f$ est transitive (\textit{i.e.} +Soit $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$ telle que $G_{f_u}$ est transitive (\textit{i.e.} $f$ appartient à $\mathcal{T}$). -Soit $(S,x) \in\mathcal{X}$ et $\varepsilon >0$. Pour +Soit $(x,S) \in\mathcal{X}_u$ et $\varepsilon >0$. 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. +$(x,\tilde S)$ et $(x,S)$ est inférieure à $\varepsilon$ et telle que +$(x,\tilde S)$ 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. +configuration obtenue après $t_1$ itérations de $G_{f_u}$ depuis $(x,S)$. +D'après la proposition précédente, $\textsc{giu}(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$. +que $x$ est atteint depuis $(x',S')$ après $t_2$ itérations de $G_{f_u}$. Soit alors la stratégie $\tilde S$ qui alterne les $t_1$ premiers termes de $S$ avec les $t_2$ premiers termes de $S'$. @@ -84,18 +84,18 @@ 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 +Il est évident que $(x,\tilde S)$ s'obtient à partir de $(x,\tilde S)$ après +$t_1+t_2$ itérations parallèles de $G_{f_u}$. Ainsi $(x,\tilde S)$ est un point périodique. Puisque $\tilde s_t$ est égal à $s_t$ pour $t<t_1$, d'après le -choix de $t_1$, on a $d((S,x),(\tilde S,x))<\epsilon$. +choix de $t_1$, on a $d((x,S),(x,\tilde S))<\epsilon$. \end{Proof} 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. +\label{Th:CaracIC:up} +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}