X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/hdrcouchot.git/blobdiff_plain/d419382ccd1a95aa44a16d1e7cfff6fd4aba0d05..78cd1e6fef0e2664357da1584c958f06b0820a88:/14Secrypt.tex?ds=inline

diff --git a/14Secrypt.tex b/14Secrypt.tex
index 597acbb..f1fae6f 100644
--- a/14Secrypt.tex
+++ b/14Secrypt.tex
@@ -380,43 +380,65 @@ vÃ©rifiant $\sum_{i=1}^nNT_n(i) = 2^n$.
 \section{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.
+De nombreuses approches ont Ã©tÃ© developpÃ©es pour rÃ©soudre le problÃ¨me de construire
+un code de Gray dans un $\mathsf{N}$-cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04}, 
+selon les propriÃ©tÃ©s que doit vÃ©rifier ce code.
+
+Dans les travaux~\cite{Robinson:1981:CS}, les auteurs 
+proposent une approche inductive de construction de code de Gray Ã©quilibrÃ©s 
+(on passe du $\mathsf{N}-2$ Ã  $\mathsf{N}$)
+pour peu que l'utilisateur fournisse une sous-sÃ©quence possÃ©dant certaines 
+propriÃ©tÃ©s Ã  chaque pas inductif.
+Ce travail a Ã©tÃ© renforcÃ© dans ~\cite{DBLP:journals/combinatorics/BhatS96}
+oÃ¹ les auteurs donnent une maniÃ¨re explicite de construire une telle sous-sÃ©quence.
+Enfin, les autheurs de~\cite{ZanSup04} prÃ©sentent une extension de l'algorithme de
+\emph{Robinson-Cohn}. La prÃ©sentation rigoureuse de cette extension leur permet 
+principalement de prouver que si $\mathsf{N}$ est une puissance de 2, 
+le code de Gray Ã©quilibrÃ© engendrÃ© par l'extension est toujours totalement Ã©quilibrÃ© et 
+que $S_{\mathsf{N}}$ est la sÃ©quence de transition d'un code de Gray de $\mathsf{N}$ bits 
+si  $S_{\mathsf{N}-2}$ l'est aussi.. 
+Cependant les auteurs ne prouvent pas que leur approche fournit systÃ©matiquement  
+un code de Gray (totalement) Ã©quilibrÃ©. 
+Cette section montre que ceci est vrai en rappelant tout d'abord
+l'extension de l'algorithme de \emph{Robinson-Cohn} pour un 
+code de Gray avec $\mathsf{N}-2$ bits.
 
-\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 codes de Gray Ã©quilibrÃ©s selon le nombre de bits.}\label{table:nbFunc}
-\end{table}
+\begin{enumerate}
+\item \label{item:nondet}Soit $l$ un entier positif pair. Trouver des sous-sequences 
+$u_1, u_2, \dots , u_{l-2}, v$ (possiblement vides) de $S_{\mathsf{N}-2}$ 
+telles que $S_{\mathsf{N}-2}$ est la concatÃ©nation de  
+$$
+s_{i_1}, u_0, s_{i_2}, u_1, s_{i_3}, u_2, \dots , s_{i_l-1}, u_{l-2}, s_{i_l}, v
+$$
+oÃ¹ $i_1 = 1$, $i_2 = 2$, et $u_0 = \emptyset$ (la sÃ©quence vide).
+\item\label{item:u'} Remplacer dans $S_{\mathsf{N}-2}$ les sequences $u_0, u_1, u_2, \ldots, u_{l-2}$ 
+  par 
+  $\mathsf{N} - 1,  u'(u_1,\mathsf{N} - 1, \mathsf{N}) , u'(u_2,\mathsf{N}, \mathsf{N} - 1), u'(u_3,\mathsf{N} - 1,\mathsf{N}), \dots, u'(u_{l-2},\mathsf{N}, \mathsf{N} - 1)$
+  respectivement, oÃ¹ $u'(u,x,y)$ est la sÃ©quence $u,x,u^R,y,u$ telle que 
+  $u^R$ est $u$, mais dans l'ordre inverse. La sÃ©quence obtenue est ensuite notÃ©e $U$.
+\item\label{item:VW} Contruire les sÃ©quences $V=v^R,\mathsf{N},v$, $W=\mathsf{N}-1,S_{\mathsf{N}-2},\mathsf{N}$. Soit  alors $W'$ dÃ©finie commÃ© Ã©tant Ã©gale Ã  $W$ sauf pour les 
+deux premiers Ã©lÃ©ments qui ont Ã©tÃ© intervertis.
+\item La sÃ©quence de transition  $S_{\mathsf{N}}$ est la concatenation $U^R, V, W'$.
+\end{enumerate} 
+
+L'Ã©tape~(\ref{item:nondet}) n'est pas constructive: il n'est pas prÃ©cisÃ©
+comment sÃ©lectionner des sous-sÃ©quences qui assurent que le code obtenu est Ã©quilibrÃ©.
+La thÃ©oreme suivante montre que c'est possible et sa preuve explique comment le faire. 
+
+
+\begin{theorem}\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} 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}
 
+La preuve de ce thÃ©orÃ¨me est donnÃ©e en annexes~\ref{anx:generateur}.
 
-Ces fonctions Ã©tant gÃ©nÃ©rÃ©e, on s'intÃ©resse Ã  Ã©tudier Ã  quelle vitesse 
+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.
 C'est l'objectif de la section suivante. 
 
@@ -541,19 +563,22 @@ Si $\tau$ est un temps d'arrÃªt fort, alors $d(t)\leq \max_{X\in\Bool^{\mathsf{N
 \P_X(\tau > t)$.
 \end{theorem}
 
+
+Soit alors $\ov{h} : \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ la fonction 
+telle que pour $X \in \Bool^{\mathsf{N}} $, 
+$(X,\ov{h}(X)) \in E$ et $X\oplus\ov{h}(X)=0^{{\mathsf{N}}-h(X)}10^{h(X)-1}$. 
+La fonction $\ov{h}$ est dite  {\it anti-involutive} si pour tout $X\in \Bool^{\mathsf{N}}$,
+$\ov{h}(\ov{h}(X))\neq X$. 
+
+
 \begin{theorem} \label{prop:stop}
-If $\ov{h}$ is bijective et telle que if for every $X\in \Bool^{\mathsf{N}}$,
+Si $\ov{h}$ is bijective et anti involutive 
 $\ov{h}(\ov{h}(X))\neq X$, alors
 $E[\ts]\leq 8{\mathsf{N}}^2+ 4{\mathsf{N}}\ln ({\mathsf{N}}+1)$. 
 \end{theorem}
 
-Sans entrer dans les dÃ©tails de la preuve, on remarque tout d'abord 
-que le calcul 
-de cette borne n'intÃ¨gre pas le fait qu'on prÃ©fÃ¨re enlever des 
-chemins hamiltoniens Ã©quilibrÃ©s. 
-En intÃ©grant cette contrainte, la borne supÃ©rieure pourrait Ãªtre rÃ©duite.
-
-On remarque ensuite que la chaÃ®ne de Markov proposÃ©e ne suit pas exactement
+Les dÃ©tails de la preuve sont donnÃ©s en annexes~\ref{anx:generateur}.
+On remarque tout d'abord que la chaÃ®ne de Markov proposÃ©e ne suit pas exactement
 l'algorithme~\ref{CI Algorithm}. En effet dans la section prÃ©sente, 
 la probabilitÃ© de rester dans une configuration donnÃ©e 
 est fixÃ©e Ã  $frac{1}{2}+\frac{1}{2n}$.
@@ -563,6 +588,67 @@ a Ã©tÃ© introduite pour simplifier le calcul de la borne sup
 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 
+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 effet, le temps de mixage est en $\Theta(N\ln N)$ lors d'une
+marche alÃ©atoire classique paresseuse dans le $\mathsf{N}$-cube.
+On peut ainsi conjecturer que cet ordre de grandeur reste le mÃªme 
+dans le contexte du $\mathsf{N}$-cube privÃ© d'un chemin hamiltonien.
+
+On peut Ã©valuer ceci pratiquement: pour une fonction
+$f: \Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ et une graine initiale
+$x^0$, le code donnÃ© Ã  l'algorithme algorithm~\ref{algo:stop} retourne le 
+nombre d'itÃ©rations suffisant tel que tous les Ã©lÃ©ments $\ell\in \llbracket 1,{\mathsf{N}} \rrbracket$ sont Ã©quitables. Il permet de dÃ©duire une approximation de $E[\ts]$
+en l'instanciant un grand nombre de fois: pour chaque nombre $\mathsf{N}$, 
+$ 3 \le \mathsf{N} \le 16$, 10 fonctionss ont Ã©tÃ© gÃ©nÃ©rÃ©es comme dans 
+ce chapitre. Pour chacune d'elle, le calcul d'une approximation de $E[\ts]$
+est exÃ©cutÃ© 10000 fois avec une graine alÃ©atoire.La Figure~\ref{fig:stopping:moy}
+rÃ©sume ces resultats. Dans celle-ci, un cercle  reprÃ©sente une approximation de 
+$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  cosntate que l'approximation de $E[\ts]$ est largement infÃ©rieure 
+Ã  la borne quadratique donnÃ©e au thÃ©rÃ¨me~\ref{prop:stop} et que la conjecture 
+donnÃ©e au paragraphe prÃ©cÃ©dent est sensÃ©e.
+
+
+\begin{algorithm}[ht]
+%\begin{scriptsize}
+\KwIn{a function $f$, an initial configuration $x^0$ ($\mathsf{N}$ bits)}
+\KwOut{a number of iterations $\textit{nbit}$}
+
+$\textit{nbit} \leftarrow 0$\;
+$x\leftarrow x^0$\;
+$\textit{fair}\leftarrow\emptyset$\;
+\While{$\left\vert{\textit{fair}}\right\vert < \mathsf{N} $}
+{
+        $ s \leftarrow \textit{Random}(\mathsf{N})$ \;
+        $\textit{image} \leftarrow f(x) $\;
+        \If{$\textit{Random}(1) \neq 0$ and $x[s] \neq \textit{image}[s]$}{
+            $\textit{fair} \leftarrow \textit{fair} \cup \{s\}$\;
+            $x[s] \leftarrow \textit{image}[s]$\;
+          }
+        $\textit{nbit} \leftarrow \textit{nbit}+1$\;
+}
+\Return{$\textit{nbit}$}\;
+%\end{scriptsize}
+\caption{Pseudo Code of stoping time calculus }
+\label{algo:stop}
+\end{algorithm}
+
+
+\begin{figure}
+\centering
+\includegraphics[width=0.49\textwidth]{images/complexityET}
+\caption{Average Stopping Time Approximation}\label{fig:stopping:moy}
+\end{figure}
+
+
 
 
 \section{Et les itÃ©rations gÃ©nÃ©ralisÃ©es?}
