From bba3979e3f3ee00ce44b16d13b4e61e434310b61 Mon Sep 17 00:00:00 2001
From: guyeux <guyeux@gmail.com>
Date: Thu, 31 May 2012 13:59:51 +0200
Subject: [PATCH] Avan

---
 review_prng.tex | 86 ++++++++++++++++++++++++-------------------------
 1 file changed, 42 insertions(+), 44 deletions(-)

diff --git a/review_prng.tex b/review_prng.tex
index d4acd30..a5d1388 100644
--- a/review_prng.tex
+++ b/review_prng.tex
@@ -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,53 +52,51 @@ 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.
 
+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}
 
-%  
-%  
-%    \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...
-- 
2.39.5