retouche preuve gray

diff --git a/14Secrypt.tex b/14Secrypt.tex
index 76e635b4b51821491df24efb166406721e6287d5..69fb6d8462374bf50a8508cda61e04d087b549c5 100644 (file)
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -340,7 +340,7 @@ différent que par un seul bit.
 \section{Lien avec les codes de Gray cycliques (totalement) équilibrés}
 \label{sub:gray}
 
 \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
+Un minorant 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
     \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


@@ -438,16 +438,16 @@ comment sélectionner des sous-séquences qui assurent que le code obtenu est é
 La théorème suivante montre que c'est possible et sa preuve,
 donnée en annexes~\ref{anx:generateur}, explique comment le faire. 
 
 La théorème suivante montre que c'est possible et sa preuve,
 donnée en annexes~\ref{anx:generateur}, explique comment le faire. 
 

-
-\begin{theorem}\label{prop:balanced}
+\begin{restatable}[Existence d'un code de Gray équilibré]{theorem}{theograyequilibre}
+\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
 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}  telle que 
+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}$.
 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}
+\end{restatable}

 
 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.
 
 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.


@@ -595,17 +595,17 @@ 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 $\frac{1}{n}$.
 Cette version, qui reste davantage sur place que l'algorithme original,
 est fixée à $\frac{1}{2}+\frac{1}{2n}$.
 Dans l'algorithme initial, celle-ci est de $\frac{1}{n}$.
 Cette version, qui reste davantage sur place que l'algorithme original,

-a été introduite pour simplifier le calcul de la borne sup 
+a été introduite pour simplifier le calcul d'un majorant 

 du temps d'arrêt.   
 
 
 Sans entrer dans les détails de la preuve, on remarque aussi
 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 
+que le calcul  de ce majorant 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.
 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 intégrant cette contrainte, ce majorant  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.
 
 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.


@@ -624,7 +624,7 @@ résume ces résultats. Dans celle-ci, un cercle  représente une approximation
 $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  constate que l'approximation de $E[\ts]$ est largement inférieure 
 $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  constate que l'approximation de $E[\ts]$ est largement inférieure 

-à la borne quadratique donnée au théorème~\ref{prop:stop} et que la conjecture 
+à le majorant quadratique donné au théorème~\ref{prop:stop} et que la conjecture 

 donnée au paragraphe précédent est sensée.
 
 
 donnée au paragraphe précédent est sensée.
 
 


@@ -1090,7 +1090,7 @@ construction de ce type de codes a été présentée étendant les méthodes
 existantes. 
 Dans le cas des itérations unaires, 
 l'algorithme qui en découle a un temps de mélange qui a 
 existantes. 
 Dans le cas des itérations unaires, 
 l'algorithme qui en découle a un temps de mélange qui a 

-une borne sup quadratique de convergence vers la distribution uniforme. 
+un majorant quadratique de convergence vers la distribution uniforme. 

 Pratiquement,  ce temps de mélange se rapproche de $N\ln N$.
 Les expérimentations au travers de la batterie de test de NIST ont montré
 que toutes les propriétés statistiques sont obtenues pour
 Pratiquement,  ce temps de mélange se rapproche de $N\ln N$.
 Les expérimentations au travers de la batterie de test de NIST ont montré
 que toutes les propriétés statistiques sont obtenues pour

diff --git a/main.tex b/main.tex
index e2161f192f69be5ec818f9b6e20098621d2abb20..1c00650ceef48889ac2cb87e81d53c5d938256e6 100644 (file)
--- a/main.tex
+++ b/main.tex
@@ -376,8 +376,11 @@ du chapitre 8}
 
 \chapter{Preuves sur les générateurs de nombres pseudo-aléatoires}\label{anx:generateur}
 \input{annexePreuveDistribution}
 
 \chapter{Preuves sur les générateurs de nombres pseudo-aléatoires}\label{anx:generateur}
 \input{annexePreuveDistribution}

+

 \section{Codes de Gray équilibrés par induction}
 \input{annexePreuveGrayEquilibre}
 \section{Codes de Gray équilibrés par induction}
 \input{annexePreuveGrayEquilibre}

+
+\section{Majoration du temps d'arrêt}

 \input{annexePreuveStopping}
 
 \chapter{Preuves sur le marquage de média}\label{anx:marquage}
 \input{annexePreuveStopping}
 
 \chapter{Preuves sur le marquage de média}\label{anx:marquage}


@@ -391,7 +394,7 @@ du chapitre 8}
 \input{annexePreuveMarquageCorrectioncompletude}
 \backmatter
 
 \input{annexePreuveMarquageCorrectioncompletude}
 \backmatter
 

-\section{Complexité d'Algorithmes de stéganographie}
+\section{Complexités d'algorithmes de stéganographie}

 \label{anx:preuve:cplxt}
 \input{annexePreuvesComplexiteStego}
 
 \label{anx:preuve:cplxt}
 \input{annexePreuvesComplexiteStego}