arête sortante et une arête entrante.
-This aim of this section is to show
-that finding DSSC matrices from a hypercube
-is a typical finite domain satisfaction
-problem, classically denoted as
-Constraint Logic Programming on Finite Domains (CLPFD).
-This part is addressed in the first section. Next, we analyse the first
-results to provide a generation of DSSC matrices with small mixing times.
-
-\section{Programmation logique par contraintes sur des domaines finis}
+% This aim of this section is to show
+% that finding DSSC matrices from a hypercube
+% is a typical finite domain satisfaction
+% problem, classically denoted as
+% Constraint Logic Programming on Finite Domains (CLPFD).
+% This part is addressed in the first section. Next, we analyse the first
+% results to provide a generation of DSSC matrices with small mixing times.
+
+\section{Programmation logique par contraintes sur des domaines finis}\label{sec:plc}
Tout d'abord, soit ${\mathsf{N}}$ le nombre d'éléments.
-Pour éviter d'avoir à gérér des fractions, on peut considérer que
+Pour éviter d'avoir à gérer des fractions, on peut considérer que
les matrices (d'incidence) à générer ont des lignes et des colonnes dont les
sommes valent ${\mathsf{N}}$ à chaque fois.
On cherche ainsi toutes les matrices $M$ de taille $2^{\mathsf{N}}\times 2^{\mathsf{N}}$ telles que
\item pour $j \neq i$, $0 \le M_{ij} \le 1$: on construit l'arc de $i$ à $j$
si et seulement si $M_{ij}$ vaut 1 (et 0 sinon)
-\item pour chque indice de ligne $i$, $1 \le i\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le j\le 2^{\mathsf{N}}} M_{ij}$:
+\item pour chaque indice de ligne $i$, $1 \le i\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le j\le 2^{\mathsf{N}}} M_{ij}$:
la matrice est stochastique à droite;
-\item pour chque indice de colonne $j$,
+\item pour chaque indice de colonne $j$,
$1 \le j\le 2^{\mathsf{N}}$, ${\mathsf{N}} = \sum_{1 \le i\le 2^{\mathsf{N}}} M_{ij}$:
la matrice est stochastique à gauche;
\item Toutes les éléments de la somme $\sum_{1\le k\le 2^{\mathsf{N}}}M^k$ sont strictement positif, \textit{i.e.}, le graphe $\textsc{giu}(f)$ est fortement connexe;
\end{enumerate}
Ce problème s'exprime sur des domaines finis entiers avec des opérateurs
-arithmétiques simples (sommes et poduits). il pourrait théoriquement être
-traité par desdémarches de programation logique par contrainte
+arithmétiques simples (sommes et produits). il pourrait théoriquement être
+traité par des démarches de programmation logique par contrainte
sur des domaines finis (comme en PROLOG).
L'algorithme donné en Figure~\ref{fig:prolog}
est en effet le c{\oe}ur du programme PROLOG
\caption{Code PROLOG permettant de trouver toutes les matrices DSSC pour $n=2$}\label{fig:prolog}
\end{figure}
-Enfin, on définit la relation $\mathcal{R}$, qui est établie pourles deux
+Enfin, on définit la relation $\mathcal{R}$, qui est établie pour les deux
fonctions $f$ et $g$ si leur graphes
respectifs $\textsf{giu}(f)$ et $\textsf{giu}(g)$
sont isomorphes.
-\subsection{Analyse de l'approche}
+%\subsection{Analyse de l'approche}\label{sub:prng:ana}
Exécutée sur un ordinateur personnelle, PROLOG trouve
en moins d'une seconde les
49 solutions pour $n=2$,
pour $n=4$.
Cette approche, basée sur une démarche de type \emph{générer, tester} ne peut
pas être retenue pour $n$ de grande taille, même
-en s'appuyant sur l'éfficience de l'algorithme de backtrack natif de PROLOG.
+en s'appuyant sur l'efficience de l'algorithme de backtrack natif de PROLOG.
Cependant, pour des valeurs de $n$ petites, nous avons
-comparé les fonctions non équivalantes selon leur proportion
+comparé les fonctions non équivalentes selon leur proportion
à engendrer des temps de mélange petits (cf. équation~\ref{eq:mt:ex}).
-\begin{xpl}
+\begin{xpl}\label{xpl:mixing:3}
Le tableau~\ref{table:mixing:3} fournit les 5 fonctions booléennes
qui ont les temps de mélange les plus petits pour $\varepsilon=10^{-5}$.
\begin{table}[ht]
\hline
f^a & (x_2 \oplus x_3, x_1 \oplus \overline{x_3},\overline{x_3}) & 16 \\
\hline
-f^* & (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) & 17 \\
+f^* & (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) & 17 \\
\hline
-f^b & (\overline{x_1}(x_2+x_3) + x_2x_3,\overline{x_1}(\overline{x_2}+\overline{x_3}) + \overline{x_2}\overline{x_3}, & \\
+f^b & (\overline{x_1}(x_2+x_3) + x_2x_3,\overline{x_1}(\overline{x_2}+\overline{x_3}) + \overline{x_2}.\overline{x_3}, & \\
& \qquad \overline{x_3}(\overline{x_1}+x_2) + \overline{x_1}x_2) & 26 \\
\hline
-f^c & (\overline{x_1}(x_2+x_3) + x_2x_3,\overline{x_1}(\overline{x_2}+\overline{x_3}) + \overline{x_2}\overline{x_3}, & \\
+f^c & (\overline{x_1}(x_2+x_3) + x_2x_3,\overline{x_1}(\overline{x_2}+\overline{x_3}) + \overline{x_2}.\overline{x_3}, & \\
& \overline{x_3}(\overline{x_1}+x_2) + \overline{x_1}x_2) & 29 \\
\hline
f^d & (x_1\oplus x_2,x_3(\overline{x_1}+\overline{x_2}),\overline{x_3}) & 30 \\
\begin{minipage}{0.35\linewidth}
\begin{scriptsize}
\begin{center}
- $ \dfrac{1}{4} \left(
- \begin{array}{cccccccc}
- 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
+
+\[
+M=\dfrac{1}{3} \left(
+\begin{array}{llllllll}
+1&1&1&0&0&0&0&0 \\
+1&1&0&0&0&1&0&0 \\
+0&0&1&1&0&0&1&0 \\
+0&1&1&1&0&0&0&0 \\
+1&0&0&0&1&0&1&0 \\
+0&0&0&0&1&1&0&1 \\
+0&0&0&0&1&0&1&1 \\
+0&0&0&1&0&1&0&1
+\end{array}
+\right)
+\]
+
+
+
+ % $ \dfrac{1}{4} \left(
+ % \begin{array}{cccccccc}
+ % 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
- 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
+ % 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
- 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
+ % 0 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
- 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
+ % 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 \\
- 1 & 0 & 1 & 0 & 1 & 0 & 1 & 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 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
+ % 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
- 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
+ % 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 \\
- \end{array} \right) $
+ % \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}
+ (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}
-\section{Graphes
- $\textsc{giu}(f)$
- $\textsc{gig}(f)$
- fortement connexes et doublement stochastiques}
-% Secrypt 14
+% section{Graphes
+% $\textsc{giu}(f)$
+% $\textsc{gig}(f)$
+% fortement connexes et doublement stochastiques}\label{sec:gen:dblstc}
+% %
+%Secrypt 14
-\subsection{Suppression des cycles hamiltoniens}
+\section{Suppression des cycles hamiltoniens}
\label{sec:hamiltonian}
-Dans un premier temps, nous montrons en section~\ref{sub:removing:theory} que la
+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}
+%\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
-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
+%Les preuves, relativement directes, sont laissées en exercices au lecteur.
+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}
+\section{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
ce code est totalement équilibré.
\end{xpl}
-\subsection{Génération de codes de Gray équilibrés par induction}
+\section{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
Ces fonctions étant générée, on s'intéresse à étudier à quelle vitesse
un générateur les embarquant converge vers la distribution uniforme.
-C'est l'objeftif de la section suivante.
+C'est l'objectif de la section suivante.
\section{Quantifier l'écart par rapport à la distribution uniforme}
On considère ici une fonction construite comme à la section précédente.
On s'intéresse ici à étudier de manière théorique les
-itérations définies à l'equation~(\ref{eq:asyn}) pour une
+itérations définies à l'équation~(\ref{eq:asyn}) pour une
stratégie donnée.
-Tout d'abord, celles-ci peuvent être inerprétées comme une marche le long d'un
+Tout d'abord, celles-ci peuvent être interprétées comme une marche le long d'un
graphe d'itérations $\textsc{giu}(f)$ tel que le choix de tel ou tel arc est donné par la
stratégie.
-On remaque que ce graphe d'itération est toujours un sous graphe
+On remarque que ce graphe d'itération est toujours un sous graphe
du ${\mathsf{N}}$-cube augmenté des
boucles sur chaque sommet, \textit{i.e.}, les arcs
$(v,v)$ pour chaque $v \in \Bool^{\mathsf{N}}$.
Pour une référence
générale à ce sujet on pourra se référer
au livre~\cite{LevinPeresWilmer2006},
-particulièrementau chapitre sur les temps d'arrêt.
+particulièrement au chapitre sur les temps d'arrêt.
\end{array}
\right.
$$
-La matrice $P$ de la chaine de Markov associée à $f^*$
+La matrice $P$ de la chaîne de Markov associée à $f^*$
est
\[
P=\dfrac{1}{6} \left(
$\nu$ est une distribution on $\Bool^{\mathsf{N}}$, on a
$$\tv{\pi-\mu}\leq \tv{\pi-\nu}+\tv{\nu-\mu}.$$
-Soit $P$ une matrice d'une chaîne de Markovs sur $\Bool^{\mathsf{N}}$.
+Soit $P$ une matrice d'une chaîne de Markov sur $\Bool^{\mathsf{N}}$.
$P(X,\cdot)$ est la distribution induite par la $X^{\textrm{ème}}$ colonne
de $P$.
Si la chaîne de Markov induite par
Un \emph{temps d'arrêt aléatoire} pour la chaîne de
Markov est un temps d'arrêt pour
$(Z_t)_{t\in\mathbb{N}}$.
-Si la chaîne de Markov est irreductible et a $\pi$
+Si la chaîne de Markov est irréductible et a $\pi$
comme distribution stationnaire, alors un
\emph{temps stationnaire} $\tau$ est temps d'arrêt aléatoire
(qui peut dépendre de la configuration initiale $X$),
$E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$.
\end{theorem}
-Sans entrer dans les détails de la preuve, on remarque que le calcul
-de cette borne ne tient pas en compte le fait qu'on préfère enlever des
+Sans entrer dans les détails de la preuve, on remarque tout d'abord
+que le calcul
+de cette borne n'intègre pas le fait qu'on préfère enlever des
chemins hamiltoniens équilibrés.
-En intégrant cette contrainte, la borne supérieure pourraît être réduite.
+En intégrant cette contrainte, la borne supérieure pourrait être réduite.
+
+On remarque ensuite que la chaîne de Markov proposée ne suit pas exactement
+l'algorithme~\ref{CI Algorithm}. En effet dans la section présente,
+la probabilité de rester dans une configuration donnée
+est fixée à $frac{1}{2}+\frac{1}{2n}$.
+Dans l'algorithme initial, celle-ci est de ${1}{n}$.
+Cette version, qui reste davantage sur place que l'algorithme original,
+a été introduite pour simplifier le calcul de la borne sup
+du temps d'arrêt.
+
+
+
+
+\section{Et les itérations généralisées?}
+Le chaptire précédent a présenté un algorithme de
+PRNG construit à partir d'itérations unaires.
+On pourrait penser que cet algorithme est peu efficace puisqu'il
+dispose d'une fonction $f$ de $\Bool^n$ dans lui même mais il ne modifie à
+chaque itération qu'un seul élément de $[n]$.
+On pourrait penser à un algorithme basé sur les itérations généralisées,
+c'est-à-dire qui modifierait une partie des éléments de $[n]$ à chaque
+itération.
+C'est l'algorithme~\ref{CI Algorithm:prng:g} donné ci-après.
+
+\begin{algorithm}[ht]
+%\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 $\;
+\For{$i=1,\dots,k$}
+{
+$s\leftarrow{\textit{Set}(\textit{Random}(2^n))}$\;
+$x\leftarrow{F_{f_g}(s,x)}$\;
+}
+return $x$\;
+%\end{scriptsize}
+\caption{PRNG basé sur les itérations généralisées.}
+\label{CI Algorithm:prng:g}
+\end{algorithm}
+
+Par rapport à l'algorithme~\ref{CI Algorithm} seule
+la ligne $s\leftarrow{\textit{Set}(\textit{Random}(2^n))}$ est différente.
+Dans celle-ci la fonction $\textit{Set} : \{1,\ldots,2^n\} \rightarrow
+\mathcal{P}(\{1,\ldots n\})$ retourne l'ensemble dont la fonction
+caractéristique serait représentée par le nombre donné en argument.
+Par exemple, pour $n=3$, l'ensemble $\textit{Set}(6)$ vaudraitt $\{3,2\}$.
+On remarque aussi que l'argument de la fonction $\textit{Random}$
+passe de $n$ à $2^n$.
+
+On a le théorème suivant qui étend le théorème~\ref{thm:prng:u} aux itérations
+généralisées.
+
+\begin{theorem}\label{thm:prng:g}
+ Soit $f: \Bool^{n} \rightarrow \Bool^{n}$, $\textsc{gig}(f)$ son
+ graphe des itérations généralisées, $\check{M}$ la matrice d'adjacence
+ correspondante à ce graphe
+ et $M$ une matrice $2^n\times 2^n$
+ définie par
+ $M = \dfrac{1}{2^n} \check{M}$.
+ Si $\textsc{gig}(f)$ est fortement connexe, alors
+ la sortie du générateur de nombres pseudo aléatoires détaillé par
+ l'algorithme~\ref{CI Algorithm:prng:g} suit une loi qui
+ tend vers la distribution uniforme si
+ et seulement si $M$ est une matrice doublement stochastique.
+\end{theorem}
+
+La preuve de ce théorème est la même que celle du théorème~\ref{thm:prng:u}.
+Elle n'est donc pas rappelée.
+
+\begin{xpl}
+
+ On reprend l'exemple donné à la section~\ref{sec:plc}.
+ Dans le $3$-cube, le cycle hamiltonien défini par la séquence
+ $000,100,101,001,011,111,110,010,000$ a été supprimé engendrant
+ 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 $\textsc{gig}(f^*)$ est représenté à la
+Figure~\ref{fig:iteration:f*}.
+La matrice de Markov $M$ correspondante est donnée à
+la figure~\ref{fig:markov:f*}.
+
+\begin{figure}[ht]
+ \begin{center}
+ \subfigure[Graphe $\textsc{gig}(f^*)$
+ \label{fig:iteration:f*}]{
+ \begin{minipage}{0.55\linewidth}
+ \centering
+ \includegraphics[width=\columnwidth]{images/iter_f}%
+ \end{minipage}
+ }%
+ \subfigure[Matrice de Markov associée au $\textsc{gig}(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}
+
+
+
+\begin{table}[ht]
+ \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] & 17 & 38 \\
+ \hline
+ $f^{*5}$ & [29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, & 13 & 48 \\
+ & 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, & 11 & 55 \\
+ & 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, & 10 & 63 \\
+ & 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,& 9 & 72 \\
+ & 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}
+\label{table:functions}
+\caption{Fonctions avec matrices DSCC et le plus faible temps de mélange.}
+
+\end{table}
+
+Le tableau~\ref{table:functions} reprend une synthèse de
+fonctions qui ont été générées selon la méthode détaillée
+à la section~\ref{sec:hamiltonian}.
+Pour chaque nombre $n=3$, $4$, $5$ et $6$,
+tous les cycles hamiltoniens non isomorphes ont été générés. Pour les
+valeur de $n=7$ et $8$, seules $10^{5}$ cycles ont été évalués. 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 (\textit{i.e.}, ce temps de mélange)
+est stocké dans la troisième
+colonne sous la variable $b$.
+La variable $b'$ reprend le temps de mélange pour
+l'algorithme~\ref{CI Algorithm}.
+
+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 décroit avec
+le nombre d'éléments alors qu'il augmente dans l'approche initiale où
+l'on marche.
+
+Cela s'explique assez simplement. Depuis une configuration initiale, le nombre
+de configurations qu'on ne peut pas atteindre en une itération est de:
+\begin{itemize}
+\item $2^n-n$ en unaire. Ceci représente un rapport de
+ $\dfrac{2^n-n}{2^n} = 1-\dfrac{n}{2^n}$
+ de toutes les configurations; plus $n$ est grand,
+ plus ce nombre est proche de $1$, et plus grand devient le nombre
+ d'itérations nécessaires pour atteinte une déviation faible;
+\item $2^n-2^{n-1}$ dans le cas généralisé,
+ soit la moitié de toutes les configurations
+ quel que soit $n$; seul 1 bit reste constant tandis que tous les autres peuvent changer. Plus $n$ grandit, plus la proportion de bits constants diminue.
+\end{itemize}
+
+Cependant, dans le cas généralisé, chaque itération a une complexité
+plus élevée puisqu'il est nécessaire d'invoquer un générateur
+produisant un nombre pseudo-aléatoire dans $[2^{n}]$ tandis qu'il suffit
+que celui-ci soit dans $[n]$ dans le cas unaire.
+Pour comparer les deux approches,
+on considère que le générateur aléatoire embarqué est binaire, \textit{i.e.} ne génère qu'un bit (0 ou 1).
+
+Dans le cas généralisé, si l'on effectue $b$ itérations,
+à chacune d'elles, la stratégie génère un nombre entre
+$1$ et $2^n$. Elle fait donc $n$ appels à ce générateur.
+On fait donc au total $b*n$ appels pour $n$ bits et
+donc $b$ appels pour 1 bit généré en moyenne.
+Dans le cas unaire, si l'on effectue $b'$ itérations,
+à chacune d'elle, la stratégie génère un nombre entre
+$1$ et $n$.
+Elle fait donc $\ln(n)/\ln(2)$ appels à ce générateur binaire en moyenne.
+La démarche fait donc au total $b'*\ln(n)/\ln(2)$ appels pour $n$ bits et
+donc $b'*\ln(n)/(n*\ln(2))$ appels pour 1 bit généré en moyenne.
+Le tableau~\ref{table:marchevssaute} donne des instances de
+ces valeurs pour $n \in\{4,5,6,7,8\}$ et les fonctions
+données au tableau~\ref{table:functions}.
+On constate que le nombre d'appels par bit généré décroit avec $n$ dans le
+cas des itérations généralisées et est toujours plus faible
+que celui des itérations unaires.
+
+
+
+\begin{table}[ht]
+$$
+\begin{array}{|l|l|l|l|l|l|}
+\hline
+\textrm{Itérations} & 4 & 5 & 6 & 7 & 8 \\
+\hline
+\textrm{Unaires} & 19.0 & 22.2905097109 & 23.6954895899 & 25.2661942985 & 27.0\\
+\hline
+\textrm{Généralisées} & 17 & 13 & 11 & 10 & 9\\
+\hline
+\end{array}
+$$
+\caption{Nombre moyen
+ d'appels à un générateurs binaire par bit généré}\label{table:marchevssaute}
+\end{table}
+
+
+
+
+\section{Tests statistiques}
+
+La qualité des séquences aléatoires produites par
+le générateur des itérations unaires ainsi que
+celles issues des itérations généralisées a été évaluée à travers la suite
+de tests statistiques développée 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
+ ces 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}[ht]
+ \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}
+
+\label{fig:TEST}
+\caption{Test de NIST réalisé sur les fonctions $f^*$ détaillées au tableau~\label{table:functions}}
+\end{table}
+
+%
