plein d'aspel

[hdrcouchot.git] / 14Secrypt.tex

diff --git a/14Secrypt.tex b/14Secrypt.tex
index 9de2b0d504d219f3c41c746cb316d040f409c4b9..b2ae05d752e2efd67ce5e0a3eb3daa64195aed0a 100644 (file)
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -23,7 +23,7 @@ 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. 
 
 \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 
 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 $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; 
 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  
   $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 
 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}
 
 \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.
 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 
 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 
 
 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}).
 
 
 à 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.
 
 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 
 
 \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.
 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.
 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}}$. 
 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},
 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.  
 $$
 \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(
 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}.$$
 
 $\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 
 $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}}$.
 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$),
 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,4 @@ $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. 
 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.