initialisation

diff --git a/Equivalence.tex b/Equivalence.tex
new file mode 100644 (file)
index 0000000..d315b6b
--- /dev/null
+++ b/Equivalence.tex
@@ -0,0 +1,294 @@
+%%%%%%%% Sample LaTeX input for Complex Systems %%%%%%%%%%% 
+%
+% This is a LaTeX input file  
+% Text following % on a particular line is treated as a comment, and 
+% ignored by LaTeX.  
+% You do not need to type any text that follows a % 
+% 
+\documentclass{article}
+
+\usepackage{epsf}
+\usepackage{complex-systems}
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{algorithm}
+\usepackage{algorithmic}
+\usepackage[utf8]{inputenc}
+\usepackage{color}
+\usepackage{framed}
+
+% complex-systems.sty is the special macro package for Complex Systems.
+% epsf.sty is the preferred graphics import method
+
+% complex-systems.sty defines the following defaults:
+% \newtheorem{theorem}{Theorem}
+% \newtheorem{lemma}{Lemma}
+% \newtheorem{corollary}{Corollary}
+% \newtheorem{example}{Example}
+% \newtheorem{proposition}{Proposition}
+
+%%% Personal definitions
+\newcommand{\Alg}[1]{Algorithm~\ref{#1}}
+\newcommand{\Sec}[1]{Section~\ref{#1}}
+\newcommand{\Equ}[1]{Equ.(\ref{#1})}
+\newcommand{\Prop}[1]{Prop.~\ref{#1}}
+\newcommand{\Th}[1]{Theorem~\ref{#1}}
+\newcommand{\Fig}[1]{Fig.~\ref{#1}}
+\newcommand{\Def}[1]{Def.~\ref{#1}}
+
+\newcommand{\astep}{\stackrel{a.s}{\mapsto}}
+\newcommand{\alead}{\stackrel{a.i}{\leadsto}}
+\newcommand{\aconv}{\stackrel{a.cv}{\Longrightarrow}}
+\newcommand{\notaconv}{\stackrel{a.cv}{\Longrightarrow}\hspace{-5mm}/\hspace{3.2mm}}
+\newcommand{\boolprod}{\stackrel{\sim}{\prod}}
+\newcommand{\cycle}{Cycle}
+\newcommand{\pcycle}{p\_Cyc}
+\newcommand{\sub}{S}
+
+\def\N{\mathbb{N}}
+\def\R{\mathbb{R}}
+
+\definecolor{shadecolor}{rgb}{0.95,0.95,0.95}
+\newenvironment{Algo}{\begin{center}\begin{minipage}[h]{0.95\columnwidth}\begin{shaded}\begin{tabbing}%
+  \hspace{3mm}\=\hspace{3mm}\=\hspace{3mm}\=\hspace{3mm}\=\hspace{3mm}\=\hspace{3mm}\=\hspace{3mm}\= \kill} %
+ { \end{tabbing}\vspace{-1em}\end{shaded}\end{minipage}\end{center}\vspace{-1em}}
+
+%%%
+%%% MAIN DOCUMENT
+%%%
+\begin{document}
+
+% 
+% The format for a general title is slightly complicated; 
+% here first is a comment giving a simple example: %
+% \title{Sample Paper for Complex Systems} 
+% \author{\authname{First Author}\\[2pt]
+% \authadd{University Department, University Name, Address,}\\ 
+% \authadd{City, State ZIP/Zone, Country}\\ 
+% \authadd{and}\\
+% \authadd{Group, Company, Address, City, State ZIP/Zone, Country}\\ 
+% \and 
+% \authname{Second Author}\\ 
+% \authname{Third Author}\\ 
+% \authname{Fourth Author}\\[2pt]
+% \authadd{Group, Laboratory, Address, City, State ZIP/Zone, Country} 
+% }
+% \markboth{F. Author, S. Author, T. Author, and F. Author}
+% {Sample Paper for Complex Systems}
+% \maketitle 
+
+% Here is a more complete case:
+
+\title{Transformation of Asynchronous System with Delays to Asynchronous System
+  without Delays} 
+% Use \\ to indicate line breaks in titles longer than about 
+% 55 characters. 
+% Lines throughout the title section should be broken so that 
+% successive lines are progressively shorter. 
+% Use \thanks for footnotes to the title. Put acknowledgments at the 
+% end of the paper. 
+%
+% \thanks{The title serves as a headline for the paper: many readers 
+% use it to decide whether to look at the paper. Avoid excessively 
+% general, technical, or cutesy titles. Questions are acceptable as 
+% titles. Capitalize the first letters of important words only. 
+% Funding and personal acknowledgments go at the end of the paper. 
+% Use footnotes to the title only for statements such as ``This paper 
+% was based on a talk given at the conference on$\ldots$'' or ``Part 1 
+% in this series of papers appeared in$\ldots$''}}
+
+\author{\authname{Sylvain Contassot-Vivier% 
+\thanks{Electronic mail address: contasss@loria.fr}}
+\\[2pt] 
+% Use \\[2pt] to end the line and add space between author and affiliation 
+\authadd{Loria UMR 7503, Université Lorraine}\\ 
+\authadd{Campus Scientifique - BP 239}\\
+\authadd{54506 Vandoeuvre-lès-Nancy, France}
+%\thanks{Give complete affiliation and mailing address, including 
+%country. Capitalize important words and proper names only. (Use 
+%standard two-letter abbreviations for state names.) For foreign 
+%addresses, give as much as possible in English. }\\ 
+%\authadd{and}\\ 
+%\authadd{Group, Company, Address, City, State ZIP/Zone, Country}\\ 
+%\and
+% precede the second set of authors with \and.
+%\authname{Second Author} \\ 
+%\authname{Third Author}\\ 
+%\authname{Fourth Author}\\[2pt]
+% Each author name goes on a separate line. 
+%\authadd{Group, Laboratory, Address, City, State ZIP/Zone, Country} 
+% Put no ``.'' at the end of any address. 
+}
+
+\maketitle    
+% End title section
+
+% The following specifies the running headings 
+\markboth{S. Contassot-Vivier}{Equivalence between asynchronous systems} 
+
+% Each running heading should be less than about 50 characters long. 
+% If necessary, give a shortened version of the title. Do not use 
+% abbreviations. 
+%
+% If they will fit, include complete author names; otherwise use 
+% initials only. If abbreviated names do not fit, truncate the author 
+% list and end with ``and others''.
+
+\begin{abstract} 
+  This  paper presents  a  transformation process  of  any asynchronous  complex
+  system with  delays to an  equivalent asynchronous system without  delays. The
+  interest of such equivalence lies in the suppression of the history dependency
+  of the system in  its evolution. This has an important impact  on the study of
+  the dynamic of  the system.  The equivalence is  illustrated on representative
+  examples and  the gain is pointed  out by a comparison  between algorithms for
+  attraction basin determination.
+\end{abstract}
+
+% The text of the paper follows. It is usually easiest to put 
+% everything in the same file. The file may however need to be 
+% split for some computer mail systems. 
+% Automatic section numbering in the LaTeX source is encouraged, 
+% but is not essential.
+
+\section{Introduction} 
+\label{intro}
+
+The different models of complex systems  are essential in the study of many real
+life  systems,  whatever  they  are  natural or  man-made.   % As  a  particularly
+% interesting example,  parallel iterative algorithms  play a central role  in the
+% domain of scientific computation and simulation. Indeed, such algorithms are the
+% key to high accuracy and  large scale simulations of complex phenomena.
+In  this paper,  we  focus  on the  discrete-time  discrete-state systems.   The
+discrete nature  of the  states is not  a limitation  of the model  according to
+potential  applications in computer  science as  current computers  actually use
+discrete  number representations.  However,  the study  of their  behavior stays
+difficult, especially due to the fast combinatorial explosion in possible states
+of such  systems. Moreover,  different models exist  that can take  into account
+some specific  behaviors such as asynchrony  between the elements  of the system
+and  also  communication delays  between  the  elements.  Such models  are  very
+interesting because  they are among  the most general  ones. However, it  is yet
+harder to study them, especially  the ones including communication delays due to
+the dependence of the history of the system in its evolution.
+
+In this paper,  we propose an equivalence between  asynchronous systems with and
+without  communication delays.   The  interest  of such  an  equivalence is  the
+possibility  to reduce  the complexity  of the  behavior study  of  systems with
+delays.  In fact, the  history of the system is no more  required to explore its
+possible evolutions  and this represents  a great simplification.   Moreover, it
+allows the use of the same  theoretical results and tools as for systems without
+delays.
+
+The next  section presents the  standard formulation of complex  systems, recall
+the main  asynchronous modes that are  usually studied and  details the specific
+model we focus on.  In  \Sec{sec:transfo}, the theoretical result of equivalence
+between asynchronism  with delays and asynchronism without  delays is presented.
+Then,  some  representative examples  are  given  in  \Sec{sec:ex}.  Finally,  a
+comparison of attraction  basin determination between the two  formulations of a
+given system is performed in \Sec{sec:comp}.
+
+\section{Asynchronous complex systems}
+\label{sec:base}
+
+\subsection{Notations}
+\label{sec:notations}
+
+Classically, a complex  system is composed of $n$  elements.  Each element $x_i$
+takes its value in the set $E_i$ and  the global value of the system is then the
+collection of  the states of all the  elements $x=(x_1,...x_n)$ in the  set $E =
+\prod_{i=1}^nE_i$.   The  dynamics of  the  system  is  given by  the  evolution
+functions $f_i$ respectively associated to the $x_i$. Here again, the collection
+of the  individual functions forms the  global evolution function  of the system
+$f=(f_1,f_2,...,f_n)$.   Each $f_i$  may  be  general and  can  be expressed  as
+algorithms  taking as  input the  values  of the  components in  the system  and
+yielding one  value in $E_i$.   This feature is  very important as it  implies a
+larger generality than specific systems  such as cellular automata. Finally, the
+system evolves during  discrete time $t$ (also called  iterations) and the state
+at time $t$ is denoted by $x^{t}=(x_1^t,...,x_n^t)$.
+
+The synchronous dynamics of such a system is given by \Alg{algo:sync}.
+\begin{algorithm}[h]
+  \caption{Synchronous system}
+  \label{algo:sync}
+  \begin{Algo}
+    Given an initial state $x^{0}=(x_{1}^{0},...,x_{n}^{0})$\\
+    \textbf{for} $t=0,1,...$\\
+    \>\textbf{for} $i=1,...,n$\\
+    \>\>$x_{i}^{t+1} = f_i(x^{t}) = f_i(x_1^t,x_2^t, ...,x_n^t)$\\
+    \>\textbf{endfor}\\
+    \textbf{endfor}
+  \end{Algo}
+\end{algorithm}
+
+\subsection{Asynchronous mode}
+\label{sec:opmodes}
+
+Classically, different models of asynchronism  are used depending on the way the
+communications      are       managed      and      the       updatings      are
+performed~\cite{Rob86,BT89,HM93}.   In   this  study,  we   consider  the  fully
+asynchronous mode with delays according to \Alg{algo:async}.
+
+\begin{algorithm}[h]
+  \caption{Asynchronous system}
+  \label{algo:async}
+  \begin{Algo}
+    Given an initial state $x^{0}=(x_{1}^{0},...,x_{n}^{0})$\\
+    \textbf{for} $t=0,1,...$\\
+    \>\textbf{for} $i=1,...,n$\\
+    \>\>\textbf{if} $i\in J(t)$ \textbf{then}\\
+    \>\>\>$x_{i}^{t+1} = f_i(x_1^{t-d_1^i(t)},x_2^{t-d_2^i(t)}, ...,x_n^{t-d_n^i(t)})$\\
+    \>\>\textbf{else}\\
+    \>\>\>$x_{i}^{t+1} = x_i^t$\\
+    \>\>\textbf{endif}\\
+    \>\textbf{endfor}\\
+    \textbf{endfor}
+  \end{Algo}
+\end{algorithm}
+
+In  this algorithm, $J(t)$  is the  subset of  elements of  the system  that are
+updated at time $t$ and $d_j^i(t)$ is  the delay of element $j$ according to $i$
+at  time $t$. So,  $d_j^i(t)$ represents  the number  of iterations  between the
+production of  the value of $x_j$ and  its reception on element  $i$.  When this
+value is 0, then there is no delay and element $i$ uses the value of element $j$
+at the previous iteration.  Although  $d_j^i(t)$ is not bounded, it is generally
+assumed  that  the  versions of  values  received  on  each element  follow  the
+evolution       of       the      system,       that       is      to       say:
+$\lim_{t\rightarrow\infty}t-d_{j}^{i}(t)  =\infty$.   Moreover,  the  \emph{fair
+  sampling} condition  is also  supposed.  It assumes  that all the  element are
+regularly updated:  $\forall i\in\left\{ 1,...,n\right\}  ,\left| \left\{ t,i\in
+    J(t)\right\} \right| =\infty$.
+
+\section{Transformation Process }
+\label{sec:transfo}
+
+\section{Representative Examples}
+\label{sec:ex}
+
+\section{Comparison of Attraction Basin Determination}
+\label{sec:comp}
+
+\section*{Acknowledgments}
+
+\bibliographystyle{plain}
+\bibliography{biblio}
+%\begin{thebibliography}{99}
+% The number of 9s indicates how wide the reference 
+% numbers must hang for all references to be aligned properly.
+
+% \bibitem{a-review}
+% % ``a-review'' is just a sample tag: use a tag that describes the 
+% % paper; or perhaps just use numerical tags.
+% First Author and Second Author, ``A Review Article,'' \textit{Full Name
+% of Journal}, \textbf{volume} (date) page--page.
+% % Use \textit{...} for italics, \textbf{...} for boldface.
+% % Do not explicitly use the word ``volume''
+% % The full year (e.g., 1991) should be used for the date.
+% % Use -- to get an appropiate dash between page numbers.
+
+%\end{thebibliography}
+
+\end{document}
+
+
+
+

diff --git a/annexecontinuite.tex b/annexecontinuite.tex
new file mode 100644 (file)
index 0000000..8929705
--- /dev/null
+++ b/annexecontinuite.tex
@@ -0,0 +1,53 @@
+Montrons que pour toute fonction booléenne 
+$f$ de $\Bool^n$ dans lui-même,  $G_f$ est continue sur $(\mathcal{X},d)$.
+
+Soit $(s_t,x^t)^{t \in \Nats}$ une suite de points de
+l'espace $\mathcal{X}$ qui converge vers $(S,x)$.
+Montrons que $(G_f (s_t,x^t))^{t \in \Nats}$ converge vers $G_f (S,x)$.
+ 
+La distance $d((s_t,x^t), (S,x))$ tend vers 0. 
+Il en est donc de même pour $d_H(x^t, x)$ et $d_S(s_t, S)$.
+Or, $d_H(x^t, x)$ ne prend que des valeurs entières.
+Cette distance est donc nulle à partir d'un certain $t_0$.
+Ainsi, à partir de $t>t_0$, on a  $x^t = x$ . 
+De plus, $d_S(s_t, S)$ tend vers $0$ donc $d_S(s_t, S) < 10^{-1}$ 
+à partir d'un certain rang $t_1$. 
+Ainsi, à partir de $t>t_1$, les suites $(s_t)_{t \in \Nats}$ 
+ont toutes le même premier terme, qui est celui
+de $S$ pour $t$ supérieur à $t_1$. 
+Pour $t > \max(t_0,t_1)$, les configurations $x^t$ et $x$
+sont les mêmes, 
+et les stratégies $s_t$ et $S$ ont le même premier terme 
+($s_0^t = s_0$), donc les configurations 
+de $F_f(s_0^t,x^t)$ et de $F_f (s_0,x)$ sont égales et donc la distance 
+entre $G_f(s_t,x^t)$ et $G_f (S,x)$  est inférieure à 1.
+
+Montrons maintenant que la distance entre
+$G_f (s_t,x^t)$ et  $G_f (S,x)$
+tend bien vers 0 quand $t$ tend vers $+\infty$. Soit $\epsilon > 0$.
+\begin{itemize}
+  \item Si $\epsilon \ge 1$. Comme la distance $d(G_f(s_t,x^t), G_f (S,x))<1$
+    pour $t >  \max(t_0, t_1)$, alors 
+    $d(G_f(s_t,x^t), G_f (S,x))<\epsilon$
+  \item Si $\epsilon < 1$, alors $\exists k \in  \Nats \textrm{ tel que } 
+    10^{-k} > \epsilon > 10^{-(k+1)}$. 
+    Comme $d_S(s_t, S)$ tend vers 0, il existe
+un rang $t_2$ à partir duquel 
+$\forall t > t_2 ,  d_S(s_t, S) < 10^{-(k+2)}$:
+à partir de ce rang, les $k+2$ premiers termes de $s_t$ sont ceux de $S$.
+Donc les $k + 1$ premiers termes des stratégies de 
+$G_f (s_t,x^t)$ et de
+$G_f (s,x)$ sont les mêmes (puisque $G_f$ 
+opère un décalage sur les stratégies), et vue la
+définition de $d_S$, la partie décimale de la distance entre les points 
+$(s_t,x^t)$ et $(S,x)$ est
+inférieure à $10^{-(k+1)} \le \epsilon$.
+\end{itemize}
+Pour conclure, $\forall\epsilon > 0$, 
+$\exists~T_0 = \max(t_0, t_1, t_2) \in \Nats$ t.q.\linebreak
+$\forall t > T_0 , d (Gf (s_t,x^t),G_f (S,x))< \epsilon$.
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: "main"
+%%% End: 

diff --git a/annexesccg.tex b/annexesccg.tex
new file mode 100644 (file)
index 0000000..10a8054
--- /dev/null
+++ b/annexesccg.tex
@@ -0,0 +1,126 @@
+Soit $\alpha\in\Bool$. 
+On nomme $f^{\alpha}$ la fonction de $\Bool^{n-1}$ 
+dans lui-même définie pour 
+chaque $x\in\Bool^{n-1}$ par 
+\[
+f^{\alpha}(x)=(f_1(x,\alpha),\dots,f_{n-1}(x,\alpha)).
+\]
+On nomme $\Gamma(f)^\alpha$ le sous-graphe
+de $\Gamma(f)$ engendré par le sous-ensemble
+$\Bool^{n-1} \times \{\alpha\}$ de $\Bool^n$.
+
+Énonçons et prouvons tout d'abord les lemmes techniques suivants:
+
+\begin{Lemma}\label{lemma:subgraph}
+$G(f^\alpha)$ est un sous-graphe de $G(f)$: chaque arc de $G(f^\alpha)$ est
+un arc de $G(f)$. De plus si $G(f)$ n'a pas d'arc de $n$ vers un autre 
+sommet $i\neq n$, alors on déduit
+$G(f^\alpha)$ de $G(f)$ en supprimant le sommet $n$ ainsi que tous les 
+arcs dont $n$ est soit l'extrémité, soit l'origine (et dans ce dernier  
+cas, les arcs sont des boucles sur $n$).
+\end{Lemma}
+
+\begin{Proof}
+Supposons que $G(f^{\alpha})$ possède un arc de  $j$ vers $i$ de signe 
+$s$. Par définition, il existe un sommet $x\in\Bool^{n-1}$ tel que
+$f'^{\alpha}_{ij}(x)=s$, et puisque 
+$f'^{\alpha}_{ij}(x)=f'_{ij}(x,\alpha)$, on en déduit que $G(f)$ possède un arc
+de $j$ à $i$ de signe $s$. Ceci prouve la première assertion. 
+Pour démontrer la seconde, il suffit de  prouver que si
+$G(f)$ a un arc de $j$ vers $i$ de signe $s$, avec $i,j\neq n$, alors
+$G(f^\alpha)$ contient aussi cet arc. Ainsi, supposons que $G(f)$ a un 
+arc de $j$ vers $i$ de signe $s$, avec $i,j\neq n$.
+Alors, il existe
+$x\in\Bool^{n-1}$ et $\beta\in\Bool$ tels que
+$f'_{ij}(x,\beta)=s$. Si $f'_{ij}(x,\beta)\neq f'_{ij}(x,\alpha)$, alors
+$f_i$ dépend du  $n^{\textrm{ème}}$ composant, ce qui est en contradiction 
+avec les hypothèses.
+Ainsi $f'_{ij}(x,\alpha)$ est égal à $s$.
+On a donc aussi
+$f'^{\alpha}_{ij}(x)=s$. Ainsi $G(f^\alpha)$ possède un arc de $j$ vers $i$ de signe $s$.
+\end{Proof}
+
+\begin{Lemma}\label{lemma:iso}
+Les graphes $\Gamma(f^\alpha)$ et $\Gamma(f)^\alpha$ sont isomorphes.
+\end{Lemma}
+
+\begin{Proof}
+Soit $h$ la bijection de $\Bool^{n-1}$ vers
+$\Bool^{n-1}\times \{\alpha\}$ définie par $h(x)=(x,\alpha)$ pour chaque
+$x\in\Bool^{n-1}$.
+On voit facilement que $h$ permet de définir un isomorphisme
+entre $\Gamma(f^\alpha)$ et $\Gamma(f)^\alpha$: 
+$\Gamma(f^\alpha)$ possède un arc de $x$ vers $y$ si et seulement si 
+$\Gamma(f)^\alpha$ a un  arc de $h(x)$ vers $h(y)$.
+\end{Proof}
+
+
+\begin{Proof}
+{\sc{\hspace{-.76em}du théorème~\ref{th:Adrien} :}}
+La preuve se fait par induction sur $n$. 
+Soit $f$ une fonction de $\Bool^n$ dans lui-même et qui vérifie les hypothèses 
+du théorème.
+Si $n=1$ la démonstration est élémentaire:
+en raison du troisième point du théorème, $G(f)$ a une boucle négative;
+ainsi $f(x)=\overline{x}$ et $\Gamma(f)$ est un cycle de longueur 2.
+On suppose donc que $n>1$ et que le théorème est valide pour toutes les 
+fonctions de $\Bool^{n-1}$ dans lui-même. 
+En raison du premier point du théorème, $G(f)$
+contient au moins un sommet $i$ tel qu'il n'existe pas dans $G(f)$
+d'arc de $i$ vers un autre sommet $j\neq i$.
+Sans perte de généralité, on peut considérer que 
+ce sommet est  $n$.
+Alors, d'après le lemme~\ref{lemma:subgraph}, 
+$f^0$ et $f^1$ vérifient les conditions de l'hypothèse.
+Ainsi, par hypothèse d'induction $\Gamma(f^0)$ et
+$\Gamma(f^1)$ sont fortement connexes. 
+Et d'après le lemme~\ref{lemma:iso}, 
+$\Gamma(f)^0$ et $\Gamma(f)^1$ sont fortement 
+connexes. 
+Pour prouver que $\Gamma(f)$ est fortement connexe, il suffit 
+de prouver que $\Gamma(f)$ contient un arc $x\to y$ avec 
+$x_n=0<y_n$ et un arc $x\to y$ avec $x_n=1>y_n$. 
+En d'autres mots, il suffit de prouver que:
+\begin{equation}\tag{$*$}
+\forall \alpha\in\Bool,~\exists x\in\Bool^n,\qquad  x_n=\alpha\neq f_n(x).
+\end{equation}
+
+On suppose tout d'abord que $n$ a une boucle 
+négative.
+Alors, d'après la définition de 
+$G(f)$, il existe $x\in\Bool^n$ tel que $f'_{nn}(x)<0$. 
+Ainsi si $x_n=0$, on a  $f_n(x)>f_n(\overline{x}^n)$, et donc 
+$x_n=0\neq f_n(x)$ et
+$\overline{x}^n_n=1\neq f_n(\overline{x}^n)$; 
+et si  $x_n=1$, on a 
+$f_n(x)<f_n(\overline{x}^n)$, donc $x_n=1\neq f_n(x)$ et $\overline{x}^n_n=0\neq
+f_n(\overline{x}^n)$. 
+Dans les deux cas, la condition ($*$) est établie.
+
+Supposons maintenant que  $n$ n'a pas de boucle négative.
+D'après la seconde hypothèse, 
+$n$ n'a pas de boucle, \emph{i.e.}, la valeur de $f_n(x)$
+ne dépend pas de la valeur de $x_n$. 
+D'après la troisième hypothèse, 
+il existe $i\in \llbracket 1;n \rrbracket$ tel que $G(f)$ a un arc de 
+$i$ vers $n$.
+Ainsi, il existe $x \in \Bool^n$ tel que $f'_{ni}(x) \neq 0$ et donc 
+%$n$ n'est donc pas de degré zéro dans $G(f)$, \emph{i.e.} 
+$f_n$ n'est pas constante.
+Ainsi, il existe $x,y\in \Bool^n$ tel que
+$f_n(x)=1$ et $f_n(y)=0$. 
+Soit  $x'=(x_1,\dots,x_{n-1},0)$ et
+$y'=(y_1,\dots,y_{n-1},1)$. 
+Puisque la valeur de $f_n(x)$
+(resp. de $f_n(y)$) ne dépend pas de la  valeur de  $x_n$ (resp. de  $y_n$),
+on a $f_n(x')=f_n(x)=1\neq x'_n$ (resp. $f_n(y')=f_n(y)=0\neq
+y'_n$). 
+Ainsi la  condition ($*$) est établie, et le théorème est prouvé.
+\end{Proof}
+
+
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: "main"
+%%% End: 

diff --git a/biblio.bib b/biblio.bib
new file mode 100644 (file)
index 0000000..7a6d51f
--- /dev/null
+++ b/biblio.bib
@@ -0,0 +1,941 @@
+@Article{TNN2006,
+  author =       {Bahi,Jacques M. and Contassot-Vivier,Sylvain},
+  title =        {Basins of attraction in fully asynchronous discrete-time discrete-state dynamic networks},
+  journal =      {IEEE Transactions on Neural Networks},
+  year =      {2006},
+  OPTkey =       {},
+  volume =    {17},
+  number =    {2},
+  pages =     {397-408},
+  OPTmonth =     {},
+}
+
+@Misc{GridComp,
+  OPTkey =       {},
+  OPTauthor =    {},
+  title =     {Grid Computing Info Centre},
+  howpublished = {http://www.gridcomputing.com/},
+  OPTmonth =     {},
+  OPTyear =      {},
+  OPTnote =      {},
+  OPTannote =    {}
+}
+
+@Article{BM99,
+  author =      {J.M.~Bahi and C.J.~Michel},
+  title =       {Simulations of asynchronous evolution of discrete systems},
+  journal =     {Simulation Practice and Theory},
+  year =        {1999},
+  OPTkey =      {},
+  volume =      {7},
+  OPTnumber =   {},
+  pages =       {309--324},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{BM00,
+  author =      {J.M.~Bahi and C.J.~Michel},
+  title =       {Convergence of discrete asynchronous iterations},
+  journal =     {International J. Computer Math.},
+  year =        {2000},
+  OPTkey =      {},
+  volume =      {74},
+  OPTnumber =   {},
+  pages =       {113--125},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{Bahi00,
+  author =      {J.M.~Bahi},
+  title =       {Boolean totally asynchronous iterations},
+  journal =     {International J. of Mathematical Algorithms},
+  year =        {2000},
+  OPTkey =      {},
+  volume =      {1},
+  OPTnumber =   {},
+  pages =       {331--346},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{Bau78,
+  author =      {G.M.~Baudet},
+  title =       {Asynchronous iterative methods for multiprocessors},
+  journal =     {J. ACM},
+  year =        {1978},
+  OPTkey =      {},
+  volume =      {25},
+  OPTnumber =   {},
+  pages =       {226--244},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Book{BT89,
+  author =      {D.P.~Bertsekas and J.N.~Tsitsiklis},
+  ALTeditor =   {},
+  title =       {Parallel and Distributed Computation},
+  publisher =   {Prentice Hall},
+  year =        {1999},
+  OPTkey =      {},
+  OPTvolume =   {},
+  OPTnumber =   {},
+  OPTseries =   {},
+  address =     {Englewood Cliffs, New Jersey},
+  OPTedition =          {},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{CB01,
+  author =      {S.~Contassot-Vivier and J.M.~Bahi},
+  title =       {Convergence dans les systèmes booléens asynchrones et application aux
+  réseaux de Hopfield},
+  journal =     {Calculateurs Parallèles},
+  year =        {2001},
+  OPTkey =      {},
+  volume =      {13},
+  number =      {1},
+  pages =       {107--124},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{CM69,
+  author =      {D.~Chazan and W.L.~Miranker},
+  title =       {Chaotic relaxation},
+  journal =     {Linear algebra Appl.},
+  year =        {1969},
+  OPTkey =      {},
+  volume =      {2},
+  OPTnumber =   {},
+  pages =       {199--222},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{Elt82,
+  author =      {M.N.~El~Tarazi},
+  title =       {Some convergence results for asynchronous algorithms},
+  journal =     {Numer. Math.},
+  year =        {1982},
+  OPTkey =      {},
+  volume =      {39},
+  OPTnumber =   {},
+  pages =       {325--340},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{Rob78,
+  author =      {F.~Robert},
+  title =       {Th\'{e}or\`{e}me de Perron-Frobenius et Stein-Rosenberg booléens},
+  journal =     {Linear Algebra and Its Applications},
+  year =        {1978},
+  OPTkey =      {},
+  volume =      {19},
+  OPTnumber =   {},
+  pages =       {237--250},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Book{Rob86,
+  author =       "F.~Robert",
+  title =        "Discrete Iterations, {A} Metric Study",
+  publisher =    "Springer-Verlag Series in Computational Mathematics",
+  volume =      {6},
+  year =         "1986",
+  address =      "Berlin",
+  pages =        "195",
+}
+
+@Book{Rob95,
+  author =      {F.~Robert},
+  ALTeditor =   {},
+  title =       {Les Syst\`{e}mes Dynamiques Discrets},
+  publisher =   {Springer-Verlag},
+  year =        {1995},
+  OPTkey =      {},
+  volume =      {19},
+  OPTnumber =   {},
+  OPTseries =   {},
+  address =     {Berlin Heidelberg},
+  OPTedition =          {},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{Hop82,
+  author =      {J.J.~Hopfield},
+  title =       {Neural networks and physical systems with emergent collective computational abilities},
+  journal =     {Proc. Nat. Acad. Sci.},
+  year =        {1982},
+  OPTkey =      {},
+  volume =      {79},
+  OPTnumber =   {},
+  pages =       {2554--2558},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{Hop84,
+  author =      {J.J.~Hopfield},
+  title =       {Neurons with graded response have collective computational properties like those of two-state neurons},
+  journal =     {Proc. Nat. Acad. Sci.},
+  year =        {1984},
+  OPTkey =      {},
+  volume =      {81},
+  OPTnumber =   {},
+  pages =       {3088--3092},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{Kan99,
+  author =      {A.J.~Kane and D.J.~Evans},
+  title =       {Neural network software simulation},
+  journal =     {Intern. J. Computer Math.},
+  year =        {1999},
+  OPTkey =      {},
+  volume =      {71},
+  OPTnumber =   {},
+  pages =       {475--494},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{BG88,
+  author =      {J.~Bruck and J.W.~Goodman},
+  title =       {A generalized convergence theorem for neural networks},
+  journal =     {IEEE Trans. Inform. Theory},
+  year =        {1998},
+  OPTkey =      {},
+  volume =      {34},
+  OPTnumber =   {},
+  pages =       {1089--1092},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{Bru90,
+  author =      {J.~Bruck},
+  title =       {On the convergence properties of the Hopfield model},
+  journal =     {Proc. IEEE},
+  year =        {1990},
+  OPTkey =      {},
+  volume =      {78},
+  number =      {10},
+  pages =       {1579--1585},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{BKK96,
+  author =      {A.~Bhaya and E.~Kaszkurewicz and V.S. Kozyakin},
+  title =       {Existence and stability of a unique equilibrium in continuous-valued discrete-time asynchronous Hopfield neural networks},
+  journal =     {IEEE Trans. Neural Networks},
+  year =        {1996},
+  OPTkey =      {},
+  volume =      {7},
+  number =      {3},
+  pages =       {620--628},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{GFSP85,
+  author =      {E.~Golès and F.~Fogelman-Soulie and D.~Pellegrin},
+  title =       {Decreasing energy functions as a tool for studying threshold networks},
+  journal =     {Disc. Appl. Math.},
+  year =        {1985},
+  OPTkey =      {},
+  volume =      {12},
+  OPTnumber =   {},
+  pages =       {261--277},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@PhdThesis{Pel86,
+  author =       {D.~Pellegrin},
+  title =        {Algorithmique discrète et réseaux d'automates},
+  school =       {Grenoble},
+  year =         {1986},
+  OPTkey =       {},
+  OPTtype =      {},
+  OPTaddress =   {},
+  OPTmonth =     {},
+  OPTnote =      {},
+  OPTannote =    {}
+}
+
+@Article{HM93,
+  author =      {A.V.M.~Herz and C.M.~Marcus},
+  title =       {Distributed dynamics in neural networks},
+  journal =     {Physical Review E},
+  year =        {1993},
+  OPTkey =      {},
+  volume =      {47},
+  number =      {3},
+  pages =       {2155--2161},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{KBK99,
+  author =      {V.S.~Kozyakin and A.~Bhaya and E.~Kaszkurewicz},
+  title =       {A global asymptotic stability result for a class of totally asynchronous discrete nonlinear systems},
+  journal =     {Mathematics of Control, Signals and Systems},
+  year =        {1999},
+  OPTkey =      {},
+  volume =      {12},
+  number =      {2},
+  pages =       {143--166},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{Koi94,
+  author =      {P.~Koiran},
+  title =       {Dynamics of discrete-time, continuous-state Hopfield networks},
+  journal =     {Neural Computation},
+  year =        {1994},
+  OPTkey =      {},
+  volume =      {6},
+  OPTnumber =   {},
+  pages =       {459--468},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{Mie75,
+  author =      {J.-C.~Miellou},
+  title =       {Algorithmes de relaxation chaotique \`a retard},
+  journal =     {RAIRO, R-1},
+  year =        {1975},
+  OPTkey =      {},
+  OPTvolume =   {},
+  OPTnumber =   {},
+  pages =       {52--82},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{MFS90,
+  author =      {A.N.~Michel and J.A.~Farrell and H.-F.~Sun},
+  title =       {Analysis and synthesis  techniques for Hopfield  type synchronous  discrete time neural networks with application  to associative memory},
+  journal =     {IEEE Transact. Circuits Syst.},
+  year =        {1990},
+  OPTkey =      {},
+  volume =      {37},
+  number =      {11},
+  pages =       {1356--1366},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{MW89,
+  author =      {C.M.~Marcus and R.M.~Westervelt},
+  title =       {Dynamics of iterated-map neural networks},
+  journal =     {Physical Review A},
+  year =        {1989},
+  OPTkey =      {},
+  volume =      {40},
+  number =      {1},
+  pages =       {501--504},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{BC02,
+  author =      {J.M.~Bahi and S.~Contassot-Vivier},
+  title =       {Stability of fully asynchronous discrete-time discrete-state dynamic networks},
+  journal =     {IEEE Transactions on Neural Networks},
+  year =        {2002},
+  OPTkey =      {},
+  volume =      {13},
+  number =      {6},
+  pages =       {1353-1363},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{BC05TNN,
+  author =      {J.M.~Bahi and S.~Contassot-Vivier},
+  title =       {Attraction basins   of   fixed  point   states   in fully asynchronous discrete-time discrete-state dynamic networks},
+  journal =     {IEEE Transactions on Neural Networks},
+  year =        {2005},
+  OPTkey =      {},
+  volume =      {?},
+  number =      {?},
+  pages =       {?-?},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@InCollection{Mar89b,
+  title =        "Dynamics of Analog Neural Networks with Time Delay",
+  booktitle =    "Advances in Neural Information Processing Systems I",
+  author =       "C.M.~Marcus and R.M.~Westervelt",
+  editor =       "D. Touretzky",
+  publisher =    "Morgan Kauffman",
+  year =         "1989",
+}
+
+@Article{ShrivastavaDR1992,
+  author =       "Yash Shrivastava and Soura Dasgupta and Sudhakar M.
+                 Reddy",
+  title =        "Guaranteed Convergence in a Class of {Hopfield}
+                 Networks",
+  journal =      "IEEE Transactions on Neural Networks",
+  year =         "1992",
+  volume =       "3",
+  number =       "6",
+  pages =        "951--961",
+  month =        nov,
+}
+
+@Article{TG86,
+  author =      {M.~Takeda  and J.W.~Goodman},
+  title =       {Neural networks   for computation:     Number   representations  and  programming complexity},
+  journal =     {Appl. Opt.},
+  year =        {1986},
+  OPTkey =      {},
+  volume =      {25},
+  number =      {18},
+  pages =       {3033--3046},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{Wan98,
+  author =      {L.P.~Wang},
+  title =       {On the dynamics of discrete-time, continuous-state Hopfield neural networks},
+  journal =     {IEEE Trans. Circuits and Systems-II: Analog and Digital Signal Processing},
+  year =        {1998},
+  OPTkey =      {},
+  volume =      {45},
+  number =      {6},
+  pages =       {747--749},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+@Article{WJBG98,
+  author =      {X.~Wang and A.~Jagota and F.~Botelho and M.~Garzon},
+  title =       {Absence of cycles in symmetric neural networks},
+  journal =     {Neural Computation},
+  year =        {1998},
+  OPTkey =      {},
+  volume =      {10},
+  OPTnumber =   {},
+  pages =       {1235--1249},
+  OPTmonth =    {},
+  OPTnote =     {},
+  OPTannote =   {}
+}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% PRNG
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+@Article{Kuehn61,
+  title =      "A 48-bit pseudorandom generator",
+  author =     "Heidi G. Kuehn",
+  journal =    "Commun. ACM",
+  year =       "1961",
+  number =     "8",
+  volume =     "4",
+  bibdate =    "2003-11-20",
+  bibsource =  "DBLP,
+                http://dblp.uni-trier.de/db/journals/cacm/cacm4.html#Kuehn61",
+  pages =      "350--352",
+  URL =        "http://doi.acm.org/10.1145/366678.366690",
+}
+
+@TechReport{ICSI-TR-90-039,
+  author =     "J. F. Traub and H. Woznaikowski",
+  title =      {The {M}onte-{C}arlo algorithm with a pseudorandom
+                generator},
+  institution =  "International Computer Science Institute",
+  number =     "TR-90-039",
+  address =    "Berkeley, CA",
+  month =      aug,
+  year =       "1990",
+  abstract =   "We analyze the Monte Carlo algorithm for the
+                approximation of multivariate integrals when a
+                pseudo-random generator is used. We establish lower and
+                upper bounds on the error of such algorithms. We prove
+                that as long as a pseudo-random generator is capable of
+                producing only finitely many points, the Monte Carlo
+                algorithm with such a pseudo-random generator fails for
+                L subscript 2 or continuous functions. It also fails
+                for Lipschitz functions if the number of points does
+                not depend on the number of variables. This is the case
+                if a linear congruential generator is used with one
+                initial seed. On the other hand, if a linear
+                congruential generator of period m is used for each
+                component with independent uniformly distributed
+                initial seeds, then the Monte Carlo algorithm with such
+                a pseudo-random generator using n function values
+                behaves as for the uniform distribution and its
+                expected error is roughly n superscript (-1/2) as long
+                as the number n of function values is less than m
+                superscript 2.",
+}
+
+@Article{Sugita04,
+  title =      {Security of pseudorandom generator and {M}onte-{C}arlo
+                method},
+  author =     "Hiroshi Sugita",
+  journal =    "Monte Carlo Meth. and Appl",
+  year =       "2004",
+  number =     "3-4",
+  volume =     "10",
+  bibdate =    "2013-01-09",
+  bibsource =  "DBLP,
+                http://dblp.uni-trier.de/db/journals/mcma/mcma10.html#Sugita04",
+  pages =      "609--615",
+  URL =        "http://dx.doi.org/10.1515/mcma.2004.10.3-4.609",
+}
+
+@Article{Marsaglia98,
+  title =      "The {M}onty {P}ython method for generating random
+                variables",
+  author =     "George Marsaglia and Wai Wan Tsang",
+  journal =    "ACM Trans. Math. Softw",
+  year =       "1998",
+  number =     "3",
+  volume =     "24",
+  bibdate =    "2003-11-27",
+  bibsource =  "DBLP,
+                http://dblp.uni-trier.de/db/journals/toms/toms24.html#MarsagliaT98",
+  pages =      "341--350",
+  URL =        "http://portal.acm.org/citation.cfm?id=292395.292453",
+}
+
+@misc{Mons14,
+inhal = {no},
+domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
+equipe = {and},
+classement = {COM},
+author = {Couchot, Jean-Fran\c{c}ois and Héam, Pierre-Cyrille and Guyeux, Christophe and Wang, Qianxue and Bahi, Jacques},
+title = {Traversing a n-cube without Balanced Hamiltonian Cycle to Generate Pseudorandom Numbers},
+howpublished = {15-th Mons Theoretical Computer Science Days (15e Journées Montoises d'Informatique Théorique), Nancy, France},
+day = 23,
+month = sep,
+year = 2014,
+
+}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% Markov.bib
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+@inproceedings{chgw14oip,
+   author              = {Jean-François Couchot and 
+                          Pierre-Cyrille Héam and 
+                          Christophe Guyeux and 
+                          Qianxue Wang and 
+                          Jacques M. Bahi},
+   title               = {Pseudorandom Number Generators with Balanced Gray Codes.},
+   booktitle           = {SECRYPT},
+   year                = {2014},
+   pages               = {469-475},
+   address = {Vienna, Austria},
+   publisher = {Springer}
+}
+
+
+@Article{rwfg,
+  author =      {Laurent Saloff-Coste},
+  title =       {Random Walks on Finite Groups},
+  journal =     {Probability on Descrete Structures},
+  year =        {},
+  OPTkey =      {},
+  volume =      {110},
+  OPTnumber =   {},
+  pages =       {263-346},
+  OPTmonth =    {},
+  note =        {http://stat.stanford.edu/~cgates/PERSI/papers/rwfg.pdf},
+  OPTannote =   {}
+}
+
+@book{LevinPeresWilmer2006,
+  added-at = {2010-01-19T17:51:27.000+0100},
+  author = {Levin, David A. and Peres, Yuval and Wilmer, Elizabeth L.},
+  biburl = {http://www.bibsonomy.org/bibtex/2097dc4d1d0e412b2444f540b04110797/tmalsburg},
+  interhash = {61354795a6accb6407bfdbf04753a683},
+  intrahash = {097dc4d1d0e412b2444f540b04110797},
+  keywords = {markovchains probabilitytheory textbook},
+  publisher = {American Mathematical Society},
+  timestamp = {2010-01-19T17:51:27.000+0100},
+  title = {{Markov chains and mixing times}},
+  url = {http://scholar.google.com/scholar.bib?q=info:3wf9IU94tyMJ:scholar.google.com/&output=citation&hl=en&as_sdt=2000&ct=citation&cd=0},
+  year = 2006
+}
+
+@BOOK{devaney,
+  title = {An Introduction to Chaotic Dynamical Systems},
+  publisher = {Addison-Wesley},
+  year = {1989},
+  author = {Devaney, Robert L.},
+  address = {Redwood City, CA},
+  edition = {2nd}
+}
+
+
+@ARTICLE{Banks92,
+  author = {J. Banks and J. Brooks and G. Cairns and P. Stacey},
+  title = {On {D}evaney's Definition of Chaos},
+  journal = {Amer. Math. Monthly},
+  year = {1992},
+  volume = {99},
+  pages = {332--334},
+  keywords = {(c+),},
+  owner = {guyeux},
+  timestamp = {27/01/2008}
+}
+
+
+@INPROCEEDINGS{wbg10ip,
+  author = {Wang, Qianxue and Bahi, Jacques and Guyeux, Christophe and Fang,
+       Xiaole},
+  title = {Randomness quality of {CI} chaotic generators. Application to Internet
+       security},
+  booktitle = {INTERNET'2010. The 2nd Int. Conf. on Evolving Internet},
+  year = {2010},
+  pages = {125--130},
+  address = {Valencia, Spain},
+  month = sep,
+  publisher = {IEEE Computer Society Press},
+  note = {Best Paper award},
+  classement = {ACTI},
+  doi = {10.1109/INTERNET.2010.30},
+  domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
+  equipe = {and},
+  inhal = {no},
+  url = {http://doi.ieeecomputersociety.org/10.1109/INTERNET.2010.30}
+}
+
+
+
+@INPROCEEDINGS{bgw10ip,
+  author = {Bahi, Jacques and Guyeux, Christophe and Wang, Qianxue},
+  title = {A Pseudo Random Numbers Generator Based on Chaotic Iterations. Application
+       to Watermarking},
+  booktitle = {WISM 2010, Int. Conf. on Web Information Systems and Mining},
+  year = {2010},
+  volume = {6318},
+  series = {LNCS},
+  pages = {202--211},
+  address = {Sanya, China},
+  month = oct,
+  classement = {ACTI},
+  doi = {10.1007/978-3-642-16515-3_26},
+  domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
+  equipe = {and},
+  inhal = {no},
+  url = {http://dx.doi.org/10.1007/978-3-642-16515-3_26}
+}
+
+
+
+@INPROCEEDINGS{bgw09ip,
+  author = {Bahi, Jacques and Guyeux, Christophe and Wang, Qianxue},
+  title = {A novel pseudo-random generator based on discrete chaotic iterations},
+  booktitle = {INTERNET'09, 1-st Int. Conf. on Evolving Internet},
+  year = {2009},
+  pages = {71--76},
+  address = {Cannes, France},
+  month = aug,
+  classement = {ACTI},
+  doi = {10.1109/INTERNET.2009.18},
+  domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
+  equipe = {and},
+  inhal = {no},
+  url = {http://dx.doi.org/10.1109/INTERNET.2009.18}
+}
+
+@INPROCEEDINGS{guyeuxTaiwan10,
+author={Guyeux, Christophe and Qianxue Wang and Bahi, J.M.},
+booktitle={Computer Application and System Modeling (ICCASM), 2010 International Conference on},
+title={Improving random number generators by chaotic iterations application in data hiding},
+year={2010},
+month={Oct},
+volume={13},
+pages={V13-643-V13-647},
+keywords={cryptography;data encapsulation;random number generation;DieHARD statistical test suite;XORshifts PRNG;chaotic iterations;cryptographic applications;data hiding;pseudo-random number generator;Authentication;Cryptography;DNA;Generators;Discrete chaotic iterations;Internet security;Pseudo-random number generator;Statistical tests;Topological chaos;data hiding},
+doi={10.1109/ICCASM.2010.5622199},
+publisher={IEEE}
+}
+
+@inproceedings{bcgw11ip,
+inhal = {no},
+domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
+equipe = {and},
+classement = {ACTI},
+author = {Bahi, Jacques and Couchot, Jean-Fran\c{c}ois and Guyeux, Christophe and Wang, Qianxue},
+title = {Class of Trustworthy Pseudo Random Number Generators},
+booktitle = {INTERNET 2011, the 3-rd Int. Conf. on Evolving Internet},
+pages = {72--77},
+address = {Luxembourg, Luxembourg},
+month = jun,
+year = 2011}
+
+@incollection{bcgr11ip,
+year={2011},
+isbn={978-3-642-22952-7},
+booktitle={Fundamentals of Computation Theory},
+volume={6914},
+series={Lecture Notes in Computer Science},
+editor={Owe, Olaf and Steffen, Martin and Telle, JanArne},
+doi={10.1007/978-3-642-22953-4_11},
+title={On the Link between Strongly Connected Iteration Graphs and Chaotic Boolean Discrete-Time Dynamical Systems},
+url={http://dx.doi.org/10.1007/978-3-642-22953-4_11},
+publisher={Springer Berlin Heidelberg},
+keywords={Boolean network; discrete-time dynamical system; topological chaos},
+author={Bahi, Jacques M. and Couchot, Jean-Francois and Guyeux, Christophe and Richard, Adrien},
+pages={126-137},
+language={English},
+address={Berlin}
+}
+
+@INPROCEEDINGS{bg10aip,
+  author = {Bahi, Jacques and Guyeux, Christophe},
+  title = {Topological chaos and chaotic iterations, application to Hash functions},
+  booktitle = {IJCNN'10, Int. Joint Conf. on Neural Networks, joint to WCCI'10,
+       IEEE World Congress on Computational Intelligence},
+  year = {2010},
+  pages = {1--7},
+  address = {Barcelona, Spain},
+  month = jul,
+  note = {Best paper award},
+  classement = {ACTI},
+  doi = {10.1109/IJCNN.2010.5596512},
+  domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
+  equipe = {and},
+  inhal = {no},
+  url = {http://dx.doi.org/10.1109/IJCNN.2010.5596512}
+}
+
+
+@ARTICLE{DBLPjournalsAbs-1112-5239,
+  author = {Jacques M. Bahi and Rapha{\"e}l Couturier and Christophe Guyeux and
+       Pierre-Cyrille H{é}am},
+  title = {Efficient and Cryptographically Secure Generation of Chaotic Pseudorandom
+       Numbers on GPU},
+  journal = {CoRR},
+  year = {2011},
+  volume = {abs/1112.5239},
+  bibsource = {DBLP, http://dblp.uni-trier.de},
+  ee = {http://arxiv.org/abs/1112.5239}
+}
+
+@MISC{Nist10,
+  author = {E. Barker and A. Roginsky},
+  title = {DRAFT {N}{I}{S}{T} Special Publication 800-131 Recommendation for
+       the Transitioning of Cryptographic Algorithms and Key Sizes},
+  year = {2010},
+  owner = {christophe},
+  timestamp = {2010.08.18}
+}
+
+
+@ARTICLE{LEcuyerS07,
+  author = {Pierre L'Ecuyer and Richard J. Simard},
+  title = {Test{U01}: {A} {C} library for empirical testing of random number
+       generators},
+  journal = {ACM Trans. Math. Softw},
+  year = {2007},
+  volume = {33},
+  number = {4},
+  bibdate = {2007-11-06},
+  bibsource = {DBLP, http://dblp.uni-trier.de/db/journals/toms/toms33.html#LEcuyerS07},
+  url = {http://doi.acm.org/10.1145/1268776.1268777}
+}
+
+
+@ARTICLE{Marsaglia1996,
+  author = {G. Marsaglia},
+  title = {DIEHARD: a battery of tests of randomness},
+  journal = {http://stat.fsu.edu/~geo/diehard.html},
+  year = {1996},
+  owner = {qianxue},
+  timestamp = {2009.11.09}
+}
+
+@PHDTHESIS{Xiaole13,
+  author = {Xiaole Fang},
+  title = {Utilization of chaotic dynamics for generating pseudorandom numbers
+       in various contexts},
+  school = {Universit\'{e} de Franche-Comt\'{e}},
+  year = {2013},
+  owner = {guyeux},
+  timestamp = {2008.01.02}
+}
+
+@BOOK{Robert,
+  title = {Discrete Iterations, a Metric Study},
+  publisher = {Springer-Verlag},
+  year = {1986},
+  author = {François Robert},
+  volume = {6},
+  series = {Series in Computational Mathematics}
+}
+
+
+@ARTICLE{915396,
+author={Stojanovski, T. and Pihl, J. and Kocarev, L.}, 
+journal={Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on}, 
+title={Chaos-based random number generators. Part II: practical realization}, 
+year={2001}, 
+month={Mar}, 
+volume={48}, 
+number={3}, 
+pages={382-385}, 
+keywords={CMOS analogue integrated circuits;chaos generators;circuit simulation;piecewise linear techniques;random number generation;redundancy;switched current circuits;0.8 micron;1 Mbit/s;chaos-based random number generators;chaotic piecewise-linear one-dimensional map;output bit rate;parasitic attractors;periodic attractors;post-layout circuit simulations;process conditions;redundancy;standard CMOS process;switched current techniques;Bit rate;CMOS process;Chaos;Circuits;Electric breakdown;Information analysis;Piecewise linear techniques;Power supplies;Random number generation;Temperature}, 
+doi={10.1109/81.915396}, 
+ISSN={1057-7122},}
+
+
+@ARTICLE{915385, 
+author={Stojanovski, T. and Kocarev, L.}, 
+journal={Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on}, 
+title={Chaos-based random number generators-part I: analysis [cryptography]}, 
+year={2001}, 
+month={Mar}, 
+volume={48}, 
+number={3}, 
+pages={281-288}, 
+keywords={Markov processes;chaos;cryptography;piecewise linear techniques;random number generation;Markov generating partition;Markov information source;chaos-based random number generators;cryptography;information generation process;parameter values;piecewise-linear one-dimensional map;random number generator;Chaos;Cryptographic protocols;Cryptography;Current measurement;Low-frequency noise;Noise measurement;Random number generation;Random sequences;Security;Semiconductor device noise}, 
+doi={10.1109/81.915385}, 
+ISSN={1057-7122},}
+
+@INPROCEEDINGS{5376454,
+author={Li Cao and Lequan Min and Hongyan Zang},
+booktitle={Computational Intelligence and Security, 2009. CIS '09. International Conference on},
+title={A Chaos-Based Pseudorandom Number Generator and Performance Analysis},
+year={2009},
+month={Dec},
+volume={1},
+pages={494-498},
+keywords={binary sequences;chaos;discrete systems;random number generation;synchronisation;2D Arnold cat map;6D discrete chaos map;FIPA-140-2 tests;National Institute of Standard and Technology;binary number sequences;chaos-based pseudorandom number generator;confidence interval analysis;generalized chaos synchronization theorem;performance analysis;Chaos;Chaotic communication;Computational intelligence;NIST;Nonlinear dynamical systems;Performance analysis;Random number generation;Security;Space technology;Testing;Discrete chaos map;generalized chaos synchronization;one-time-pad;statistical test},
+doi={10.1109/CIS.2009.203},
+publisher={IEEE}
+}
+
+@article{bfgw13ij,
+inhal = {no},
+domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
+equipe = {and},
+classement = {ACLI},
+impact-factor ={1.065},
+isi-acro = {J NETW COMPUT APPL},
+author = {Bahi, Jacques and Fang, Xiaole and Guyeux, Christophe and Wang, Qianxue},
+title = {Suitability of chaotic iterations schemes using {XORshift} for security applications},
+journal = {JNCA, Journal of Network and Computer Applications},
+pages = {282--292},
+volume = 37,
+doi = {10.1016/j.jnca.2013.03.001},
+url = {http://dx.doi.org/10.1016/j.jnca.2013.03.001},
+abstract = {The design and engineering of original cryptographic solutions is a major concern to provide secure information systems. In a previous study, we have described a generator based on chaotic iterations, which uses the well-known XORshift generator. By doing so, we have improved the statistical performances of XORshift and make it behave chaotically, as defined by Devaney. The speed and security of this former generator have been improved in a second study, to make its usage more relevant in the Internet security context. In this paper, these contributions are summarized and a new version of the generator is introduced. It is based on a new Lookup Table implying a large improvement of speed. A comparison and a security analysis between the XORshift and these three versions of our generator are proposed, and various new statistical results are given. Finally, an application in the information hiding framework is presented, to give an illustrative example of the use of such a generator in the Internet security field.},
+publisher = {Elsevier},
+year = 2013,
+
+}
+
+
+@article{Marsaglia2003JSSOBKv08i14,
+  author =     "George Marsaglia",
+  title =      "Xorshift RNGs",
+  journal =    "Journal of Statistical Software",
+  volume =     "8",
+  number =     "14",
+  pages =      "1--6",
+  day =        "4",
+  month =      "7",
+  year =       "2003",
+  CODEN =      "JSSOBK",
+  ISSN =       "1548-7660",
+  bibdate =    "2003-07-04",
+  URL =        "http://www.jstatsoft.org/v08/i14",
+  accepted =   "2003-07-04",
+  acknowledgement = "",
+  keywords =   "",
+  submitted =  "2003-05-06",
+}
+
+
+
+@INPROCEEDINGS{cghwb14ip,
+  author = {Couchot, Jean-Fran\c{c}ois and Guyeux, Christophe and Heam, 
+Pierre-Cyrille, and Wang, Qianxue and Bahi, Jacques},
+  title = {Pseudorandom Number Generators with Balanced Gray Codes},
+  booktitle = {SECRYPT 2014, the 11th International Conference on Security and Cryptography},
+  year = {2014},
+  pages = {***--***},
+  address = {Vienna, Austria},
+  month = aug,
+  classement = {ACTI},
+  doi = {10.1007/978-3-642-22953-4_11},
+  domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
+  equipe = {and},
+  inhal = {no},
+}
+
+@Article{ZanSup04,
+  author =       {Suparta, IN and Zanten, AJ van},
+  title =        {Totally balanced and exponentially balanced Gray codes},
+  journal =      {Discrete Analysis and Operation Research (Russia)},
+  year =         {2004},
+  OPTkey =       {},
+  volume =    {11},
+  number =    {4},
+  pages =     {81-98},
+  OPTmonth =     {},
+  OPTnote =      {},
+  OPTannote =    {}
+}
+
+@Article{Feder2009NTB,
+  title =      "Nearly tight bounds on the number of Hamiltonian
+                circuits of the hypercube and generalizations",
+  author =     "Tom{\'a}s Feder and Carlos S. Subi",
+  journal =    "Info. Process. Lett",
+  year =       "2009",
+  number =     "5",
+  volume =     "109",
+  pages =      "267--272",
+  URL =        "http://dx.doi.org/10.1016/j.ipl.2008.10.015",
+}

diff --git a/conclusion.tex b/conclusion.tex
new file mode 100644 (file)
index 0000000..af0400f
--- /dev/null
+++ b/conclusion.tex
@@ -0,0 +1,18 @@
+Dans cet  article, nous avons montré  qu'une fonction $G_f$ est  chaotique si et
+seulement  la  fonction  booléenne  $f$  a  un  graphe  d'itérations  chaotiques
+fortement  connexe.  L'originalité  majeure repose  sur le  type d'itérations
+considéré,  qui  n'est pas  limité  à  la mise  à  jour  d'un  seul élément  par
+itération, mais qui est étendu à la mise à jour simultanée de plusieurs éléments
+du système  à chaque itération.  De plus,  il a été  prouvé que la  sortie d'une
+telle  fonction suit  une loi  de distribution  uniforme si  et seulement  si la
+chaîne de Markov  induite peut se représenter à  l'aide d'une matrice doublement
+stochastique.   Enfin, un  algorithme permettant  d'engendrer des  fonctions qui
+vérifient ces deux contraintes a été  présenté et évalué.  Ces fonctions ont été
+ensuite  appliquées avec succès  à la  génération de  nombres pseudo-aléatoires.
+Les  expériences  sur  une  batterie  de  tests éprouvée  ont  pu  confirmer  la
+pertinence de l'approche théorique.
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: "main"
+%%% End: 

diff --git a/cs.tex b/cs.tex
new file mode 100644 (file)
index 0000000..8855779
--- /dev/null
+++ b/cs.tex
@@ -0,0 +1,171 @@
+Dans  cette  partie, les  définitions  fondamentales  liées  au chaos  dans  les
+systèmes booléens sont rappelées et plusieurs résultats théoriques sont montrés.
+
+\begin{Def}[Chaos (Devaney)]
+Une fonction $k$ continue sur un espace métrique $(\mathcal{X},d)$ est \textbf{chaotique}
+si elle est transitive,
+régulière et fortement sensible aux conditions initiales.
+\end{Def}
+
+\begin{Def}[Transitivité]
+Une fonction $k$ est  \textbf{transitive} sur $(\mathcal{X},d)$ si  la propriété suivante est établie:
+\[
+\forall X, Y\in \mathcal{X},
+\forall \epsilon > 0,
+\exists  Z \in \mathcal{X},
+\exists  t \in \Nats,
+d(X,Z) < \epsilon  \land k^t(Z) = Y
+\] 
+\end{Def}
+
+\begin{Def}[Point périodique]
+  Un point $P  \in \mathcal{X}$ est dit \textbf{périodique}  de période $t$ pour
+  une fonction $k$ si $t$ est un entier  naturel non nul tel que $k^t(P) = P$ et
+  pour tout $n$, $0 < n \le t-1$, on a $k^n(P) \neq P$.
+  Par la  suite, $\textbf{Per(k)}$ dénote  l'ensemble des points  périodiques de
+  $k$ dans $\mathcal{X}$ de période quelconque.
+\end{Def}
+
+\begin{Def}[Régularité]
+Une fonction $k$  est dite \textbf{régulière} dans $(\mathcal{X},d)$ 
+si l'ensemble des points périodiques de $k$ est dense dans $\mathcal{X}$, 
+c'est-à-dire  si la propriété suivante est établie: 
+\[
+\forall X \in \mathcal{X}, \forall \epsilon > 0, \exists Y \in \textit{Per}(k) 
+ \textrm{ tel que } d(X,Y) < \epsilon.
+\]
+\end{Def}
+
+\begin{Def}[Forte sensibilité aux conditions initiales]
+Une fonction $k$ définie sur $(\mathcal{X},d)$ 
+est  \textbf{fortement sensible aux conditions initiales} 
+s'il existe une valeur $\epsilon> 0$ telle que
+pour tout $X \in \mathcal{X}$ et pour tout 
+ $\delta > 0$, il existe  $Y \in  \mathcal{X}$ et  
+$t \in \Nats$ qui vérifient  $d(X,Y) < \delta$ et 
+$d(k^t(X) , k^t(Y)) > \epsilon$.
+\end{Def}
+
+
+John Banks et ses collègues ont cependant
+démontré que la sensibilité aux conditions initiales est une conséquence
+de la régularité et de la transitivité topologique~\cite{Banks92}. 
+On ne se focalise donc que sur ces deux dernières
+propriétés pour caractériser les fonctions booléennes $f$ 
+rendant chaotique la fonction engendrée $G_f$.
+Ceci est réalisé en établissant les relations d'inclusion entre 
+les ensembles $\mathcal{T}$ des fonctions topologiquement transitives, 
+$\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 \textrm{ est transitive} \right\}$,
+\item   $\mathcal{R}   =    \left\{f   :   \mathds{B}^n   \to
+\mathds{B}^n \big/ G_f \textrm{ est régulière} \right\}$,
+\item   $\mathcal{C}   =    \left\{f   :   \mathds{B}^n   \to
+\mathds{B}^n  \big/  G_f  \textrm{  est chaotique} \right\}$.
+\end{itemize}
+
+
+Commençons par caractériser l'ensemble $\mathcal{T}$ des fonctions transitives:
+
+\begin{Theo} $G_f$  est transitive si et seulement si 
+ $\Gamma(f)$ est fortement connexe.
+\end{Theo}
+
+\begin{Proof} 
+
+$\Longleftarrow$ Supposons que $\Gamma(f)$ soit fortement connexe.
+Soient $(S,x)$ et $(S',x')$ deux points de $\mathcal{X}$ 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')$.
+
+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 
+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$.
+
+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 
+$\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.
+
+$\Longrightarrow$ Démontrons la contraposée.
+Si $\Gamma(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'$. 
+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)$ 
+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')$. 
+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.
+Pour tout entier naturel $t$, on a 
+$G_f^t(S'',x'') \neq (S',x')$.
+Ainsi $G_f$ n'est pas transitive et 
+par contraposée, on a la démonstration souhaitée.
+\end{Proof}
+
+
+Prouvons à présent le théorème suivant: 
+
+\begin{Theo}
+\label{Prop: T est dans R} $\mathcal{T} \subset \mathcal{R}$.
+\end{Theo}
+
+
+\begin{Proof}  
+Soit $f:\Bool^n\to\Bool^n$ telle que  $G_f$ est transitive (\textit{i.e.}
+$f$ appartient à $\mathcal{T}$). 
+Soit $(S,x) \in\mathcal{X}$ 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.
+
+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.
+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$.
+
+Soit alors la  stratégie $\tilde S$ qui alterne les $t_1$ premiers termes
+de $S$ avec les $t_2$ premiers termes de $S'$. 
+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 
+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$.
+\end{Proof}
+
+On peut conclure  que $\mathcal{C} = \mathcal{R} \cap \mathcal{T}
+= \mathcal{T}$. On a alors la  caractérisation suivante:
+
+\begin{Theo}%[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.
+\end{Theo}
+
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: "main"
+%%% End: 

diff --git a/exp.tex b/exp.tex
new file mode 100644 (file)
index 0000000..931aec7
--- /dev/null
+++ b/exp.tex
@@ -0,0 +1,267 @@
+Cette section présente une application directe de la théorie développée ci-avant
+à la génération de nombres pseudo-aléatoires. On présente tout d'abord le générateur
+basé sur des fonctions chaotiques (section~\ref{sub:prng:algo}), 
+puis comment intégrer la contrainte de \gls{distributionuniforme} (cf. glossaire) 
+de la sortie 
+dans le choix de la fonction à itérer (section~\ref{sub:prng:unif}). 
+
+
+\subsection{Générateur de nombres pseudo-aléatoires basé sur le chaos}
+\label{sub:prng:algo}
+
+On peut penser à construire un générateur de nombres pseudo-aléatoires comme dans l'algorithme~\ref{CI Algorithm} donné ci-dessous.
+
+\begin{algorithm}[h]
+%\begin{scriptsize}
+\KwIn{une fonction $f$, un nombre d'itérations $b$, 
+une configuration initiale $x^0$ ($n$ bits)}
+\KwOut{une configuration $x$ ($n$ bits)}
+$x\leftarrow x^0$\;
+$k\leftarrow b + \textit{Random}(b+1)$\;
+%$k\leftarrow b + \textit{XORshift}(b+1)$\;
+\For{$i=0,\dots,k-1$}
+{
+$s\leftarrow{\textit{Set}(\textit{Random}(2^n))}$\;
+%$s\leftarrow{\textit{XORshift}(n)}$\;
+$x\leftarrow{F_f(s,x)}$\;
+}
+return $x$\;
+%\end{scriptsize}
+\caption{Algorithme de génération de nombres pseudo-aléatoires 
+à l'aide de la fonction chaotique $G_f$.}
+\label{CI Algorithm}
+\end{algorithm}
+
+
+Celui-ci prend  en entrée: une  fonction $f$; un  entier $b$, qui assure  que le
+nombre  d'itérations est compris  entre $b+1  $ et  $2b+1$ et  une configuration
+initiale $x^0$.   Il retourne  une nouvelle configuration  $x$.  En  interne, il
+exploite    la   fonction \linebreak    $\textit{Set}   :    \{1,\ldots,2^n\}   \rightarrow
+\mathcal{P}(\{1,\ldots   n\})$   qui   donne   l'ensemble   dont   la   fonction
+caractéristique  serait  représentée par  le  nombre  donné  en argument  et  un
+algorithme de génération de nombres pseudo-aléatoires \textit{Random}$(l)$.  Cet
+algorithme est utilisé  dans notre générateur pour construire  la longueur de la
+stratégie ainsi  que les éléments  qui la composent.  Pratiquement,  il retourne
+des    entiers   dans    $\llbracket    1   ;    l    \rrbracket$   selon    une
+\gls{distributionuniforme} %(cf. glossaire)
+et utilise \textit{XORshift} qui est
+une classe de  générateurs de nombres pseudo-aléatoires très  rapides conçus par
+George Marsaglia~\cite{Marsaglia98}.
+
+% L'algorithme \textit{XORshift} exploite itérativement
+% la fonction \og \gls{xor}\fg{} $\oplus$ (cf. glossaire) 
+% sur des nombres obtenus grâce à des \glspl{decalageDeBits} (cf. glossaire).
+
+L'algorithme \textit{XORshift} 
+exploite itérativement l'opérateur $\oplus$  
+sur des nombres obtenus grâce à des \glspl{decalageDeBits} (cf. glossaire)
+.
+Cet opérateur, défini dans $\Bool^{n}$, 
+applique la fonction \og  \gls{xor} \fg{} (cf. glossaire) 
+aux bits de même rang de ses deux opérandes (\og opération bit à bit \fg{}).
+Une instance de cette classe est donnée dans l'algorithme~\ref{XORshift} détaillé
+ci-dessous.
+
+\begin{algorithm}[h]
+%\SetLine
+\KwIn{la configuration interne $z$ (un mot de 32-bit)}
+\KwOut{$y$ (un mot de 32-bits)}
+$z\leftarrow{z\oplus{(z\ll13)}}$\;
+$z\leftarrow{z\oplus{(z\gg17)}}$\;
+$z\leftarrow{z\oplus{(z\ll5)}}$\;
+$y\leftarrow{z}$\;
+return $y$\;
+\medskip
+\caption{Une boucle de l'algorithme de \textit{XORshift}.}
+\label{XORshift}
+\end{algorithm}
+
+Il reste à instancier une fonction $f$ dans 
+l'algorithme~\ref{CI Algorithm}. 
+%en adéquation avec  l'approche développée 
+%en section~\ref{sec:sccg}.
+La section suivante montre comment l'uniformité de la distribution
+contraint cette instanciation.
+
+\subsection{Un générateur à sortie uniformément distribuée}
+\label{sub:prng:unif}
+
+Une matrice \emph{stochastique} est une matrice carrée
+dont tous les éléments sont positifs ou nuls et dont
+la somme de chaque ligne
+vaut 1. 
+Une matrice est \emph{doublement stochastique} si elle est stochastique et que la somme de chaque colonne est 1.
+Enfin, une matrice stochastique de taille $n \times n$ est \emph{régulière} 
+si  la propriété suivante est établie:
+$$\exists k \in \mathds{N}^\ast, \forall i,j \in \llbracket 1; n \rrbracket, M_{ij}^k>0.$$
+
+On énonce enfin le théorème suivant liant les 
+\glspl{vecteurDeProbabilite} (cf. glossaire) 
+et les \glspl{chaineDeMarkov}  (cf. glossaire)
+:
+
+ 
+\begin{Theo}\label{th}
+  Si $M$ est une matrice stochastique régulière, alors $M$ 
+  possède un unique vecteur stationnaire de probabilités  $\pi$
+  ($\pi.M = \pi$).
+  De plus, si $\pi^0$ est un \gls{vecteurDeProbabilite} 
+ et si on définit 
+  la suite $(\pi^{k})^{k \in  \Nats}$ par 
+  $\pi^{k+1} = \pi^k.M $ pour $k = 0, 1,\dots$ 
+  alors la \gls{chaineDeMarkov} $\pi^k$
+  converge vers $\pi$ lorsque $k$ tend vers l'infini.
+\end{Theo}
+
+
+Montrons sur un exemple jouet à deux éléments 
+que ce théorème permet de vérifier si la sortie d'un générateur de 
+nombres pseudo-aléatoires est uniformément distribuée ou non.
+Soit alors $g$ et $h$ deux fonctions  de $\Bool^2$
+définies par $g(x_1,x_2)=(\overline{x_1},x_1.\overline{x_2}) $
+et $h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$.
+% Leurs graphes d'interactions donnés en figures \ref{fig:g:inter} et \ref{fig:h:inter}
+% vérifient les hypothèses du théorème~\ref{th:Adrien}. 
+Leurs graphes d'itérations
+sont  fortement connexes, ce que l'on a pu déjà vérifier aux figures
+\ref{fig:g:iter} et \ref{fig:h:iter}.
+\textit{A priori}, ces deux fonctions pourraient être intégrées
+dans un générateur de nombres pseudo-aléatoires. Montrons que ce n'est pas le cas pour $g$ et 
+que cela l'est pour $h$.
+
+Comme le générateur \textit{Random} possède une sortie uniformément 
+distribuée,  la  stratégie est uniforme sur $\llbracket 1, 2^2 \rrbracket$,
+et donc, 
+pour tout sommet de $\Gamma(g)$ et de  $\Gamma(h)$,
+chaque arc sortant de ce sommet a, parmi l'ensemble des arcs sortant 
+de ce sommet, une probabilité $1/4$ d'être celui qui sera traversé.
+En d'autres mots, $\Gamma(g)$ est le graphe orienté d'une chaîne de Markov.
+Il est facile de vérifier que la \gls{matriceDeTransitions} (cf. glossaire)
+d'un tel processus 
+est $M_g   = \frac{1}{4} \check{M}_g$, 
+où $\check{M}_g$ est la \gls{matriceDAdjacence} (cf. glossaire)
+donnée en figure~\ref{fig:g:incidence} (voir ci-après), et similairement pour $M_h$. 
+
+\begin{figure}[ht]
+  \begin{center}
+    \subfloat[$\check{M}_g $]{
+      \begin{minipage}{0.25\textwidth}
+        \begin{center}
+          % \vspace{-3cm}
+          $\left( 
+            \begin{array}{cccc} 
+              2 & 0 & 2 & 0 \\ 
+              1 & 1 & 1 & 1 \\ 
+              1 & 1 & 1 & 1 \\ 
+              1 & 1 & 1 & 1 
+            \end{array}
+          \right)
+          $
+        \end{center}
+      \end{minipage}
+      \label{fig:g:incidence}
+    }
+    \subfloat[$\check{M}_h $]{
+      \begin{minipage}{0.25\textwidth}
+        \begin{center}
+          $\left( 
+            \begin{array}{cccc} 
+              2 & 0 & 2 & 0 \\ 
+              0 & 2 & 0 & 2 \\ 
+              1 & 1 & 1 & 1 \\ 
+              1 & 1 & 1 & 1 
+            \end{array}
+          \right)
+          $
+        \end{center}
+      \end{minipage}
+      \label{fig:h:incidence}
+    }
+  \end{center}
+  \caption{Graphe des fonctions candidates avec $n=2$.}
+  \label{fig:xplgraph}
+\end{figure}
+
+Les deux matrices $M_g$ et $M_h$ sont  stochastiques. Pour
+montrer qu'elles sont régulières il suffit de constater qu'aucun élément de 
+$M^2_g$ ni de  $M^2_h$ n'est nul.
+De plus, les vecteurs de probabilités 
+$\pi_g=(\frac{1}{3}, \frac{1}{6},\frac{1}{3},\frac{1}{6})$ et
+$\pi_h=(\frac{1}{4},\frac{1}{4},\frac{1}{4},\frac{1}{4})$ 
+vérifient $\pi_g M_g = \pi_g$ et 
+$\pi_h M_h = \pi_h$. 
+Alors d'après le théorème~\ref{th}, 
+pour n'importe quel vecteur initial de probabilités $\pi^0$, on a 
+$\lim_{k \to \infty} \pi^0 M^k_g = \pi_g$ et 
+$\lim_{k \to \infty} \pi^0 M^k_h = \pi_h$. 
+Ainsi, la chaîne de Markov associée à $h$ tend vers une 
+distribution uniforme, contrairement à celle associée à $g$.
+On en déduit que $g$ ne devrait pas être itérée dans 
+un générateur de nombres pseudo-aléatoires.
+Au contraire, 
+$h$ devrait pouvoir être embarquée dans l'algorithme~\ref{CI Algorithm}, 
+pour peu que le nombre $b$ d'itérations entre deux mesures successives 
+de valeurs  soit suffisamment grand de sorte que
+le vecteur d'état de la chaîne de Markov
+ait une distribution suffisamment proche de la distribution uniforme.
+
+
+Considérons le lemme technique suivant:
+\begin{Lemma}\label{lem:stoc}
+Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\Gamma(f)$ son graphe d'itérations, $\check{M}$ la matrice d'adjacence de $\Gamma(f)$, et  $M$  la matrice 
+$2^n\times 2^n$  définie par
+$M = \frac{1}{n}\check{M}$.
+Alors $M$ est une matrice stochastique régulière si et seulement si
+$\Gamma(f)$ est fortement connexe.
+\end{Lemma}
+
+\begin{Proof}  
+On remarque tout d'abord que $M$ 
+est une matrice stochastique par construction.
+Supposons $M$ régulière. 
+Il existe donc  $k$ tel que $M_{ij}^k>0$ pour chaque $i,j\in \llbracket
+1;  2^n  \rrbracket$. L'inégalité  $\check{M}_{ij}^k>0$  est alors établie.
+Puisque $\check{M}_{ij}^k$ est le nombre de chemins de  $i$ à $j$ de longueur $k$
+dans $\Gamma(f)$ et puisque ce nombre est positif, alors 
+$\Gamma(f)$ est fortement connexe.
+
+Réciproquement si $\Gamma(f)$ 
+est fortement connexe, alors pour tous les sommets $i$ et $j$, un chemin peut être construit pour atteindre  $j$  depuis $i$ en au plus $2^n$ étapes.
+Il existe donc 
+$k_{ij} \in \llbracket 1,  2^n \rrbracket$ tel que $\check{M}_{ij}^{k_{ij}}>0$.  
+Comme tous les  multiples $l \times k_{ij}$ de $k_{ij}$ sont tels que 
+$\check{M}_{ij}^{l\times  k_{ij}}>0$, 
+on peut conclure que, si 
+$k$ est le plus petit multiple commun de $\{k_{ij}  \big/ i,j  \in \llbracket 1,  2^n \rrbracket  \}$ alors
+$\forall i,j  \in \llbracket  1, 2^n \rrbracket,  \check{M}_{ij}^{k}>0$. 
+Ainsi, $\check{M}$ et donc $M$ sont régulières.
+\end{Proof}
+
+Ces résultats permettent de formuler et de prouver le théorème suivant:
+
+\begin{Theo}
+  Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\Gamma(f)$ son 
+  graphe d'itérations, $\check{M}$ sa matrice d'adjacence
+  et $M$ une matrice  $2^n\times 2^n$  définie comme dans le lemme précédent.
+  Si $\Gamma(f)$ est fortement connexe, alors 
+  la sortie du générateur de nombres pseudo-aléatoires détaillé par 
+  l'algorithme~\ref{CI Algorithm} suit une loi qui 
+  tend vers la distribution uniforme si 
+  et seulement si  $M$ est une matrice doublement stochastique.
+\end{Theo}
+\begin{Proof}
+  $M$ est une matrice stochastique régulière (lemme~\ref{lem:stoc}) 
+  qui a un unique vecteur de probabilités stationnaire
+  (théorème \ref{th}).
+  Soit $\pi$  défini par 
+  $\pi = \left(\frac{1}{2^n}, \hdots, \frac{1}{2^n} \right)$.
+  On a  $\pi M = \pi$ si et seulement si
+  la somme des valeurs de chaque colonne de $M$  est 1, 
+  \textit{i.e.} si et seulement si 
+  $M$ est  doublement  stochastique.
+\end{Proof}
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: "main"
+%%% End: 

diff --git a/glossaire.tex b/glossaire.tex
new file mode 100644 (file)
index 0000000..7bf0eb6
--- /dev/null
+++ b/glossaire.tex
@@ -0,0 +1,82 @@
+\newglossaryentry{graphoriente}{name=Graphe orienté, description={
+Un graphe orienté $G=(S,A)$
+est défini par la donnée d'un ensemble de sommets $S$ et 
+d'un ensemble d'arcs $A$, 
+chaque arc étant représenté par un couple de sommets.
+Si $x$ et $y$ sont des sommets de $S$, 
+le couple $(x,y)$ représente l'arc orienté allant du sommet \emph{origine}  
+$x$ au sommet \emph{extrémité} $y$}}
+
+\newglossaryentry{graphfortementconnexe}{name=Graphe fortement connexe, description={
+Un graphe orienté $G=(S,A)$ est fortement connexe si pour tout
+couple de sommets $x$, $y$ de $S$ il existe un chemin reliant $x$ à $y$
+et un chemin reliant $y$ à $x$}}      
+
+\newglossaryentry{distributionuniforme}{name=distribution uniforme, description={Les lois de distribution uniforme (ou loi uniformes continues) 
+forment une famille de lois à densité, caractérisées par le fait que
+tous les intervalles de même longueur inclus dans le support de la loi ont 
+la même probabilité}}
+
+\newglossaryentry{partieentiere}{name=partie entière, symbol={\ensuremath{\lfloor x \rfloor}},
+description={La partie entière d'un nombre réel (notée $\lfloor x \rfloor$) est l'entier qui lui est immédiatement
+ inférieur ou égal}}
+
+\newglossaryentry{distanceHamming}{name=distance de Hamming, description=
+{La distance de Hamming entre deux éléments $x=(x_1,\ldots,x_n)$ et 
+$y=(y_1,\ldots,y_n)$ dans $\Bool^n$ 
+est le nombre d'indices $i$, $1 \le i \le n$ tels que 
+$x_i$ diffère de $y_i$}}
+
+\newglossaryentry{decalageDeBits}{name=décalage de bits,
+plural=décalages de bits,
+description={Soit $x$ un nombre binaire de $n$ bits et $b$ un entier. 
+Le nombre binaire de $n$ bits $x \ll b$ (respectivement $x \gg b$)
+est obtenu en 
+décalant les bits de $x$ de $b$ bits vers la gauche 
+(resp. vers la droite) et
+en complétant avec des zéros à droite (resp. à gauche)}}
+
+\newglossaryentry{chaineDeMarkov}{name=chaîne de  Markov,
+plural=chaînes de  Markov, description={
+On se restreint à la définition d'une chaîne de Markov homogène. Celle-ci 
+désigne une suite de variables aléatoires $(X_n)_{n \in \Nats}$
+à temps discret, à espace d'états discret, sans mémoire et 
+dont le mécanisme de transition ne change pas au cours du temps.
+Formellement la propriété suivante doit être établie :\linebreak
+\begin{small}
+  $
+  % \begin{equation*}
+  %   \begin{array}{l}
+  \forall n \ge 0, \forall (i_0, \ldots, i_{n-1}, i,j),\\
+  \textrm{ }P(X_{n+1}=j\mid X_0=i_0, X_1=i_1, \ldots, X_{n-1}=i_{n-1}, X_{n}=i)
+  \textrm{ }= P(X_{n+1}=j\mid X_n=i)
+  % \end{array}
+  % \end{equation*}
+  $
+\end{small}}}
+
+\newglossaryentry{vecteurDeProbabilite}{name=vecteur de probabilités,
+plural=vecteurs de probabilités, description={
+Un vecteur de probabilités est un vecteur tel que toutes ses composantes
+sont positives ou nulles et leur somme vaut 1}}
+
+\newglossaryentry{matriceDAdjacence}{name=matrice d'adjacence, 
+description={La matrice d'adjacence du graphe orienté $G=(S,A)$ à $n$ sommets 
+est la matrice $\check{M}$ de dimensions $n \times n$ 
+dont l'élément $\check{M}_{ij}$ représente le nombre d'arcs d'origine $i$ et d'extrémité $j$}}
+
+\newglossaryentry{xor}{name={ou exclusif}, symbol={\ensuremath{\oplus}}, 
+description={La fonction \og ou exclusif\fg{} (XOR, notée \ensuremath{\oplus}), est l'opérateur de $\Bool^2$ dans
+$\Bool$  qui prend la valeur 1 si seulement 
+si les deux opérandes ont des valeurs distinctes}}
+
+\newglossaryentry{matriceDeTransitions}{name=matrice de transitions, description=
+{
+ Le nombre $p_{ij}= P(X_1=j \mid X_0 =i)$ est appelé probabilité de transition
+  de l'état $i$  à l'état $j$ en un pas. La matrice composée des $p_{ij}$
+  est la  matrice de transitions associée à la chaîne de Markov $X$}}
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: "main"
+%%% End: 

diff --git a/gray.tex b/gray.tex
new file mode 100644 (file)
index 0000000..129e2df
--- /dev/null
+++ b/gray.tex
@@ -0,0 +1,245 @@
+On  a vu  dans  la  partie précédente  que  pour avoir  un  générateur à  sortie
+uniforme, il est nécessaire que  la matrice d'adjacence du graphe d'itération du
+système  soit doublement stochastique.   Nous présentons  dans cette  partie une
+méthode permettant de générer de telles matrices.
+
+Les approches théoriques basées sur la programmation logique par contraintes sur
+domaines  finis ne  sont pas  envisageables en  pratique dès  que la  taille des
+matrices considérées devient suffisamment grande.
+
+Une approche plus pragmatique consiste  à supprimer un cycle hamiltonien dans le
+graphe d'itérations, ce qui revient à supprimer en chaque n{\oe}ud de ce graphe une
+arête sortante et une arête entrante.
+
+\begin{xpl}
+  On considère   le 
+  $3$-cube   dans  lequel  le cycle hamiltonien défini par la séquence
+  $000,100,101,001,011,111,110,010,000$ a été supprimé.
+  Ceci correspond à la fonction $f^*$ définie par 
+$$f^*(x_1,x_2,x_3)=
+(x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
+\overline{x_1}\overline{x_3} + x_1x_2).
+$$ 
+
+Le graphe  des itérations chaotiques de  $f^*$  est représenté à la 
+Figure~\ref{fig:iteration:f*}.
+La matrice de Markov correspondante est donnée à 
+la figure~\ref{fig:markov:f*}.
+
+\begin{figure}[ht]
+  \begin{center}
+    \subfloat[Graphe des itérations chaotiques de $f^*$.
+    \label{fig:iteration:f*}]{
+      \begin{minipage}{0.55\linewidth}
+        \centering
+        \includegraphics[width=\columnwidth]{images/iter_f}%
+      \end{minipage}
+    }%
+    \subfloat[Matrice de Markov du graphe d'itérations chaotiques de 
+    $f^*$\label{fig:markov:f*}]{%
+      \begin{minipage}{0.35\linewidth}
+        \begin{scriptsize}
+          \begin{center}
+            $ \dfrac{1}{4} \left(
+              \begin{array}{cccccccc}
+                1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
+              
+                1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
+              
+                0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
+              
+                1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
+              
+                1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\
+              
+                0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
+              
+                0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
+              
+                0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
+              
+              \end{array}            \right) $
+          \end{center}
+        \end{scriptsize}
+      \end{minipage}
+    }%
+    \caption{Représentations de $f^*(x_1,x_2,x_3)=
+      (x_2 \oplus x_3, \overline{x_1}\overline{x_3} + x_1\overline{x_2},
+      \overline{x_1}\overline{x_3} + x_1x_2)$.}\label{fig1}
+  \end{center}
+\end{figure}
+\end{xpl}
+
+\subsection{Suppression des cycles hamiltoniens}
+\label{sec:hamiltonian}
+
+Dans un premier temps, nous montrons en section~\ref{sub:removing:theory} que la
+suppression  d'un  cycle  hamiltonien   produit  bien  des  matrices  doublement
+stochastiques.   Nous  établissons  ensuite  le  lien avec  les  codes  de  Gray
+équilibrés.
+
+\subsubsection{Aspects théoriques}
+\label{sub:removing:theory}
+
+Nous donnons  deux résultats complémentaires, reliant la  suppression d'un cycle
+hamiltonien  du $n$-cube,  les matrices  doublement stochastiques  et  la forte
+connexité du graphe d'itérations.
+
+\begin{Theo}\label{th:supprCH}
+  La suppression d'un cycle hamiltonien dans une matrice de Markov $M$, issue du
+  $n$-cube, produit une matrice doublement stochastique.
+\end{Theo}
+\begin{Proof}
+
+Un cycle hamiltonien passe par chaque n{\oe}ud une et une seule fois.
+Pour chaque n{\oe}ud $v$ dans le $n$-cube $C_1$,
+une arête entrante $(o,v)$ et une arête sortante $(v,e)$ 
+est ainsi enlevée.
+Considérons un autre  $n$-cube $C_2$ auquel on ajoute les arêtes 
+pour le rendre complet. La matrice de Markov $M$ correspondante est
+remplie de $\frac{1}{2^n}$ et est doublement stochastique.
+Comme on enlève exactement une arête sortante $(v,e)$ 
+à chaque n{\oe}ud $v$ dans $C_1$, on enlève ainsi dans 
+$C_2$ les $2^{n-1}$ arêtes issues de $v$ et 
+relatives aux parties de $\{1,\ldots,n\}$ qui
+contiennent $e$. Cela revient à annuler 
+dans la matrice $M$ les $2^{n-1}$ coefficients correspondants et ajouter 
+$1/2$ à l'élément $M_{vv}$.
+La matrice $M$ reste stochastique.
+On effectue un raisonnement similaire pour les arêtes entrantes:
+comme on enlève exactement une arête entrante $(o,v)$ pour chaque 
+n{\oe}ud $v$ dans $C_1$, dans $C_2$, ce sont exactement 
+$2^{n-1}$ arêtes menant à $v$ qui sont enlevées. 
+Dans $M$ les $2^{n-1}$ coefficients correspondants sont mis à 0 et 
+$M_{vv}$ vaut alors $\frac{2^{n-1} +1}{2}$.
+$M$ est donc doublement stochastique.
+\end{Proof}
+
+
+
+\begin{Theo}\label{th:grapheFC}
+  Le  graphe d'itérations  issu du  $n$-cube,  auquel un  cycle hamiltonien  est
+  enlevé, est fortement connexe.
+\end{Theo}
+
+
+\begin{Proof}
+On considère les deux $n$-cubes $C_1$ et $C_2$ définis 
+dans la preuve du théorème~\ref{th:supprCH}.
+Dans $C_1$ on considère le cycle inverse $r$ du cycle
+hamiltonien $c$.
+Aucun arc n'appartient à la fois  à $r$ et à $c$: 
+en effet, sinon $c$ contiendrait un n{\oe}ud deux fois.
+Ainsi aucune arête de $r$ n'est enlevée dans $C_1$.
+Le cycle $r$ est évidement un cycle hamiltonien et contient tous les n{\oe}uds.
+Tous les n{\oe}uds de $C_1$ dans lequel $c$ a été enlevé sont accessibles 
+depuis n'importe quel n{\oe}ud. Le graphe des itérations $\Gamma$ qui
+étend le précédent graphe est ainsi fortement connexe. 
+
+\end{Proof}
+
+
+
+Les preuves, relativement directes, sont  laissées en exercices au lecteur.  Par
+contre, ce qui  est moins aisé est la génération de  cycles hamiltoniens dans le
+$n$-cube,  ce qui  revient à  trouver des  \emph{codes de  Gray  cycliques}.  On
+rappelle que  les codes de  Gray sont des  séquences de mots binaires  de taille
+fixe ($n$),  dont les éléments successifs ne  différent que par un  seul bit. Un
+code  de  Gray est  \emph{cyclique}  si  le premier  élément  et  le dernier  ne
+différent que par un seul bit.
+
+\subsection{Lien avec les codes de Gray cycliques (totalement) équilibrés}
+\label{sub:gray}
+
+La borne  inférieure du  nombre de codes  de Gray  ($\left(\frac{n*\log2}{e \log
+    \log   n}\times(1  -  o(1))\right)^{2^n}$),   donnée  dans~\cite{Feder2009NTB},
+indique  une explosion combinatoire  pour notre  recherche.  Afin  de contourner
+cette  difficulté,  nous  nous   restreignons  aux  codes  induisant  un  graphe
+d'itérations $\Gamma(f)$  \emph{uniforme}.  Cette uniformité se  traduit par des
+nombres d'arcs  équilibrés entre les  \emph{dimensions} du graphe,  la dimension
+$i$  correspondant aux  seules variations  du  bit $i$  (parmi les  $n$ bits  au
+total).   Cette  approche  revient  à  chercher  des  codes  de  Gray  cycliques
+\emph{équilibrés}.
+
+Un code de Gray équilibré peut être défini de la façon suivante :
+
+\begin{Def}[Code de Gray cyclique équilibré]\label{def:grayequ}
+  Soit $L = w_1,  w_2, \dots, w_{2^n}$ la séquence d'un code  de Gray cyclique à
+  $n$ bits.  Soit $S = s_1,  s_2, \dots, s_{2^n}$ la séquence des transitions où
+  $s_i$, $1  \le i \le 2^n$  est l'indice du seul  bit qui varie  entre les mots
+  $w_i$ et  $w_{i+1}$. Enfin, soit  $\textit{NT}_n : \{1,\dots,  n\} \rightarrow
+  \{0, \ldots, 2^n\}$  la fonction qui au paramètre  $i$ associe le \emph{nombre
+    de transitions} présentes dans la séquence $L$ pour le bit $i$, c'est-à-dire
+  le nombre d'occurrences de $i$ dans $S$.
+  
+  Le      code       $L$      est      \textbf{équilibré}       si      $\forall
+  i,j\in\{1,...,n\},~|\textit{NT}_n(i)  -  \textit{NT}_n(j)|  \le  2$.   Il  est
+  \textbf{totalement             équilibré}             si             $\forall
+  i\in\{1,...,n\},~\textit{NT}_n(i)=\frac{2^n}{n}$.
+\end{Def}
+
+On peut  donc déjà déduire  qu'il ne peut  exister des codes de  Gray totalement
+équilibrés que  pour les  systèmes ayant un  nombre d'éléments $n=2^k,  k>0$. De
+plus,  comme  dans tout  code  de  Gray  cyclique, $\textit{NT}_n(i)$  est  pair
+$\forall  i\in\{1,...,n\}$,  alors  les  systèmes  ayant  un  nombre  d'éléments
+différent  de $2^k$,  ne peuvent  avoir  que des  codes de  Gray équilibrés  avec
+$\textit{NT}_n(i)=\lfloor\frac{2^n}{n}\rfloor$                                 ou
+$\textit{NT}_n(i)=\lceil\frac{2^n}{n}\rceil,    \forall    i\in\{1,...,n\}$   et
+vérifiant $\sum_{i=1}^nNT_n(i) = 2^n$.
+
+\begin{xpl}
+  Soit  $L^*=000,100,101,001,011,111,110,010$ le code  de Gray  correspondant au
+  cycle hamiltonien enlevé de $f^*$.  Sa séquence des transitions est \linebreak
+  $S=3,1,3,2,3,1,3,2$  et  les nombres  de  transitions sont  $\textit{TC}_3(1)=
+  \textit{TC}_3(2)=2$ et $\textit{TC}_3(3)=4$. Un tel code est équilibré.
+
+  Si l'on  considère maintenant $L^4=$ 0000,  0010, 0110, 1110, 1111,  0111, 0011,
+  0001,  0101, 0100,  1100, 1101,  1001,  1011, 1010,  1000,  un  code de  Gray
+  cyclique. En construisant la séquence $S=$ 2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4, 
+  on constate que  $\forall
+  i\in\{1,..,4\},~\textit{TC}_4(i)=4$ et donc que 
+  ce code est totalement équilibré.
+\end{xpl}
+
+\subsection{Génération de codes de Gray équilibrés par induction}
+\label{sec:induction}
+
+Dans  leur  article de  2004~\cite{ZanSup04},  Zanten  et  Suparta proposent  un
+algorithme inductif  pour générer  des codes  de Gray équilibrés  de $n$  bits à
+partir   de  codes   de  $n-2$   bits.   Cependant,   leur  méthode   n'est  pas
+constructive. En effet, elle effectue  des manipulations sur un partitionnement du
+code de Gray  initial de $n-2$ bits pour  obtenir un code de Gray  sur $n$ bits,
+mais le  résultat n'est pas  systématiquement équilibré. Il est  donc nécessaire
+d'évaluer les résultats obtenus à  partir de tous les partitionnements réalisables
+en suivant les  contraintes spécifiées.  Or, le nombre  de possibilités augmente
+exponentiellement (voir~\cite{Mons14} pour  l'évaluation détaillée), ce qui rend
+déraisonnable    tout   parcours    exhaustif.    Une    amélioration   proposée
+dans~\cite{Mons14} permet  de réduire le nombre  de partitionnements considérés,
+mais l'ordre  de grandeur  reste similaire. On  constate donc clairement  ici la
+nécessité de trouver  des algorithmes de génération de  codes de Gray équilibrés
+plus  efficaces.  Ce  problème  représente  une des  voies  que nous  souhaitons
+explorer dans la suite de nos travaux.
+
+Le   tableau~\ref{table:nbFunc}  donne  le   nombre  de   fonctions  différentes
+compatibles avec les codes de  Gray équilibrés générés par l'approche précédente
+selon le nombre  de bits. Il donne  donc la taille de la  classe des générateurs
+pouvant être produits.  Les  cas 7 et 8 ne sont que  des bornes minimales basées
+sur des sous-ensembles des partitionnements possibles.
+
+\begin{table}[table:nbFunc]{Nombre de générateurs selon le nombre de bits.}
+  \begin{center}
+    \begin{tabular}{|l|c|c|c|c|c|}
+      \hline
+      $n$              & 4 & 5 & 6    & 7      & 8      \\
+      \hline
+      nb. de fonctions & 1 & 2 & 1332 & > 2300 & > 4500 \\
+      \hline
+    \end{tabular}
+  \end{center}
+\end{table}
+
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: "main"
+%%% End: 

diff --git a/images/Gi.dot b/images/Gi.dot
new file mode 100644 (file)
index 0000000..cf9e416
--- /dev/null
+++ b/images/Gi.dot
@@ -0,0 +1,9 @@
+digraph {
+1 -> 1 [label=" -"]
+1 -> 4 [label=" +-"]
+2 -> 2 [label=" -"]
+2 -> 4 [label=" +-"]
+3 -> 3 [label=" -"]
+3 -> 4 [label=" +-"]
+4 -> 4 [label=" +-"]
+}
\ No newline at end of file

diff --git a/images/g-eps-converted-to.pdf b/images/g-eps-converted-to.pdf
new file mode 100644 (file)
index 0000000..8973679
Binary files /dev/null and b/images/g-eps-converted-to.pdf differ

diff --git a/images/g.dot b/images/g.dot
new file mode 100644 (file)
index 0000000..ae54226
--- /dev/null
+++ b/images/g.dot
@@ -0,0 +1,21 @@
+digraph {
+00 [shape="none",label="00", pos="0,0!"];
+01 [shape="none",label="01", pos="0,2!"];
+10 [shape="none",label="10", pos="2,0!"];
+11 [shape="none", label="11", pos="2,2!"];
+ 00 -> 10 [headlabel="{1},{1,2}", labeldistance=5.0,labelangle=-15]
+ 01 -> 00 [headlabel="{2}", labeldistance=5.0,labelangle=15]
+ 01 -> 11 [headlabel="{1}", labeldistance=5.0,labelangle=-15]
+ 01 -> 10 [headlabel="{1,2}", labeldistance=5.0,labelangle=-15]
+ 10 -> 11 [headlabel="{2}", labeldistance=5.0,labelangle=-15]
+ 10 -> 00 [headlabel="{1}", labeldistance=5.0,labelangle=-15]
+ 10 -> 01 [headlabel="{1,2}", labeldistance=5.0,labelangle=-15]
+ 11 -> 10 [headlabel="{2}", labeldistance=5.0,labelangle=-15]
+ 11 -> 01 [headlabel="{1}", labeldistance=5.0,labelangle=-15]
+ 11 -> 00 [headlabel="{1,2}", labeldistance=5.0,labelangle=-15]
+ 01:nw -> 01:sw [headlabel="∅", labeldistance=2.5, labelangle=-90]
+ 00:nw -> 00:sw [headlabel="∅,{2}", labeldistance=2.5, labelangle=-90]
+ 11:ne -> 11:se [headlabel="∅",labeldistance=2.5,labelangle=90]
+ 10:ne -> 10:se [headlabel="∅",labeldistance=2.5,labelangle=90]
+
+}

diff --git a/images/g.eps b/images/g.eps
new file mode 100644 (file)
index 0000000..975515b
--- /dev/null
+++ b/images/g.eps
@@ -0,0 +1,476 @@
+%!PS-Adobe-3.0
+%%Creator: graphviz version 2.36.0 (20140111.2315)
+%%Title: %3
+%%Pages: (atend)
+%%BoundingBox: (atend)
+%%EndComments
+save
+%%BeginProlog
+/DotDict 200 dict def
+DotDict begin
+
+/setupLatin1 {
+mark
+/EncodingVector 256 array def
+ EncodingVector 0
+
+ISOLatin1Encoding 0 255 getinterval putinterval
+EncodingVector 45 /hyphen put
+
+% Set up ISO Latin 1 character encoding
+/starnetISO {
+        dup dup findfont dup length dict begin
+        { 1 index /FID ne { def }{ pop pop } ifelse
+        } forall
+        /Encoding EncodingVector def
+        currentdict end definefont
+} def
+/Times-Roman starnetISO def
+/Times-Italic starnetISO def
+/Times-Bold starnetISO def
+/Times-BoldItalic starnetISO def
+/Helvetica starnetISO def
+/Helvetica-Oblique starnetISO def
+/Helvetica-Bold starnetISO def
+/Helvetica-BoldOblique starnetISO def
+/Courier starnetISO def
+/Courier-Oblique starnetISO def
+/Courier-Bold starnetISO def
+/Courier-BoldOblique starnetISO def
+cleartomark
+} bind def
+
+%%BeginResource: procset graphviz 0 0
+/coord-font-family /Times-Roman def
+/default-font-family /Times-Roman def
+/coordfont coord-font-family findfont 8 scalefont def
+
+/InvScaleFactor 1.0 def
+/set_scale {
+       dup 1 exch div /InvScaleFactor exch def
+       scale
+} bind def
+
+% styles
+/solid { [] 0 setdash } bind def
+/dashed { [9 InvScaleFactor mul dup ] 0 setdash } bind def
+/dotted { [1 InvScaleFactor mul 6 InvScaleFactor mul] 0 setdash } bind def
+/invis {/fill {newpath} def /stroke {newpath} def /show {pop newpath} def} bind def
+/bold { 2 setlinewidth } bind def
+/filled { } bind def
+/unfilled { } bind def
+/rounded { } bind def
+/diagonals { } bind def
+/tapered { } bind def
+
+% hooks for setting color 
+/nodecolor { sethsbcolor } bind def
+/edgecolor { sethsbcolor } bind def
+/graphcolor { sethsbcolor } bind def
+/nopcolor {pop pop pop} bind def
+
+/beginpage {   % i j npages
+       /npages exch def
+       /j exch def
+       /i exch def
+       /str 10 string def
+       npages 1 gt {
+               gsave
+                       coordfont setfont
+                       0 0 moveto
+                       (\() show i str cvs show (,) show j str cvs show (\)) show
+               grestore
+       } if
+} bind def
+
+/set_font {
+       findfont exch
+       scalefont setfont
+} def
+
+% draw text fitted to its expected width
+/alignedtext {                 % width text
+       /text exch def
+       /width exch def
+       gsave
+               width 0 gt {
+                       [] 0 setdash
+                       text stringwidth pop width exch sub text length div 0 text ashow
+               } if
+       grestore
+} def
+
+/boxprim {                             % xcorner ycorner xsize ysize
+               4 2 roll
+               moveto
+               2 copy
+               exch 0 rlineto
+               0 exch rlineto
+               pop neg 0 rlineto
+               closepath
+} bind def
+
+/ellipse_path {
+       /ry exch def
+       /rx exch def
+       /y exch def
+       /x exch def
+       matrix currentmatrix
+       newpath
+       x y translate
+       rx ry scale
+       0 0 1 0 360 arc
+       setmatrix
+} bind def
+
+/endpage { showpage } bind def
+/showpage { } def
+
+/layercolorseq
+       [       % layer color sequence - darkest to lightest
+               [0 0 0]
+               [.2 .8 .8]
+               [.4 .8 .8]
+               [.6 .8 .8]
+               [.8 .8 .8]
+       ]
+def
+
+/layerlen layercolorseq length def
+
+/setlayer {/maxlayer exch def /curlayer exch def
+       layercolorseq curlayer 1 sub layerlen mod get
+       aload pop sethsbcolor
+       /nodecolor {nopcolor} def
+       /edgecolor {nopcolor} def
+       /graphcolor {nopcolor} def
+} bind def
+
+/onlayer { curlayer ne {invis} if } def
+
+/onlayers {
+       /myupper exch def
+       /mylower exch def
+       curlayer mylower lt
+       curlayer myupper gt
+       or
+       {invis} if
+} def
+
+/curlayer 0 def
+
+%%EndResource
+%%EndProlog
+%%BeginSetup
+14 default-font-family set_font
+1 setmiterlimit
+% /arrowlength 10 def
+% /arrowwidth 5 def
+
+% make sure pdfmark is harmless for PS-interpreters other than Distiller
+/pdfmark where {pop} {userdict /pdfmark /cleartomark load put} ifelse
+% make '<<' and '>>' safe on PS Level 1 devices
+/languagelevel where {pop languagelevel}{1} ifelse
+2 lt {
+    userdict (<<) cvn ([) cvn load put
+    userdict (>>) cvn ([) cvn load put
+} if
+
+%%EndSetup
+setupLatin1
+%%Page: 1 1
+%%PageBoundingBox: 36 36 265 245
+%%PageOrientation: Portrait
+0 0 1 beginpage
+gsave
+36 36 229 209 boxprim clip newpath
+1 1 set_scale 0 rotate 40 40 translate
+% 00
+gsave
+0 0 0 nodecolor
+14 /Times-Roman set_font
+38 24.89 moveto 14 (00) alignedtext
+grestore
+% 00->00
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 27 46.59 moveto
+12 55.59 0 55.59 0 28.59 curveto
+0 7.5 7.32 2.88 17.68 6.17 curveto
+stroke
+0 0 0 edgecolor
+newpath 16.47 9.46 moveto
+27 10.59 lineto
+19.47 3.14 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 16.47 9.46 moveto
+27 10.59 lineto
+19.47 3.14 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+3.63 33.99 moveto 21 ({2}) alignedtext
+grestore
+% 10
+gsave
+0 0 0 nodecolor
+14 /Times-Roman set_font
+182 24.89 moveto 14 (10) alignedtext
+grestore
+% 00->10
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 72.09 34 moveto
+94.47 35.56 126.5 35.76 151.37 34.6 curveto
+stroke
+0 0 0 edgecolor
+newpath 151.76 38.09 moveto
+161.55 34.03 lineto
+151.36 31.1 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 151.76 38.09 moveto
+161.55 34.03 lineto
+151.36 31.1 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+86.56 45.98 moveto 55 ({1},{1,2}) alignedtext
+grestore
+% 01
+gsave
+0 0 0 nodecolor
+14 /Times-Roman set_font
+38 168.89 moveto 14 (01) alignedtext
+grestore
+% 01->00
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 45 154.35 moveto
+45 129.79 45 85.84 45 56.95 curveto
+stroke
+0 0 0 edgecolor
+newpath 48.5 56.68 moveto
+45 46.68 lineto
+41.5 56.68 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 48.5 56.68 moveto
+45 46.68 lineto
+41.5 56.68 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+21.56 91.28 moveto 21 ({2}) alignedtext
+grestore
+% 01->10
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 70.08 154.56 moveto
+98.7 129.24 144.65 83.32 170.31 54.41 curveto
+stroke
+0 0 0 edgecolor
+newpath 173.06 56.58 moveto
+176.98 46.74 lineto
+167.78 51.99 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 173.06 56.58 moveto
+176.98 46.74 lineto
+167.78 51.99 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+139.56 87.98 moveto 31 ({1,2}) alignedtext
+grestore
+% 11
+gsave
+0 0 0 nodecolor
+14 /Times-Roman set_font
+182 168.89 moveto 14 (11) alignedtext
+grestore
+% 01->11
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 72.09 178 moveto
+94.47 179.56 126.5 179.76 151.37 178.6 curveto
+stroke
+0 0 0 edgecolor
+newpath 151.76 182.09 moveto
+161.55 178.03 lineto
+151.36 175.1 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 151.76 182.09 moveto
+161.55 178.03 lineto
+151.36 175.1 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+103.56 189.98 moveto 21 ({1}) alignedtext
+grestore
+% 10->00
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 161.91 23.18 moveto
+139.53 21.63 107.5 21.42 82.63 22.58 curveto
+stroke
+0 0 0 edgecolor
+newpath 82.24 19.09 moveto
+72.45 23.15 lineto
+82.64 26.08 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 82.24 19.09 moveto
+72.45 23.15 lineto
+82.64 26.08 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+109.44 3.8 moveto 21 ({1}) alignedtext
+grestore
+% 10->01
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 163.92 46.63 moveto
+135.3 71.94 89.35 117.86 63.69 146.77 curveto
+stroke
+0 0 0 edgecolor
+newpath 60.94 144.6 moveto
+57.02 154.44 lineto
+66.22 149.19 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 60.94 144.6 moveto
+57.02 154.44 lineto
+66.22 149.19 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+63.44 105.8 moveto 31 ({1,2}) alignedtext
+grestore
+% 10->11
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 184.33 46.83 moveto
+181.87 71.39 181.59 115.34 183.5 144.24 curveto
+stroke
+0 0 0 edgecolor
+newpath 180.04 144.82 moveto
+184.34 154.5 lineto
+187.02 144.25 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 180.04 144.82 moveto
+184.34 154.5 lineto
+187.02 144.25 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+157.01 103.72 moveto 21 ({2}) alignedtext
+grestore
+% 11->00
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 170.76 154.35 moveto
+145.34 128.93 99.13 82.72 70.36 53.95 curveto
+stroke
+0 0 0 edgecolor
+newpath 72.64 51.28 moveto
+63.09 46.68 lineto
+67.69 56.23 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 72.64 51.28 moveto
+63.09 46.68 lineto
+67.69 56.23 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+90.89 67.98 moveto 31 ({1,2}) alignedtext
+grestore
+% 11->01
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 161.91 167.18 moveto
+139.53 165.63 107.5 165.42 82.63 166.58 curveto
+stroke
+0 0 0 edgecolor
+newpath 82.24 163.09 moveto
+72.45 167.15 lineto
+82.64 170.08 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 82.24 163.09 moveto
+72.45 167.15 lineto
+82.64 170.08 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+109.44 147.8 moveto 21 ({1}) alignedtext
+grestore
+% 11->10
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 193.67 154.35 moveto
+196.13 129.79 196.41 85.84 194.5 56.95 curveto
+stroke
+0 0 0 edgecolor
+newpath 197.96 56.36 moveto
+193.66 46.68 lineto
+190.98 56.93 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 197.96 56.36 moveto
+193.66 46.68 lineto
+190.98 56.93 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+199.99 90.06 moveto 21 ({2}) alignedtext
+grestore
+endpage
+showpage
+grestore
+%%PageTrailer
+%%EndPage: 1
+%%Trailer
+%%Pages: 1
+%%BoundingBox: 36 36 265 245
+end
+restore
+%%EOF

diff --git a/images/gp.dot b/images/gp.dot
new file mode 100644 (file)
index 0000000..161e9d2
--- /dev/null
+++ b/images/gp.dot
@@ -0,0 +1,5 @@
+digraph{
+ 1 -> 1 [label=" -"]
+ 1 -> 2 [label=" +"]
+ 2 -> 2 [label=" -"]
+}
\ No newline at end of file

diff --git a/images/h-eps-converted-to.pdf b/images/h-eps-converted-to.pdf
new file mode 100644 (file)
index 0000000..6f5af57
Binary files /dev/null and b/images/h-eps-converted-to.pdf differ

diff --git a/images/h.dot b/images/h.dot
new file mode 100644 (file)
index 0000000..95e3145
--- /dev/null
+++ b/images/h.dot
@@ -0,0 +1,18 @@
+digraph {
+00 [shape="none",label="00", pos="0,0!"];
+01 [shape="none",label="01", pos="0,2!"];
+10 [shape="none",label="10", pos="2,0!"];
+11 [shape="none", label="11", pos="2,2!"];
+ 00 -> 10 [headlabel="{1},{1,2}", labeldistance=5.0,labelangle=-15]
+ 01 -> 11 [headlabel="{1},{1,2}", labeldistance=5.0,labelangle=-15]
+ 10 -> 11 [headlabel="{2}", labeldistance=5.0,labelangle=-15]
+ 10 -> 00 [headlabel="{1}", labeldistance=5.0,labelangle=-15]
+ 10 -> 01 [headlabel="{1,2}", labeldistance=5.0,labelangle=-15]
+ 11 -> 00 [headlabel="{1,2}", labeldistance=5.0,labelangle=-15]
+ 11 -> 10 [headlabel="{2}", labeldistance=5.0,labelangle=-15]
+ 11 -> 01 [headlabel="{1}", labeldistance=5.0,labelangle=-15]
+ 01:nw -> 01:sw [headlabel="∅,{2}", labeldistance=2.5, labelangle=-90]
+ 00:nw -> 00:sw [headlabel="∅,{2}", labeldistance=2.5, labelangle=-90]
+ 11:ne -> 11:se [headlabel="∅",labeldistance=2.5,labelangle=90]
+ 10:ne -> 10:se [headlabel="∅",labeldistance=2.5,labelangle=90]
+}

diff --git a/images/h.eps b/images/h.eps
new file mode 100644 (file)
index 0000000..eddf9e2
--- /dev/null
+++ b/images/h.eps
@@ -0,0 +1,454 @@
+%!PS-Adobe-3.0
+%%Creator: graphviz version 2.36.0 (20140111.2315)
+%%Title: %3
+%%Pages: (atend)
+%%BoundingBox: (atend)
+%%EndComments
+save
+%%BeginProlog
+/DotDict 200 dict def
+DotDict begin
+
+/setupLatin1 {
+mark
+/EncodingVector 256 array def
+ EncodingVector 0
+
+ISOLatin1Encoding 0 255 getinterval putinterval
+EncodingVector 45 /hyphen put
+
+% Set up ISO Latin 1 character encoding
+/starnetISO {
+        dup dup findfont dup length dict begin
+        { 1 index /FID ne { def }{ pop pop } ifelse
+        } forall
+        /Encoding EncodingVector def
+        currentdict end definefont
+} def
+/Times-Roman starnetISO def
+/Times-Italic starnetISO def
+/Times-Bold starnetISO def
+/Times-BoldItalic starnetISO def
+/Helvetica starnetISO def
+/Helvetica-Oblique starnetISO def
+/Helvetica-Bold starnetISO def
+/Helvetica-BoldOblique starnetISO def
+/Courier starnetISO def
+/Courier-Oblique starnetISO def
+/Courier-Bold starnetISO def
+/Courier-BoldOblique starnetISO def
+cleartomark
+} bind def
+
+%%BeginResource: procset graphviz 0 0
+/coord-font-family /Times-Roman def
+/default-font-family /Times-Roman def
+/coordfont coord-font-family findfont 8 scalefont def
+
+/InvScaleFactor 1.0 def
+/set_scale {
+       dup 1 exch div /InvScaleFactor exch def
+       scale
+} bind def
+
+% styles
+/solid { [] 0 setdash } bind def
+/dashed { [9 InvScaleFactor mul dup ] 0 setdash } bind def
+/dotted { [1 InvScaleFactor mul 6 InvScaleFactor mul] 0 setdash } bind def
+/invis {/fill {newpath} def /stroke {newpath} def /show {pop newpath} def} bind def
+/bold { 2 setlinewidth } bind def
+/filled { } bind def
+/unfilled { } bind def
+/rounded { } bind def
+/diagonals { } bind def
+/tapered { } bind def
+
+% hooks for setting color 
+/nodecolor { sethsbcolor } bind def
+/edgecolor { sethsbcolor } bind def
+/graphcolor { sethsbcolor } bind def
+/nopcolor {pop pop pop} bind def
+
+/beginpage {   % i j npages
+       /npages exch def
+       /j exch def
+       /i exch def
+       /str 10 string def
+       npages 1 gt {
+               gsave
+                       coordfont setfont
+                       0 0 moveto
+                       (\() show i str cvs show (,) show j str cvs show (\)) show
+               grestore
+       } if
+} bind def
+
+/set_font {
+       findfont exch
+       scalefont setfont
+} def
+
+% draw text fitted to its expected width
+/alignedtext {                 % width text
+       /text exch def
+       /width exch def
+       gsave
+               width 0 gt {
+                       [] 0 setdash
+                       text stringwidth pop width exch sub text length div 0 text ashow
+               } if
+       grestore
+} def
+
+/boxprim {                             % xcorner ycorner xsize ysize
+               4 2 roll
+               moveto
+               2 copy
+               exch 0 rlineto
+               0 exch rlineto
+               pop neg 0 rlineto
+               closepath
+} bind def
+
+/ellipse_path {
+       /ry exch def
+       /rx exch def
+       /y exch def
+       /x exch def
+       matrix currentmatrix
+       newpath
+       x y translate
+       rx ry scale
+       0 0 1 0 360 arc
+       setmatrix
+} bind def
+
+/endpage { showpage } bind def
+/showpage { } def
+
+/layercolorseq
+       [       % layer color sequence - darkest to lightest
+               [0 0 0]
+               [.2 .8 .8]
+               [.4 .8 .8]
+               [.6 .8 .8]
+               [.8 .8 .8]
+       ]
+def
+
+/layerlen layercolorseq length def
+
+/setlayer {/maxlayer exch def /curlayer exch def
+       layercolorseq curlayer 1 sub layerlen mod get
+       aload pop sethsbcolor
+       /nodecolor {nopcolor} def
+       /edgecolor {nopcolor} def
+       /graphcolor {nopcolor} def
+} bind def
+
+/onlayer { curlayer ne {invis} if } def
+
+/onlayers {
+       /myupper exch def
+       /mylower exch def
+       curlayer mylower lt
+       curlayer myupper gt
+       or
+       {invis} if
+} def
+
+/curlayer 0 def
+
+%%EndResource
+%%EndProlog
+%%BeginSetup
+14 default-font-family set_font
+1 setmiterlimit
+% /arrowlength 10 def
+% /arrowwidth 5 def
+
+% make sure pdfmark is harmless for PS-interpreters other than Distiller
+/pdfmark where {pop} {userdict /pdfmark /cleartomark load put} ifelse
+% make '<<' and '>>' safe on PS Level 1 devices
+/languagelevel where {pop languagelevel}{1} ifelse
+2 lt {
+    userdict (<<) cvn ([) cvn load put
+    userdict (>>) cvn ([) cvn load put
+} if
+
+%%EndSetup
+setupLatin1
+%%Page: 1 1
+%%PageBoundingBox: 36 36 266 245
+%%PageOrientation: Portrait
+0 0 1 beginpage
+gsave
+36 36 230 209 boxprim clip newpath
+1 1 set_scale 0 rotate 40 40 translate
+% 00
+gsave
+0 0 0 nodecolor
+14 /Times-Roman set_font
+38.73 24.89 moveto 14 (00) alignedtext
+grestore
+% 00->00
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 27.73 46.59 moveto
+12.73 55.59 .73 55.59 .73 28.59 curveto
+.73 7.5 8.05 2.88 18.41 6.17 curveto
+stroke
+0 0 0 edgecolor
+newpath 17.19 9.46 moveto
+27.73 10.59 lineto
+20.19 3.14 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 17.19 9.46 moveto
+27.73 10.59 lineto
+20.19 3.14 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+0 29.47 moveto 34 ({2},∅) alignedtext
+grestore
+% 10
+gsave
+0 0 0 nodecolor
+14 /Times-Roman set_font
+182.73 24.89 moveto 14 (10) alignedtext
+grestore
+% 00->10
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 72.81 34 moveto
+95.19 35.56 127.22 35.76 152.1 34.6 curveto
+stroke
+0 0 0 edgecolor
+newpath 152.49 38.09 moveto
+162.27 34.03 lineto
+152.09 31.1 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 152.49 38.09 moveto
+162.27 34.03 lineto
+152.09 31.1 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+87.29 45.98 moveto 55 ({1},{1,2}) alignedtext
+grestore
+% 01
+gsave
+0 0 0 nodecolor
+14 /Times-Roman set_font
+38.73 168.89 moveto 14 (01) alignedtext
+grestore
+% 01->01
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 27.73 190.59 moveto
+12.73 199.59 .73 199.59 .73 172.59 curveto
+.73 151.5 8.05 146.88 18.41 150.17 curveto
+stroke
+0 0 0 edgecolor
+newpath 17.19 153.46 moveto
+27.73 154.59 lineto
+20.19 147.14 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 17.19 153.46 moveto
+27.73 154.59 lineto
+20.19 147.14 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+6.5 173.47 moveto 21 ({2}) alignedtext
+grestore
+% 11
+gsave
+0 0 0 nodecolor
+14 /Times-Roman set_font
+182.73 168.89 moveto 14 (11) alignedtext
+grestore
+% 01->11
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 72.81 178 moveto
+95.19 179.56 127.22 179.76 152.1 178.6 curveto
+stroke
+0 0 0 edgecolor
+newpath 152.49 182.09 moveto
+162.27 178.03 lineto
+152.09 175.1 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 152.49 182.09 moveto
+162.27 178.03 lineto
+152.09 175.1 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+87.29 189.98 moveto 55 ({1},{1,2}) alignedtext
+grestore
+% 10->00
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 162.64 23.18 moveto
+140.26 21.63 108.23 21.42 83.35 22.58 curveto
+stroke
+0 0 0 edgecolor
+newpath 82.96 19.09 moveto
+73.18 23.15 lineto
+83.36 26.08 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 82.96 19.09 moveto
+73.18 23.15 lineto
+83.36 26.08 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+110.16 3.8 moveto 21 ({1}) alignedtext
+grestore
+% 10->01
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 171.49 46.83 moveto
+146.06 72.26 99.85 118.47 71.08 147.23 curveto
+stroke
+0 0 0 edgecolor
+newpath 68.41 144.96 moveto
+63.81 154.5 lineto
+73.36 149.91 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 68.41 144.96 moveto
+63.81 154.5 lineto
+73.36 149.91 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+73.31 107.5 moveto 31 ({1,2}) alignedtext
+grestore
+% 10->11
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 185.05 46.83 moveto
+182.59 71.39 182.32 115.34 184.23 144.24 curveto
+stroke
+0 0 0 edgecolor
+newpath 180.76 144.82 moveto
+185.07 154.5 lineto
+187.74 144.25 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 180.76 144.82 moveto
+185.07 154.5 lineto
+187.74 144.25 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+157.73 103.72 moveto 21 ({2}) alignedtext
+grestore
+% 11->00
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 171.49 154.35 moveto
+146.06 128.93 99.85 82.72 71.08 53.95 curveto
+stroke
+0 0 0 edgecolor
+newpath 73.36 51.28 moveto
+63.81 46.68 lineto
+68.41 56.23 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 73.36 51.28 moveto
+63.81 46.68 lineto
+68.41 56.23 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+91.62 67.98 moveto 31 ({1,2}) alignedtext
+grestore
+% 11->01
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 162.64 167.18 moveto
+140.26 165.63 108.23 165.42 83.35 166.58 curveto
+stroke
+0 0 0 edgecolor
+newpath 82.96 163.09 moveto
+73.18 167.15 lineto
+83.36 170.08 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 82.96 163.09 moveto
+73.18 167.15 lineto
+83.36 170.08 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+110.16 147.8 moveto 21 ({1}) alignedtext
+grestore
+% 11->10
+gsave
+1 setlinewidth
+0 0 0 edgecolor
+newpath 194.4 154.35 moveto
+196.86 129.79 197.13 85.84 195.22 56.95 curveto
+stroke
+0 0 0 edgecolor
+newpath 198.69 56.36 moveto
+194.38 46.68 lineto
+191.71 56.93 lineto
+closepath fill
+1 setlinewidth
+solid
+0 0 0 edgecolor
+newpath 198.69 56.36 moveto
+194.38 46.68 lineto
+191.71 56.93 lineto
+closepath stroke
+0 0 0 edgecolor
+14 /Times-Roman set_font
+200.72 90.06 moveto 21 ({2}) alignedtext
+grestore
+endpage
+showpage
+grestore
+%%PageTrailer
+%%EndPage: 1
+%%Trailer
+%%Pages: 1
+%%BoundingBox: 36 36 266 245
+end
+restore
+%%EOF

diff --git a/images/hp.dot b/images/hp.dot
new file mode 100644 (file)
index 0000000..a8145cf
--- /dev/null
+++ b/images/hp.dot
@@ -0,0 +1,5 @@
+digraph{
+ 1 -> 1 [label=" -"]
+ 1 -> 2 [label=" +-"]
+ 2 -> 2 [label=" +-"]
+}
\ No newline at end of file

diff --git a/images/iter_f.dot b/images/iter_f.dot
new file mode 100644 (file)
index 0000000..3f3ab3a
--- /dev/null
+++ b/images/iter_f.dot
@@ -0,0 +1,42 @@
+digraph {
+000 [shape="none",label="000", pos="2,4!"]
+001 [shape="none",label="001", pos="0,6!"]
+010 [shape="none",label="010", pos="4,4!"]
+011 [shape="none",label="011", pos="6,6!"]
+100 [shape="none",label="100", pos="2,2!"]
+101 [shape="none",label="101", pos="0,0!"]
+110 [shape="none",label="110", pos="4,2!"]
+111 [shape="none",label="111", pos="6,0!"]
+000:nw -> 000:sw [headlabel="∅,{1}", labeldistance=1.5,labelangle=-90]
+000 -> 001 [headlabel="{3}{1,3}", labeldistance=5.0,labelangle=-15]
+000 -> 010 [headlabel="{2}{1,2}", labeldistance=5.0,labelangle=15]
+000 -> 011 [headlabel="{2,3}{1,2,3}", labeldistance=5.0,labelangle=-15]
+001 -> 000 [headlabel="{3}{2,3}", labeldistance=7.0,labelangle=-15]
+001:nw -> 001:sw [headlabel="∅,{2}", labeldistance=1.5,labelangle=-90]
+001 -> 100 [headlabel="{1,3}{1,2,3}", labeldistance=7.0,labelangle=15]
+001 -> 101 [headlabel="{1}{1,2}", labeldistance=7.0,labelangle=15]
+010 -> 010 [headlabel="∅,{2}", labeldistance=2.0,labelangle=-15]
+010 -> 011 [headlabel="{3}{2,3}", labeldistance=5.0,labelangle=-15]
+010 -> 110 [headlabel="{1}{1,2}", labeldistance=5.0,labelangle=-15]
+010 -> 111 [headlabel="{1,3}{1,2,3}", labeldistance=5.0,labelangle=-15]
+011 -> 000 [headlabel="{2,3}{1,2,3}", labeldistance=7.0,labelangle=-15]
+011 -> 001 [headlabel="{2}{1,2}", labeldistance=7.0,labelangle=15]
+011 -> 010 [headlabel="{3}{1,3}", labeldistance=7.0,labelangle=-15]
+011:ne -> 011:se [headlabel="∅,{1}", labeldistance=1.5,labelangle=90]
+100 -> 000 [headlabel="{1}{1,3}", labeldistance=5.0,labelangle=0]
+100 -> 010 [headlabel="{1,2}{1,2,3}", labeldistance=5.0,labelangle=-15]
+100:nw -> 100:sw [headlabel="∅,{3}", labeldistance=1.5,labelangle=-90]
+100 -> 110 [headlabel="{2}{2,3}", labeldistance=5.0,labelangle=-15]
+101 -> 100 [headlabel="{3}{1,3}", labeldistance=7.0,labelangle=-15]
+101:nw -> 101:sw [headlabel="∅,{1}", labeldistance=1.5,labelangle=-90]
+101 -> 110 [headlabel="{2,3}{1,2,3}", labeldistance=10.0,labelangle=-5]
+101 -> 111 [headlabel="{2}{1,2}", labeldistance=7.0,labelangle=-15]
+110 -> 100 [headlabel="{2}{1,2}", labeldistance=5.0,labelangle=-15]
+110 -> 101 [headlabel="{2,3}{1,2,3}", labeldistance=5.0,labelangle=-15]
+110 -> 110 [headlabel="∅,{1}", labeldistance=2.0,labelangle=90]
+110 -> 111 [headlabel="{3}{1,3}", labeldistance=5.0,labelangle=15]
+111:ne -> 001:ne [headlabel="{1,2}{1,2,3}", labeldistance=5.0,labelangle=-15]
+111 -> 011 [headlabel="{1}{1,3}", labeldistance=7.0,labelangle=15]
+111 -> 101 [headlabel="{2}{2,3}", labeldistance=7.0,labelangle=-15]
+111:ne -> 111:se [headlabel="∅,{3}", labeldistance=1.5,labelangle=90]
+}

diff --git a/images/iter_f0_chaos.dot b/images/iter_f0_chaos.dot
new file mode 100644 (file)
index 0000000..2085927
--- /dev/null
+++ b/images/iter_f0_chaos.dot
@@ -0,0 +1,45 @@
+digraph  {
+000 [shape="none"label="000", pos="10,10!"];
+001 [shape="none"label="001", pos="11.7320508076,11!"];
+010 [shape="none", label="010", pos="12,10!"];
+011 [shape="none", label="011", pos="13.7320508076,11!"];
+100 [shape="none", label="100", pos="10,8!"];
+101 [shape="none", label="101", pos="11.7320508076,9!"];
+110 [shape="none", label="110", pos="12,8!"];
+111 [shape="none", label="111", pos="13.7320508076,9!"];
+       000 -> 000 [color="blue"]
+       000 -> 010;
+       000 -> 001;
+       010 -> 010 [color="blue"] 
+       010 -> 110;
+       010 -> 011;
+       001 -> 000;
+       001 -> 001 [color="blue"]
+       001 -> 101;
+       101 -> 101 [color="blue"]
+       101 -> 100;
+       101 -> 111;
+       110 -> 110 [color="blue"]
+       110 -> 100;
+       110 -> 111;
+       011 -> 010;
+       011 -> 001;
+       011 -> 011 [color="blue"]
+       100 -> 000;
+       100 -> 100 [color="blue"]
+       100 -> 110 
+       111 -> 111 [color="blue"]
+       111 -> 011;
+       111 -> 101 
+/*     
+       000 -> 100 [style="dashed"]
+       100 -> 101 [style="dashed"]
+       101 -> 001 [style="dashed"]
+       001 -> 011 [style="dashed"]
+       011 -> 111 [style="dashed"]
+       111 -> 110 [style="dashed"]
+       110 -> 010 [style="dashed"]
+       010 -> 000 [style="dashed"]
+*/
+
+}

diff --git a/images/iter_f0_chaos_ini.dot b/images/iter_f0_chaos_ini.dot
new file mode 100644 (file)
index 0000000..0650a0b
--- /dev/null
+++ b/images/iter_f0_chaos_ini.dot
@@ -0,0 +1,45 @@
+digraph  {
+000 [shape="none"label="000"]
+001 [shape="none"label="001"]
+010 [shape="none", label="010"]
+011 [shape="none", label="011"]
+100 [shape="none", label="100"]
+101 [shape="none", label="101"]
+110 [shape="none", label="110"]
+111 [shape="none", label="111"]
+       000 -> 000 [color="blue"]
+       000 -> 010;
+       000 -> 001;
+       010 -> 010 [color="blue"] 
+       010 -> 110;
+       010 -> 011;
+       001 -> 000;
+       001 -> 001 [color="blue"]
+       001 -> 101;
+       101 -> 101 [color="blue"]
+       101 -> 100;
+       101 -> 111;
+       110 -> 110 [color="blue"]
+       110 -> 100;
+       110 -> 111;
+       011 -> 010;
+       011 -> 001;
+       011 -> 011 [color="blue"]
+       100 -> 000;
+       100 -> 100 [color="blue"]
+       100 -> 110 
+       111 -> 111 [color="blue"]
+       111 -> 011;
+       111 -> 101 
+/*     
+       000 -> 100 [style="dashed"]
+       100 -> 101 [style="dashed"]
+       101 -> 001 [style="dashed"]
+       001 -> 011 [style="dashed"]
+       011 -> 111 [style="dashed"]
+       111 -> 110 [style="dashed"]
+       110 -> 010 [style="dashed"]
+       010 -> 000 [style="dashed"]
+*/
+
+}

diff --git a/images/iter_f0b.dot b/images/iter_f0b.dot
new file mode 100644 (file)
index 0000000..e00de78
--- /dev/null
+++ b/images/iter_f0b.dot
@@ -0,0 +1,45 @@
+digraph  {
+000 [shape="none"label="000", pos="10,10!"];
+001 [shape="none"label="001", pos="11.7320508076,11!"];
+010 [shape="none", label="010", pos="12,10!"];
+011 [shape="none", label="011", pos="13.7320508076,11!"];
+100 [shape="none", label="100", pos="10,8!"];
+101 [shape="none", label="101", pos="11.7320508076,9!"];
+110 [shape="none", label="110", pos="12,8!"];
+111 [shape="none", label="111", pos="13.7320508076,9!"];
+       000 -> 000:w;
+       000 -> 010;
+       000 -> 001;
+       010 -> 010;
+       010 -> 110;
+       010 -> 011;
+       001 -> 000;
+       001 -> 001:w;
+       001 -> 101;
+       101 -> 101:w;
+       101 -> 100;
+       101 -> 111;
+       110 -> 110;
+       110 -> 100;
+       110 -> 111;
+       011 -> 010;
+       011 -> 001;
+       011 -> 011;
+       100 -> 000;
+       100 -> 101;
+       100 -> 100:w;
+       111 -> 110;
+       111 -> 011;
+       111 -> 111;
+/*     
+       000 -> 100 [style="dashed"]
+       100 -> 101 [style="dashed"]
+       101 -> 001 [style="dashed"]
+       001 -> 011 [style="dashed"]
+       011 -> 111 [style="dashed"]
+       111 -> 110 [style="dashed"]
+       110 -> 010 [style="dashed"]
+       010 -> 000 [style="dashed"]
+*/
+
+}

diff --git a/images/iter_f0c.dot b/images/iter_f0c.dot
new file mode 100644 (file)
index 0000000..be8e695
--- /dev/null
+++ b/images/iter_f0c.dot
@@ -0,0 +1,45 @@
+digraph  {
+000 [shape="none"label="000", pos="10,10!"];
+001 [shape="none"label="001", pos="11.7320508076,11!"];
+010 [shape="none", label="010", pos="12,10!"];
+011 [shape="none", label="011", pos="13.7320508076,11!"];
+100 [shape="none", label="100", pos="10,8!"];
+101 [shape="none", label="101", pos="11.7320508076,9!"];
+110 [shape="none", label="110", pos="12,8!"];
+111 [shape="none", label="111", pos="13.7320508076,9!"];
+    // 000:nw -> 000:so [color="blue"]
+       000 -> 010;
+       000 -> 001;
+       //010:ne -> 010:se [color="blue"] 
+       010 -> 110;
+       010 -> 011;
+       001 -> 000;
+       //001 -> 001 [color="blue"]
+       001 -> 101;
+       //101 -> 101 [color="blue"]
+       101 -> 100;
+       101 -> 111;
+       //110 -> 110 [color="blue"]
+       110 -> 100;
+       110 -> 111;
+       011 -> 010;
+       011 -> 001;
+       //011 -> 011 [color="blue"]
+       100 -> 000;
+       //100 -> 100 [color="blue"]
+       100 -> 110 
+       //111 -> 111 [color="blue"]
+       111 -> 011;
+       111 -> 101 
+/*     
+       000 -> 100 [style="dashed"]
+       100 -> 101 [style="dashed"]
+       101 -> 001 [style="dashed"]
+       001 -> 011 [style="dashed"]
+       011 -> 111 [style="dashed"]
+       111 -> 110 [style="dashed"]
+       110 -> 010 [style="dashed"]
+       010 -> 000 [style="dashed"]
+*/
+
+}

diff --git a/images/iter_f0c.eps b/images/iter_f0c.eps
new file mode 100644 (file)
index 0000000..22d84c4
Binary files /dev/null and b/images/iter_f0c.eps differ

diff --git a/intro.tex b/intro.tex
new file mode 100644 (file)
index 0000000..6460412
--- /dev/null
+++ b/intro.tex
@@ -0,0 +1,250 @@
+L'exploitation de  \og systèmes chaotiques\fg{} pour générer des séquences
+pseudo-aléatoires est un sujet actif de recherche~\cite{915396,915385,5376454}. 
+Ces systèmes sont choisis principalement
+en raison de leur imprévisibilité et de leur sensibilité aux conditions initiales.
+
+Souvent   les   travaux  se   limitent   à   itérer   une  fonction   paramétrée
+\emph{chaotique}  comme la  fonction logistique~\cite{915396,915385},  ou encore
+celle du  chat d'Arnold~\cite{5376454}\ldots Il  reste à trouver  les paramètres
+optimaux permettant d'éviter les attracteurs de telles fonctions et garantissant
+que les séquences de nombres  produits suivent une loi de distribution uniforme.
+Pour vérifier  la qualité des  sorties produites il  est usuel de  soumettre les
+PRNG   (Pseudo-Random  Number   Generator)   à  des   tests  statistiques   tels
+DieHARD~\cite{Marsaglia1996}, NIST~\cite{Nist10} et TestU01~\cite{LEcuyerS07}.
+
+Dans son acception vulgarisée, 
+la notion de chaos est souvent réduite à celle de forte sensibilité
+aux conditions initiales (le fameux \og \emph{effet papillon}\fg{}): 
+une fonction continue $k$ définie sur un espace métrique 
+est dite \emph{fortement sensible aux conditions initiales} si pour tout
+point $x$ et pour toute valeur positive $\epsilon$
+il est possible de trouver un point $y$, arbitrairement proche 
+de $x$, et un entier $t$ tels que la distance entre les 
+$t^{\textrm{ièmes}}$ itérés de $x$ et de $y$ 
+-- notés $k^t(x)$ et $k^t(y)$ 
+-- est supérieure à $\epsilon$. 
+Cependant, dans sa définition du chaos, 
+Devaney~\cite{Devaney} impose à la fonction chaotique deux autres propriétés 
+appelées \emph{transitivité} et \emph{régularité},
+Les fonctions citées plus haut ont été étudiées 
+au regard de ces propriétés et ont été prouvées comme chaotiques sur $\R$.
+Cependant, rien ne garantit que ces propriétés sont préservées sur les nombres 
+flottants qui est le domaine d'interprétation des nombres réels de $\R$.
+
+Pour éviter cette perte de chaos,  nous avons présenté des PRNGs qui itèrent des
+fonctions continues  $G_f$ sur  un domaine discret  $\{ 1, \ldots,  n \}^{\Nats}
+\times  \{0,1\}^n$  où $f$  est  une  fonction  booléenne (\textit{i.e.},  $f  :
+\{0,1\}^n      \rightarrow      \{0,1\}^n$).       Ces     générateurs      sont
+$\textit{CIPRNG}_f^1(u)$ \cite{guyeuxTaiwan10,bcgr11ip},
+$\textit{CIPRNG}_f^2(u,v)$ \cite{wbg10ip}                                     et
+$\chi_{\textit{14Secrypt}}$ \cite{chgw14oip}     où    \textit{CI}    signifie
+\emph{Chaotic Iterations}.
+
+Dans~\cite{bcgr11ip} nous avons tout d'abord  prouvé que pour établir la nature
+chaotique de l'algorithme $\textit{CIPRNG}_f^1$,  il est nécessaire et suffisant
+que le  graphe des  itérations asynchrones soit  fortement connexe.   Nous avons
+ensuite  prouvé que  pour  que la  sortie de  cet  algorithme suive  une loi  de
+distribution uniforme, il  est nécessaire et suffisant que  la matrice de Markov
+associée à ce graphe soit  doublement stochastique.  Nous avons enfin établi des
+conditions suffisantes pour garantir  la première propriété de connexité.  Parmi
+les  fonctions générées,  on ne  retenait ensuite  que celles  qui  vérifiait la
+seconde  propriété.  Dans~\cite{chgw14oip},  nous avons  proposé  une démarche
+algorithmique permettant d'obtenir  directement un graphe d'itérations fortement
+connexe et  dont la matrice de  Markov est doublement  stochastique.  Le travail
+présenté ici généralise ce dernier  article en changeant le domaine d'itération,
+et donc de métrique. L'algorithme  obtenu possède les même propriétés théoriques
+mais un temps de mélange plus réduit.
+
+% Pour décrire un peu plus précisément le principe de
+% la génération pseudo-aléatoire, considérons l'espace booléen 
+% $\Bool=\{0,1\}$
+% muni des lois \og +\fg{}, \og . \fg{} et \og $\overline{\bullet}$ \fg{} 
+% définies par les tableaux ci-dessous:
+
+% \begin{center}
+%   \begin{tabular}{|c|c|c|}
+%     \hline 
+%     +              & 0 & 1 \\
+%     \hline 
+%     0              & 0 & 1 \\
+%     \hline 
+%     1              & 1 & 1 \\
+%     \hline
+%   \end{tabular}\qquad
+%   \begin{tabular}{|c|c|c|}
+%     \hline 
+%     .              & 0 & 1 \\
+%     \hline 
+%     0              & 0 & 0 \\
+%     \hline 
+%     1              & 0 & 1 \\
+%     \hline
+%   \end{tabular}\qquad
+%   \begin{tabular}{|c|c|c|}
+%     \hline 
+%     x              & 0 & 1 \\
+%     \hline 
+%     $\overline{x}$ & 1 & 0 \\
+%     \hline 
+%   \end{tabular}
+% \end{center}
+
+
+% La fonction itérée est
+% une fonction $f$ de $\Bool^n$ dans lui-même qui à
+% un mot binaire $x = (x_1,\ldots,x_n)$ 
+% associe le mot $(f_1(x),\ldots, f_n(x))$.
+% Un exemple de fonction de $\Bool^n$ dans lui-même
+% est la fonction négation 
+% définie par  
+% $\neg(x)=(\overline{x_1},\dots,\overline{x_n})$. 
+
+% Le principe itératif, basé sur  le mode opératoire dit \emph{asynchrone}, est le
+% suivant: à chaque itération  $t$, on choisit un indice $i$ entre  $1$ et $n$, et
+% le mot $x^t = (x_1^t,\ldots,x_n^t)$  est remplacé par $x^{t+1} = (x_1^t,\ldots ,
+% x_{i-1}^t, f_i(x^t), x_{i+1}^t,\ldots, x_n^t)$.
+
+% Au  bout d'un  nombre $N$  d'itérations,  si la  fonction (notée  $G_f$ dans  ce
+% document)  que l'on  peut  associer à  l'algorithme  décrit ci-dessus  a de  \og
+% \emph{bonnes}\fg{} propriétés chaotiques, le  mot $x^N$ doit être \og \emph{très
+%   différent}\fg{} de  $x^0$ de  façon à  sembler ne plus  dépendre de  $x_0$. En
+% effet, pour  un générateur aléatoire, il  faut que la structure  de $x^N$ semble
+% être due  au hasard;  pour une application  cryptographique, il faut  qu'il soit
+% matériellement  impossible   (dans  les  conditions   techniques  actuelles)  de
+% retrouver $x^0$ à partir de $x^N$.
+
+% Tous  les  mots   de  $\Bool^n$  peuvent  constituer  les   $2^n$  sommets  d'un
+% \gls{graphoriente} (cf. glossaire) dans lequel  un arc relie deux sommets $x$ et
+% $x'$  s'il existe  une itération  de l'algorithme  de génération  qui  permet de
+% passer directement de  $x$ à $x'$.   Ce graphe est  appelé le \emph{graphe  d'itérations} et
+% nous montrons ici que si  l'on a un \gls{graphfortementconnexe} (cf. glossaire),
+% alors la fonction $G_f$ est transitive, donc chaotique.
+
+% Enfin, un bon générateur aléatoire se doit de 
+% fournir  des nombres selon une \gls{distributionuniforme} (cf. glossaire). 
+% La dernière partie de cet article donne, 
+% dans le cas où le graphe d'itérations est fortement connexe, 
+% une condition nécessaire et suffisante pour que
+% cette propriété soit satisfaite.
+
+
+% Le chaos a été appliqué à des domaines variés en 
+% informatique, comme les fonctions de hachage,
+% la stéganographie, la génération de nombres pseudo 
+% aléatoires\ldots
+% Toutes ces  applications  exploitent les  propriétés définissant des 
+% fonctions  chaotiques et énoncées par Devaney,  telles que la
+% transitivité, la régularité et la sensibilité aux conditions initiales.
+
+
+% Les systèmes dynamiques \emph{chaotiques} sont des processus itératifs 
+% définis par une fonction chaotique  $f$  d'un  domaine $E$ dans lui-même.
+% En démarrant d'un état quelconque $x$ du sytème, 
+% nommé par la suite \emph{configuration}, 
+% le système construit la séquence $x$, $f(x)$, $f^2(x)$, $f^3(x)$, \dots 
+% où $f^k(x)$  est le   $k^{\textrm{ème}}$ itéré  de  $f$ en  $x$.  
+% La plupart des applications informatiques dite \og chaotiques \fg{}
+% sont basées sur des processus itératifs de la forme $x^{n+1} = f(x^n)$
+% où $f$ est la fonction  \emph{tente} avec  $x^0 = 0,4001$ (donnée à la figure~\ref{fig:iter:tent}) 
+% ou la fonction  \emph{logistique} avec $\mu = 3,45$ et $x^0 = 0,1$ (donnée à la figure~\ref{fig:iter:log}) 
+% connues pour être chaotiques dans $\R$.
+
+% \begin{figure}[hb]
+% \begin{center}
+%     \subfloat[Fonction tente $f=\min\{x,\,1-x\}$]{
+%       \begin{minipage}{0.45\textwidth}
+%         \begin{center}
+%           \includegraphics[height=3cm]{images/tente.png}
+%         \end{center}
+%       \end{minipage}
+%       \label{fig:iter:tent}
+%     }
+%     \subfloat[Fonction logistique $f(x) =  \mu x (1 -x)$]{
+%       \begin{minipage}{0.45\textwidth}
+%         \begin{center}
+%           \includegraphics[height=3cm]{images/logistique.png}
+%         \end{center}
+%       \end{minipage}
+%       \label{fig:iter:log}
+%     }
+% \end{center}
+%  \caption{Systèmes itératifs basés sur des fonctions chaotiques dans $\R$ \label{fig:iter}}
+% \end{figure}
+
+
+% Cependant il n'a pas été établi que des fonctions prouvées
+% comme étant chaotiques sur $\R$ le restent sur les  nombres à virgule flottante,
+% qui est le domaine d'interprétation informatique des réels.  
+% On souhaite ainsi éviter une éventuelle perte des propriétés de chaos
+% lors de l'exécution des programmes implémentant ces fonctions. 
+% Ce document présente pour cela l'alternative suivante: 
+% à partir d'une fonction booléenne, $f: \Bool^n \rightarrow \Bool^n$, 
+% où $\Bool$ est le domaine des booléens  $\{0,1\}$, on
+% construit une fonction $G_f : \llbracket 1 ;  n \rrbracket^{\Nats}  \times \Bool^n$, 
+% où $\llbracket 1  ; n \rrbracket$ est l'ensemble des entiers
+% $\{1, 2, \hdots,  n\}$ et on itère celle-ci.
+% Comme $f$ est discrète, $G_f$ l'est aussi et les résultats théoriques
+% obtenus sur $G_f$, notamment sa chaoticité, sont maintenus durant 
+% l'implémentation.
+% Un exemple de fonction booléenne de $\Bool^n$ dans lui-même est la fonction négation 
+% définie par  
+% $\neg(x)=(\overline{x_1},\dots,\overline{x_n})$. 
+
+
+
+
+% De plus,  plutôt que de trouver des exemples de telles fonctions $f$, et de prouver 
+% (\textit{a  posteriori}) la chaoticité de $G_f$, on peut penser à caractériser  
+% les fonctions engendrant systématiquement des fonctions chaotiques.
+% Ce document présente une telle caractérisation 
+% qui s'exprime sur le graphe des itérations asynchrones
+% de la fonction booléenne $f$, qui est, intuitivement, le graphe 
+% de toutes les itérations possibles de la fonction. 
+% Cette situation se réduit en un problème portant sur des graphes à $2^n$  
+% sommets.  
+% Ainsi pour étendre l'applicabilité de cette caractérisation, on s'intéresse
+% au graphe des interactions de $f$, qui, intuitivement,
+% représente les dépendances entre les $f_i$, $1\le i \le n$ et les $i$
+% et qui ne contient que  $n$ sommets (et qui est à comparer aux $2^n$ 
+% sommets.
+% Sur ce graphe on exprime des conditions garantissant la chaoticité de la fonction $G_f$.
+% Ainsi, toutes les fonctions $G_f$ engendrées à partir d'un graphe
+% d'interactions de $f$ aux propriétés \textit{ad hoc} seront chaotiques.
+
+% Se pose enfin l'applicabilité des fonctions $G_f$ à la génération
+% de nombres pseudo aléatoires, l'aléa étant intuitivement 
+% une notion proche de celle du chaos.
+% Pour aborder cette classe de problèmes, on remarque que l'on doit au moins 
+% garantir que l'ensemble des valeurs retournées par l'algorithme suit
+% une loi uniforme, propriété qui n'est pas imposée d'un point de vue topologique.
+% Ce document montre que cette contrainte peut s'exprimer à nouveau sur le graphe des itérations asynchrones de $f$
+% et qu'on peut ainsi filtrer les bons candidats à la génération de nombres pseudo aléatoires.
+% Cette idée est validée après évaluation 
+% des générateurs de nombres pseudo aléatoires 
+% sur une batterie de tests.
+
+
+% Le reste de ce document est organisé comme suit. 
+% La section~\ref{section:chaos} présente ce qu'est un système dynamique discret booléen itérant une fonction $f$.
+% La chaoticité de la fonction engendrée $G_f$ est caractérisée en 
+% section~\ref{sec:charac}. 
+% Des conditions suffisantes pour obtenir cette chaoticité sont présentées  en
+% section~\ref{sec:sccg}.
+% L'application à la génération de nombres pseudo aléatoires est formalisée,
+% les fonctions dont l'image est uniformément distribuée sur le domaine sont
+% caractérisées et les générateurs sont évalués en section~\ref{sec:prng}.
+
+Dans  la section  suivante,  nous  rappelons les  notions  élémentaires sur  les
+systèmes   booléens.   La  section~\ref{section:caracterisation}   présente  les
+définitions théoriques liées au chaos. Ensuite, une application de ces résultats
+à    la   génération    de   nombres    pseudo-aléatoires   est    proposée   en
+section~\ref{section:genpa}  ainsi  qu'une   méthode  permettant  d'obtenir  des
+matrices         d'itérations         doublement        stochastiques         en
+section~\ref{section:genmat}.  Enfin, en section~\ref{section:expes}  la qualité
+du PRNG obtenu est éprouvée avec les tests standards du domaine.
+
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: "main"
+%%% End: 

diff --git a/ita.cls b/ita.cls
new file mode 100644 (file)
index 0000000..9d18b72
--- /dev/null
+++ b/ita.cls
@@ -0,0 +1,391 @@
+\NeedsTeXFormat{LaTeX2e}
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%      ita  class for LaTeX2e                         %%
+%%%      Pierre Damphousse                              %%
+%%%      Copyright (C) EDP Sciences                     %%
+%%%      Version 1.2. September 2002                    %%
+%%%      tex-support@edpsciences.com                    %%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%% --> THE CLASS OPTION MATERIAL
+%% --> THE CLASS PRESENTATION MATERIAL
+%% --> THE SECTIONING MATERIAL
+%% --> THE METRIC DATA
+%% --> THE TOP MATTER MATERIAL
+%----  (A) The MAKETITLE command and its components
+%----  (B) Preparing the MAKETITLE components
+%          -1-   Heading
+%          -2-   Title and Running Title
+%          -3-   Authors and Running authors
+%          -4-   Date
+%          -5-   Subject Class
+%          -6-   Resume
+%          -7-   Abstract
+%          -8-   Address (\address, given after the \author command)
+%          -9-   Thanks  (given after the title: \thanks)
+%% --> MISCELLANEOUS
+%% --> MESSAGES
+%% --> VARIOUS MACROS
+%----  (A) LATIN ABBREVIATIONS
+%----  (B) REFERENCES
+%----  (C) NEWTHEOREM AND ENVIRONMENTS
+%----  (D) MATHEMATICS
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%
+%%-----------------------------------------------------------------------------
+%% --> THE CLASS OPTION MATERIAL
+%%-----------------------------------------------------------------------------
+\ProvidesClass{ita}[1999/03/01 v1.1 EDP-Sciences]
+\DeclareOption*{\PassOptionsToClass{\CurrentOption}{amsart}}
+\ProcessOptions\relax
+%%-----------------------------------------------------------------------------
+%% --> THE CLASS PRESENTATION MATERIAL
+%%-----------------------------------------------------------------------------
+\LoadClass[reqno]{amsart}[1996/10/24]
+\RequirePackage{cite}
+%%-----------------------------------------------------------------------------
+%% --> THE SECTIONING MATERIAL
+%%-----------------------------------------------------------------------------
+\def\section{\@startsection{section}{1}\z@{1.2\linespacing\@plus\linespacing}%
+{\linespacing} {\fontsize{12}{14}\selectfont\scshape\centering}}
+\def\subsection{\@startsection{subsection}{2}\z@{\linespacing\@plus.8\linespacing}%
+{.8\linespacing}{\fontsize{10}{12}\selectfont\scshape}}
+\def\subsubsection{\@startsection{subsubsection}{3}\z@{.7\linespacing\@plus.5\linespacing}%
+{.5\linespacing}{\normalfont\itshape}}
+\def\paragraph{\@startsection{paragraph}{4}\z@\z@{-\fontdimen2\font}\normalfont}
+\def\subparagraph{\@startsection{subparagraph}{5}\z@\z@{-\fontdimen2\font}\normalfont}
+%%-----------------------------------------------------------------------------
+%% --> THE METRIC DATA
+%%-----------------------------------------------------------------------------
+\setlength\oddsidemargin {15pt}\setlength\evensidemargin{15pt}
+\setlength{\textwidth}{125mm}\setlength{\textheight}{190mm}
+\setlength{\headheight}{18pt}
+%%-----------------------------------------------------------------------------
+%% --> THE TOP MATTER MATERIAL
+%%-----------------------------------------------------------------------------
+% =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   
+%----  (A) The MAKETITLE command and its components
+\def\@maketitle{%
+  \normalfont\normalsize
+  \let\@makefnmark\relax \let\@thefnmark\relax
+  \global\def\shorttitle{\@MSSG@RNNGTTL}
+  \global\def\shortauthors{\@MSSG@RNNGTHR}
+  \@mkboth{\@nx\shortauthors}{\@nx\shorttitle}%
+  \global\topskip42\p@\relax
+  \@SKIP@Aa
+  \vbox{\hbox to\hsize{{\fontsize{10}{12}\selectfont{\bf\@NMJRNL@E}}\hfill%
+  {\fontsize{8}{9}\selectfont\@JRNL@X}}
+  \hbox to\hsize{\fontsize{8}{9}\selectfont{\@NMJRNL@F}\hfill}}
+  \@SKIP@Ab
+  \@setkeywords
+  \@settitle
+  \@setauthors
+  \@setabstract
+  \@setresume
+  \@setsubjclass
+  \normalsize
+  \if@titlepage\newpage\else\dimen@34\p@\advance\dimen@-\baselineskip\vskip\dimen@\relax\fi
+  \gdef\thanks##1{\relax}\gdef\address##1{\relax}
+}% end \@maketitle
+% =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   =   
+%----  (B) Preparing the MAKETITLE components
+%................ ................ ................ ................  ................
+%          -1-   Heading
+%................ ................ ................ ................  ................
+\def\@SKIP@Aa{\vspace*{-1.5cm}}%
+\def\@SKIP@Ab{\vspace*{1.5cm}}%
+\def\@NMJRNL@F{{Informatique Th\'eorique et Applications}}%
+\def\@NMJRNL@E{{Theoretical Informatics and Applications}}%
+\def\@JRNL@X{{Will be set by the publisher}}%
+\def\idline#1page#2{\global\def\@JRNL@X{#1}\setcounter{page}{#2}}
+%................ ................ ................ ................  ................
+%          -2-   Title and Running Title
+%................ ................ ................ ................  ................
+\def\@settitle{\begin{center}\fontsize{11}{15}\selectfont\bfseries
+    \uppercasenonmath\@title\@title\@thnks@i\@thnks@ii\@thnks@iii\@thnks@iv\@thnks@v
+\ifnum\the\@c@thnks@=0\else\footnote{\box\@b@thnks@}\fi
+\end{center}}
+\newbox\@b@rnngttl
+\def\runningtitle#1{\setbox\@b@rnngttl=\hbox{\fontsize{7}{9}\selectfont\rm\uppercase{#1}}}
+%................ ................ ................ ................  ................
+%          -3-   Authors and Running authors
+%................ ................ ................ ................  ................
+\def\@setauthors{\begingroup\trivlist
+  \centering\footnotesize \@topsep30\p@\relax\advance\@topsep by -\baselineskip
+  \item\relax\fontsize{12}{14}\selectfont\scshape\@@th@rs\ignorespaces
+  \footnote{\box\@b@ddrss@}\endtrivlist\endgroup}
+\def\email#1{{e-mail: \tt#1}}
+\newbox\@b@rnngthr
+\def\runningauthors#1{\setbox\@b@rnngthr=\hbox{#1}%
+\global\def\@rnngthrs{\fontsize{7}{9}\selectfont\rm\uppercase{#1}}}
+\newcount\@c@thr@\@c@thr@=0
+\def\author#1{\global\advance\@c@thr@ by 1
+          \global\expandafter\edef\csname @thr@\romannumeral\@c@thr@\endcsname{#1}
+          \global\expandafter\edef\csname @Mthr@\romannumeral\@c@thr@\endcsname{\uppercase{#1}}
+          \global\expandafter\def\csname @ddrss@\romannumeral\@c@thr@\endcsname{}
+          \global\expandafter\def\csname @scndddrss@\romannumeral\@c@thr@\endcsname{}
+          \global\expandafter\def\csname @smddrss@\romannumeral\@c@thr@\endcsname{}}%\author
+%    Elaborating the two author lists (First page and heading)
+\newcount\@y\newcount\@x
+\def\@cnjctn{\ifnum\the\@c@thr@=1\null\else{{\ and\ }}\fi}
+\def\@Mcnjctn{\ifnum\the\@c@thr@=1\null\else{{\ AND\ }}\fi}
+\def\@@th@rs{\@x=0\global\@y=\@c@thr@\global\advance\@y by -1
+\loop\advance\@x by 1
+\ifnum\the\@x<\the\@y\csname  @thr@\romannumeral\@x\endcsname\ignorespaces
+            ${}^{\csname  @ddrss@\romannumeral\@x\endcsname
+                 \csname  @smddrss@\romannumeral\@x\endcsname
+                 \csname  @scndddrss@\romannumeral\@x\endcsname}$,
+\repeat
+\csname  @thr@\romannumeral\@y\endcsname\ignorespaces
+            ${}^{\csname  @ddrss@\romannumeral\@y\endcsname
+                 \csname  @smddrss@\romannumeral\@y\endcsname
+                 \csname  @scndddrss@\romannumeral\@y\endcsname}$\@cnjctn
+\csname  @thr@\romannumeral\@c@thr@\endcsname\ignorespaces
+            ${}^{\csname  @ddrss@\romannumeral\@c@thr@\endcsname
+                 \csname  @smddrss@\romannumeral\@c@thr@\endcsname
+                 \csname  @scndddrss@\romannumeral\@c@thr@\endcsname}$}%\@@th@rs
+\def\M@@th@rs{\@x=0\global\@y=\@c@thr@\global\advance\@y by -1
+\loop\advance\@x by 1
+\ifnum\the\@x<\the\@y\csname  @Mthr@\romannumeral\@x\endcsname,
+\repeat
+\csname  @Mthr@\romannumeral\@y\endcsname\@Mcnjctn
+\csname  @Mthr@\romannumeral\@c@thr@\endcsname}%\M@@th@rs
+\def\@qq#1#2{\vrule height#1 depth#2 width0pt}
+%................ ................ ................ ................  ................
+%          -4-   Date and editor 
+%................ ................ ................ ................  ................
+\let\@date\@empty
+\def\@setdate{\noindent\fontsize{8}{10}\selectfont\hbox{\@date\@addpunct.}}
+\def\editor#1{\def\@editor{#1}}
+\let\@editor\@empty
+\def\@seteditor{\vskip6\p@\noindent\fontsize{8}{10}\selectfont\noindent\hbox{Communicated by 
+\@editor\@addpunct.}}
+%................ ................ ................ ................  ................
+%          -5-   Subject Class
+%................ ................ ................ ................  ................
+%
+\def\@setsubjclass{\skip@20\p@\advance\skip@-\lastskip\advance\skip@-\baselineskip\vskip\skip@
+  \moveright 3pc\hbox{{\bfseries\subjclassname.}\enspace \@subjclass \@addpunct.}} %
+\renewcommand{\subjclassname}{AMS Subject Classification}
+%
+\newbox\@b@kwrds
+\def\keywords#1{\global\setbox\@b@kwrds\vtop{\advance\hsize by-12pt
+    \noindent\footnotesize\textit{\@MSSG@KWRD@0K}#1\@qq{0pt}{4pt}}}
+\def\@setkeywords{\ifvoid\@b@kwrds\else\footnote{\box\@b@kwrds}\fi}
+%................ ................ ................ ................  ................
+%          -6-   Resume
+%................ ................ ................ ................  ................
+\newbox\resumebox
+\newenvironment{resume}{\ifx\maketitle\relax\ClassWarning{\@classname}{\@MSSG@CLSSWRNG}\fi
+  \global\setbox\resumebox=\vtop\bgroup\fontsize{9}{11}\selectfont\advance \hsize -6pc
+  \trivlist 
+    \labelsep.5em\item[\hskip\labelsep{\scshape\fontsize{10}{12}\selectfont\bf R\'esum\'e}.]}
+{\endtrivlist\egroup\ifx\@setresume\relax \@setresumea \fi}
+\def\@setresume{\@setresumea\global\let\@setresume\relax}
+\def\@setresumea{\skip@20\p@\advance\skip@-\lastskip\advance\skip@-\baselineskip \vskip\skip@
+  \ifvoid\resumebox\else\moveright 3pc \box\resumebox\fi}
+%................ ................ ................ ................  ................
+%          -7-   Abstract
+%................ ................ ................ ................  ................
+\newbox\abstractbox
+\renewenvironment{abstract}{\ifx\maketitle\relax\ClassWarning{\@classname}{\@MSSG@CLSSWRNGBSTRCT}\fi
+  \global\setbox\abstractbox=\vtop\bgroup\fontsize{9}{11}\selectfont 
+  \advance \hsize -6pc
+  \trivlist 
+    \labelsep.5em\item[\hskip\labelsep{\scshape\fontsize{10}{12}\selectfont\bf Abstract}.]}
+{\endtrivlist\egroup\ifx\@setabstract\relax \@setabstracta \fi}
+\def\@setabstract{\@setabstracta\global\let\@setabstract\relax}
+\def\@setabstracta{\skip@20\p@ \advance\skip@-\lastskip \advance\skip@-\baselineskip \vskip\skip@
+  \ifvoid\abstractbox{\hbox to\hsize{\kern3pc\fontsize{10}{12}
+          \selectfont\bf \hbox to55pt{Abstract\hfill}\qquad\@MSSG@BSTRCT\hfill}}
+    \else\moveright 3pc \box\abstractbox \fi}
+%................ ................ ................ ................  ................
+%                Address         (\address, given after the \author command)
+%         -8-    Same Address    (\sameaddress, given after the \author command)
+%                Second Address  (\secondaddress, given after the \author command)
+%................ ................ ................ ................  ................
+\def\@spc{\kern1pt}\def\@spcc{\kern2pt}
+\newcount\@c@ddrss@\newbox\@b@ddrss@
+%
+\def\@dd@ddrss@#1{%
+\global\setbox51=\vbox{\advance\hsize by-12pt\unvbox\@b@ddrss@
+  \vtop{\footnotesize\noindent{${}^{\the\@c@ddrss@}$\ }\@qq{10pt}{0pt}\textrm{#1}}}
+  \global\setbox\@b@ddrss@=\vbox{\unvbox51}}%
+%
+\def\@dd@scndddrss@#1{%
+\global\setbox51=\vbox{\advance\hsize by-12pt\unvbox\@b@ddrss@
+  \vtop{\footnotesize\noindent{${}^{\the\@c@ddrss@}$\ }\@qq{10pt}{0pt}\textrm{#1}}}
+  \global\setbox\@b@ddrss@=\vbox{\unvbox51}}
+%
+\def\address#1{\global\advance\@c@ddrss@ by 1\@dd@ddrss@{#1}
+  \expandafter\edef\csname @ddrss@\romannumeral\@c@thr@\endcsname{\@spc\number\@c@ddrss@}}
+\def\secondaddress#1{\global\advance\@c@ddrss@ by 1\@dd@ddrss@{#1}
+  \expandafter\edef\csname @scndddrss@\romannumeral\@c@thr@\endcsname%
+{,\@spcc\number\@c@ddrss@}}%\secondaddress#1
+\def\sameaddress#1{\expandafter\edef\csname @smddrss@\romannumeral\@c@thr@\endcsname{\@spc{}#1}}
+%................ ................ ................ ................  ................
+%          -9-   Thanks  (given in the title: \thanks)
+%................ ................ ................ ................  ................
+\def\@rmnnmrl#1{\ifcase#1\null\or*\or**\or***\or****\or*****\else\@MSSG@THNKS\fi}
+\def\@thnks@i{}\def\@thnks@ii{}\def\@thnks@iii{}\def\@thnks@iv{}\def\@thnks@v{}
+\newcount\@c@thnks@\newbox\@b@thnks@
+\def\@dd@thnks@#1{%
+\global\setbox50=\vbox{\advance\hsize by-12pt\unvbox\@b@thnks@
+  \vtop{\noindent\footnotesize{${}^{\@rmnnmrl\@c@thnks@}$\ }\@qq{10pt}{0pt}\textit{#1}\hfill}}
+\global\setbox\@b@thnks@=\vbox{\unvbox50}}%
+\def\thanks#1{\global\advance\@c@thnks@ by 1\@dd@thnks@{#1}%
+\global\expandafter\edef\csname @thnks@\romannumeral\@c@thnks@\endcsname{%
+\ifnum\the\@c@thnks@=1\@spcc${}^{\@rmnnmrl\@c@thnks@}$\else$^{,\@spcc\@rmnnmrl\@c@thnks@}$\fi}}
+%%-----------------------------------------------------------------------------
+%% --> MISCELLANEOUS
+%%-----------------------------------------------------------------------------
+\DeclareRobustCommand*\cal{\@fontswitch\relax\mathcal}
+%
+\renewcommand\normalsize{\@xsetfontsize\normalsize 6%
+  \@adjustvertspacing \let\@listi\@listI 
+  \abovedisplayskip 11pt \@plus2pt \@minus2pt
+  \belowdisplayskip \abovedisplayskip}
+%
+\def\ps@firstpage{\ps@plain
+  \def\@oddfoot{\hfill{\scriptsize \copyright\ EDP Sciences 1999}}%
+  \let\@evenfoot\@oddfoot\def\@oddhead{\null\hss}
+  \let\@evenhead\@oddhead}% in case an article starts on a left-hand page
+%
+\def\ps@headings{\ps@empty
+  \def\@evenhead{\normalfont\scriptsize\llap{\normalsize\thepage\kern-4pt}\hfil\scriptsize\leftmark{}{}\hfil}%
+  \def\@oddhead{\normalfont\scriptsize\hfil\rightmark{}{}\hfil\rlap{\kern-4pt\normalsize{\thepage}}}%
+  \let\@mkboth\markboth}
+\def\ps@myheadings{\ps@headings \let\@mkboth\@gobbletwo}\pagestyle{headings}
+%%-----------------------------------------------------------------------------
+%% --> MESSAGES
+%%-----------------------------------------------------------------------------
+\def\@MSSG@THNKS{At most 5 thanks allowed}
+\def\@MSSG@CLSSWRNGRSM{Resume should precede \protect\maketitle\space in AMS documentclasses; reported}
+\def\@MSSG@CLSSWRNGBSTRCT{Abstract should precede \protect\maketitle\space in AMS documentclasses; 
+           reported}
+\def\@MSSG@KWRD{{WARNING:  --- Give at least one key words ---}}
+\def\@MSSG@KWRD@0K{{Keywords and phrases:\ }}
+\def\@MSSG@SBJCTCLSS{{--- Give AMS classification codes  ---}}
+\def\@MSSG@RSM{{WARNING:  --- Il est obligatoire de donner un r\'esum\'e en fran\c cais! ---}}
+\def\@MSSG@BSTRCT{{WARNING:  --- An English abstract is mandatory! ---}}
+\def\@MSSG@DT{{(The dates will be set by the publisher)}}
+\def\@MSSG@DTR{{(The editor will be set by the publisher)}}
+%% September 2002
+\def\@MSSG@RNNGTTL{\uppercase{Title will be set by the publisher}}
+\def\@MSSG@RNNGTHR{\uppercase{Title will be set by the publisher}}
+%
+\def\@date{\@MSSG@DT}
+\def\@editor{\@MSSG@DTR}
+\def\@subjclass#1{\@MSSG@SBJCTCLSS}
+%%-----------------------------------------------------------------------------
+%% --> VARIOUS MACROS
+%%-----------------------------------------------------------------------------
+%................ ................ ................ ................  ................
+%----  (A) LATIN ABBREVIATIONS
+%................ ................ ................ ................  ................
+\def\cf{\emph{cf.\/}}\def\ie{\emph{i.e.\/}}\def\etc{\emph{etc\/}}
+\def\apriori{\emph{a priori\/}}\def\afortiori{\emph{a fortiori\/}}
+\def\loccit{\emph{a loc. cit.\/}}\def\etal{\emph{et al.\/}}
+\def\vg{\emph{v.g.\/}}
+%................ ................ ................ ................  ................
+%----  (B) REFERENCES
+%................ ................ ................ ................  ................
+\def\@Rref#1{\hbox{\rm \ref{#1}}}
+\def\Rref#1{\@Rref{#1}}
+%................ ................ ................ ................  ................
+%----  (C) NEWTHEOREM AND ENVIRONMENTS
+%................ ................ ................ ................  ................
+%-------------------
+\theoremstyle{plain}
+%-------------------
+\newtheorem{thrm}{Theorem}[section]
+\newtheorem{lmm}[thrm]{Lemma}
+\newtheorem{crllr}[thrm]{Corollary}
+\newtheorem{prpstn}[thrm]{Proposition}
+\newtheorem{crtrn}[thrm]{Criterion}
+\newtheorem{lgrthm}[thrm]{Algorithm}
+%------------------------
+\theoremstyle{definition}
+%------------------------
+\newtheorem{dfntn}[thrm]{Definition}
+\newtheorem{cnjctr}[thrm]{Conjecture}
+\newtheorem{xmpl}[thrm]{Example}
+\newtheorem{prblm}[thrm]{Problem}
+\newtheorem{rmrk}[thrm]{Remark}
+\newtheorem{nt}[thrm]{Note}
+\newtheorem{clm}[thrm]{Claim}
+\newtheorem{smmr}[thrm]{Summary}
+\newtheorem{cs}[thrm]{Case}
+\newtheorem{bsrvtn}[thrm]{Observation}
+%
+%-------------------
+\theoremstyle{plain}
+%-------------------
+\newenvironment{acknowledgement}{\par\addvspace{17pt}\small\rmfamily\noindent}{\par\addvspace{6pt}}
+%................ ................ ................ ................  ................
+%----  (D) MACROS FOR MATHEMATICS
+%................ ................ ................ ................  ................
+\def\xQuaternion{\mathbb{H}} \def\xC{\mathbb{C}} \def\xR{\mathbb{R}}
+\def\xQ{\mathbb{Q}} \def\xZ{\mathbb{Z}} \def\xN{\mathbb{N}}
+\def\xP{\mathbb{P}} \def\xA{\mathbb{A}}
+%--
+\def\xCzero{{\rm C}^{0}}
+\def\xCone{{\rm C}^{1}} 
+\def\xCtwo{{\rm C}^{2}} 
+\def\xCinfty{{\rm C}^{\infty}} 
+\def\xCn#1{{\rm C}^#1}
+%--
+\def\xHzero{{\rm H}^{0}}
+\def\xHone{{\rm H}^{1}}
+\def\xHtwo{{\rm H}^{2}} 
+\def\xHinfty{{\rm H}^{\infty}}
+\def\xHn#1{{\rm H}^#1}
+%
+\def\xWzero{{\rm W}^{0}}
+\def\xWone{{\rm W}^{1}}
+\def\xWtwo{{\rm W}^{2}} 
+\def\xWinfty{{\rm W}^{\infty}}
+\def\xWn#1{{\rm W}^#1}
+%
+\def\xLzero{{\rm L}^{0}}
+\def\xLone{{\rm L}^{1}}
+\def\xLtwo{{\rm L}^{2}} 
+\def\xLinfty{{\rm L}^{\infty}} 
+\def\xLn#1{{\rm L}^#1}
+%-- 
+\def\xDif{{\rm D}}
+\def\xdif{\,{\rm d}}
+%-- 
+\def\xdrv#1#2{\frac{{\rm d}#1}{{\rm d}#2}}%  "d#1 over d#2"
+\def\xDrv#1#2{\frac{{\rm d}}{{\rm d}#2}#1}%  "d   over d#2  #1"
+%--
+\def\xker{\mathop{\rm ker\,}\nolimits}
+\def\xcoker{\mathop{\rm coker\,}\nolimits}
+\def\xim{\mathop{\rm im\,}\nolimits}
+\def\xcoim{\mathop{\rm coim\,}\nolimits}
+\def\xdim{\mathop{\rm dim\,}\nolimits}
+\def\xcodim{\mathop{\rm codim\,}\nolimits}
+\def\xtr{\mathop{\rm tr\,}\nolimits}
+\def\xHom{\mathop{\rm Hom\,}\nolimits}
+\def\xExt{\mathop{\rm Ext\,}\nolimits}
+\def\xTor{\mathop{\rm Tor\,}\nolimits}
+%--
+\def\xGL{\mathop{\rm GL\,}\nolimits}
+\def\xSL{\mathop{\rm SL\,}\nolimits}
+\def\xPSL{\mathop{\rm PSL\,}\nolimits}
+\def\xSO{\mathop{\rm SO\,}\nolimits}
+\def\xSU{\mathop{\rm SU\,}\nolimits}
+%
+\def\xProof{
+  \normalfont
+  \medskip
+  {\noindent\itshape Proof.\hspace*{6pt}\ignorespaces}}
+%
+\def\enddoc@text{\ifx\@empty\@translators \else\@settranslators\fi
+  \ifx\@empty\@editor \else\@seteditor\\\fi
+  \ifx\@empty\@date \else\@setdate\fi}
+%
+%
+\endinput

diff --git a/main.tex b/main.tex
new file mode 100644 (file)
index 0000000..9192540
--- /dev/null
+++ b/main.tex
@@ -0,0 +1,129 @@
+\documentclass{ita}
+\usepackage{graphicx}
+\usepackage{dsfont}
+\usepackage{stmaryrd}
+\usepackage[font=footnotesize]{subfig}
+\usepackage{ifthen}
+\usepackage{color}
+\usepackage{algorithm2e}
+\usepackage[hyperfirst=true,nogroupskip,nonumberlist,xindy]{glossaries}
+
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% Définitions personnelles
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+
+\definecolor{bleuclair}{rgb}{0.75,0.75,1.0}
+\newcommand{\ANNOT}[1]{
+  ~\linebreak
+  \centerline{
+    {\Huge{\danger}}
+    \large\fcolorbox{black}{bleuclair}{
+      \begin{minipage}[h]{.8\linewidth}
+        #1
+      \end{minipage}
+    }
+    {\Huge{\danger}}
+  }
+}
+
+% \theoremstyle{plain}
+% \theoremheaderfont{\normalfont\bfseries\sc}
+% \theorembodyfont{\slshape}
+% \theoremsymbol{\ensuremath{\diamondsuit}}
+% \theoremprework{\bigskip}
+% \theoremseparator{.}
+\newtheorem{Def}{\underline{Définition}}
+\newtheorem{Lemma}{\underline{Lemme}}
+\newtheorem{Theo}{\underline{Théorème}}
+% \theoremheaderfont{\sc}
+% \theorembodyfont{\upshape}
+% \theoremstyle{nonumberplain}
+% \theoremseparator{}
+% \theoremsymbol{\rule{1ex}{1ex}}
+\newtheorem{Proof}{Preuve :}
+\newtheorem{xpl}{Exemple illustratif :}
+
+\newcommand{\vectornorm}[1]{\ensuremath{\left|\left|#1\right|\right|_2}}
+%\newcommand{\ie}{\textit{i.e.}}
+\newcommand{\Nats}[0]{\ensuremath{\mathbb{N}}}
+\newcommand{\R}[0]{\ensuremath{\mathbb{R}}}
+\newcommand{\Z}[0]{\ensuremath{\mathbb{Z}}}
+\newcommand{\Bool}[0]{\ensuremath{\mathds{B}}}
+\newcommand{\rel}[0]{\ensuremath{{\mathcal{R}}}}
+\newcommand{\Gall}[0]{\ensuremath{\mathcal{G}}}
+
+
+\newcommand{\JFC}[1]{\begin{color}{green}\textit{}\end{color}}
+\newcommand{\CG}[1]{\begin{color}{blue}\textit{}\end{color}}
+\newcommand{\og}[0]{``}
+\newcommand{\fg}[1]{''}
+
+
+
+
+\makeglossaries
+\loadglsentries{glossaire}
+
+
+\title{XXX}
+
+\begin{document}
+
+\author{Jean-François Couchot, Christophe Guyeux, Pierre-Cyrile Heam}
+\address{Institut FEMTO-ST, Université de Franche-Comté, Belfort, France}
+
+\author{Sylvain Contassot-Vivier}
+\address{Loria - UMR 7503, Université de Lorraine, Nancy, France}
+
+\date{...}
+
+\begin{abstract}
+This   paper  extends   the  results   presented  in~\cite{bcgr11ip}
+and~\cite{chgw14oip} by using the \emph{chaotic} updating mode, in the sense
+of F.  Robert~\cite{Robert}.  In this mode, several components of the system
+may be  updated at each iteration.   At the theoretical level,  we show that
+    the properties of  chaos and uniformity of the  obtained PRNG are preserved.
+    At  the practical level,  we show  that the  algorithm that  builds strongly
+    connected  iteration graphs,  with doubly  stochastic Markov  matrix,  has a
+    reduced mixing time.
+\end{abstract}
+
+\section{Introduction}
+\input{intro}
+
+\section{Préliminaires}
+\label{section:chaos}
+\input{sdd}
+
+\section{Caractérisation des systèmes dynamiques booléens chaotiques}
+\label{section:caracterisation}
+\input{cs}
+
+
+\section{Application  à la génération de nombres pseudo-aléatoires}
+\label{section:genpa}
+\input{exp}
+
+
+\section{Expérimentations}
+\label{section:expes}
+\input{nist}
+
+\section{Conclusion}
+\input{conclusion}
+
+%\acknowledgements{...}
+
+\appendix%\begin{annex}
+   \section{Preuve de continuité de $G_f$ dans $(\mathcal{X},d)$}
+  \label{anx:cont}
+  \input{annexecontinuite}
+
+
+\printglossaries
+
+\bibliography{biblio}
+
+\end{document}

diff --git a/markov.bib b/markov.bib
new file mode 100644 (file)
index 0000000..9b5189b
--- /dev/null
+++ b/markov.bib
@@ -0,0 +1,390 @@
+@inproceedings{chgw+14oip,
+inhal = {no},
+domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO, INFO:INFO_SE},
+equipe = {ie},
+classement = {COM},
+author = {Couchot, Jean-Fran\c{c}ois and H\'eam, Pierre-Cyrille and Guyeux, Christophe and Wang, Qianxue and Bahi, Jacques},
+title = {Pseudorandom Number Generators with Balanced Gray Codes},
+booktitle = {Secrypt 2014, 11th Int. Conf. on Security and Cryptography},
+pages = {***--***},
+address = {Vienna, Austria},
+month = aug,
+date = {28-30 aout},
+year = 2014,
+note = {Position short paper. To appear},
+
+}
+@Article{rwfg,
+  author =      {Laurent Saloff-Coste},
+  title =       {Random Walks on Finite Groups},
+  journal =     {Probability on Descrete Structures},
+  year =        {},
+  OPTkey =      {},
+  volume =      {110},
+  OPTnumber =   {},
+  pages =       {263-346},
+  OPTmonth =    {},
+  note =        {http://stat.stanford.edu/~cgates/PERSI/papers/rwfg.pdf},
+  OPTannote =   {}
+}
+
+@book{LevinPeresWilmer2006,
+  added-at = {2010-01-19T17:51:27.000+0100},
+  author = {Levin, David A. and Peres, Yuval and Wilmer, Elizabeth L.},
+  biburl = {http://www.bibsonomy.org/bibtex/2097dc4d1d0e412b2444f540b04110797/tmalsburg},
+  interhash = {61354795a6accb6407bfdbf04753a683},
+  intrahash = {097dc4d1d0e412b2444f540b04110797},
+  keywords = {markovchains probabilitytheory textbook},
+  publisher = {American Mathematical Society},
+  timestamp = {2010-01-19T17:51:27.000+0100},
+  title = {{Markov chains and mixing times}},
+  url = {http://scholar.google.com/scholar.bib?q=info:3wf9IU94tyMJ:scholar.google.com/&output=citation&hl=en&as_sdt=2000&ct=citation&cd=0},
+  year = 2006
+}
+
+@BOOK{devaney,
+  title = {An Introduction to Chaotic Dynamical Systems},
+  publisher = {Addison-Wesley},
+  year = {1989},
+  author = {Devaney, Robert L.},
+  address = {Redwood City, CA},
+  edition = {2nd}
+}
+
+
+@ARTICLE{Banks92,
+  author = {J. Banks and J. Brooks and G. Cairns and P. Stacey},
+  title = {On {D}evaney's Definition of Chaos},
+  journal = {Amer. Math. Monthly},
+  year = {1992},
+  volume = {99},
+  pages = {332--334},
+  keywords = {(c+),},
+  owner = {guyeux},
+  timestamp = {27/01/2008}
+}
+
+
+@INPROCEEDINGS{wbg10ip,
+  author = {Wang, Qianxue and Bahi, Jacques and Guyeux, Christophe and Fang,
+       Xiaole},
+  title = {Randomness quality of {CI} chaotic generators. Application to Internet
+       security},
+  booktitle = {INTERNET'2010. The 2nd Int. Conf. on Evolving Internet},
+  year = {2010},
+  pages = {125--130},
+  address = {Valencia, Spain},
+  month = sep,
+  publisher = {IEEE Computer Society Press},
+  note = {Best Paper award},
+  classement = {ACTI},
+  doi = {10.1109/INTERNET.2010.30},
+  domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
+  equipe = {and},
+  inhal = {no},
+  url = {http://doi.ieeecomputersociety.org/10.1109/INTERNET.2010.30}
+}
+
+
+
+@INPROCEEDINGS{bgw10ip,
+  author = {Bahi, Jacques and Guyeux, Christophe and Wang, Qianxue},
+  title = {A Pseudo Random Numbers Generator Based on Chaotic Iterations. Application
+       to Watermarking},
+  booktitle = {WISM 2010, Int. Conf. on Web Information Systems and Mining},
+  year = {2010},
+  volume = {6318},
+  series = {LNCS},
+  pages = {202--211},
+  address = {Sanya, China},
+  month = oct,
+  classement = {ACTI},
+  doi = {10.1007/978-3-642-16515-3_26},
+  domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
+  equipe = {and},
+  inhal = {no},
+  url = {http://dx.doi.org/10.1007/978-3-642-16515-3_26}
+}
+
+
+
+@INPROCEEDINGS{bgw09ip,
+  author = {Bahi, Jacques and Guyeux, Christophe and Wang, Qianxue},
+  title = {A novel pseudo-random generator based on discrete chaotic iterations},
+  booktitle = {INTERNET'09, 1-st Int. Conf. on Evolving Internet},
+  year = {2009},
+  pages = {71--76},
+  address = {Cannes, France},
+  month = aug,
+  classement = {ACTI},
+  doi = {10.1109/INTERNET.2009.18},
+  domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
+  equipe = {and},
+  inhal = {no},
+  url = {http://dx.doi.org/10.1109/INTERNET.2009.18}
+}
+
+
+
+@INPROCEEDINGS{guyeuxTaiwan10,
+  author = {Bahi, Jacques M. and Guyeux, Christophe and Wang, Qianxue},
+  title = {Improving random number generators by chaotic iterations. {A}pplication
+       in data hiding},
+  booktitle = {ICCASM 2010, Int. Conf. on Computer Application and System Modeling},
+  year = {2010},
+  pages = {V13-643--V13-647},
+  address = {Taiyuan, China},
+  month = oct,
+  classement = {ACTI},
+  doi = {10.1109/ICCASM.2010.5622199},
+  domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
+  equipe = {and},
+  inhal = {no},
+  url = {http://dx.doi.org/10.1109/ICCASM.2010.5622199}
+}
+
+@inproceedings{bcgw11ip,
+inhal = {no},
+domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
+equipe = {and},
+classement = {ACTI},
+author = {Bahi, Jacques and Couchot, Jean-Fran\c{c}ois and Guyeux, Christophe and Wang, Qianxue},
+title = {Class of Trustworthy Pseudo Random Number Generators},
+booktitle = {INTERNET 2011, the 3-rd Int. Conf. on Evolving Internet},
+pages = {72--77},
+address = {Luxembourg, Luxembourg},
+month = jun,
+year = 2011}
+
+
+
+@INPROCEEDINGS{bcgr11ip,
+  author = {Bahi, Jacques and Couchot, Jean-Fran\c{c}ois and Guyeux, Christophe
+       and Richard, Adrien},
+  title = {On the Link Between Strongly Connected Iteration Graphs and Chaotic
+       Boolean Discrete-Time Dynamical Systems},
+  booktitle = {FCT'11, 18th Int. Symp. on Fundamentals of Computation Theory},
+  year = {2011},
+  volume = {6914},
+  series = {LNCS},
+  pages = {126--137},
+  address = {Oslo, Norway},
+  month = aug,
+  classement = {ACTI},
+  doi = {10.1007/978-3-642-22953-4_11},
+  domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
+  equipe = {and},
+  inhal = {no},
+  url = "http://dx.doi.org/10.1007/978-3-642-22953-4_11"
+}
+
+
+
+@INPROCEEDINGS{bg10aip,
+  author = {Bahi, Jacques and Guyeux, Christophe},
+  title = {Topological chaos and chaotic iterations, application to Hash functions},
+  booktitle = {IJCNN'10, Int. Joint Conf. on Neural Networks, joint to WCCI'10,
+       IEEE World Congress on Computational Intelligence},
+  year = {2010},
+  pages = {1--7},
+  address = {Barcelona, Spain},
+  month = jul,
+  note = {Best paper award},
+  classement = {ACTI},
+  doi = {10.1109/IJCNN.2010.5596512},
+  domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
+  equipe = {and},
+  inhal = {no},
+  url = {http://dx.doi.org/10.1109/IJCNN.2010.5596512}
+}
+
+
+@ARTICLE{DBLPjournals/corr/abs-1112-5239,
+  author = {Jacques M. Bahi and Rapha{\"e}l Couturier and Christophe Guyeux and
+       Pierre-Cyrille H{\'e}am},
+  title = {Efficient and Cryptographically Secure Generation of Chaotic Pseudorandom
+       Numbers on GPU},
+  journal = {CoRR},
+  year = {2011},
+  volume = {abs/1112.5239},
+  bibsource = {DBLP, http://dblp.uni-trier.de},
+  ee = {http://arxiv.org/abs/1112.5239}
+}
+
+@MISC{Nist10,
+  author = {E. Barker and A. Roginsky},
+  title = {DRAFT {N}{I}{S}{T} Special Publication 800-131 Recommendation for
+       the Transitioning of Cryptographic Algorithms and Key Sizes},
+  year = {2010},
+  owner = {christophe},
+  timestamp = {2010.08.18}
+}
+
+
+@ARTICLE{LEcuyerS07,
+  author = {Pierre L'Ecuyer and Richard J. Simard},
+  title = {Test{U01}: {A} {C} library for empirical testing of random number
+       generators},
+  journal = {ACM Trans. Math. Softw},
+  year = {2007},
+  volume = {33},
+  number = {4},
+  bibdate = {2007-11-06},
+  bibsource = {DBLP, http://dblp.uni-trier.de/db/journals/toms/toms33.html#LEcuyerS07},
+  url = {http://doi.acm.org/10.1145/1268776.1268777}
+}
+
+
+@ARTICLE{Marsaglia1996,
+  author = {G. Marsaglia},
+  title = {DIEHARD: a battery of tests of randomness},
+  journal = {http://stat.fsu.edu/~geo/diehard.html},
+  year = {1996},
+  owner = {qianxue},
+  timestamp = {2009.11.09}
+}
+
+@PHDTHESIS{Xiaole13,
+  author = {Xiaole Fang},
+  title = {Utilization of chaotic dynamics for generating pseudorandom numbers
+       in various contexts},
+  school = {Universit\'{e} de Franche-Comt\'{e}},
+  year = {2013},
+  owner = {guyeux},
+  timestamp = {2008.01.02}
+}
+
+@BOOK{Robert,
+  title = {Discrete Iterations, a Metric Study},
+  publisher = {Springer-Verlag},
+  year = {1986},
+  author = {Fran\,cois Robert},
+  volume = {6},
+  series = {Series in Computational Mathematics}
+}
+
+
+@ARTICLE{915396,
+author={Stojanovski, T. and Pihl, J. and Kocarev, L.}, 
+journal={Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on}, 
+title={Chaos-based random number generators. Part II: practical realization}, 
+year={2001}, 
+month={Mar}, 
+volume={48}, 
+number={3}, 
+pages={382-385}, 
+keywords={CMOS analogue integrated circuits;chaos generators;circuit simulation;piecewise linear techniques;random number generation;redundancy;switched current circuits;0.8 micron;1 Mbit/s;chaos-based random number generators;chaotic piecewise-linear one-dimensional map;output bit rate;parasitic attractors;periodic attractors;post-layout circuit simulations;process conditions;redundancy;standard CMOS process;switched current techniques;Bit rate;CMOS process;Chaos;Circuits;Electric breakdown;Information analysis;Piecewise linear techniques;Power supplies;Random number generation;Temperature}, 
+doi={10.1109/81.915396}, 
+ISSN={1057-7122},}
+
+
+@ARTICLE{915385, 
+author={Stojanovski, T. and Kocarev, L.}, 
+journal={Circuits and Systems I: Fundamental Theory and Applications, IEEE Transactions on}, 
+title={Chaos-based random number generators-part I: analysis [cryptography]}, 
+year={2001}, 
+month={Mar}, 
+volume={48}, 
+number={3}, 
+pages={281-288}, 
+keywords={Markov processes;chaos;cryptography;piecewise linear techniques;random number generation;Markov generating partition;Markov information source;chaos-based random number generators;cryptography;information generation process;parameter values;piecewise-linear one-dimensional map;random number generator;Chaos;Cryptographic protocols;Cryptography;Current measurement;Low-frequency noise;Noise measurement;Random number generation;Random sequences;Security;Semiconductor device noise}, 
+doi={10.1109/81.915385}, 
+ISSN={1057-7122},}
+
+@INPROCEEDINGS{5376454, 
+author={Li Cao and Lequan Min and Hongyan Zang}, 
+booktitle={Computational Intelligence and Security, 2009. CIS '09. International Conference on}, 
+title={A Chaos-Based Pseudorandom Number Generator and Performance Analysis}, 
+year={2009}, 
+month={Dec}, 
+volume={1}, 
+pages={494-498}, 
+keywords={binary sequences;chaos;discrete systems;random number generation;synchronisation;2D Arnold cat map;6D discrete chaos map;FIPA-140-2 tests;National Institute of Standard and Technology;binary number sequences;chaos-based pseudorandom number generator;confidence interval analysis;generalized chaos synchronization theorem;performance analysis;Chaos;Chaotic communication;Computational intelligence;NIST;Nonlinear dynamical systems;Performance analysis;Random number generation;Security;Space technology;Testing;Discrete chaos map;generalized chaos synchronization;one-time-pad;statistical test}, 
+doi={10.1109/CIS.2009.203},}
+
+@article{bfgw13ij,
+inhal = {no},
+domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
+equipe = {and},
+classement = {ACLI},
+impact-factor ={1.065},
+isi-acro = {J NETW COMPUT APPL},
+author = {Bahi, Jacques and Fang, Xiaole and Guyeux, Christophe and Wang, Qianxue},
+title = {Suitability of chaotic iterations schemes using {XORshift} for security applications},
+journal = {JNCA, Journal of Network and Computer Applications},
+pages = {282--292},
+volume = 37,
+doi = {10.1016/j.jnca.2013.03.001},
+url = {http://dx.doi.org/10.1016/j.jnca.2013.03.001},
+abstract = {The design and engineering of original cryptographic solutions is a major concern to provide secure information systems. In a previous study, we have described a generator based on chaotic iterations, which uses the well-known XORshift generator. By doing so, we have improved the statistical performances of XORshift and make it behave chaotically, as defined by Devaney. The speed and security of this former generator have been improved in a second study, to make its usage more relevant in the Internet security context. In this paper, these contributions are summarized and a new version of the generator is introduced. It is based on a new Lookup Table implying a large improvement of speed. A comparison and a security analysis between the XORshift and these three versions of our generator are proposed, and various new statistical results are given. Finally, an application in the information hiding framework is presented, to give an illustrative example of the use of such a generator in the Internet security field.},
+publisher = {Elsevier},
+year = 2013,
+
+}
+
+
+@article{Marsaglia2003JSSOBKv08i14,
+  author =     "George Marsaglia",
+  title =      "Xorshift RNGs",
+  journal =    "Journal of Statistical Software",
+  volume =     "8",
+  number =     "14",
+  pages =      "1--6",
+  day =        "4",
+  month =      "7",
+  year =       "2003",
+  CODEN =      "JSSOBK",
+  ISSN =       "1548-7660",
+  bibdate =    "2003-07-04",
+  URL =        "http://www.jstatsoft.org/v08/i14",
+  accepted =   "2003-07-04",
+  acknowledgement = "",
+  keywords =   "",
+  submitted =  "2003-05-06",
+}
+
+
+
+@INPROCEEDINGS{cghwb14ip,
+  author = {Couchot, Jean-Fran\c{c}ois and Guyeux, Christophe and Heam, 
+Pierre-Cyrille, and Wang, Qianxue and Bahi, Jacques},
+  title = {Pseudorandom Number Generators with Balanced Gray Codes},
+  booktitle = {SECRYPT 2014, the 11th International Conference on Security and Cryptography},
+  year = {2014},
+  pages = {***--***},
+  address = {Vienna, Austria},
+  month = aug,
+  classement = {ACTI},
+  doi = {10.1007/978-3-642-22953-4_11},
+  domainehal = {INFO:INFO_DC, INFO:INFO_CR, INFO:INFO_MO},
+  equipe = {and},
+  inhal = {no},
+}
+
+@Article{ZanSup04,
+  author =       {Suparta, IN and Zanten, AJ van},
+  title =        {Totally balanced and exponentially balanced Gray codes},
+  journal =      {Discrete Analysis and Operation Research (Russia)},
+  year =         {2004},
+  OPTkey =       {},
+  volume =    {11},
+  number =    {4},
+  pages =     {81-98},
+  OPTmonth =     {},
+  OPTnote =      {},
+  OPTannote =    {}
+}
+
+@Article{Feder2009NTB,
+  title =      "Nearly tight bounds on the number of Hamiltonian
+                circuits of the hypercube and generalizations",
+  author =     "Tom{\'a}s Feder and Carlos S. Subi",
+  journal =    "Info. Process. Lett",
+  year =       "2009",
+  number =     "5",
+  volume =     "109",
+  pages =      "267--272",
+  URL =        "http://dx.doi.org/10.1016/j.ipl.2008.10.015",
+}
+
+

diff --git a/nist.tex b/nist.tex
new file mode 100644 (file)
index 0000000..7e196e6
--- /dev/null
+++ b/nist.tex
@@ -0,0 +1,143 @@
+% Soit $e_i$ le $i^{\textrm{ème}}$ vecteur de la base canonique de $\R^{2^{n}}$. 
+% Chacun des éléments $v_j$, $1 \le j \le 2^n$, 
+% du vecteur $e_i M_f^t$ représente la probabilité 
+% d'être dans la configuration $j$ après $t$ étapes du processus de Markov 
+% associé à $\Gamma(f)$ en partant de la configuration $i$.   
+% Le nombre \linebreak $\min \{
+%  t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4}
+% \}$ représente le plus petit nombre d'itérations où la distance de 
+% ce vecteur au vecteur $\pi=(\frac{1}{2^n},\ldots,\frac{1}{2^n})$
+% -- autrement dit, où la déviation par rapport à la distribution uniforme --
+%  est inférieure 
+% à $10^{-4}$. En prenant le max pour tous les $e_i$, on obtient une valeur pour
+%  $b$. Ainsi, on a 
+% $$
+% b = \max\limits_{i \in \llbracket 1, 2^n \rrbracket} 
+% \{
+% \min \{
+%  t \mid t \in \Nats, \vectornorm{e_i M_f^t - \pi} < 10^{-4}
+% \}
+% \}. 
+% $$
+
+\begin{table}[table:functions]{Fonctions avec matrices DSCC et le plus faible temps de mélange.}
+  \begin{center}
+    \begin{scriptsize}
+      \begin{tabular}{|c|l|c|c|}
+        \hline
+        fonction  & $f(x)$, $f(x)$ pour $x \in [0,1,2,\hdots,2^n-1]$                 & $b$ & $b'$ \\ 
+        \hline
+        $f^{*4}$  & [13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8]                          & 15  & 32   \\
+        \hline
+        $f^{*5}$  & [29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1,        & 13  & 43   \\
+                  & 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4]     &     &      \\
+        \hline
+        $f^{*6}$  & [55, 60, 45, 44, 58, 62, 61, 48, 53, 50, 52, 36, 59, 34, 33,     & 9   & 50   \\
+                  & 49, 15, 42, 47, 46, 35, 10, 57, 56, 7, 54, 39, 37, 51, 2, 1,     &     &      \\
+                  & 40, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22,      &     &      \\
+                  & 16, 24, 13, 12, 29, 8, 43, 14, 41, 0, 5, 38, 4, 6, 11, 3, 9, 32] &     &      \\
+         \hline
+         $f^{*7}$ & [111, 94, 93, 116, 122, 114, 125, 88, 87, 126, 119, 84, 123,     & 8   & 57   \\
+                  & 98, 81, 120, 109, 106, 105, 110, 99, 107, 104, 108, 101, 70,     &     &      \\ 
+                  & 117, 96, 67, 102, 113, 64, 79, 30, 95, 124, 83, 91, 121, 24,     &     &      \\ 
+                  & 23, 118, 69, 20, 115, 90, 17, 112, 77, 14, 73, 78, 74, 10, 72,   &     &      \\ 
+                  & 76, 103, 6, 71, 100, 75, 82, 97, 0, 127, 54, 57, 62, 51, 59,     &     &      \\ 
+                  & 56, 48, 53, 38, 37, 60, 55, 58, 33, 49, 63, 44, 47, 40, 42,      &     &      \\ 
+                  & 46, 45, 41, 35, 34, 39, 52, 43, 50, 32, 36, 29, 28, 61, 92,      &     &      \\ 
+                  & 26, 18, 89, 25, 19, 86, 85, 4, 27, 2, 16, 80, 31, 12, 15, 8,     &     &      \\ 
+                  & 3, 11, 13, 9, 5, 22, 21, 68, 7, 66, 65, 1]                       &     &      \\
+        \hline
+        $f^{*8}$  &[223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180,&        7 & 63    \\
+                 & 227, 178, 240, 248, 237, 236, 253, 172, 203, 170, 201, 168, &&\\
+                 & 229, 166, 165, 244, 163, 242, 241, 192, 215, 220, 205, 216, &&\\
+                 & 218, 222, 221, 208, 213, 210, 212, 214, 219, 211, 217, 209, &&\\
+                 & 239, 202, 207, 140, 139, 234, 193, 204, 135, 196, 199, 132, &&\\
+                 & 194, 130, 225, 200, 159, 62, 185, 252, 59, 250, 169, 56, 191,&&\\
+                 & 246, 245, 52, 243, 50, 176, 48, 173, 238, 189, 44, 235, 42, &&\\
+                 & 137, 184, 231, 38, 37, 228, 35, 226, 177, 224, 151, 156, 141,&&\\
+                 & 152, 154, 158, 157, 144, 149, 146, 148, 150, 155, 147, 153, &&\\
+                 & 145, 175, 206, 143, 136, 11, 142, 129, 8, 7, 198, 197, 4, 195, &&\\
+                 & 2, 161, 160, 255, 124, 109, 108, 122, 126, 125, 112, 117, 114, &&\\
+                 & 116, 100, 123, 98, 97, 113, 79, 106, 111, 110, 99, 74, 121, 120,&&\\
+                 & 71, 118, 103, 101, 115, 66, 65, 104, 127, 90, 89, 94, 83, 91, 81,&&\\
+                 & 92, 95, 84, 87, 85, 82, 86, 80, 88, 77, 76, 93, 72, 107, 78, 105, &&\\
+                 & 64, 69, 102, 68, 70, 75, 67, 73, 96, 55, 58, 45, 188, 51, 186, 61, &&\\
+                 & 40, 119, 182, 181, 53, 179, 54, 33, 49, 15, 174, 47, 60, 171, && \\
+                 & 46, 57, 32, 167, 6, 36, 164, 43, 162, 1, 0, 63, 26, 25, 30, 19,&&\\
+                 & 27, 17, 28, 31, 20, 23, 21, 18, 22, 16, 24, 13, 10, 29, 14, 3, &&\\
+                 &138, 41, 12, 39, 134, 133, 5, 131, 34, 9, 128]&&\\
+        \hline
+      \end{tabular}
+    \end{scriptsize}
+  \end{center}
+\end{table}
+
+Le  tableau~\ref{table:functions} reprend  les  fonctions qui  ont été  générées
+selon  la méthode détaillée  dans~\cite{chgw14oip} correspondant  à ce  qui est
+présenté en  section~\ref{section:genmat}.  Pour  chaque nombre $n=3$,  $4$, $5$
+,$6$, tous  les cycles  hamiltoniens non isomorphes  ont été générés.   Pour les
+valeur de $n=7$ et $8$,  seules $10^{5}$ configurations ont été évaluées.  Parmi
+toutes  les fonctions  obtenues en  enlevant du  $n$-cube ces  cycles,  n'ont été
+retenues que celles  qui minimisaient le temps de mélange relatif  à une valeur de
+$\epsilon$ fixée à $10^{-8}$.  Ce  nombre d'itérations est stocké dans la troisième
+colonne sous la variable $b$.  La variable $b'$ reprend le temps de mélange pour
+l'algorithme $\chi_{\textit{14Secrypt}}$~\cite{chgw14oip}.
+
+Un premier  résultat est  que ce nouvel  algorithme réduit grandement  le nombre
+d'itérations  suffisant pour  obtenir une  faible  déviation par  rapport à  une
+distribution uniforme.  On constate de  plus que ce nombre semble décroître avec
+le nombre d'éléments alors qu'il augmentait dans l'approche précédente.
+
+La qualité des séquences aléatoires a été évaluée à travers la suite 
+de tests statistiques développée pour les générateurs de nombres 
+pseudo-aléatoires par le 
+\emph{National Institute of Standards and Technology} (NIST).
+ Pour les 15 tests, le seuil $\alpha$ est fixé à $1\%$:
+ une  valeur  
+ qui est plus grande que $1\%$  signifie 
+ que la chaîne est considérée comme aléatoire avec une confiance de $99\%$.
+ Le tableau~\ref{fig:TEST} donne une vision synthétique de toutes 
+ les expérimentations. 
+L'expérience a montré notamment que toutes ces fonctions
+passent avec succès cette batterie de tests. 
+
+%%%%%%%%% Relancer pour n=6, n=7, n=8
+%%%%%%%%% Recalculer le MT
+%%%%%%%%% Regenerer les 10^6 bits
+%%%%%%%%% Evaluer sur NIST
+ 
+\begin{table}[fig:TEST]{Test de NIST réalisé sur les fonctions $f^*$ détaillées au tableau~\ref{table:functions}.}
+  \centering
+  \begin{scriptsize}
+    \begin{tabular}{|*{5}{c|}}
+      \hline
+Test                          & $f^{*4}$      & $f^{*5}$      & $f^{*6}$      & $f^{*7}$      \\ \hline
+Fréquence (Monobit)           & 0.025 (0.99)  & 0.066 (1.0)   & 0.319 (0.99)  & 0.001 (1.0)   \\ \hline  
+Fréquence / bloc              & 0.401 (0.99)  & 0.867 (1.0)   & 0.045 (0.99)  & 0.085 (0.99)  \\ \hline
+Somme Cumulé*                 & 0.219 (0.995) & 0.633 (1.0)   & 0.635 (1.0)   & 0.386 (0.99)  \\ \hline 
+Exécution                     & 0.964 (0.98)  & 0.699 (0.99)  & 0.181 (0.99)  & 0.911 (0.98)  \\ \hline 
+Longue exécution dans un bloc & 0.137 (0.99)  & 0.964 (1.0)   & 0.145 (0.99)  & 0.162 (0.98)  \\ \hline 
+Rang                          & 0.616 (0.99)  & 0.678 (1.0)   & 0.004 (1.0)   & 0.816 (1.0)   \\ \hline 
+Fourier rapide                & 0.048 (0.99)  & 0.637 (0.97)  & 0.366 (0.99)  & 0.162 (0.99)  \\ \hline 
+Patron sans superposition*    & 0.479 (0.988) & 0.465 (0.989) & 0.535 (0.989) & 0.499 (0.989) \\ \hline 
+Patron avec superposition     & 0.897 (1.0)   & 0.657 (0.97)  & 0.897 (0.98)  & 0.236 (0.99)  \\ \hline 
+Statistiques universelles     & 0.991 (0.98)  & 0.657 (0.98)  & 0.102 (0.98)  & 0.719 (0.98)  \\ \hline 
+Entropie approchée (m=10)     & 0.455 (1.0)   & 0.964 (1.0)   & 0.162 (1.0)   & 0.897 (0.98)  \\ \hline 
+Suite aléatoire *             & 0.372 (0.993) & 0.494 (0.986) & 0.243 (0.992) & 0.258 (0.993) \\ \hline 
+Suite aléatoire variante *    & 0.496 (0.989) & 0.498 (0.992) & 0.308 (0.983) & 0.310 (0.999) \\ \hline 
+Série* (m=10)                 & 0.595 (0.995) & 0.289 (0.975) & 0.660 (0.995) & 0.544 (0.99)  \\ \hline 
+Complexité linaire            & 0.816 (1.0)   & 0.897 (0.98)  & 0.080 (0.98)  & 0.798 (1.0)   \\ \hline
+    \end{tabular}
+  \end{scriptsize}
+\end{table}
+
+Enfin,  nous avons  également débuté  une campagne  de tests  complémentaires de
+notre  générateur  aléatoire, utilisant  les  trois  \emph{crush tests}  (small,
+normal  et big)  proposés dans  la bibliothèque  TestU01~\cite{LEcuyerS07}.  Les
+premiers résultats que nous obtenons sont très encourageants puisque la fonction
+$f^{*4}$ passe avec succès tous les tests du small crush.
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: "main"
+%%% End: 

diff --git a/retardprng.tex b/retardprng.tex
new file mode 100644 (file)
index 0000000..d6985d0
--- /dev/null
+++ b/retardprng.tex
@@ -0,0 +1,58 @@
+Nous avons  vu comment construire  un générateur de nombre  pseudo-aléatoires en
+utilisant un système  booléen en mode chaotique.  Cependant,  cela nécessite une
+contrainte forte  sur le graphe d'itérations  de la fonction  associée, qui doit
+être fortement connexe.  Nous étudions  dans cette partie une méthode permettant
+de relâcher  un peu les contraintes  sur les fonctions $f_i$  en enrichissant le
+système initial de façon à modéliser la notion de \emph{retards} entre éléments.
+
+\subsection{Les retards dans les systèmes dynamiques}
+\label{sec:retards}
+
+La notion  de retard provient  initialement du besoin  de prendre en  compte les
+délais de transfert d'information entre les éléments d'un système.  Lorsque l'on
+se place dans  le contexte général, ces délais peuvent  eux-mêmes varier dans le
+temps. On décrit donc  le retard de l'élément $j$ par rapport  à l'élément $i$ à
+l'instant $t$ par  $r_j^i(t)$. Ainsi, l'information reçue de $j$ en  $i$ à $t$ a
+été générée à  l'instant (ou itération) $s_j^i(t)=t-r_j^i(t)$. On  en déduit que
+la mise à jour de l'élément $i$ de l'instant $t$ à $t+1$ s'écrit :
+\begin{equation*}
+  x_i(t+1) = f_i(x_1^{s_1^i(t)},x_2^{s_2^i(t)},\dots,x_i^t,\dots,x_{n-1}^{s_{n-1}^i(t)},x_n^{s_n^i(t)})
+\end{equation*}
+On constate que même si le modèle le permet, on ne met généralement pas de délai
+entre l'élément $i$ et lui-même car cela n'a pas d'intérêt pratique fort.
+
+Plusieurs travaux  sur les systèmes  à retards (\cite{Mie75, Rob86,  BT89, BC02,
+  TNN2006})  ont montré que  l'une des  influences majeures  des retards  sur la
+dynamique du  système est d'augmenter  le nombre de transitions  possibles entre
+les états. En  d'autres termes, cela revient à augmenter  la connexité du graphe
+d'itérations, ce qui est justement la propriété recherchée.
+
+Cependant, une difficulté  majeure dans notre contexte de  génération de nombres
+pseudo-aléatoires  vient du  fait que  les retards  induisent une  dépendance du
+système à son  \emph{historique} plus ancien que la  seule itération précédente.
+Cela  empêche le  recours  aux chaînes  de  Markov classiques  pour établir  les
+preuves que les propriétés nécessaires à un bon générateur sont vérifiées.
+
+Afin  de  contourner  cet  obstacle,  nous  proposons  ici  une  méthode  simple
+permettant de simuler des retards dans un système booléen chaotique.
+
+\subsection{Simulation de retards dans un système booléen chaotique}
+\label{sec:simuRets}
+
+Soit un système  booléen à $n$ éléments dont la  dynamique chaotique est décrite
+par $G_f$. Nous  proposons d'étendre ce système afin  d'y incorporer des retards
+simulés.  Le  principe consiste  à ajouter un  n{\oe}ud intermédiaire au  niveau de
+chaque interaction entre deux éléments  différents (les arcs $(i,s,j)$ t.q $i\ne
+j$) du graphe d'interactions. Ainsi, si l'on considère l'arc $(i,s,j)$ du graphe
+initial,  alors cet  arc  sera remplacé  dans  le nouveau  graphe  par les  arcs
+$(i,+,k)$ et  $(k,s,j)$, avec $x_k$ un  nouvel élément booléen  du système ayant
+pour fonction  d'évolution $f_k(x)=x_i$. De  plus, les occurrences  de l'élément
+$x_i$ dans la fonction $f_j(x)$ seront  remplacées par $x_k$.  On note que l'arc
+allant de $i$ à $k$ est systématiquement positif alors que l'arc allant de $k$ à
+$j$ conserve le signe $s$ de l'ancien arc $(i,s,j)$.
+
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: "main"
+%%% End: 

diff --git a/sdd.tex b/sdd.tex
new file mode 100644 (file)
index 0000000..fc48a65
--- /dev/null
+++ b/sdd.tex
@@ -0,0 +1,299 @@
+Cette section énonce les notions fondamentales relatives aux systèmes dynamiques
+booléens  et  à la  mesure  du chaos.   Le  formalisme  des systèmes  dynamiques
+booléens est donné en section~\ref{sub:sdd}, suivi des méthodes de déduction des
+graphes     d'itérations     (section~\ref{sub:grIter}).
+%    et     d'interactions
+%(section~\ref{sub:sdd:inter}).
+% La notion de retards est présentée en
+% section~\ref{sub:sdd:retards}.
+Enfin,  une   distance  sur  l'espace   $\llbracket  1;n\rrbracket^{\Nats}\times
+\Bool^n$ est  définie en section~\ref{sub:metric}, qui  permet ensuite d'établir
+la   nature   chaotique   des   systèmes   dynamiques   booléens,   abordée   en
+section~\ref{section:caracterisation}.
+
+\subsection{Système dynamique booléen}\label{sub:sdd}
+
+Soit $n$ un entier naturel. Un système dynamique booléen est 
+défini à partir d'une fonction booléenne:
+\[
+f:\Bool^n\to\Bool^n,\qquad x=(x_1,\dots,x_n)\mapsto f(x)=(f_1(x),\dots,f_n(x)),
+\]
+et un  {\emph{schéma itératif}} ou  encore \emph{mode de  mise à jour}  qui peut
+être parallèle, séquentiel ou asynchrone%, et intégrer ou non des retards
+.  À  partir d'une configuration initiale $x^0\in\Bool^n$,  la suite $(x^{t})^{t
+  \in  \Nats}$ des  configurations  du  système est  construite  selon l'un  des
+schémas suivants :
+\begin{itemize}
+\item \textbf{Schéma parallèle  synchrone :} basé sur la  relation de récurrence
+  $x^{t+1}=f(x^t)$. Tous  les $x_i$, $1 \le  i \le n$,  sont ainsi mis à  jour à
+  chaque itération en utilisant l'état global précédent du système ($x^t$).
+\item \textbf{Schéma séquentiel synchrone :} basé sur une mise à jour successive
+  des différents éléments du système,  selon un ordre défini. Le mode séquentiel
+  de référence est basé sur la séquence ordonnée des éléments, de 1 à $n$.
+\item \textbf{Schéma  asynchrone :} cette terminologie  a plusieurs acceptations
+  dans  la littérature,  mais celle  qui  reste la  plus répandue,  et que  nous
+  retenons ici,  consiste à ne modifier  qu'un élément $i$,  $1 \le i \le  n$, à
+  chaque itération. Le choix de l'élément qui est modifié à chaque itération est
+  défini  par une  suite. Lorsque  cette  suite est  strictement cyclique  (sans
+  occurrences multiples  dans le motif) sur l'ensemble  des éléments $\{1,\ldots
+  n\}$, alors on retrouve le comportement du mode séquentiel synchrone.
+\item \textbf{Schéma chaotique:}  dans ce schéma, ce n'est  plus un seul élément
+  qui  est  modifié  à  chaque  itération,  mais  une  partie  des  éléments  de
+  $\{1,\ldots  n\}$.  Dans  le premier  cas  particulier où  c'est un  singleton
+  $\{k\}$, $1 \le k  \le n$, qui est modifié à chaque  itération, on retrouve le
+  mode asynchrone,  et si la séquence  des singletons est  ordonnée et cyclique,
+  alors on retrouve le mode séquentiel.  Dans le second cas particulier où c'est
+  $\{1, \ldots,  n\}$ qui est  modifié à chaque  itération, on retrouve  le mode
+  parallèle.  Ce mode généralise donc les trois autres modes précédents.  
+  Plus formellement,  à  la  $t^{\textrm{ème}}$
+  itération, seuls les éléments de la partie 
+  $s_{t} \in \mathcal{P}(\{1, \ldots, n\})$ sont mis à
+  jour.  La  suite $S  = \left(s_t\right)_{t \in  \mathds{N}}$ est  une séquence
+  de sous-ensembles 
+  de   $\{  1, \ldots,n   \}$   appelée   \emph{stratégie}.
+  Dans      ce      mode     opératoire,  on définit la fonction\linebreak
+  $F_f:~\mathcal{P}(\{1, \ldots, n\}) \times \Bool^{n} \rightarrow \Bool^n$  par
+  \[
+  F_f(s,x)_i=\left\{
+    \begin{array}{l}
+      f_i(x) \textrm{ si $i \in s$;}\\   
+      x_i \textrm{ sinon.}
+    \end{array}\right.
+  \]
+  Dans le schéma des itérations chaotiques, pour une configuration initiale
+  $x^0\in\Bool^n$ et une stratégie $S = \left(s_t\right)_{t \in  \mathds{N}}
+\in \mathcal{P}(\{1, \ldots, n\})^{\Nats}$,
+  les
+  configurations $x^t$ sont définies par la récurrence
+  \begin{equation}\label{eq:asyn}
+    x^{t+1}=F_f(s_t,x^t).
+  \end{equation}
+  Soit alors $G_f$ une fonction de $\mathcal{P}(\{1, \ldots, n\})^{\Nats}\times\Bool^n$ 
+  dans lui-même définie par 
+  \[
+  G_f(S,x)=(\sigma(S),F_f(s_0,x)),
+  \] 
+  où $\forall t\in\Nats,\sigma(S)_t=s_{t+1}$.
+  En d'autres termes la fonction $\sigma$ \emph{décale}
+  la stratégie fournie en argument d'un élément vers la gauche en supprimant 
+  l'élément de tête. 
+  Les itérations parallèles de $G_f$ depuis un point initial
+  $X^0=(S,x^0)$ décrivent la même orbite que les  
+  itérations chaotiques de $f$ induites par $x^0$ et la  stratégie
+  $S$.
+\end{itemize}
+
+\subsection{Graphe d'itérations chaotiques}\label{sub:grIter}
+
+Soit $f$ une fonction de $\Bool^n$ dans lui-même. 
+Le {\emph{graphe des itérations chaotiques}} associé à $f$ est le 
+graphe orienté $\Gamma(f)$ défini ainsi: 
+l'ensemble de ses sommets est $\Bool^n$ et pour chaque $x\in\Bool^n$ et  
+$s\in \mathcal{P}(\{1, \ldots, n\})$, le graphe $\Gamma(f)$ 
+contient un arc de $x$ vers $F_f(s,x)$. 
+La relation entre $\Gamma(f)$ et $G_f$ est claire: il  existe un 
+chemin  de $x$ à  $x'$ dans $\Gamma(f)$ si et seulement s'il existe une 
+stratégie  $S$ telle que les itérations  parallèles $G_f$ à partir 
+du point $(S,x)$ mènent à un point $(.,x')$.
+
+Dans ce qui suit, et par souci de concision, le terme \emph{graphe des itérations}
+est une abréviation de  graphe des itérations chaotiques.
+La figure~\ref{fig:xplgraphIter} donne deux exemples de graphes d'itérations 
+pour les fonctions $g$ et $h$ définies dans $\Bool^2$, qui sont reprises tout au long 
+de cet article. 
+
+\begin{figure}[ht]
+  \begin{center}
+    \subfloat[$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $]{
+      \begin{minipage}{0.40\textwidth}
+        \begin{center}
+          \includegraphics[width=\columnwidth]{images/g}
+        \end{center}
+      \end{minipage}
+      \label{fig:g:iter}
+    }
+    \subfloat[$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$]{
+      \begin{minipage}{0.40\textwidth}
+        \begin{center}
+          \includegraphics[width=\columnwidth]{images/h}
+        \end{center}
+      \end{minipage}
+      \label{fig:h:iter}
+    }   
+  \end{center}
+  \caption{Graphes d'itérations de fonctions booléennes dans $\Bool^2$.}
+  \label{fig:xplgraphIter}
+\end{figure}
+
+% \subsection{Graphe d'interactions}\label{sub:sdd:inter}
+
+% Pour $x\in\Bool^n$ et $i\in\llbracket 1;n\rrbracket$, on nomme  
+%  $\overline{x}^i$ la configuration obtenue en niant le 
+% $i^{\textrm{ème}}$ composant de $x$. En d'autres termes
+% $\overline{x}^i=(x_1,\dots,\overline{x_i},\dots,x_n)$.
+% Des interactions entre les composants du 
+% système peuvent être mémorisées 
+% dans la {\emph{matrice Jacobienne discrète}} $f'$.
+% Celle-ci est définie comme étant la fonction  qui  à chaque 
+% configuration $x\in\Bool^n$ associe la matrice de taille 
+% $n\times n$ définie par : 
+% \[
+% f'(x)=(f'_{ij}(x)),\qquad 
+% f'_{ij}(x)=\frac{f_i(\overline{x}^j)-f_i(x)}{\overline{x}^j_j-x_j}\qquad (i,j\in\llbracket1;n\rrbracket).
+% \]
+
+% On  note que  dans  l'équation donnant  la  valeur de  $f'_{ij}(x)$, les  termes
+% $f_i(\overline{x}^j)$,  $f_i(x)$, $\overline{x}^j_j$  et  $x_j$ sont  considérés
+% comme des entiers  naturels égaux à $0$ ou  à $1$ et que le  calcul est effectué
+% dans  $\Z$. Cela  est important  car le  signe des  $f'_{ij}(x)$ nous  donne une
+% information supplémentaire sur la dynamique du système.
+
+% En outre, les interactions peuvent se  représenter à l'aide d'un 
+% graphe $G(f)$ orienté et signé défini ainsi: 
+% l'ensemble des sommets est 
+% $\llbracket1;n\rrbracket$ et il existe un arc de $j$ à $i$ de signe
+%  $s\in\{-1,1\}$, noté $(j,s,i)$, si $f'_{ij}(x)=s$ pour au moins
+% un $x\in\Bool^n$. 
+% On note que la présence de 
+% deux arcs de signes opposés entre deux sommets donnés 
+% est possible.
+
+% \begin{figure}%[t]
+%   \begin{center}
+%     \subfloat[$g(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}) $]{
+%       \begin{minipage}{0.40\textwidth}
+%         \begin{center}
+%           \includegraphics[height=3cm]{images/gp.pdf}
+%         \end{center}
+%       \end{minipage}
+%       \label{fig:g:inter}
+%     }
+%     \subfloat[$h(x_1,x_2)=(\overline{x_1},x_1\overline{x_2}+\overline{x_1}x_2)$]{
+%       \begin{minipage}{0.40\textwidth}
+%         \begin{center}
+%           \includegraphics[height=3cm]{images/hp.pdf}
+%         \end{center}
+%       \end{minipage}
+%       \label{fig:h:inter}
+%     }    \end{center}
+%     \caption{Graphes d'interactions de fonctions booléennes dans $\Bool^2$}
+%     \label{fig:xplgraphInter}
+%   \end{figure}
+
+% Soit $P$ une suite d'arcs de $G(f)$ de la forme
+% \[
+% (i_1,s_1,i_2),(i_2,s_2,i_3),\ldots,(i_r,s_r,i_{r+1}).
+% \]
+% Alors, $P$ est dit un \emph{chemin} de $G(f)$ de longueur $r$ et de signe
+% $\Pi_{i=1}^{r}s_i$ et  $i_{r+1}$ est dit accessible depuis
+% $i_1$. 
+% $P$ est un {\emph{circuit}} si $i_{r+1}=i_1$ et si les sommets
+% $i_1$,\ldots $i_r$ sont deux à deux disjoints.
+% Un sommet $i$ de $G(f)$ a une {\emph{boucle}} 
+% positive (resp. négative) , si $G(f)$ a un 
+% arc positif (resp. un arc négatif) de $i$ vers lui-même.
+
+% \subsection{Retards entre les éléments du système}
+% \label{sub:sdd:retards}
+
+% La notion  de retard provient  initialement du besoin  de prendre en  compte les
+% délais de transfert  d'information entre les éléments du  système.  Lorsque l'on
+% se place dans  le contexte général, ces délais peuvent  eux-mêmes varier dans le
+% temps. On décrit donc  le retard de l'élément $j$ par rapport  à l'élément $i$ à
+% l'instant $t$ par  $r_j^i(t)$. Ainsi, l'information reçue de $j$ en  $i$ à $t$ a
+% été générée à  l'instant (ou itération) $s_j^i(t)=t-r_j^i(t)$. On  en déduit que
+% la mise à jour de l'élément $i$ de l'instant $t$ à $t+1$ s'écrit :
+% \begin{equation*}
+%   x_i(t+1) = f_i(x_1^{s_1^i(t)},x_2^{s_2^i(t)},\dots,x_i^t,\dots,x_{n-1}^{s_{n-1}^i(t)},x_n^{s_n^i(t)})
+% \end{equation*}
+% On constate que même si le modèle le permet, on ne met généralement pas de délai
+% entre l'élément $i$ et lui-même car cela n'a pas d'intérêt pratique fort.
+
+\subsection{Distance sur l'espace $\mathcal{P}(\{1, \ldots, n\})^{\Nats}\times \Bool^n$}\label{sub:metric}
+Pour $A$ et $B$ deux ensembles de l'univers $\Omega$,
+on rappelle la définition de l'opérateur 
+de \emph{différence ensembliste} symétrique :
+\[
+A \Delta B = (A \cap \overline{B}) \cup (\overline{A} \cap B)
+\]  
+où $\overline{B}$ désigne le complémentaire de $B$ dans $\Omega$.
+
+On considère l'espace $\mathcal{X}=\mathcal{P}(\{1, \ldots, n\})^{\Nats}\times
+\Bool^n$ et
+on définit la distance $d$ entre les points $X=(S,x)$ et
+$X'=(S',x')$ de $\mathcal{X}$ par 
+\[
+d(X,X')= d_H(x,x')+d_S(S,S'),~\textrm{où}~
+\left\{
+\begin{array}{l}
+\displaystyle{d_H(x,x')=\sum_{i=1}^n |x_i-x'_i|}\\[5mm] 
+\displaystyle{d_S(S,S')=\frac{9}{n}\sum_{t\in\Nats}\frac{|S_t \Delta S'_t|}{10^{t+1}}}.
+\end{array}
+\right.\,.
+\]
+On note que dans le calcul de $d_H(x,x')$ -- 
+appelée \gls{distanceHamming} (cf. glossaire) 
+entre $x$ et $x'$-- 
+les termes $x_i$ et $x'_i$ sont considérés comme des entiers naturels 
+égaux à $0$ ou à $1$ et que le calcul est effectué dans $\Z$.
+On note aussi que le symbole $|.|$ est utilisé avec deux sémantiques
+différentes dans ce calcul: 
+on somme des valeurs absolues dans la distance 
+de Hamming tandis que l'on somme des cardinalités d'ensemble dans 
+$d_S$. 
+De plus, la \gls{partieentiere} (cf. glossaire) 
+$\lfloor d(X,X')\rfloor$ est égale à $d_H(x,x')$ soit la distance 
+de Hamming entre $x$ et $x'$. 
+%D'autre part, $d(X,X')-\lfloor d(X,X')\rfloor=d_S(s,s')$ 
+%mesure la différence entre $s$ et $s'$.
+On remarque que la partie décimale est inférieure à $10^{-l}$ si
+et seulement si les $l$ premiers termes des deux stratégies sont égaux. 
+De plus, si la 
+$(l+1)^{\textrm{ème}}$ décimale  
+de $d_S(S,S')$ 
+n'est pas nulle, alors $s_l$ est différent de  $s'_l$. 
+
+La fonction $d$ est une somme de deux fonctions.
+La fonction $d_H$ est la distance de Hamming; il est aussi établi que la 
+somme de deux distances est une distance.
+Ainsi, pour montrer que $d$ est aussi une distance, il suffit 
+de montrer que $d_S$ en une aussi.
+
+Soit $S$, $S'$ et $S''$ trois parties de $\{1,\ldots,n\}$.
+\begin{itemize}
+\item De manière évidente, $d_s(S,S')$ est positive ou bien nulle si 
+  et seulement si $S$ et $S'$ sont égales.
+\item Comme la différence symétrique est commutative, la valeur de  
+  $d_S(S,S')$ est égale à  celle de $d_S(S',S)$.
+\item On a enfin la succession d'éléments suivants:
+  $$
+  \begin{array}{rcl}
+    S \Delta S' & = & (S \cap \overline{S'}) \cup (\overline{S} \cap S')\\
+    & = & (S \cap \overline{S'} \cap S'' ) \cup  (S \cap \overline{S'} \cap \overline{S''} ) \cup (\overline{S} \cap S'\cap S'') \cup (\overline{S} \cap S'\cap \overline{S''})\\
+    & \subseteq & (S \cap \overline{S'} \cap S'' ) \cup  (S \cap \overline{S'} \cap \overline{S''} ) \cup (\overline{S} \cap S'\cap S'') \cup (\overline{S} \cap S'\cap \overline{S''}) \cup \\
+     & & (\overline{S} \cap \overline{S'} \cap S'') \cup (S \cap S' \cap \overline{S''} ) \cup (\overline{S} \cap \overline{S'} \cap S'') \cup (S \cap S' \cap \overline{S''})\\     
+    & = & (\overline{S'} \cap S'' ) \cup  (S \cap \overline{S''} ) \cup (\overline{S} \cap S'') \cup (S'\cap \overline{S''}) \\
+    & = & (S \Delta S'') \cup (S'' \Delta S')   
+  \end{array}
+  $$
+  On en déduit ainsi que 
+$|S \Delta S'| \le |S \Delta S''| + |S'' \Delta S'|$ et donc que 
+l'égalité triangulaire $d_S(S,S') \le d_S(S,S'') + d_S(S'',S')$ est établie.
+\end{itemize}
+
+On peut démontrer que pour toute fonction booléenne $f$, 
+$G_f$ est continue sur $\mathcal{X}$ (cf.~annexe~\ref{anx:cont}).   
+
+\subsection{Temps de mélange}
+\label{sec:mixingtime}
+
+Le  temps de mélange  (\emph{mixing time})~\cite{LevinPeresWilmer2006},  est une
+des métriques usuelles  pour estimer la vitesse de  convergence des lignes d'une
+matrice de  Markov vers  une distribution spécifique.   Elle est définie  par le
+nombre minimal d'itérations nécessaires  pour obtenir une déviation inférieure à
+un $\varepsilon$ donné pour chaque ligne de la matrice.
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: "main"
+%%% End: