Ajout exemple 3-cube pour algo Wild

[16dcc.git] / hamilton.tex

diff --git a/hamilton.tex b/hamilton.tex
index 32888bd792e2d61c47253b31f850e957f452fab0..a48fc6254648226359a098a9f4d7e8101dbb0ce2 100644 (file)
--- a/hamilton.tex
+++ b/hamilton.tex
@@ -7,7 +7,7 @@ the number of transitions of each element must differ
 at most by 2.
 This uniformity is a global property on the cycle, \textit{i.e.},
 a property that is established while traversing the whole cycle.
 at most by 2.
 This uniformity is a global property on the cycle, \textit{i.e.},
 a property that is established while traversing the whole cycle.

-On the opposite side, when the objective is to follow a subpart 
+On the other hand, when the objective is to follow a subpart 

 of the Gray code and to switch each element approximately the 
 same amount of times,
 local properties are wished.
 of the Gray code and to switch each element approximately the 
 same amount of times,
 local properties are wished.


@@ -21,11 +21,11 @@ $b$ times to produce a pseudorandom number,
 \textit{i.e.}, a vertex in the 
 $\mathsf{N}$-cube.
 Obviously, the number of iterations $b$ has to be sufficiently large 
 \textit{i.e.}, a vertex in the 
 $\mathsf{N}$-cube.
 Obviously, the number of iterations $b$ has to be sufficiently large 

-to provide an uniform output distribution.
+to provide a uniform output distribution.

 To reduce the number of iterations, it can be claimed
 that the provided Gray code
 should ideally possess both balanced and locally balanced properties.
 To reduce the number of iterations, it can be claimed
 that the provided Gray code
 should ideally possess both balanced and locally balanced properties.

-However, none of the two algorithms is compatible with the second one:
+However, both algorithms are incompatible with the second one:

 balanced Gray codes that are generated by state of the art works~\cite{ZanSup04,DBLP:journals/combinatorics/BhatS96} are not locally balanced. Conversely,
 locally balanced Gray codes yielded by Igor Bykov approach~\cite{Bykov2016}
 are not globally balanced.
 balanced Gray codes that are generated by state of the art works~\cite{ZanSup04,DBLP:journals/combinatorics/BhatS96} are not locally balanced. Conversely,
 locally balanced Gray codes yielded by Igor Bykov approach~\cite{Bykov2016}
 are not globally balanced.


@@ -40,13 +40,13 @@ namely~\cite{Robinson:1981:CS},~\cite{DBLP:journals/combinatorics/BhatS96},
 and~\cite{ZanSup04} have addressed the problem of providing an approach
 to produce balanced gray code.
 The authors of~\cite{Robinson:1981:CS} introduced an inductive approach
 and~\cite{ZanSup04} have addressed the problem of providing an approach
 to produce balanced gray code.
 The authors of~\cite{Robinson:1981:CS} introduced an inductive approach

-aiming at producing balanced Gray codes, provided the user gives 
+aiming at producing balanced Gray codes, assuming the user gives 

 a special subsequence of the transition sequence at each induction step.
 a special subsequence of the transition sequence at each induction step.

-This work have been strengthened in~\cite{DBLP:journals/combinatorics/BhatS96}
-where the authors have explicitly shown how to construct such a subsequence.
+This work has been strengthened in~\cite{DBLP:journals/combinatorics/BhatS96}
+where the authors have explicitly shown how to build such a subsequence.

 Finally the authors of~\cite{ZanSup04} have presented 
 the \emph{Robinson-Cohn extension} 
 Finally the authors of~\cite{ZanSup04} have presented 
 the \emph{Robinson-Cohn extension} 

-algorithm. Their rigorous presentation of this one 
+algorithm. Their rigorous presentation of this algorithm

 has mainly allowed them to prove two properties.
 The former states that if 
 $\mathsf{N}$ is a 2-power, a balanced Gray code is always totally balanced.
 has mainly allowed them to prove two properties.
 The former states that if 
 $\mathsf{N}$ is a 2-power, a balanced Gray code is always totally balanced.


@@ -55,7 +55,7 @@ exists a Gray code such that all transition count numbers
 are 2-powers whose exponents are either equal
 or differ from each other by 1.
 However, the authors do not prove that the approach allows to build 
 are 2-powers whose exponents are either equal
 or differ from each other by 1.
 However, the authors do not prove that the approach allows to build 

-(totally balanced) Gray code. 
+(totally balanced) Gray codes. 

 What follows shows that this fact is established and first recalls the approach.
 
 
 What follows shows that this fact is established and first recalls the approach.
 
 


@@ -86,10 +86,10 @@ two elements have been exchanged.
 It has been proven in~\cite{ZanSup04} that 
 $S_{\mathsf{N}}$ is the transition sequence of a cyclic $\mathsf{N}$-bits Gray code 
 if $S_{\mathsf{N}-2}$ is. 
 It has been proven in~\cite{ZanSup04} that 
 $S_{\mathsf{N}}$ is the transition sequence of a cyclic $\mathsf{N}$-bits Gray code 
 if $S_{\mathsf{N}-2}$ is. 

-However, the step~(\ref{item:nondet}) is not a constructive 
-step that precises how to select the subsequences which ensures that 
+However, step~(\ref{item:nondet}) is not a constructive 
+step that precises how to select the subsequences which ensure that 

 yielded Gray code is balanced.
 yielded Gray code is balanced.

-Next section shows how to choose the sequence $l$ to have the balance property.
+Following sections show how to choose the sequence $l$ to have the balance property.

 
 \subsection{Balanced Codes}
 Let us first recall how to formalize the balance property of a Gray code.
 
 \subsection{Balanced Codes}
 Let us first recall how to formalize the balance property of a Gray code.


@@ -118,14 +118,13 @@ the Hamiltonian cycle that has been removed in $f^*$.
 Its transition sequence is $S=3,1,3,2,3,1,3,2$ and its transition count function is 
 $\textit{TC}_3(1)= \textit{TC}_3(2)=2$ and  $\textit{TC}_3(3)=4$. Such a Gray code is balanced. 
 
 Its transition sequence is $S=3,1,3,2,3,1,3,2$ and its transition count function is 
 $\textit{TC}_3(1)= \textit{TC}_3(2)=2$ and  $\textit{TC}_3(3)=4$. Such a Gray code is balanced. 
 

-Let now  
-$L^4=0000, 0010, 0110, 1110, 1111, 0111, 0011,$ $0001, 0101,0100,$ $1100, 1101, 1001, 1011, 1010, 1000$
+Let  $L^4$ $=0000,0010,0110,1110,1111,0111,0011,0001,0101,0100,1100,1101,1001,1011,1010,1000$

 be a cyclic Gray code. Since $S=2,3,4,1,4,$ $3,2,3,1,4,1,3,2,1,2,4$, $\textit{TC}_4$ is equal to 4 everywhere, this code
 is thus totally balanced.
 
 On the contrary, for the standard $4$-bits Gray code  
 be a cyclic Gray code. Since $S=2,3,4,1,4,$ $3,2,3,1,4,1,3,2,1,2,4$, $\textit{TC}_4$ is equal to 4 everywhere, this code
 is thus totally balanced.
 
 On the contrary, for the standard $4$-bits Gray code  

-$L^{\textit{st}}=0000,0001,0011,$ 
-$0010,0110,0111,0101,0100,1100,1101,1111,1110,1010,1011,1001,1000$,
+$L^{\textit{st}}=0000,0001,0011, 
+0010,0110,0111,0101,0100,$ \newline $1100,1101,1111,1110,1010,1011,1001,1000$,

 we have $\textit{TC}_4(1)=8$ $\textit{TC}_4(2)=4$ $\textit{TC}_4(3)=\textit{TC}_4(4)=2$ and
 the code is neither balanced nor totally balanced.
 \end{xpl}
 we have $\textit{TC}_4(1)=8$ $\textit{TC}_4(2)=4$ $\textit{TC}_4(3)=\textit{TC}_4(4)=2$ and
 the code is neither balanced nor totally balanced.
 \end{xpl}


@@ -168,7 +167,7 @@ odd and even initial values.
 For the inductive case, let us first define some variables.
 Let $c_{\mathsf{N}}$ (resp. $d_{\mathsf{N}}$) be the number of elements 
 whose transition count is exactly $a_{\mathsf{N}}$ (resp $a_{\mathsf{N}} +2$).
 For the inductive case, let us first define some variables.
 Let $c_{\mathsf{N}}$ (resp. $d_{\mathsf{N}}$) be the number of elements 
 whose transition count is exactly $a_{\mathsf{N}}$ (resp $a_{\mathsf{N}} +2$).

-These two variables are defined by the system 
+Both of these variables are defined by the system 

  
 \[
 \left\{
  
 \[
 \left\{


@@ -265,7 +264,7 @@ When $3 \le N \le 7$, values are defined as follows:
 \textit{TC}_{4} & = & [4,4,4,4] \\
 \textit{TC}_{6} & = & [10,10,10,10,12,12] \\
 \end{eqnarray*}
 \textit{TC}_{4} & = & [4,4,4,4] \\
 \textit{TC}_{6} & = & [10,10,10,10,12,12] \\
 \end{eqnarray*}

-It is not hard to verify that all these instanciations verify the aformentioned contraints. 
+It is not difficult to check that all these instanciations verify the aforementioned constraints. 

 
 When  $N  \ge 8$, $\textit{TC}_{\mathsf{N}}(i)$ is defined as follows:
 \begin{equation}
 
 When  $N  \ge 8$, $\textit{TC}_{\mathsf{N}}(i)$ is defined as follows:
 \begin{equation}