X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/1042ddb8d08dc129da9358b73e723fc5014fb2c8..8e936c00e392b3c17977d1f959b601dbf17bbf0e:/14Secrypt.tex?ds=sidebyside

diff --git a/14Secrypt.tex b/14Secrypt.tex
index 9de2b0d..a04c11e 100644
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -13,17 +13,17 @@ graphe d'itérations, ce qui revient à supprimer en chaque n{\oe}ud de ce graph
 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. 
+% 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 
+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 
@@ -37,16 +37,16 @@ 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}$: 
+\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 
@@ -86,7 +86,7 @@ bistoc(X):-
 \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.
@@ -105,10 +105,10 @@ 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.
+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}).
 
 
@@ -395,17 +395,17 @@ sur des sous-ensembles des partitionnements possibles.
 
 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}}$. 
@@ -416,7 +416,7 @@ Ceci se base sur la théorie des chaînes de Markov.
 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.
 
 
 
@@ -433,7 +433,7 @@ p(e) \left\{
 \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(
@@ -465,7 +465,7 @@ De plus, si
 $\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 
@@ -500,7 +500,7 @@ $f(X_{t-1},Z_t)$  une représentation fonctionnelle de celle-ci.
 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$),
@@ -527,4 +527,44 @@ $E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$.
 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 
 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.
+
+\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}.
+
+\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 $\;
+\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$.
+
+