-
-
-%% \end{block}
-%%\uncover<2->{
-%%Différents modes d'itérations: séries, parallèles, chaotiques, asynchrones...
-%%}
-%%}
-
-
-
-
-
-
-
-
-
-
-%\subsection*{Cas des Itérations chaotiques}
-%\frame{
-% \frametitle{Les « itérations chaotiques »}
-% \begin{block}{Définition (Itérations chaotiques)}
-% Soient $f: \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$ et $S \subset \mathcal{P} \left(\llbracket1,\mathsf{N}\rrbracket\right)^\mathds{N}$. Les \emph{itérations chaotiques} sont:
-%$$\left\{
-%\begin{array}{l}
-%x^0 \in \mathds{B}^\mathsf{N} \\
-%\forall n \in \mathds{N}^*, \forall i \in \llbracket 1; \mathsf{N} \rrbracket, x^{n}_i = \left\{
-%\begin{array}{ll}
-%x^{n-1}_{i} & \textrm{ si } i \notin S^n\\
-%f(x^{n-1})_{i} & \textrm{ si } i \in S^n
-%\end{array}
-%\right.
-%\end{array}
-%\right.$$
-%\end{block}
-%%\uncover<2->{
-%%Itérations chaotiques et théorie du chaos: a priori, rien à voir.
-%%}
-%%\uncover<3->{Y a-t-il un lien ?}\uncover<4->{ Pour quoi faire ?}
-%}
-
-
-
-
-
-%\frame{
-% \frametitle{Non-convergence des IC}
-% \begin{alertblock}{Théorème (Condition nécessaire de non-convergence)}
-% % Soit $f : \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$ et $S \in \mathcal{S}$.
-% Si les itérations chaotiques $\left(f,(x^0,S)\right)$ sont non convergentes, alors:
-%\begin{itemize}
-%\item soit $f$ n'est pas contractante,
-%\item soit $S$ n'est pas pseudo-périodique (complète).
-%\end{itemize}
-% \end{alertblock}
-% \uncover<2->{
-% Quelle quantité de désordre ?
-% }
-%}
-
-
-
-
-
-
-
-
-
-
-%\frame{
-%\frametitle{Présentation du problème}
-
-%\begin{tabular}{c||c}
-%MATHS DISCRÈTES & TOPOLOGIE MATHÉMATIQUE \tabularnewline
-%\hline
-%\multirow{2}{5cm}{\centering $f: \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$} & $(\mathcal{X},\tau)$ espace topologique\\
-%& $f : \mathcal{X} \to \mathcal{X}$ continue pour $\tau$\\
-%\hline
-%$S \in \mathcal{S} = \llbracket 1,\mathsf{N}\rrbracket^\mathds{N}$ & \multirow{2}{5cm}{\centering $x^0 \in \mathcal{X}$} \\
-%$x^0 \in \mathds{B}^\mathds{N}$ & \\
-%\hline
-%$x_i^{n+1} = \left\{ \begin{array}{ll} x^{n}_{i} & \textrm{ si } i \neq S^n\\ f(x^{n})_{i} & \textrm{ si } i = S^n \end{array} \right.$ & $\forall n \in \mathds{N}, x^{n+1} = f(x^n)$ \\
-%\end{tabular}
-
-%}
-
-
-
-
-
-
-%\frame{
-%\frametitle{Définitions et notations}
-%\begin{block}{Introduisons quelques fonctions...}
-%\begin{itemize}
-%\item décalage: $\sigma : \mathcal{S} \longrightarrow \mathcal{S}, (S^n)_{n \in \mathds{N}} \mapsto (S^{n+1})_{n \in \mathds{N}}$.
-%\item initiale: $i : \mathcal{S} \longrightarrow \llbracket 1 ; \mathsf{N} \rrbracket, (S^n)_{n \in \mathds{N}} \mapsto S^0$
-%\item $F_f : \llbracket 1 ; \mathsf{N} \rrbracket \times \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N},$ $$(k,E) \longmapsto \left( E_j.\delta(k,j) + f(E)_k.\overline{\delta (k,j)} \right)_{j \in \llbracket 1 ; \mathsf{N} \rrbracket}$$
-%\end{itemize}
-%où $\delta(x,y) = \left\{\begin{array}{ll}
-%0 & \textrm{ si } x=y, \\
-%1 & \textrm{ sinon.}
-% \end{array}\right.
-%$
-%\end{block}
-%}
-
-
-
-
-%\frame{
-%\frametitle{Modélisation des IC}
-%\begin{alertblock}{Modélisation des IC en topologie}
-%Soit $\mathcal{X} = \llbracket 1 ; \mathsf{N} \rrbracket^\mathds{N} \times \mathds{B}^\mathsf{N},$ et $G_f\left(S,E\right) = \left(\sigma(S), F_f(i(S),E)\right).$
-
-
-%On modélise les itérations chaotiques $\left(f, (S,x^0)\right)$ par le système dynamique discret:
-%$$\left\{
-%\begin{array}{l}
-%X^0 = (S,x^0) \in \mathcal{X}, \\
-%\forall k \in \mathds{N}, X^{k+1} = G_f(X^k).
-%\end{array}
-%\right.$$
-%\end{alertblock}
-
-% \uncover<2>{
-% On peut donc étudier leur désordre topologique.
-% }
-%}
-
-
-
-
-
-%\frame{
-% \frametitle{Métrique et continuité}
-
-%Distance sur $\mathcal{X}:$
-%$$d((S,E);(\check{S};\check{E})) = d_e(E,\check{E}) + d_s(S,\check{S})$$
-
-%\noindent où $\displaystyle{d_e(E,\check{E}) = \sum_{k=1}^\mathsf{N} \delta (E_k, \check{E}_k)}$, ~~et~ $\displaystyle{d_s(S,\check{S}) = \dfrac{9}{\textsf{N}} \sum_{k = 1}^\infty \dfrac{|S^k-\check{S}^k|}{10^k}}$.
-%%\end{block}
-
-%\vspace{0.5cm}
-
-%\begin{alertblock}{Théorème}
-%La fonction $G_f : (\mathcal{X},d) \to (\mathcal{X},d)$ est continue.
-%\end{alertblock}
-
-%}
-
-
-
-% \frame{
-% \frametitle{\'Etude de $(\mathcal{X},d)$}
-% \begin{block}{Propriétés de $(\mathcal{X},d)$}
-% \begin{itemize}
-% \item $\mathcal{X}$ est infini indénombrable
-% \vspace{0.15cm}
-% \item $(\mathcal{X},d)$ est un espace métrique compact, complet et parfait
-% \end{itemize}
-% \end{block}
-%
-% \vspace{0.5cm}
-%
-% \begin{block}{\'Etude de $G_{f_0}$}
-% $G_{f_0}$ est surjective, mais pas injective \vspace{0.3cm}\newline $\Rightarrow (\mathcal{X},G_{f_0})$ pas réversible.
-% \end{block}
-
-% }
-
-
-
-%%\frame{
-%% \frametitle{Etude des périodes}
-%% \begin{block}{Multiplicité des périodes ?}
-%% Soit $f_0:\mathds{B}^\mathsf{N} \rightarrow \mathds{B}^\mathsf{N}$ la négation vectorielle.
-%% \begin{itemize}
-%% \item $\forall k \in \mathds{N}, Per_{2k+1}(G_{f_0}) = \varnothing, card\left(Per_{2k+2}(G_{f_0})\right)>0$ \vspace{0.3cm} \linebreak $\Rightarrow G_{f_0}$ pas chaotique sur $\mathcal{X}$
-%% \item Cependant :
-%% \begin{itemize}
-%% \item Il y a chaos sur $\mathcal{X}^G = \mathcal{P}\left(\llbracket 1,\mathsf{N}\rrbracket\right)^\mathds{N}\times \mathds{B}^\mathsf{N}$.
-%% \item $G_{f_0}$ possède plus de $n^2$ points périodiques de période $2n$.
-%% \end{itemize}
-%% \end{itemize}
-%% \end{block}
-%% \uncover<2->{
-%% Cette multiplicité des périodes n'est pas le désordre complet...
-%% }
-%%}
-
-
-
-%\subsection*{Approche type Devaney/Knudsen}
-
-%\frame{
-% \frametitle{Les approches Devaney et Knudsen}
-% \begin{block}{3 propriétés pour de l'imprévisibilité}
-% \begin{enumerate}
-% \item \emph{Indécomposabilité.} On ne doit pas pouvoir simplifier le système
-% \begin{itemize}
-% \item Impossible de diviser pour régner
-% \item Des orbites doivent visiter tout l'espace
-% \end{itemize}
-% \item \emph{Élément de régularité.}
-% \begin{itemize}
-% \item Contrecarre l'effet précédent
-% \item Des points proches \textit{peuvent} se comporter complètement différemment
-% \end{itemize}
-% \item \emph{Sensibilité.} Des points proches \textit{peuvent} finir éloignés
-% \end{enumerate}
-% \end{block}
-%}
-
-
-%\frame{
-% \frametitle{Exemple : définition de Devaney}
-%\begin{enumerate}
-%\item \emph{Transitivité:} Pour chaque couple d'ouverts non vides $A,B \subset \mathcal{X}$, il existe $k \in \mathbb{N}$ tel que $f^{(k)}(A)\cap B \neq \varnothing$
-%\item \emph{Régularité:} Les points périodiques sont denses
-%\item \emph{Sensibilité aux conditions initiales:} Il existe $\varepsilon>0$ tel que $$\forall x \in \mathcal{X}, \forall \delta >0, \exists y \in \mathcal{X}, \exists n \in \mathbb{N}, d(x,y)<\delta \textrm{ et } d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon$$
-%\end{enumerate}
-%}
-
-%\frame{
-% \frametitle{Systèmes intrinsèquement compliqués}
-% \begin{block}{Définitions de l'indécomposabilité}
-% \begin{itemize}
-% \item \emph{Indécomposable}: pas la réunion de deux parties non vides, fermées et t.q. $f(A) \subset A$
-% \item \emph{Totalement transitive}: $\forall n \geqslant 1$, l'application composée $f^{(n)}$ est transitive.
-% \item \emph{Fortement transitif}:
-%$\forall x,y \in \mathcal{X},$ $\forall r>0,$ $\exists z \in B(x,r),$ $\exists n \in \mathbb{N},$ $f^{(n)}(z)=y.$
-% \item \emph{Topologiquement mélangeant}: pour toute paire d'ouverts disjoints et non vides $U$ et $V$, il existe $n_0 \in \mathbb{N}$ tel que $\forall n \geqslant n_0, f^{(n)}(U) \cap V \neq \varnothing$.
-% \end{itemize}
-% \end{block}
-%}
-
-
-
-
-%\frame{
-%\frametitle{Stabilité et expansivité}
-% \begin{block}{Définitions de la sensibilité}
-% \begin{itemize}
-% \item $(\mathcal{X},f)$ est \emph{instable} si tous ses points le sont: $\forall x \in \mathcal{X},$ $\exists \varepsilon >0,$ $\forall \delta > 0,$ $\exists y \in \mathcal{X},$ $\exists n \in \mathbb{N},$ $d(x,y)<\delta$ et $d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon$
-% \item $(\mathcal{X},f)$ est \emph{expansif} si
-%$\exists \varepsilon >0,$ $\forall x \neq y,$ $\exists n \in \mathbb{N},$ $d(f^{(n)}(x),f^{(n)}(y)) \geqslant \varepsilon$
-% \end{itemize}
-% \end{block}
-%}
-
-%%\frame{
-%% \frametitle{Des systèmes imprévisibles}
-%% \begin{block}{Définitions des systèmes dynamiques désordonnés}
-%% \begin{itemize}
-%% \item \emph{Devaney:} $(\mathcal{X},f)$ est sensible aux conditions initiales, régulier et transitif
-%% \item \emph{Wiggins:} $(\mathcal{X},f)$ est transitif et sensible aux conditions initiales
-%% \item \emph{Knudsen:} $(\mathcal{X},f)$ a une orbite dense et s'il est sensible aux conditions initiales
-%% \item \emph{expansif:} $(\mathcal{X},f)$ est transitif, régulier et expansif
-%% \end{itemize}
-%% \end{block}
-%%}
-
-
-
-%\subsection*{Autres approches}
-
-
-%\frame{
-% \frametitle{Selon Li et Yorke}
-% \begin{block}{Définitions}
-% \begin{description}
-%\item[Couple de Li-Yorke.] $(x,y)$ en est un quand: $\limsup_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))>0$ et $\liminf_{n \rightarrow +\infty} d(f^{(n)}(x), f^{(n)}(y))=0.$
-
-%\item[Ensemble brouillé.] $B \subset \mathcal{X}$ en est un si tout couple de points distincts de $B$ est de Li-Yorke.
-
-%\item[Systèmes de Li-Yorke.] $\mathcal{X}$ est compact et contient un ensemble brouillé indénombrable.
-%\end{description}
-%\end{block}
-%}
-
-
-
-
-
-
-%\frame{
-% \frametitle{Approche entropie topologique}
-% \begin{block}{Entropie topologique}
-% \begin{itemize}
-% \item $x,y \in \mathcal{X}$ sont ~$\varepsilon-$\emph{séparés en temps $n$} s'il existe $k \leqslant n$ tel que $d\left(f^{(k)}(x),f^{(k)}(y)\right)>\varepsilon$.
-% \item Les ensembles $(n,\varepsilon)-$séparé sont des ensembles de points qui seront tous $\varepsilon-$séparés en temps $n$
-% \item $s_n(\varepsilon,Y)$: cardinal maximal d'un ensemble $(n,\varepsilon)-$séparé $$h_{top}(\mathcal{X},f) = \displaystyle{\lim_{\varepsilon \rightarrow 0} \Big[ \limsup_{n \rightarrow +\infty} \dfrac{1}{n} \log s_n(\varepsilon,\mathcal{X})\Big]}$$
-% \end{itemize}
-% \end{block}
-%}
-
-
-
-
-%\frame{
-% \frametitle{Exposant de Lyapunov}
-%\begin{block}{L'exposant de Lyapunov}
-%$$\lambda(x^0) = \displaystyle{\lim_{n \to +\infty} \dfrac{1}{n} \sum_{i=1}^n \ln \left| ~f'\left(x^{i-1}\right)\right|}$$
-%Il doit être positif pour multiplier les erreurs
-%\end{block}
-%}
-
-
-
-
-
-%\subsection*{Etude des systèmes itératifs}
-
-%%\frame{
-%% \frametitle{IC et propriété de Devaney}
-%%\begin{alertblock}{Théorème}
-%%$G_{f_0}$ est régulier et transitif (Devaney).
-
-%%Sa sensibilité est $\geqslant \mathsf{N}-1$.
-%%\end{alertblock}
-
-%%\uncover<2->{
-%% \begin{exampleblock}{Question}
-%% $f_0$ est-elle la seule fonction dont le système itératif vérifie la condition de Devaney ?
-%% \end{exampleblock}
-%%
-%% \vspace{0.5cm}
-
-%%Pour y répondre, nous avons utilisé le graphe de tous les possibles par itérations chaotiques : le GTPIC.}
-%%}
-
-
-
-
-%%\frame{
-%% \frametitle{Nombre de fonctions imprévisibles}
-%% \begin{alertblock}{Caractérisation des IC imprévisibles selon Devaney}
-%%$G_f$ vérifie l'hypothèse de Devaney $\Leftrightarrow$ Son graphe des possibles est fortement connexe.
-
-%%$\Rightarrow$ Il y a $\left(2^\mathsf{N}\right)^{2^\mathsf{N}}$ IC chaotiques.
-%%\end{alertblock}
-%%}
-
-
-
-
-
-
-
-%\frame{
-% \frametitle{Etude topologique}
-% \begin{exampleblock}{Etude topologique des ICs}
-% \begin{itemize}
-% \item $\forall f \in \mathcal{C}$, $Per\left(G_f\right)$ est infini dénombrable, $G_f$ est fortement transitive, est chaotique selon Knudsen,
-% \item $\left(\mathcal{X}, G_{f_0}\right)$ est topologiquement mélangeant, expansif (constante 1), est chaotique selon Li-Yorke, a une entropie topologique infinie, un exposant de Lyapunov de $ln(\mathsf{N})$
-% \item Indécomposabilité, instabilité, chaos de Wiggins, de la multiplicité des périodes...
-% \end{itemize}
-% \end{exampleblock}
-%}
-
-
-
-
-
-
-
-%\frame{
-% \frametitle{Graphe de tous les possibles par IC}
-% \begin{center}
-% \includegraphics[scale=0.55]{14.Caracterisation_des_IC_chaotiques_selon_Devaney/grapheTPICver2.pdf}
-% \end{center}
-%}
-
-
+\emph{A priori}, there is no relation between these chaotic iterations
+and the mathematical theory of chaos recalled in the previous section.
+On our side, we have regarded whether these chaotic iterations can
+behave chaotically, as it is defined for instance by Devaney, and if so,
+in which applicative context this behavior can be profitable.
+This questioning has led to a first necessary condition of non convergence~\cite{GuyeuxThese10}.
+
+\begin{proposition}
+Let $f : \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$ and
+$S \in \llbracket 1, \mathsf{N} \rrbracket^{\mathds{N}}$.
+If the chaotic iterations $\left(f,(x^0,S)\right)$ are not convergent, then:
+\begin{itemize}
+\item either $f$ is not a contraction, meaning that there is no Boolean matrix
+ $M$ of size $\mathsf{N}$ satisfying $\forall x,y\in \mathds{B}^\mathsf{N}$,
+ $d(f(x),f(y)) \leqslant M d(x,y)$, where $d$ is here the ``vectorial distance''
+ defined by $d(x,y) = \left(\begin{array}{c} \delta(x_1,y_1)\\ \vdots \\ \delta(x_\mathsf{N},
+ y_\mathsf{N}) \end{array}\right)$, with $\delta$ the discrete metric defined by $\delta(x,y) = \left\{\begin{matrix} 1 &\mbox{if}\ x\neq y , \\ 0 &\mbox{if}\ x = y \end{matrix}\right.$, and $\leqslant$ is the inequality term by term~\cite{Robert}.
+\item or $S$ is not pseudo-periodic: it is not constituted by an infinite succession of finite sequences, each having any element of $\llbracket
+ 1, \mathsf{N} \rrbracket$ at least once.
+\end{itemize}
+\end{proposition}
+
+The second alternative of the proposition above concerns the strategy,
+which should be provided by the outside world. Indeed, in our opinion,
+chaotic iterations can receive a PRNG $S$ as input, and due to
+properties of disorder of $f$, generate a new pseudorandom sequence
+that presents better statistical properties than $S$. Having this
+approach in mind, we thus have searched vectorial Boolean iteration
+functions that are not contractions. The vectorial negation function
+$f_0:\mathds{B}^\mathsf{N} \longrightarrow \mathds{N}^\mathsf{N},$
+$(x_1, \hdots, x_\mathsf{N}) \longmapsto (\overline{x_1}, \hdots,
+\overline{x_\mathsf{N}}) $ is such a function, which served has a
+model in our further studies ($\overline{x}$ stands for the negation
+of the Boolean $x$).
+
+The quantity of disorder generated by such chaotic iterations, when
+satisfying the proposition above, has then been measured. To do so,
+chaotic iterations have first been rewritten as simple discrete
+dynamical systems, as follows.
+
+
+\subsection{Chaotic Iterations as Dynamical Systems}
+
+The problems raised by such a formalization can be summarized as
+follows.
+Chaotic iterations are defined in the discrete mathematics framework,
+considering $x^0 \in \mathds{B}^\mathds{N}$ and $S \in \mathcal{S} = \llbracket 1,\mathsf{N}\rrbracket^\mathds{N}$, and iterations having the
+form
+$$x_i^{n+1} = \left\{ \begin{array}{ll} x^{n}_{i} & \textrm{ si } i \neq S^n\\ f(x^{n})_{i} & \textrm{ si } i = S^n \end{array} \right.$$
+where $f: \mathds{B}^\mathsf{N} \to \mathds{B}^\mathsf{N}$.
+However, the mathematical theory of chaos takes place into a
+topological space $(\mathcal{X},\tau)$. It studies the iterations
+$x^0 \in \mathcal{X}$, $\forall n \in \mathds{N}, x^{n+1} = f(x^n)$,
+where $f : \mathcal{X} \to \mathcal{X}$ is continuous for the
+topology $\tau$.
+
+To realize the junction between these two frameworks, the following
+material has been introduced~\cite{GuyeuxThese10,bgw09:ip}:
+\begin{itemize}
+\item the shift function: $\sigma : \mathcal{S} \longrightarrow \mathcal{S}, (S^n)_{n \in \mathds{N}} \mapsto (S^{n+1})_{n \in \mathds{N}}$.
+\item the initial function, defined by $i : \mathcal{S} \longrightarrow \llbracket 1 ; \mathsf{N} \rrbracket, (S^n)_{n \in \mathds{N}} \mapsto S^0$
+\item and $F_f : \llbracket 1 ; \mathsf{N} \rrbracket \times \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N},$ $$(k,E) \longmapsto \left( E_j.\delta(k,j) + f(E)_k.\overline{\delta (k,j)} \right)_{j \in \llbracket 1 ; \mathsf{N} \rrbracket}$$
+\end{itemize}
+where $\delta$ is the discrete metric.
