From: couchot <jf.couchot@gmail.com>
Date: Wed, 6 Apr 2016 09:10:51 +0000 (+0200)
Subject: debut d'hamilton
X-Git-Url: https://bilbo.iut-bm.univ-fcomte.fr/and/gitweb/16dcc.git/commitdiff_plain/58738f61949e1cc6312f88494db31a201184a407?ds=inline

debut d'hamilton
---

diff --git a/hamilton.tex b/hamilton.tex
new file mode 100644
index 0000000..8f022c6
--- /dev/null
+++ b/hamilton.tex
@@ -0,0 +1,35 @@
+Many approaches have been developed to solve the problem of building
+a Gray code in a $\mathsf{N}$ cube~\cite{}, according to properties 
+the produced code has to verify.
+For instance,~\cite{ZanSup04,DBLP:journals/combinatorics/BhatS96} 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.
+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 
+same amount of times,
+local properties are wished.
+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 
+$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
+$b$ time to produce a pseudo random number, \textit{i.e.} a vertex in the 
+$\mathsf{N}$ cube.
+Obviously, the number of iterations $b$ has to be sufficiently large 
+to provide a uniform output distribution.
+To reduced the number of iterations, the provided Gray code
+should ideally possess the 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}
+are not globally balanced.
+This section thus show how the non deterministic approach 
+presented in~\cite{ZanSup04} has been automatized to provide balanced 
+Hamiltonian paths such that, for each subpart, 
+the number of swiches of each element is as constant as possible.
+
+