pch

[16dcc.git] / hamilton.tex

diff --git a/hamilton.tex b/hamilton.tex
index 40e4ba32a16114bea72a22feae672a4bd9695afe..b2c6e54f20363f788ccc99a530be58f74bbb40f2 100644 (file)
--- a/hamilton.tex
+++ b/hamilton.tex
@@ -22,7 +22,8 @@ $b$ times to produce a pseudo random number,
 $\mathsf{N}$-cube.
 Obviously, the number of iterations $b$ has to be sufficiently large 
 to provide a uniform output distribution.
 $\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 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,


@@ -112,13 +113,13 @@ $|\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,$
+$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.
 $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.


@@ -170,23 +171,21 @@ 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.
 Let us first proove that both $c_{\mathsf{N}}$ and  $d_{\mathsf{N}}$ are positive
 
 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


@@ -282,7 +281,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,9 +293,9 @@ 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