From: couchot Date: Wed, 7 Sep 2016 20:04:52 +0000 (+0200) Subject: retouche preuve gray X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/commitdiff_plain/749714e242c186d9017fa85964d6c67edf1bf4d1 retouche preuve gray --- diff --git a/14Secrypt.tex b/14Secrypt.tex index 76e635b..69fb6d8 100644 --- 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} -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 @@ -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. - -\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 -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}$. -\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. @@ -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, -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 -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. -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. @@ -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 -à 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. @@ -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 -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 diff --git a/main.tex b/main.tex index e2161f1..1c00650 100644 --- 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} + \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} @@ -391,7 +394,7 @@ du chapitre 8} \input{annexePreuveMarquageCorrectioncompletude} \backmatter -\section{Complexité d'Algorithmes de stéganographie} +\section{Complexités d'algorithmes de stéganographie} \label{anx:preuve:cplxt} \input{annexePreuvesComplexiteStego}