% 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}
+\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érer des fractions, on peut considérer que
les matrices (d'incidence) à générer ont des lignes et des colonnes dont les
-\subsection{Analyse de l'approche}\label{sub:prng:ana}
+%\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$,
-\section{Graphes
- $\textsc{giu}(f)$
- $\textsc{gig}(f)$
- fortement connexes et doublement stochastiques}\label{sec:gen:dblstc}
-% 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
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
-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.
+De nombreuses approches ont été developpées pour résoudre le problème de construire
+un code de Gray dans un $\mathsf{N}$-cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04},
+selon les propriétés que doit vérifier ce code.
+
+Dans les travaux~\cite{Robinson:1981:CS}, les auteurs
+proposent une approche inductive de construction de code de Gray équilibrés
+(on passe du $\mathsf{N}-2$ à $\mathsf{N}$)
+pour peu que l'utilisateur fournisse une sous-séquence possédant certaines
+propriétés à chaque pas inductif.
+Ce travail a été renforcé dans ~\cite{DBLP:journals/combinatorics/BhatS96}
+où les auteurs donnent une manière explicite de construire une telle sous-séquence.
+Enfin, les autheurs de~\cite{ZanSup04} présentent une extension de l'algorithme de
+\emph{Robinson-Cohn}. La présentation rigoureuse de cette extension leur permet
+principalement de prouver que si $\mathsf{N}$ est une puissance de 2,
+le code de Gray équilibré engendré par l'extension est toujours totalement équilibré et
+que $S_{\mathsf{N}}$ est la séquence de transition d'un code de Gray de $\mathsf{N}$ bits
+si $S_{\mathsf{N}-2}$ l'est aussi..
+Cependant les auteurs ne prouvent pas que leur approche fournit systématiquement
+un code de Gray (totalement) équilibré.
+Cette section montre que ceci est vrai en rappelant tout d'abord
+l'extension de l'algorithme de \emph{Robinson-Cohn} pour un
+code de Gray avec $\mathsf{N}-2$ bits.
-\begin{table}[ht]
- \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}
-\caption{Nombre de codes de Gray équilibrés selon le nombre de bits.}\label{table:nbFunc}
-\end{table}
+\begin{enumerate}
+\item \label{item:nondet}Soit $l$ un entier positif pair. Trouver des sous-sequences
+$u_1, u_2, \dots , u_{l-2}, v$ (possiblement vides) de $S_{\mathsf{N}-2}$
+telles que $S_{\mathsf{N}-2}$ est la concaténation de
+$$
+s_{i_1}, u_0, s_{i_2}, u_1, s_{i_3}, u_2, \dots , s_{i_l-1}, u_{l-2}, s_{i_l}, v
+$$
+où $i_1 = 1$, $i_2 = 2$, et $u_0 = \emptyset$ (la séquence vide).
+\item\label{item:u'} Remplacer dans $S_{\mathsf{N}-2}$ les sequences $u_0, u_1, u_2, \ldots, u_{l-2}$
+ par
+ $\mathsf{N} - 1, u'(u_1,\mathsf{N} - 1, \mathsf{N}) , u'(u_2,\mathsf{N}, \mathsf{N} - 1), u'(u_3,\mathsf{N} - 1,\mathsf{N}), \dots, u'(u_{l-2},\mathsf{N}, \mathsf{N} - 1)$
+ respectivement, où $u'(u,x,y)$ est la séquence $u,x,u^R,y,u$ telle que
+ $u^R$ est $u$, mais dans l'ordre inverse. La séquence obtenue est ensuite notée $U$.
+\item\label{item:VW} Contruire les séquences $V=v^R,\mathsf{N},v$, $W=\mathsf{N}-1,S_{\mathsf{N}-2},\mathsf{N}$. Soit alors $W'$ définie commé étant égale à $W$ sauf pour les
+deux premiers éléments qui ont été intervertis.
+\item La séquence de transition $S_{\mathsf{N}}$ est la concatenation $U^R, V, W'$.
+\end{enumerate}
+
+L'étape~(\ref{item:nondet}) n'est pas constructive: il n'est pas précisé
+comment sélectionner des sous-séquences qui assurent que le code obtenu est équilibré.
+La théoreme suivante montre que c'est possible et sa preuve explique comment le faire.
+
+
+\begin{theorem}\label{prop:balanced}
+Soit $\mathsf{N}$ dans $\Nats^*$, et $a_{\mathsf{N}}$ défini par
+$a_{\mathsf{N}}= 2 \left\lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \right\rfloor$.
+il existe une séquence $l$ dans l'étape~(\ref{item:nondet}) de l'extension
+de l'algorithme de \emph{Robinson-Cohn} extension telle que
+le nombres de transitions $\textit{TC}_{\mathsf{N}}(i)$
+sont tous $a_{\mathsf{N}}$ ou $a_{\mathsf{N}}+2$
+pour chaque $i$, $1 \le i \le \mathsf{N}$.
+\end{theorem}
+La preuve de ce théorème est donnée en annexes~\ref{anx:generateur}.
-Ces fonctions étant générée, on s'intéresse à étudier à quelle vitesse
+Ces fonctions étant générées, on s'intéresse à étudier à quelle vitesse
un générateur les embarquant converge vers la distribution uniforme.
C'est l'objectif de la section suivante.
\P_X(\tau > t)$.
\end{theorem}
+
+Soit alors $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ la fonction
+telle que pour $X \in \Bool^{\mathsf{N}} $,
+$(X,\ov{h}(X)) \in E$ et $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$.
+La fonction $\ov{h}$ est dite {\it anti-involutive} si pour tout $X\in \Bool^{\mathsf{N}}$,
+$\ov{h}(\ov{h}(X))\neq X$.
+
+
\begin{theorem} \label{prop:stop}
-If $\ov{h}$ is bijective et telle que if for every $X\in \Bool^{\mathsf{N}}$,
+Si $\ov{h}$ is bijective et anti involutive
$\ov{h}(\ov{h}(X))\neq X$, alors
$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 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 pourrait être réduite.
-
-On remarque ensuite que la chaîne de Markov proposée ne suit pas exactement
+Les détails de la preuve sont donnés en annexes~\ref{anx:generateur}.
+On remarque tout d'abord 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}$.
du temps d'arrêt.
+Sans entrer dans les détails de la preuve, on remarque aussi
+que le calcul de cette borne impose uniquement que
+pour chaque n{\oe}ud du $\mathsf{N}$-cube
+un arc entrant et un arc sortant sont supprimés.
+Le fait qu'on enlève un cycle hamiltonien et que ce dernier
+soit équilibré n'est pas pris en compte.
+En intégrant cette contrainte, la borne supérieure pourrait être réduite.
+
+En effet, le temps de mixage est en $\Theta(N\ln N)$ lors d'une
+marche aléatoire classique paresseuse dans le $\mathsf{N}$-cube.
+On peut ainsi conjecturer que cet ordre de grandeur reste le même
+dans le contexte du $\mathsf{N}$-cube privé d'un chemin hamiltonien.
+
+On peut évaluer ceci pratiquement: pour une fonction
+$f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ et une graine initiale
+$x^0$, le code donné à l'algorithme algorithm~\ref{algo:stop} retourne le
+nombre d'itérations suffisant tel que tous les éléments $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ sont équitables. Il permet de déduire une approximation de $E[\ts]$
+en l'instanciant un grand nombre de fois: pour chaque nombre $\mathsf{N}$,
+$ 3 \le \mathsf{N} \le 16$, 10 fonctionss ont été générées comme dans
+ce chapitre. Pour chacune d'elle, le calcul d'une approximation de $E[\ts]$
+est exécuté 10000 fois avec une graine aléatoire.La Figure~\ref{fig:stopping:moy}
+résume ces resultats. Dans celle-ci, un cercle représente une approximation de
+$E[\ts]$ pour un $\mathsf{N}$ donné tandis que la courbe est une représentation de
+la fonction $x \mapsto 2x\ln(2x+8)$.
+On cosntate que l'approximation de $E[\ts]$ est largement inférieure
+à la borne quadratique donnée au thérème~\ref{prop:stop} et que la conjecture
+donnée au paragraphe précédent est sensée.
+
+
+\begin{algorithm}[ht]
+%\begin{scriptsize}
+\KwIn{a function $f$, an initial configuration $x^0$ ($\mathsf{N}$ bits)}
+\KwOut{a number of iterations $\textit{nbit}$}
+
+$\textit{nbit} \leftarrow 0$\;
+$x\leftarrow x^0$\;
+$\textit{fair}\leftarrow\emptyset$\;
+\While{$\left\vert{\textit{fair}}\right\vert < \mathsf{N} $}
+{
+ $ s \leftarrow \textit{Random}(\mathsf{N})$ \;
+ $\textit{image} \leftarrow f(x) $\;
+ \If{$\textit{Random}(1) \neq 0$ and $x[s] \neq \textit{image}[s]$}{
+ $\textit{fair} \leftarrow \textit{fair} \cup \{s\}$\;
+ $x[s] \leftarrow \textit{image}[s]$\;
+ }
+ $\textit{nbit} \leftarrow \textit{nbit}+1$\;
+}
+\Return{$\textit{nbit}$}\;
+%\end{scriptsize}
+\caption{Pseudo Code of stoping time calculus }
+\label{algo:stop}
+\end{algorithm}
+
+
+\begin{figure}
+\centering
+\includegraphics[width=0.49\textwidth]{images/complexityET}
+\caption{Average Stopping Time Approximation}\label{fig:stopping:moy}
+\end{figure}
+
+
\section{Et les itérations généralisées?}
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}.
+C'est l'algorithme~\ref{CI Algorithm:prng:g} donné ci-après.
-\begin{algorithm}[h]
+\begin{algorithm}[ht]
%\begin{scriptsize}
\KwIn{une fonction $f$, un nombre d'itérations $b$,
une configuration initiale $x^0$ ($n$ bits)}
correspondante à ce graphe
et $M$ une matrice $2^n\times 2^n$
définie par
- $M = \dfrac{1}{n} \check{M}$.
+ $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} suit une loi qui
+ 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}
\begin{xpl}
- On reprend l'exemple donné à la section~\ref{sub:prng:ana}:
- Dans le $3$-cube cycle hamiltonien défini par la séquence
+ 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)=
\begin{figure}[ht]
\begin{center}
- \subfigure[Graphe des itérations chaotiques de $f^*$.
+ \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 du graphe d'itérations chaotiques de
- $f^*$\label{fig:markov:f*}]{%
+ \subfigure[Matrice de Markov associée au $\textsc{gig}(f^*)$
+ \label{fig:markov:f*}]{%
\begin{minipage}{0.35\linewidth}
\begin{scriptsize}
\begin{center}
\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}
\end{xpl}
-\begin{table}[table:functions]{Fonctions avec matrices DSCC et le plus faible temps de mélange.}
+\begin{table}[ht]
\begin{center}
\begin{scriptsize}
- \begin{tabular}{|c|l|c|c|}
+ \begin{tabular}{|c|c|l|c|c|}
\hline
- fonction & $f(x)$, $f(x)$ pour $x \in [0,1,2,\hdots,2^n-1]$ & $b$ & $b'$ \\
+ $n$ & 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 \\
+ 4 & $f^{*4}$ & [13,10,9,14,3,11,1,12,15,4,7,5,2,6,0,8] & \textbf{17} & \textbf{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] & & \\
+ \multirow{4}{0.5cm}{5}& $f^{*5}$ & [29, 22, 25, 30, 19, 27, 24, 16, 21, 6, 5, 28, 23, 26, 1, & \textbf{13} & 48 \\
+ & & 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 7, 20, 11, 18, 0, 4] & & \\
+ \cline{2-5}
+ & $g^{*5}$ & [29, 22, 21, 30, 19, 27, 24, 28, 7, 20, 5, 4, 23, 26, 25, & 15 & \textbf{47} \\
+ & & 17, 31, 12, 15, 8, 10, 14, 13, 9, 3, 2, 1, 6, 11, 18, 0, 16
+ & & \\
+
\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] & & \\
+ \multirow{8}{0.5cm}{6}& $f^{*6}$ &
+ [55, 60, 45, 56, 58, 42, 61, 40, 53, 50, 52, 54, 59, 34, 33, & \multirow{4}{0.5cm}{\textbf{11}}& \multirow{4}{0.5cm}{55}\\
+& & 49, 39, 62, 47, 46, 11, 43, 57, 8, 37, 6, 36, 4, 51, 38, 1, & & \\
+& & 48, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, & & \\
+& & 16, 24, 13, 12, 29, 44, 10, 14, 41, 0, 15, 2, 7, 5, 35, 3, 9, 32] & &\\
+ \cline{2-5}
+&$g^{*6}$ & [55, 60, 45, 44, 43, 62, 61, 48, 53, 50, 52, 36, 59, 51, 33, & \multirow{4}{0.5cm}{12}& \multirow{4}{0.5cm}{\textbf{54}}\\
+ & & 49, 15, 14, 47, 46, 35, 58, 57, 56, 7, 54, 39, 37, 3, 38, 1, & & \\
+ & & 40, 63, 26, 25, 30, 19, 27, 17, 28, 31, 20, 23, 21, 18, 22, & & \\
+ & & 16, 24, 13, 12, 29, 8, 10, 42, 41, 0, 5, 2, 4, 6, 11, 34, 9, 32] & & \\
+ \hline
+ \multirow{9}{0.5cm}{7} &$f^{*7}$ & [111, 94, 93, 116, 122, 114, 125, 88, 115, 126, 85, 84, 123, & \multirow{9}{0.5cm}{\textbf{10}} & \multirow{9}{0.5cm}{\textbf{63}} \\
+ & & 98, 81, 120, 109, 78, 105, 110, 99, 107, 104, 108, 101, 118, & & \\
+ & & 117, 96, 103, 66, 113, 64, 79, 86, 95, 124, 83, 91, 121, 24, & & \\
+ & & 119, 22, 69, 20, 87, 18, 17, 112, 77, 76, 73, 12, 74, 106, 72, & & \\
+ & & 8, 7, 102, 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, 90, 89, 25, 19, 30, 23, 4, 27, 2, 16, 80, 31, 10, 15, 14, & & \\
+ & & 3, 11, 13, 9, 5, 70, 21, 68, 67, 6, 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]&&\\
+ \multirow{20}{0.5cm}{8} & $f^{*8}$ &
+[223, 190, 249, 254, 187, 251, 233, 232, 183, 230, 247, 180,&
+\multirow{20}{0.5cm}{9}&
+\multirow{20}{0.5cm}{71}\\
+& & 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, 12, 11, 142, 129, 128, 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, 136, 39, 134, 133, 5, 131,& & \\
+& & 34, 9, 8]&&\\
\hline
\end{tabular}
\end{scriptsize}
\end{center}
+\caption{Fonctions avec matrices DSCC et le plus faible temps de mélange}\label{table:functions}
\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:gen:dblstc}.
-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
+à 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}$.
+$\epsilon$ fixée à $10^{-8}$ et pour un mode donné.
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
+l'algorithme~\ref{CI Algorithm}.
+On note que pour un nombre $n$ de bits fixé et un mode donné d'itérations,
+il peut avoir plusieurs fonctions minimisant ce temps de mélange. De plus, comme ce temps
+de mélange est construit à partir de la matrice de Markov et que celle-ci dépend
+du mode, une fonction peut être optimale pour un mode et ne pas l'être pour l'autre
+(c.f. pour $n=5$).
+
+Un second 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
+de configurations qu'on ne peut pas atteindre en une itération est de:
\begin{itemize}
-\item $2^n-n$ en marchant, ce qui représente $\dfrac{2^n-n}{2^n} = 1-\dfrac{n}{2^n}$
+\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 suffisantes pour atteinte une déviation faible;
-\item $2^n-2^{n-1}$ en sautant, soit la moitié de toutes les configurations
+ 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 où l'on saute, chaque itération a une complexité
-plus élevée puisqu'il est nécessaire d'invoquer un générateur
-de nombres pseudo-aléatoires entre 1 et $2^{n}$ tandis qu'il suffit
-d'avoir un générateur entre 1 et $n$ dans le premier cas.
+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).
-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).
-
-Lorsqu'on marche et qu'on effectue $i$ itérations,
-à chaque itération, la stratégie génère un nombre entre
-$1$ et $n$.
-Elle fait donc $\ln(n)/\ln(2)$ appels à ce générateur en moyenne.
-La démarche fait donc au total $i*\ln(n)/\ln(2)$ appels pour $n$ bits et
-donc $i*\ln(n)/(n*\ln(2))$ appels pour 1 bit généré en moyenne.
-Lorsqu'on saute et qu'on effectue $i'$ itérations,
-à chaque itération, la stratégie génère un nombre entre
+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 $i'*n$ appels pour $n$ bits et
-donc $i'$ appels pour 1 bit généré en moyenne.
+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:fonctions}.
-On constate que le nombre d'appels par bit généré décroit avec $n$ dans la
-seconde démarche et est toujours plus faible que celui de la première.
+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}
+\begin{table}[ht]
$$
\begin{array}{|l|l|l|l|l|l|}
\hline
-\textrm{Algorithme} & 4 & 5 & 6 & 7 & 8 \\
+\textrm{Itérations} & 4 & 5 & 6 & 7 & 8 \\
\hline
-\textrm{marchant} & 19.0 & 22.2905097109 & 23.6954895899 & 25.2661942985 & 27.0\\
+\textrm{Unaires} & 19.0 & 22.3 & 23.7 & 25.3 & 27.0\\
\hline
-\textrm{sautant} & 17 & 13 & 11 & 10 & 9\\
+\textrm{Généralisées} & 17 & 13 & 11 & 10 & 9\\
\hline
\end{array}
$$
-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
+\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).
+En interne, c'est l'implantation de l'algorithme de Mersenne Twister qui
+permet de générer la stratégie aléatoire.
+
+
+
+
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.
+
+
+Les tableau~\ref{fig:TEST:generalise} donnent
+une vision synthétique de ces expérimentations.
+Nous avons évalué les fonctions préfixées par
+$f$ (respecitvement $g$) avec les générateurs issus des itérations
+généralisées (resp. unaires).
+Quelle que soit la méthode utilisée, on constate que chacun des
+générateurs passe
+avec succes le test de NIST.
+
+Interpréter ces resultats en concluant que ces générateurs sont
+tous équivalents serait erroné: la meilleur des
+méthodes basées sur le mode des itérations
+généralisées (pour $n=8$ par exemple)
+est au moins deux fois plus rapide que la meilleur de celles qui
+sont basées sur les itérations unaires.
+
+
+
%%%%%%%%% 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~\label{table:functions}.}
+\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}
+
+
+\begin{tabular}{|l|r|r|r|r|}
+ \hline
+Test & $f^{*5}$ &$f^{*6}$ &$f^{*7}$ &$f^{*8}$ \\ \hline
+Fréquence (Monobit)& 0.401 (0.97)& 0.924 (1.0)& 0.779 (0.98)& 0.883 (0.99)\\ \hline
+Fréquence ds un bloc& 0.574 (0.98)& 0.062 (1.0)& 0.978 (0.98)& 0.964 (0.98)\\ \hline
+Somme Cumulé*& 0.598 (0.975)& 0.812 (1.0)& 0.576 (0.99)& 0.637 (0.99)\\ \hline
+Exécution& 0.998 (0.99)& 0.213 (0.98)& 0.816 (0.98)& 0.494 (1.0)\\ \hline
+Longue exécution dans un bloc& 0.085 (0.99)& 0.971 (0.99)& 0.474 (1.0)& 0.574 (0.99)\\ \hline
+Rang& 0.994 (0.96)& 0.779 (1.0)& 0.191 (0.99)& 0.883 (0.99)\\ \hline
+Fourier rapide& 0.798 (1.0)& 0.595 (0.99)& 0.739 (0.99)& 0.595 (1.0)\\ \hline
+Patron sans superposition*& 0.521 (0.987)& 0.494 (0.989)& 0.530 (0.990)& 0.520 (0.989)\\ \hline
+Patron avec superposition& 0.066 (0.99)& 0.040 (0.99)& 0.304 (1.0)& 0.249 (0.98)\\ \hline
+Statistiques universelles& 0.851 (0.99)& 0.911 (0.99)& 0.924 (0.96)& 0.066 (1.0)\\ \hline
+Entropie approchée (m=10)& 0.637 (0.99)& 0.102 (0.99)& 0.115 (0.99)& 0.350 (0.98)\\ \hline
+Suite aléatoire *& 0.573 (0.981)& 0.144 (0.989)& 0.422 (1.0)& 0.314 (0.984)\\ \hline
+Suite aléatoire variante *& 0.359 (0.968)& 0.401 (0.982)& 0.378 (0.989)& 0.329 (0.985)\\ \hline
+Série* (m=10)& 0.469 (0.98)& 0.475 (0.995)& 0.473 (0.985)& 0.651 (0.995)\\ \hline
+Complexité linaire& 0.129 (1.0)& 0.494 (1.0)& 0.062 (1.0)& 0.739 (1.0)\\ \hline
+
+\end{tabular}
\end{scriptsize}
+
+
+\caption{Test de NIST pour les fonctions
+ du tableau~\ref{table:functions} selon les itérations généralisées}\label{fig:TEST:generalise}
\end{table}
+
+\begin{table}[ht]
+ \centering
+ \begin{scriptsize}
+\begin{tabular}{|l|r|r|r|r|}
+\hline
+Test & $g^{*5}$& $g^{*6}$& $f^{*7}$& $f^{*8}$\\ \hline
+Fréquence (Monobit)& 0.236 (1.0)& 0.867 (0.99)& 0.437 (0.99)& 0.911 (1.0)\\ \hline
+Fréquence ds un bloc& 0.129 (0.98)& 0.350 (0.99)& 0.366 (0.96)& 0.657 (1.0)\\ \hline
+Somme Cumulé*& 0.903 (0.995)& 0.931 (0.985)& 0.863 (0.995)& 0.851 (0.995)\\ \hline
+Exécution& 0.699 (0.98)& 0.595 (0.99)& 0.181 (1.0)& 0.437 (0.99)\\ \hline
+Longue exécution dans un bloc& 0.009 (0.99)& 0.474 (0.97)& 0.816 (1.0)& 0.051 (1.0)\\ \hline
+Rang& 0.946 (0.96)& 0.637 (0.98)& 0.494 (1.0)& 0.946 (1.0)\\ \hline
+Fourier rapide& 0.383 (0.99)& 0.437 (1.0)& 0.616 (0.98)& 0.924 (0.99)\\ \hline
+Patron sans superposition*& 0.466 (0.990)& 0.540 (0.989)& 0.505 (0.990)& 0.529 (0.991)\\ \hline
+Patron avec superposition& 0.202 (0.96)& 0.129 (0.98)& 0.851 (0.99)& 0.319 (0.98)\\ \hline
+Statistiques universelles& 0.319 (0.97)& 0.534 (0.99)& 0.759 (1.0)& 0.657 (0.99)\\ \hline
+Entropie approchée (m=10)& 0.075 (0.97)& 0.181 (0.99)& 0.213 (0.98)& 0.366 (0.98)\\ \hline
+Suite aléatoire *& 0.357 (0.986)& 0.569 (0.991)& 0.539 (0.987)& 0.435 (0.992)\\ \hline
+Suite aléatoire variante *& 0.398 (0.989)& 0.507 (0.986)& 0.668 (0.991)& 0.514 (0.994)\\ \hline
+Série* (m=10)& 0.859 (0.995)& 0.768 (0.99)& 0.427 (0.995)& 0.637 (0.98)\\ \hline
+Complexité linaire& 0.897 (0.99)& 0.366 (0.98)& 0.153 (1.0)& 0.437 (1.0)\\ \hline
+
+\end{tabular}
+\end{scriptsize}
+
+
+\caption{Test de NIST pour les fonctions
+ du tableau~\ref{table:functions} selon les itérations unaires}\label{fig:TEST:unaire}
+\end{table}
+
+
+\begin{table}[ht]
+ \centering
+ \begin{scriptsize}
+
+\begin{tabular}{|l|r|r|r|r|}
+ \hline
+Test & 5 bits& 6 bits & 7 bits & 8bits \\ \hline
+Fréquence (Monobit)& 0.289 (1.0)& 0.437 (1.0)& 0.678 (1.0)& 0.153 (0.99)\\ \hline
+Fréquence ds un bloc& 0.419 (1.0)& 0.971 (0.98)& 0.419 (0.99)& 0.275 (1.0)\\ \hline
+Somme Cumulé*& 0.607 (0.99)& 0.224 (0.995)& 0.645 (0.995)& 0.901 (0.99)\\ \hline
+Exécution& 0.129 (0.99)& 0.005 (0.99)& 0.935 (0.98)& 0.699 (0.98)\\ \hline
+Longue exécution dans un bloc& 0.514 (1.0)& 0.739 (0.99)& 0.994 (1.0)& 0.834 (0.99)\\ \hline
+Rang& 0.455 (0.97)& 0.851 (0.99)& 0.554 (1.0)& 0.964 (0.99)\\ \hline
+Fourier rapide& 0.096 (0.98)& 0.955 (0.99)& 0.851 (0.97)& 0.037 (1.0)\\ \hline
+Patron sans superposition*& 0.534 (0.990)& 0.524 (0.990)& 0.508 (0.987)& 0.515 (0.99)\\ \hline
+Patron avec superposition& 0.699 (0.99)& 0.616 (0.95)& 0.071 (1.0)& 0.058 (1.0)\\ \hline
+Statistiques universelles& 0.062 (0.99)& 0.071 (1.0)& 0.637 (1.0)& 0.494 (0.98)\\ \hline
+Entropie approchée (m=10)& 0.897 (0.99)& 0.383 (0.99)& 0.366 (1.0)& 0.911 (0.99)\\ \hline
+Suite aléatoire *& 0.365 (0.983)& 0.442 (0.994)& 0.579 (0.992)& 0.296 (0.993)\\ \hline
+Suite aléatoire variante *& 0.471 (0.978)& 0.559 (0.992)& 0.519 (0.987)& 0.340 (0.995)\\ \hline
+Série* (m=10)& 0.447 (0.985)& 0.298 (0.995)& 0.648 (1.0)& 0.352 (0.995)\\ \hline
+Complexité linaire& 0.005 (0.98)& 0.534 (0.99)& 0.085 (0.97)& 0.996 (1.0)\\ \hline
+
+\end{tabular}
+
+
+
+
+
+
+
+
+
+
+ \end{scriptsize}
+
+
+\caption{Test de NIST pour l'algorithme de Mersenne Twister}\label{fig:TEST:Mersenne}
+\end{table}
+
+
%
