Relecture Sylvain avec commentaires/questions

[16dcc.git] / hamilton.tex

diff --git a/hamilton.tex b/hamilton.tex
index 17d93803a0d523ddadc31cfe930449bc6a996f41..40e4ba32a16114bea72a22feae672a4bd9695afe 100644 (file)
--- a/hamilton.tex
+++ b/hamilton.tex
@@ -1,5 +1,5 @@
 Many approaches have been developed to solve the problem of building
 Many approaches have been developed to solve the problem of building

-a Gray code in a $\mathsf{N}$ cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04,Bykov2016}, according to properties 
+a Gray code in a $\mathsf{N}$-cube~\cite{Robinson:1981:CS,DBLP:journals/combinatorics/BhatS96,ZanSup04,Bykov2016}, according to properties 

 the produced code has to verify.
 For instance,~\cite{DBLP:journals/combinatorics/BhatS96,ZanSup04} focus on
 balanced Gray codes. In the transition sequence of these codes, 
 the produced code has to verify.
 For instance,~\cite{DBLP:journals/combinatorics/BhatS96,ZanSup04} focus on
 balanced Gray codes. In the transition sequence of these codes, 


@@ -16,14 +16,14 @@ and an algorithm that establishes locally balanced Gray codes is given.
  
 The current context is to provide a function 
 $f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ by removing a Hamiltonian 
  
 The current context is to provide a function 
 $f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ by removing a Hamiltonian 

-cycle in the $\mathsf{N}$ cube. Such a function is going to be iterated
+cycle in the $\mathsf{N}$-cube. Such a function is going to be iterated

 $b$ times to produce a pseudo random number,
 \textit{i.e.} a vertex in the 
 $b$ times to produce a pseudo random number,
 \textit{i.e.} a vertex in the 

-$\mathsf{N}$ cube.
+$\mathsf{N}$-cube.

 Obviously, the number of iterations $b$ has to be sufficiently large 
 to provide a uniform output distribution.
 To reduce the number of iterations, the provided Gray code
 Obviously, the number of iterations $b$ has to be sufficiently large 
 to provide a uniform output distribution.
 To reduce the number of iterations, the provided Gray code

-should ideally possess the both balanced and locally balanced properties.
+should ideally possess both balanced and locally balanced properties.

 However, none of the two algorithms is compatible 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}
 However, none of the two algorithms is compatible 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}


@@ -50,7 +50,7 @@ have 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.
 The latter states that for every $\mathsf{N}$ there 
 The former states that if 
 $\mathsf{N}$ is a 2-power, a balanced Gray code is always totally balanced.
 The latter states that for every $\mathsf{N}$ there 

-exists a Gray code such that all transition count numbers are 
+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 


@@ -83,7 +83,7 @@ two elements have been exchanged.
 \end{enumerate} 
 
 It has been proven in~\cite{ZanSup04} that 
 \end{enumerate} 
 
 It has been proven in~\cite{ZanSup04} that 

-$S_{\mathsf{N}}$ is transition sequence of a cyclic $\mathsf{N}$-bits Gray code 
+$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 
 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 


@@ -120,7 +120,7 @@ $\textit{TC}_3(1)= \textit{TC}_3(2)=2$ and  $\textit{TC}_3(3)=4$. Such a Gray co
 Let now  
 $L^4=0000, 0010, 0110, 1110, 1111, 0111, 0011, 0001, 0101,$
 $0100, 1100, 1101, 1001, 1011, 1010, 1000$
 Let now  
 $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
+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  
 is thus totally balanced.
 
 On the contrary, for the standard $4$-bits Gray code  


@@ -133,7 +133,7 @@ the code is neither balanced nor totally balanced.
 
 \begin{thrm}\label{prop:balanced}
 Let $\mathsf{N}$ in $\Nats^*$, and $a_{\mathsf{N}}$ be defined by
 
 \begin{thrm}\label{prop:balanced}
 Let $\mathsf{N}$ in $\Nats^*$, and $a_{\mathsf{N}}$ be defined by

-$a_{\mathsf{N}}= 2 \lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \rfloor$. 
+$a_{\mathsf{N}}= 2 \left\lfloor \dfrac{2^{\mathsf{N}}}{2\mathsf{N}} \right\rfloor$. 

 There exists then a sequence $l$ in 
 step~(\ref{item:nondet}) of the \emph{Robinson-Cohn extension} algorithm
 such that all the transition counts $\textit{TC}_{\mathsf{N}}(i)$ 
 There exists then a sequence $l$ in 
 step~(\ref{item:nondet}) of the \emph{Robinson-Cohn extension} algorithm
 such that all the transition counts $\textit{TC}_{\mathsf{N}}(i)$ 


@@ -328,3 +328,9 @@ Notice that all such choices lead to a hamiltonian path.
 
 
 
 
 
 

+%%% Local Variables:
+%%% mode: latex
+%%% TeX-master: "main"
+%%% ispell-dictionary: "american"
+%%% mode: flyspell
+%%% End: