From: couchot Date: Thu, 1 Sep 2016 09:33:43 +0000 (+0200) Subject: chapitre chaos repris X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/commitdiff_plain/d69000ebda300fc836232f34cebb88ddfce4ac98 chapitre chaos repris --- diff --git a/11FCT.tex b/11FCT.tex index 45d91c9..498af15 100644 --- a/11FCT.tex +++ b/11FCT.tex @@ -55,7 +55,8 @@ $f_j$ et qui permet de n'engendrer que des fonctions $f$ dont le graphe d'itérations $\textsc{giu}(f)$ est fortement connexe. -\begin{theorem}\label{th:Adrien} +\begin{restatable}{theorem}{thAdrien} +\label{th:Adrien} Soit $f$ une fonction de $\Bool^{\mathsf{N}}$ vers lui-même telle que: \begin{enumerate} \item @@ -68,11 +69,11 @@ chaque sommet de $\Gamma(f)$ est accessible depuis un sommet qui possède une boucle négative. \end{enumerate} Alors, $\textsc{giu}(f)$ est fortement connexe. -\end{theorem} +\end{restatable} La preuve de ce théorème est donnée en annexe~\ref{anx:sccg}. -Illustrons ce théorème par un exemple. On considère par le graphe d'interactions +Illustrons ce théorème par un exemple. On considère le graphe d'interactions $\Gamma(f)$ donné en figure~\ref{fig:Adrien:G}. Il vérifie le théorème~\ref{th:Adrien}: toutes les fonctions $f$ possédant un tel graphe d'interactions diff --git a/12TIPE.tex b/12TIPE.tex index 7ebcfde..afd6077 100644 --- a/12TIPE.tex +++ b/12TIPE.tex @@ -8,11 +8,11 @@ $\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 \[ F_{f_u}(x,i)=(x_1,\dots,x_{i-1},f_i(x),x_{i+1},\dots,x_\mathsf{N}). @@ -20,7 +20,7 @@ F_{f_u}(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$ +[\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,7 +29,7 @@ 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}$ +\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 @@ -39,8 +39,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 @@ -59,7 +59,7 @@ La section suivante introduit une métrique sur $\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 +67,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,8 +93,8 @@ 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 caractériser 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}$. @@ -103,16 +104,16 @@ $\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\}$, +\mathds{B}^n \textrm{ t. q. } 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\}$, +\mathds{B}^n \textrm{ t. q. } 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\}$. +\mathds{B}^n \textrm{ t. q. } G_{f_u} \textrm{ est chaotique} \right\}$. \end{itemize} -On énonce 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{guyeux10}. \begin{theorem} $G_{f_u}$ est transitive si et seulement si $\textsc{giu}(f)$ est fortement connexe. @@ -127,7 +128,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} diff --git a/15TSI.tex b/15TSI.tex index f2fe17b..138036f 100644 --- a/15TSI.tex +++ b/15TSI.tex @@ -7,7 +7,7 @@ On reprend ici le même plan que dans la section précédente. Dans le schéma généralisé, à la $t^{\textrm{ème}}$ itération, c'est l'ensemble -des $s_{t}^{\textrm{ème}}$ éléments (inclus dans $[n]$) qui +des $s_{t}^{\textrm{ème}}$ éléments (inclus dans $[{\mathsf{N}}]$) qui sont mis à jour (cf. équation~(\ref{eq:schema:generalise})). On redéfinit la fonction la fonction $F_{f_g}: \Bool^{\mathsf{N}} \times \mathcal{P}(\{1, \ldots, \mathsf{N}\}) @@ -36,7 +36,7 @@ configurations $x^t$ sont définies par la récurrence \] où la fonction $\sigma$ est définie comme à la section précédente. A nouveau, les itérations généralisées - de $f$ induites par $x^0$ et la stratégie $S$. + de $f$ induites par $x^0$ et la stratégie $S$ décrivent la même orbite que les itérations parallèles de $G_{f_g}$ depuis un point initial $X^0=(x^0,S)$ @@ -62,7 +62,8 @@ On considère l'espace $\mathcal{X}_g=\mathcal{P}(\{1, \ldots, {\mathsf{N}}\})^{ \Bool^{\mathsf{N}}$ et on définit la distance $d$ entre les points $X=(S,x)$ et $X'=(S',x')$ de $\mathcal{X}_g$ par -\[ + +\begin{equation} d(X,X')= d_H(x,x')+d_S(S,S'),~\textrm{où}~ \left\{ \begin{array}{l} @@ -70,7 +71,8 @@ d(X,X')= d_H(x,x')+d_S(S,S'),~\textrm{où}~ \displaystyle{d_S(S,S')=\frac{9}{{\mathsf{N}}}\sum_{t\in\Nats}\frac{|S_t \Delta S'_t|}{10^{t+1}}}. \end{array} \right.\,. -\] +\label{eq:distance:Xg} +\end{equation} La fonction $d$ est une somme de deux fonctions. La fonction $d_H$ est la distance de Hamming; il est aussi établi que la @@ -79,7 +81,7 @@ Ainsi, pour montrer que $d$ est aussi une distance, il suffit de montrer que $d_S$ en une aussi, ce qui est fait en annexe~\ref{anx:distance:generalise}. La section suivante caractérise les fonctions $f$ qui sont -chaotiques pour le schéma généralisées. +chaotiques pour le schéma généralisé. \subsection{Caractérisation des fonctions rendant chaotiques $G_{f_g}$ sur $\mathcal{X}_g$} @@ -88,13 +90,23 @@ en les adaptant à $G_{f_g}$. On a les théorèmes suivants dont les preuves sont données en annexe~\ref{anx:chaos:generalise}. -\begin{theorem} $G_{f_g}$ est transitive si et seulement si + + +\begin{restatable}{theorem}{caractransitivegeneralise} +\label{Theo:carac:transitive:gen} +$G_{f_g}$ est transitive si et seulement si $\textsc{gig}(f)$ est fortement connexe. -\end{theorem} +\end{restatable} -\begin{theorem} -\label{Prop: T est dans R:g} $\mathcal{T} \subset \mathcal{R}$. -\end{theorem} + + +\begin{restatable}{theorem}{caracsubgeneralise} +\label{Prop: T est dans R:g} + $\mathcal{T} \subset \mathcal{R}$. +\end{restatable} + +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}$] diff --git a/annexesccg.tex b/annexesccg.tex index 9d32b22..257f86c 100644 --- a/annexesccg.tex +++ b/annexesccg.tex @@ -59,8 +59,10 @@ $\textsc{giu}(f)^\alpha$ a un arc de $h(x)$ vers $h(y)$. \end{Proof} +On peut alors prouver le théorème: +\thAdrien* + \begin{Proof} -du Théorème~\ref{th:Adrien}. La preuve se fait par induction sur ${\mathsf{N}}$. Soit $f$ une fonction de $\Bool^{\mathsf{N}}$ dans lui-même et qui vérifie les hypothèses du théorème. @@ -106,7 +108,7 @@ D'après la seconde hypothèse, ${\mathsf{N}}$ n'a pas de boucle, \emph{i.e.}, la valeur de $f_{\mathsf{N}}(x)$ ne dépend pas de la valeur de $x_{\mathsf{N}}$. D'après la troisième hypothèse, -il existe $i\in \llbracket 1;{\mathsf{N}} \rrbracket$ tel que $G(f)$ a un arc de +il existe $i\in [{\mathsf{N}}]$ tel que $G(f)$ a un arc de $i$ vers ${\mathsf{N}}$. Ainsi, il existe $x \in \Bool^{\mathsf{N}}$ tel que $f_{{\mathsf{N}}i}(x) \neq 0$ et donc %$n$ n'est donc pas de degré zéro dans $G(f)$, \emph{i.e.} diff --git a/caracgeneralise.tex b/caracgeneralise.tex index 54d99af..3014a6b 100644 --- a/caracgeneralise.tex +++ b/caracgeneralise.tex @@ -1,9 +1,8 @@ -Commençons par caractériser l'ensemble $\mathcal{T}$ des fonctions transitives: +Commençons par caractériser l'ensemble $\mathcal{T}$ des fonctions transitives dans le cas +des itérations généralisées. -\begin{theorem} $G_{f_g}$ est transitive si et seulement si - $\textsc{gig}(f)$ est fortement connexe. -\end{theorem} +\caractransitivegeneralise* \begin{Proof} @@ -55,9 +54,7 @@ par contraposée, on a la démonstration souhaitée. Prouvons à présent le théorème suivant: -\begin{theorem} -\label{Prop: T est dans R:gp} $\mathcal{T} \subset \mathcal{R}$. -\end{theorem} +\caracsubgeneralise* \begin{Proof} @@ -88,10 +85,4 @@ 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:gp} -Soit $f:\Bool^{\mathsf{N}}\to\Bool^{\mathsf{N}}$. La fonction $G_{f_g}$ est chaotique -si et seulement si $\textsc{gig}(f)$ est fortement connexe. -\end{theorem} += \mathcal{T}$. \ No newline at end of file diff --git a/demandeInscription/president.tex b/demandeInscription/president.tex index 4dd1c77..c01b381 100644 --- a/demandeInscription/president.tex +++ b/demandeInscription/president.tex @@ -41,7 +41,8 @@ Par le présent courrier, je vous sollicite pour une inscription à l'Habilitation à Diriger des Recheches (HDR). Je vous informe que je n'ai effectué aucune demande inscription dans une autre université cette année universitaire et que cette requête -constitue ma première demande. +constitue ma seconde demande. Ma première demande d'inscription +a été formulé le 31 aout 2015. diff --git a/demandeInscription/synthese.tex b/demandeInscription/synthese.tex index 58ad6b7..4a31101 100755 --- a/demandeInscription/synthese.tex +++ b/demandeInscription/synthese.tex @@ -148,9 +148,7 @@ Je suis membre de l'équipe Algorithmique Numérique Distribuée (AND) du Département d'Informatique des Systèmes Complexes (DISC) du laboratoire FEMTO-ST. Je relève de l'école doctorale 37 Sciences Pour l'Ingénieur et Microtechniques (SPIM) de l'UFC. -Mon directeur de recherche pour cette HDR est Pr. J. {\sc Bahi} -du département DISC. Son avis, ainsi que celui du directeur de l'équipe (Pr. R. {\sc Couturier}, du directeur de l'école doctorale (PR. P. {\sc Lutz}) -et du directeur du département (Pr. O. {\sc Kouchnarenko}) sont donnés en annexes. +Les avis du directeur de l'équipe AND (Pr. R. {\sc Couturier} et du directeur du département DISC (Pr. O. {\sc Kouchnarenko}) sont donnés en annexes. % \subsection{Avis du directeur de l'équipe}\label{sec:avis:directeur:equipe} diff --git a/main.tex b/main.tex index 33a3ba1..628e4f9 100644 --- a/main.tex +++ b/main.tex @@ -221,15 +221,16 @@ au chaos} La suite de ce document se focalise sur des systèmes dynamiques discrets qui ne convergent pas. Parmi ceux-ci se trouvent ceux qui sont \og chaotiques\fg{}. La première section de ce chapitre rappelle ce que sont les systèmes -dynamiques chaotiques et leur caractéristiques. Celles-ci dépendent -tout d'abord de la stratégie itérée. La section~\ref{sec:TIPE12} -se focalise sur le schéma unaire tandis que la section~\ref{sec:chaos:TSI} -considère le mode généralisé. Pour chacun de ces modes, -une distance est définie. Finalement, la section~\ref{sec:11FCT} +dynamiques chaotiques et leur caractéristiques. +La section~\ref{sec:TIPE12}, qui est une reformulation de~\cite{guyeux10}, +se focalise sur le schéma unaire. Elle est rappelée pour avoir un document se +suffisant à lui-même. +La section~\ref{sec:chaos:TSI} étend ceci au mode généralisé. Pour chacun de ces modes, +une métrique est définie. Finalement, la section~\ref{sec:11FCT} exhibe des conditions suffisantes premettant d'engendrer des fonctions chaotiques seon le mode unaire. Les sections~\ref{sec:TIPE12} et~\ref{sec:11FCT} ont été publiées -dans~\cite{bcgr11:ip}. +dans~\cite{bcg11:ij,bcgr11:ip}. \section{Systèmes dynamiques chaotiques selon Devaney} \label{subsec:Devaney} @@ -354,13 +355,12 @@ du chapitre 8} \chapter{Preuves sur les systèmes chaotiques} -\section{Continuité de $G_f$ dans $(\mathcal{X}_u,d)$}\label{anx:cont} -\input{annexecontinuite.tex} +%\section{Continuité de $G_f$ dans $(\mathcal{X}_u,d)$}\label{anx:cont} +%\input{annexecontinuite.tex} -\section{Caractérisation des fonctions $f$ rendant chaotique $G_{f_u}$ dans $(\mathcal{X}_u,d)$}\label{anx:chaos:unaire} -\input{caracunaire.tex} - +%\section{Caractérisation des fonctions $f$ rendant chaotique $G_{f_u}$ dans $(\mathcal{X}_u,d)$}\label{anx:chaos:unaire} +%\input{caracunaire.tex} \section{Preuve que $d$ est une distance sur $\mathcal{X}_g$}\label{anx:distance:generalise} \input{preuveDistanceGeneralisee} @@ -370,7 +370,7 @@ du chapitre 8} \input{caracgeneralise.tex} -\section{Théorème~\ref{th:Adrien}}\label{anx:sccg} +\section{Conditions suffisantes pour un $\textsc{giu}(f)$ fortement connexe \label{anx:sccg}} \input{annexesccg} diff --git a/preuveDistanceGeneralisee.tex b/preuveDistanceGeneralisee.tex index 9b7f3b6..c8a6c5c 100644 --- a/preuveDistanceGeneralisee.tex +++ b/preuveDistanceGeneralisee.tex @@ -3,7 +3,8 @@ on définit \[ \displaystyle{d_S(S,S')=\frac{9}{{\mathsf{N}}}\sum_{t\in\Nats}\frac{|S_t \Delta S'_t|}{10^{t+1}}}. \] -Montrons que $d_S$ est une distance sur $\mathcal{P}(\{1, \ldots, {\mathsf{N}}\})$. +Montrons que $d_S$ est une distance sur $\mathcal{P}(\{1, \ldots, {\mathsf{N}}\})$ et ainsi +que $d$ définie à l'equation~(\ref{eq:distance:Xg}) est une distance.