From: couchot 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=sidebyside;hp=--cc debut d'hamilton --- 58738f61949e1cc6312f88494db31a201184a407 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. + +