Ajout diapos présentation PRNG

[16dcc.git] / hamilton.tex

diff --git a/hamilton.tex b/hamilton.tex
index 40e4ba32a16114bea72a22feae672a4bd9695afe..32888bd792e2d61c47253b31f850e957f452fab0 100644 (file)
--- a/hamilton.tex
+++ b/hamilton.tex
@@ -5,7 +5,7 @@ For instance,~\cite{DBLP:journals/combinatorics/BhatS96,ZanSup04} focus on
 balanced Gray codes. In the transition sequence of these codes, 
 the number of transitions of each element must differ
 at most by 2.
 balanced Gray codes. In the transition sequence of these codes, 
 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.}
+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 
 of the Gray code and to switch each element approximately the 
 a property that is established while traversing the whole cycle.
 On the opposite side, when the objective is to follow a subpart 
 of the Gray code and to switch each element approximately the 


@@ -15,14 +15,15 @@ For instance, the locally balanced property is studied in~\cite{Bykov2016}
 and an algorithm that establishes locally balanced Gray codes is given.
  
 The current context is to provide a function 
 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 
+$f:\Bool^{\mathsf{N}} \rightarrow \Bool^{\mathsf{N}}$ by removing an 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 pseudorandom number,
+\textit{i.e.}, a vertex in the 

 $\mathsf{N}$-cube.
 Obviously, the number of iterations $b$ has to be sufficiently large 
 $\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
+to provide an 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.
 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,
 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,


@@ -45,8 +46,8 @@ This work have been strengthened in~\cite{DBLP:journals/combinatorics/BhatS96}
 where the authors have explicitly shown how to construct such a subsequence.
 Finally the authors of~\cite{ZanSup04} have presented 
 the \emph{Robinson-Cohn extension} 
 where the authors have explicitly shown how to construct such a subsequence.
 Finally the authors of~\cite{ZanSup04} have presented 
 the \emph{Robinson-Cohn extension} 

-algorithm. There rigorous presentation of this one 
-have mainly allowed them to prove two properties.
+algorithm. Their rigorous presentation of this one 
+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.
 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 


@@ -61,7 +62,7 @@ What follows shows that this fact is established and first recalls the approach.
 Let be given a $\mathsf{N}-2$-bit Gray code whose transition sequence is
 $S_{\mathsf{N}-2}$. What follows is the 
  \emph{Robinson-Cohn extension} method~\cite{ZanSup04}
 Let be given a $\mathsf{N}-2$-bit Gray code whose transition sequence is
 $S_{\mathsf{N}-2}$. What follows is the 
  \emph{Robinson-Cohn extension} method~\cite{ZanSup04}

-which produces a $n$-bits Gray code.
+which produces a $\mathsf{N}$-bits Gray code.

 
 \begin{enumerate}
 \item \label{item:nondet}Let $l$ be an even positive integer. Find 
 
 \begin{enumerate}
 \item \label{item:nondet}Let $l$ be an even positive integer. Find 


@@ -112,20 +113,19 @@ $|\textit{TC}_{\mathsf{N}}(i) - \textit{TC}_{\mathsf{N}}(j)| \le  2$.
 
    
 \begin{xpl}
 
    
 \begin{xpl}

-Let $L^*=000,100,101,001,011,111,110,010$ be the Gray code that corresponds to 
+Let $L^*=000,100,101,001,011,111,$ $110,010$ be the Gray code that corresponds to 

 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. 
 
 Let now  
 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. 
 
 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
+$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  
 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,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}


@@ -146,13 +146,13 @@ for any $i$, $1 \le i \le \mathsf{N}$.
 
 
 The proof is done by induction on $\mathsf{N}$. Let us immediately verify 
 
 
 The proof is done by induction on $\mathsf{N}$. Let us immediately verify 

-that it is established for both odd and even smallest values, \textit{i.e.} 
+that it is established for both odd and even smallest values, \textit{i.e.}, 

 $3$ and $4$.
 $3$ and $4$.

-For the initial case where $\mathsf{N}=3$, \textit{i.e.} $\mathsf{N-2}=1$ we successively have:  $S_1=1,1$, $l=2$,  $u_0 = \emptyset$, and $v=\emptyset$.
+For the initial case where $\mathsf{N}=3$, \textit{i.e.}, $\mathsf{N-2}=1$ we successively have:  $S_1=1,1$, $l=2$,  $u_0 = \emptyset$, and $v=\emptyset$.

 Thus again the algorithm successively produces 
 $U= 1,2,1$, $V = 3$, $W= 2, 1, 1,3$, and $W' = 1,2,1,3$.
 Finally, $S_3$ is $1,2,1,3,1,2,1,3$ which obviously verifies the theorem.    
 Thus again the algorithm successively produces 
 $U= 1,2,1$, $V = 3$, $W= 2, 1, 1,3$, and $W' = 1,2,1,3$.
 Finally, $S_3$ is $1,2,1,3,1,2,1,3$ which obviously verifies the theorem.    

