X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/review_prng.git/blobdiff_plain/2a4c35a90cbd9b41b4a730aafa519c8e28ea04ab..aa282765b88f449ee03206e4995360fcced37f56:/review_prng.tex?ds=sidebyside

diff --git a/review_prng.tex b/review_prng.tex
index d4acd30..158f90b 100644
--- a/review_prng.tex
+++ b/review_prng.tex
@@ -3,7 +3,7 @@
 \usepackage[standard]{ntheorem}
 \usepackage[english]{babel}
 
-
+\usepackage{stmaryrd}
 \usepackage{amsmath}
 \usepackage{color}
 \usepackage{dsfont}
@@ -27,9 +27,9 @@
 \section{Introduction}
 
 
-\section{Topology}
+\section{Topologycal Study of Disorder}
 
-\subsection{Historical context}
+\subsection{Historical Context}
 
 Pseudorandom number generators are recurrent sequences having a disordered behavior.
 
@@ -52,113 +52,102 @@ More precisely, his theorem states that, considering Eq.~\eqref{sdd} with a func
 $f:I \longrightarrow I$ continuous on the line segment $I$, the absence of
 any 2-cycle implies the convergence of the discrete dynamical system.
 
-
-%  
-%  
-%    \begin{block}{Convergence}
-%      \begin{itemize}
-%        \item $f$ monotone
-%        \item Applications contractantes
-%        \item Coppel: Pas de 2-cycle $\Rightarrow$ convergence
-%      \end{itemize}
-%    \end{block}
-%}
-
-
-
-%\frame{
-%  \frametitle{3-cycle implique chaos}
-%  \begin{alertblock}{Period Three Implies Chaos (Li et Yorke, 1975)}
-%S'il y a un point de période 3, alors il y a un point de n'importe quelle période
-%  \end{alertblock}
-%  
-%  \uncover<2->{
-%  \begin{exampleblock}{Remarques}
-%  \begin{itemize}
-%    \item Désordre lié à la multiplicité des périodes
-%    \item \`A AND, on étudie des ``systèmes itératifs'' pour le calcul distribué, généralisation des suites récurrentes
-%  \end{itemize}
-%  \end{exampleblock}
-%  }
-%}
-
-
-
-
-
-%%\subsection*{Réécriture des systèmes itératifs}
-
-%%\frame{
-%%  \frametitle{Les systèmes itératifs: généralisation}
-%%  \begin{block}{Les systèmes itératifs en toute généralité}
-%%  La formulation suivante englobe tous les modes d'itérations imaginables:
-%%  $$\left\{
-%%  \begin{array}{l}
-%%    x^0 \in \mathcal{X}\\
-%%    x^{n+1} = f^n(x^0, \hdots, x^n)
-%%  \end{array}
-%%  \right.$$
-%%  où $f^n:\mathcal{X}^{n+1}\rightarrow \mathcal{X}$
-%%  \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 ?
-%   }
-%}
-
-
-
-
+This theorem establish a clear link between the existence of a cycle of 
+a given length and the convergence of the system. In other words, between
+cycles and order. Conversely, Li and Yorke have established in 1975~\cite{Li75} that
+the presence of a point of period three implies chaos in the same situation
+than previously. By chaos, they mean the existence of points of any 
+period: this kind of disorder, which is the first occurrence of the
+term ``chaos'' in the mathematical litterature, is thus related to the 
+multiplicity of periods. Since that time, the mathematical theory of
+chaos has known several developments to qualify or quantify the richness
+of chaos presented by a given discrete dynamical system, one of the most
+famous work, although old, being the one of Devaney~\cite{devaney}.
+
+\subsection{Iterative Systems}
+
+In the distributed computing community, dynamical systems have been
+generatized to take into account delay transmission or heterogeneous
+computational powers. Mathematically, the intended result is often one 
+fixed point resulting from the iterations of a given function over a
+Boolean vector, considering that:
+\begin{itemize}
+\item at time $t$, $x^{t}$ is computed using not only $x^{t-1}$, but 
+potentially any $x^{k}, k<t$, due to delay transmission,
+\item not all the components of $x^{t}$ are supposed to be updated at
+each iteration: each component represents a unit of computation, and 
+these units have not the same processing frequency.
+\end{itemize} 
+
+These considerations lead to the following definition of an iterative
+system.
+
+\begin{definition}
+Iterative systems on a set $\mathcal{X}$ are defined by
+$$\left\{
+  \begin{array}{l}
+    x^0 \in \mathcal{X}\\
+    x^{n+1} = f^n(x^0, \hdots, x^n)
+  \end{array}
+ \right.$$
+where $f^n:\mathcal{X}^{n+1}\rightarrow \mathcal{X}$.
+\end{definition}
+
+Some particular cases of these iterative systems are well documented,
+namely the serial, parallel, or chaotic modes.
+In the serial mode, each component is updated one by one, whereas the
+parallel mode consists in updating all the components at each iteration,
+leading to an usual discrete dynamical system.
+These modes are compiliant with the definition above, 
+
+On appelle \emph{itérations parallèles} \index{itérations!parallèles} de $f$ sur 
+$\mathcal{X}$ toute itération synchrone $\Sigma = (\mathcal{X}, \mathcal{F})$ 
+telle que la suite $\mathcal{F}$ est constante égale à $f: \X \to \X$.
+On parle encore d'itérations parallèles $\left(\mathcal{X},f\right)$.
+
+
+
+Finally, iterative systems in chaotic mode, simply called chaotic iterations,
+ are defined as follows.
+ 
+
+\begin{definition}
+Let $f: \mathds{B}^\mathsf{N} \longrightarrow \mathds{B}^\mathsf{N}$ and 
+$S \subset \mathcal{P} \left(\llbracket1,\mathsf{N}\rrbracket\right)^\mathds{N}$. 
+\emph{Chaotic iterations} are defined by:
+$$\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{ if } i \notin S^n\\
+f(x^{n-1})_{i} & \textrm{ if } i \in S^n
+\end{array}
+\right.
+\end{array}
+\right.$$
+\end{definition}
+
+\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 questionning has led to a first necessary condition of non convergence.
+
+\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,
+\item or $S$ is not pseudo-periodic.
+\end{itemize}
+\end{proposition}
+
+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 rewriten as simple discrete dynamical systems, as follows.