]> AND Private Git Repository - 16dcc.git/blobdiff - generating.tex
Logo AND Algorithmique Numérique Distribuée

Private GIT Repository
quelques corrections après remarques de Sylvain
[16dcc.git] / generating.tex
index d512a9803b59c27f0a95a6a6bff958b887a8f30d..0837fdaec746214beea9f8734d672881c96634cc 100644 (file)
@@ -51,7 +51,7 @@ The question which remains to solve is:
 The answer is indeed positive. We furthermore have the following strongest 
 result.
 \begin{thrm}
-There exist $b \in \Nats$ such that $\Gamma_{\{b\}}(f)$ is complete.
+There exists $b \in \Nats$ such that $\Gamma_{\{b\}}(f)$ is complete.
 \end{thrm}
 \begin{proof}
 There is an arc $(x,y)$ in the 
@@ -65,13 +65,12 @@ This section ends with the idea of removing a Hamiltonian cycle in the
 $\mathsf{N}$-cube. 
 In such a context, the Hamiltonian cycle is equivalent to a Gray code.
 Many approaches have been proposed a way to build such codes, for instance 
-the Reflected Binary Code. In this one, one of the bits is switched 
-exactly $2^{\mathsf{N}-}$ \ANNOT{formule incomplète : $2^{\mathsf{N}-1}$ ??} for a $\mathsf{N}$-length cycle. 
-
-%%%%%%%%%%%%%%%%%%%%%
-
-The function that is built 
-from the \ANNOT{Phrase non terminée}
+the Reflected Binary Code. In this one and 
+for a $\mathsf{N}$-length cycle, one of the bits is exactly switched 
+$2^{\mathsf{N}-1}$ times whereas the others bits are modified at most 
+$\left\lfloor \dfrac{2^{\mathsf{N-1}}}{\mathsf{N}-1} \right\rfloor$ times.
+It is clear that the function that is built from such a code would
+not provide a uniform output.  
 
 The next section presents how to build balanced Hamiltonian cycles in the 
 $\mathsf{N}$-cube with the objective to embed them into the