- For the initial case where $\mathsf{N}=4$, \textit{i.e.} $\mathsf{N-2}=2$ 
+ For the initial case where $\mathsf{N}=4$, \textit{i.e.}, $\mathsf{N-2}=2$ 

 we successively have:  $S_1=1,2,1,2$, $l=4$, 
 $u_0,u_1,u_2 = \emptyset,\emptyset,\emptyset$, and $v=\emptyset$.
 Thus again the algorithm successively produces 
 we successively have:  $S_1=1,2,1,2$, $l=4$, 
 $u_0,u_1,u_2 = \emptyset,\emptyset,\emptyset$, and $v=\emptyset$.
 Thus again the algorithm successively produces 


@@ -170,30 +170,28 @@ 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 
  
 whose transition count is exactly $a_{\mathsf{N}}$ (resp $a_{\mathsf{N}} +2$).
 These two variables are defined by the system 
  

-$$
+\[

 \left\{
 \begin{array}{lcl}
 c_{\mathsf{N}} + d_{\mathsf{N}} & = & \mathsf{N} \\
 c_{\mathsf{N}}a_{\mathsf{N}} + d_{\mathsf{N}}(a_{\mathsf{N}}+2) & = & 2^{\mathsf{N}} 
 \end{array}
 \right.
 \left\{
 \begin{array}{lcl}
 c_{\mathsf{N}} + d_{\mathsf{N}} & = & \mathsf{N} \\
 c_{\mathsf{N}}a_{\mathsf{N}} + d_{\mathsf{N}}(a_{\mathsf{N}}+2) & = & 2^{\mathsf{N}} 
 \end{array}
 \right.

-\qquad 

 \Leftrightarrow 
 \Leftrightarrow 

-\qquad 

 \left\{
 \begin{array}{lcl}
 d_{\mathsf{N}} & = & \dfrac{2^{\mathsf{N}} -\mathsf{N}.a_{\mathsf{N}}}{2} \\
 c_{\mathsf{N}} &= &\mathsf{N} -  d_{\mathsf{N}}
 \end{array}
 \right.
 \left\{
 \begin{array}{lcl}
 d_{\mathsf{N}} & = & \dfrac{2^{\mathsf{N}} -\mathsf{N}.a_{\mathsf{N}}}{2} \\
 c_{\mathsf{N}} &= &\mathsf{N} -  d_{\mathsf{N}}
 \end{array}
 \right.

-$$
+\]

 
 Since $a_{\mathsf{N}}$ is even, $d_{\mathsf{N}}$ is an integer.
 
 Since $a_{\mathsf{N}}$ is even, $d_{\mathsf{N}}$ is an integer.

-Let us first proove that both $c_{\mathsf{N}}$ and  $d_{\mathsf{N}}$ are positive
+Let us first prove that both $c_{\mathsf{N}}$ and  $d_{\mathsf{N}}$ are positive

 integers.
 Let $q_{\mathsf{N}}$ and $r_{\mathsf{N}}$, respectively, be  
 integers.
 Let $q_{\mathsf{N}}$ and $r_{\mathsf{N}}$, respectively, be  

-the quotient and the remainder in the Euclidean disvision
-of $2^{\mathsf{N}}$ by $2\mathsf{N}$, \textit{i.e.} 
+the quotient and the remainder in the Euclidean division
+of $2^{\mathsf{N}}$ by $2\mathsf{N}$, \textit{i.e.}, 

 $2^{\mathsf{N}} = q_{\mathsf{N}}.2\mathsf{N} + r_{\mathsf{N}}$, with $0 \le r_{\mathsf{N}} <2\mathsf{N}$.
 First of all, the integer $r$ is even since $r_{\mathsf{N}} = 2^{\mathsf{N}} - q_{\mathsf{N}}.2\mathsf{N}= 2(2^{\mathsf{N}-1} - q_{\mathsf{N}}.\mathsf{N})$. 
 Next,  $a_{\mathsf{N}}$ is $\frac{2^{\mathsf{N}}-r_{\mathsf{N}}}{\mathsf{N}}$. Consequently 
 $2^{\mathsf{N}} = q_{\mathsf{N}}.2\mathsf{N} + r_{\mathsf{N}}$, with $0 \le r_{\mathsf{N}} <2\mathsf{N}$.
 First of all, the integer $r$ is even since $r_{\mathsf{N}} = 2^{\mathsf{N}} - q_{\mathsf{N}}.2\mathsf{N}= 2(2^{\mathsf{N}-1} - q_{\mathsf{N}}.\mathsf{N})$. 
 Next,  $a_{\mathsf{N}}$ is $\frac{2^{\mathsf{N}}-r_{\mathsf{N}}}{\mathsf{N}}$. Consequently 


@@ -203,7 +201,7 @@ The proof for $c_{\mathsf{N}}$ is obvious.
 
 
 For any $i$, $1 \le i \le \mathsf{N}$, let $zi_{\mathsf{N}}$ (resp. $ti_{\mathsf{N}}$ and $bi_{\mathsf{N}}$) 
 
 
 For any $i$, $1 \le i \le \mathsf{N}$, let $zi_{\mathsf{N}}$ (resp. $ti_{\mathsf{N}}$ and $bi_{\mathsf{N}}$) 

-be the occurence number of element $i$ in the sequence $u_0, \dots, u_{l-2}$ 
+be the occurrence number of element $i$ in the sequence $u_0, \dots, u_{l-2}$ 

 (resp. in the sequences $s_{i_1}, \dots , s_{i_l}$ and $v$)
 in step (\ref{item:nondet}) of the algorithm.
 
 (resp. in the sequences $s_{i_1}, \dots , s_{i_l}$ and $v$)
 in step (\ref{item:nondet}) of the algorithm.
 


@@ -241,7 +239,7 @@ or to $a_{\mathsf{N}}+2$), the variable  $zi_{\mathsf{N}}$ is thus an integer.
 Let us now prove that the resulting system has always positive integer 
 solutions $z_i$, $t_i$, $0 \le z_i, t_i \le \textit{TC}_{\mathsf{N}-2}(i)$ 
 and s.t. their sum is equal to $\textit{TC}_{\mathsf{N}-2}(i)$. 
 Let us now prove that the resulting system has always positive integer 
 solutions $z_i$, $t_i$, $0 \le z_i, t_i \le \textit{TC}_{\mathsf{N}-2}(i)$ 
 and s.t. their sum is equal to $\textit{TC}_{\mathsf{N}-2}(i)$. 

-This latter consraint is obviously established if the system has a solution.
+This latter constraint is obviously established if the system has a solution.

 We thus have the following system.
 
 
 We thus have the following system.
 
 


@@ -282,7 +280,7 @@ a_{\mathsf{N}}+2 \textrm{ if } c_{\mathsf{N}} +1 \le i \le c_{\mathsf{N}} + d_{\
 
 
 We thus  have
 
 
 We thus  have

-$$
+\[

 \begin{array}{rcl} 
 \textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) 
 &\ge& 
 \begin{array}{rcl} 
 \textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i) 
 &\ge& 


@@ -294,13 +292,13 @@ a_{\mathsf{N}} - 2(a_{\mathsf{N}-2}+2) \\
 \frac{2^{\mathsf{N}}-2N}{\mathsf{N}}
 -2 \left( \frac{2^{\mathsf{N-2}}}{\mathsf{N-2}}+2\right)\\
 &\ge& 
 \frac{2^{\mathsf{N}}-2N}{\mathsf{N}}
 -2 \left( \frac{2^{\mathsf{N-2}}}{\mathsf{N-2}}+2\right)\\
 &\ge& 

-\dfrac{(\mathsf{N} -2).2^{\mathsf{N}}-2N.2^{\mathsf{N-2}}-6N(N-2)}{\mathsf{N.(N-2)}}\\
+\frac{(\mathsf{N} -2).2^{\mathsf{N}}-2N.2^{\mathsf{N-2}}-6N(N-2)}{\mathsf{N.(N-2)}}\\

 \end{array}
 \end{array}

-$$
+\]

 
 A simple variation study of the function $t:\R \rightarrow \R$ such that 
 $x \mapsto t(x) = (x -2).2^{x}-2x.2^{x-2}-6x(x-2)$ shows that 
 
 A simple variation study of the function $t:\R \rightarrow \R$ such that 
 $x \mapsto t(x) = (x -2).2^{x}-2x.2^{x-2}-6x(x-2)$ shows that 

-its derivative is strictly postive if $x \ge 6$ and $t(8)=224$.
+its derivative is strictly positive if $x \ge 6$ and $t(8)=224$.

 The integer $\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i)$ is thus positive 
 for any $\mathsf{N} \ge 8$ and the proof is established.
 
 The integer $\textit{TC}_{\mathsf{N}}(i) - 2.\textit{TC}_{\mathsf{N}-2}(i)$ is thus positive 
 for any $\mathsf{N} \ge 8$ and the proof is established.
 


@@ -322,7 +320,7 @@ for any $\mathsf{N} \ge 8$ and the proof is established.
 For each element $i$, we are then left to choose $zi_{\mathsf{N}}$ positions 
 among $\textit{TC}_{\mathsf{N}}(i)$, which leads to 
 ${\textit{TC}_{\mathsf{N}}(i) \choose zi_{\mathsf{N}} }$ possibilities.
 For each element $i$, we are then left to choose $zi_{\mathsf{N}}$ positions 
 among $\textit{TC}_{\mathsf{N}}(i)$, which leads to 
 ${\textit{TC}_{\mathsf{N}}(i) \choose zi_{\mathsf{N}} }$ possibilities.

-Notice that all such choices lead to a hamiltonian path.
+Notice that all such choices lead to an Hamiltonian path.