+On a vu dans le chapitre précédent 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.
+
+
+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}
+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
+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
+
+\begin{enumerate}
+\item $M_{ij}$ vaut 0 si $j$ n'est pas un voisin de $i$, \textit{i.e.},
+ il n'y a pas d'arc de $i$ à $j$ dans le graphe $\textsc{giu}(f)$;
+
+\item $0 \le M_{ii} \le {\mathsf{N}}$: le nombre de boucles autour de chaque
+configuration $i$ est inférieur à ${\mathsf{N}}$;
+
+\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}$:
+la matrice est stochastique à droite;
+\item pour chque 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
+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
+qui pourrait être utilisé pour instancier toutes les solutions,
+ici pour $\mathsf{N} = 2$. Dans ce code,
+\verb+mmult(+$X,Y,R$\verb+)+ et
+\verb+summ(+$X,Y,R$\verb+)+
+valent True si et seulement si $R$
+est le produit matriciel (ou la somme matricielle)
+entre $X$ and $Y$ respectivement.
+il n'est pas difficile d'adapter ce code à n'importe quelle valeur
+entière naturelle $\mathsf{N}$.
+
+\begin{figure}[ht]
+\begin{scriptsize}
+\lstset{language=prolog}
+\begin{lstlisting}
+bistoc(X):-
+ M=[[M0_0, M0_1, 0, M0_3], [M1_0, M1_1, 0, M1_3],
+ [M2_0, 0, M2_2, M2_3], [0, M3_1, M3_2, M3_3]],
+ [M0_0, M1_1, M2_2, M3_3] ins 0..2,
+ [M0_1, M0_3, M1_0, M1_3, M2_0, M2_3, M3_1, M3_2]
+ ins 0..1,
+ M0_0+ M0_1+ M0_2 #=2, M1_0+ M1_1+ M1_3 #=2,
+ M2_0+ M2_2+ M2_3 #=2, M3_1+ M3_2+ M3_3 #=2,
+ M0_0+ M1_0+ M2_0 #=2, M0_1+ M1_1+ M3_1 #=2,
+ M0_2+ M2_2+ M3_2 #=2, M1_3+ M2_3+ M3_3 #=2,
+ mmult(M,M,M2),
+ mmult(M,M2,M3),
+ mmult(M,M3,M4),
+ summ(M,M2,S2),
+ summ(S2,M3,S3),
+ summ(S3,M4,S4),
+ allpositive(S4).
+\end{lstlisting}
+\end{scriptsize}
+\caption{Prolog Problem to Find DSSC Matrix when $n=2$}\label{fig:prolog}
+\end{figure}
+
+Enfin, on définit la relation $\mathcal{R}$, qui est établie pourles deux
+fonctions $f$ et $g$ si leur graphes
+respectifs $\textsf{giu}(f)$ et $\textsf{giu}(g)$
+sont isomorphes.
+C'est évidemment une relation d'équivalence.
+
+
+
+\subsection{Analyse de l'approche}
+Exécutée sur un ordinateur personnelle, PROLOG trouve
+en moins d'une seconde les
+49 solutions pour $n=2$,
+dont 2 seulement ne sont pas équivalentes,
+en moins d'une minute les 27642 solutions dont seulement 111 ne
+sont pas équivalentes pour $n=3$.
+Cependant, l'approche ne permet pas d'engendrer toutes les solutions
+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.
+
+Cependant, pour des valeurs de $n$ petites, nous avons
+comparé les fonctions non équivalantes selon leur proportion
+à engendrer des temps de mélange petits (cf. équation~\ref{eq:mt:ex}).
+
+
+
+
+\begin{xpl}
+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]
+\begin{small}
+$$
+\begin{array}{|l|l|l|}
+\hline
+\textrm{Name} & \textrm{Image} & \textrm{MT}\\
+\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 \\
+\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}, & \\
+& \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}, & \\
+& \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 \\
+\hline
+% [3, 4, 7, 0, 1, 6, 5, 2], #16
+% [3, 4, 7, 0, 2, 6, 5, 1], #17
+% [3, 6, 7, 5, 2, 0, 1, 4], #26
+% [3, 4, 7, 5, 2, 6, 1, 0], #29
+% [3, 2, 5, 6, 7, 0, 1, 4]] #30
+\end{array}
+$$
+\end{small}
+\caption{Les 5 fonctions booléennes $n=3$ aux temps de mélange les plus faibles.}\label{table:mixing:3}
+\end{table}
+\end{xpl}
+
+Une analyse syntaxique de ces fonctions ne permet pas, à priori,
+de déduire des règles permettant de construire de nouvelles
+fonction dont le temps de mélange serait faible.
+Cependant, le graphe $\textsc{giu}(f^*)$
+(donné à la Figure~\ref{fig:iteration:f*})
+est le $3$-cube dans lequel le cycle
+$000,100,101,001,011,111,110,010,000$
+a été enlevé.
+Ce cycle qui visite chaque n{\oe}ud exactement une fois est un
+\emph{cycle hamiltonien}.
+La matrice de Markov correspondante est donnée à
+la figure~\ref{fig:markov:f*}.
+On s'intéresse par la suite à la génération de ce genre de cycles.
+
+
+
+
+
+\begin{figure}[ht]
+ \begin{center}
+ \subfigure[Graphe $\textsc{giu}(f^*)$.
+ \label{fig:iteration:f*}]{
+ \begin{minipage}{0.55\linewidth}
+ \centering
+ \includegraphics[width=\columnwidth]{images/iter_f0c}%
+ \end{minipage}
+ }%
+ \subfigure[Matrice de Markov associée à $\textsc{giu}(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}
+
+
+
+
+\section{Graphes
+ $\textsc{giu}(f)$
+ $\textsc{gig}(f)$
+ fortement connexes et doublement stochastiques}
+% Secrypt 14
+
+
+
+
+\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{theorem}\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{theorem}
+\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{theorem}\label{th:grapheFC}
+ Le graphe d'itérations issu du $n$-cube, auquel un cycle hamiltonien est
+ enlevé, est fortement connexe.
+\end{theorem}
+
+
+\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 $\textsf{giu}$ 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 $\textsf{giu}(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}[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 générateurs selon le nombre de bits.}\label{table:nbFunc}
+\end{table}
+
+
+\section{Quantifier l'écart par rapport à la distribution uniforme}
+%15 Rairo
\ No newline at end of file
