+\documentclass[compress]{beamer}
+
+\usetheme[compress]{Ilmenau}
+\setbeamertemplate{items}[ball]
+\usenavigationsymbolstemplate{}
+
+\usepackage{thumbpdf}
+\usepackage[T1]{fontenc}
+\usepackage[latin1]{inputenc}
+\usepackage{pifont}
+\usepackage{amsmath}
+\usepackage{wasysym}
+\usepackage{amsfonts}
+\usepackage{tabularx}
+\usepackage{graphicx}
+\usepackage{ifthen}
+\usepackage[francais]{babel}
+\usepackage{rotating}
+
+\graphicspath{{Figures/}}
+
+%\includeonlyframes{1,2,3,4,5,6,7,8,9,10,11,15,17,18,19,20,21,22,23,24,25,26,28,29,30,31,32,33,34,35,36,37,38,39,bibliocont,bibliodisc}
+%\includeonlyframes{6}
+
+\newboolean{acroread}
+\setboolean{acroread}{true}
+\newcommand{\N}{\mathbb N}
+\newcommand{\R}{\mathbb R}
+\newcommand{\Z}{\mathbb Z}
+\newcommand{\Q}{\mathbb Q}
+\newcommand{\C}{\mathbb C}
+\newlength{\tl}
+\newcommand{\attention}{%
+ \settowidth{\tl}{$\triangle$}%
+ \makebox[0pt][l]{$\triangle$}%
+ \makebox[\tl][c]{\raisebox{.2ex}{\tiny\string!}}}
+\newcommand{\hauteur}[2]{\raisebox{0pt}[#1][-#1]{#2}}
+\def\oeuvre{\oe uvre }
+\def\oeuvrepv{\oe uvre}
+
+%\newenvironment{myitemize}[1]{
+%% \setlength{\topsep}{#1mm}
+% \begin{itemize}
+%% \setlength{\partopsep}{#1mm}
+% \setlength{\itemsep}{#1}
+% }
+% {\end{itemize}
+%}
+
+%\newcounter{selection}
+%\setcounter{selection}{0}
+%\newcounter{num}
+%\setcounter{num}{0}
+
+\newcommand{\frameselect}[2]{
+ % \addtocounter{num}{1}
+ \ifthenelse{\boolean{#1}}%\value{selection}=0 \or
+ % \value{num}=\value{selection}}
+ {
+ #2
+ }{}
+}
+
+\newenvironment{algo}[0] {
+ \begin{quotation}
+ \begin{tabbing}
+ \hspace{5mm}\=\hspace{5mm}\=\hspace{5mm}\=\hspace{5mm}\= \kill} %
+ { \end{tabbing}\end{quotation}}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% TITRE
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\author{Jean-François Couchot$^1$ et Sylvain Contassot-Vivier$^2$}
+
+\title{Construction de codes de Gray équilibrés \\et forme canonique}
+%\subtitle{Habilitation à Diriger des Recherches}
+
+\date{1 - Équipe AND - FEMTO-ST - Univ. Bourgogne Franche-Comté\\
+ 2 - Équipe Simbiot - LORIA - Université de Lorraine
+}
+
+\begin{document}
+
+\frameselect{true}{
+ \begin{frame}[label=1]
+ \titlepage
+ \end{frame}
+}
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+% Méthode R-C
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\frameselect{true}{
+ \begin{frame}[label=2]
+ \frametitle{Méthode R-C de construction de CG}
+
+ Méthode de Robinson-Cohn :
+ \begin{itemize}
+ \item Méthode inductive
+ \item Produit un CG à N bits à partir d'un CG à N-2 bits
+ \begin{itemize}
+ \item Séquence connue de transitions $S_{N-2} = (s_1,...,s_{2^{N-2}})$
+ \item Codées par la dimension empruntée lors de chaque déplacement du code\\
+ $\Rightarrow$ $1\le s_i \le N-2$
+ \end{itemize}
+ \end{itemize}
+
+ Définitions :
+ \begin{itemize}
+ \item $u^R$ est le renversé de la séquence $u$
+ \item $u'(u, x, y) = (u,x,u^R,y,u)$
+ \end{itemize}
+ \end{frame}
+}
+
+\frameselect{true}{
+ \begin{frame}
+ \frametitle{Méthode R-C de construction de CG}
+ Algorithme :
+ \begin{enumerate}
+ \item Pour $l$ un entier pair, décomposer $S_{N-2}$ en une séquence :\\
+ \centerline{$(s_{i_1}, \underline{u_0}, s_{i_2}, \underline{u_1}, s_{i_3}, \underline{u_2}, \dots , s_{i_l-1}, \underline{u_{l-2}}, s_{i_l}, \underline{v})$}
+ où les $u_i$ sont des ss-séqs éventuellement vides de $S_{N-2}$\\
+ et $u_0 = \emptyset$, $i_1 = 1$, $i_2 = 2$ et $v$ éventuellement $\emptyset$.
+ \item Obtenir une nouvelle séquence $U$ en remplaçant :
+ \begin{itemize}
+ \item $u_0$ par $N-1$
+ \item $u_{2i+1}$ par $u'(u_{2i+1},N-1,N)$
+ \item $u_{2i}$ par $u'(u_{2i},N,N-1)$
+ \end{itemize}
+ \item Construire les séquences :\\
+ \begin{itemize}
+ \item $V=(v^R,N,v)$
+ \item $W=(N-1,S_{N-2},N)$
+ \item $W'=(w_2,w_1,W_{[3:]})$ \hfill(inversion des 2 1ers élts de $W$)
+ \end{itemize}
+ \item $S_{N} = (U^R, V, W')$
+ \end{enumerate}
+ \end{frame}
+}
+
+\frameselect{true}{
+ \begin{frame}
+ \frametitle{Méthode R-C de construction de CG}
+ \textbf{Exemple 1} : $N = 5$ et $S_3 = (1,2,1,3,1,2,1,3)$
+ \begin{enumerate}
+ \item le choix $l=2$ implique : $S_3=(s_{1}, \underline{u_0}, s_{2},v)$\\
+ avec $v = (s_3,...,s_{2^{N-2}}) = (1,3,1,2,1,3)$
+ \item on obtient $U = (s_1, 4, s_2, s_3,...,s_{2^{N-2}}) = (1,4,2,1,3,1,2,1,3)$
+ \item et les séquences :\\
+ \begin{itemize}
+ \item $V= (v^R,N,v) = (3,1,2,1,3,1,5,1,3,1,2,1,3)$
+ \item $W=(N-1,S_{N-2},N)=(4,1,2,1,3,1,2,1,3,5)$
+ \item $W'=(w_2,w_1,W_{[3:]})=(1,4,2,1,3,1,2,1,3,5)$
+ \end{itemize}
+ \item $S_{N} = (U^R, V, W')=(\underline{3,1,2,1,3,1,2,4,1},$\\
+ \hspace{9em} $3,1,2,1,3,1,5,1,3,1,2,1,3,$\\
+ \hspace{9em} $1,4,2,1,3,1,2,1,3,5)$
+ \end{enumerate}
+
+ Fréquences = 14, 6, 8, 2, 2
+ \end{frame}
+}
+
+\frameselect{true}{
+ \begin{frame}
+ \frametitle{Méthode R-C de construction de CG}
+ \textbf{Exemple 2} : $N = 5$ et $S_3 = (1,2,1,3,1,2,1,3)$
+ \begin{enumerate}
+ \item le choix $l=4$ implique : $S_3=(s_{1}, \underline{u_0}, s_{2}, \underline{u_1}, s_{i_3}, \underline{u_2}, s_{i_4},v)$\\
+ on choisit $u_1=(1,3)$, donc $s_{i_3}=1$\\
+ et $u_2=(2)$, donc $s_{i_4}=1$ et $v =(3)$
+ \item on a $u'(u_1,4,5) = (1,3,4,3,1,5,1,3)$\\
+ et $u'(u_2,5,4) = (2,5,2,4,2)$\\
+ et donc $U = (1,4,2,\underline{1,3,4,3,1,5,1,3},1,\underline{2,5,2,4,2},1,3)$
+ \item et les séquences :\\
+ \begin{itemize}
+ \item $V= (v^R,N,v) = (3,5,3)$
+ \item $W$ et $W'$ comme précédemment
+ \end{itemize}
+ \item $S_{N} = (U^R, V, W')=(\underline{3,1,2,4,2,5,2,1,3,1,5,1,3,4,3,}$\\
+ \hspace{9em} $\underline{1,2,4,1},3,5,3,$\\
+ \hspace{9em} $1,4,2,1,3,1,2,1,3,5)$
+ \end{enumerate}
+
+ Fréquences = 10, 6, 8, 4, 4
+ \end{frame}
+}
+
+\frameselect{true}{
+ \begin{frame}
+ \frametitle{Problématique des CG équilibrés}
+
+ L'algo précédent n'est pas \textbf{constructif}\\
+ $\rightarrow$ pas d'indication sur le choix de $l$ et des $u_i$ !
+ \vspace{1em}
+
+ Formalisation de l'équilibre d'un CG :
+ \begin{itemize}
+ \item Soit $TC_N : \{1,\dots, N\} \rightarrow \{0, \ldots, 2^N\}$\\
+ nb d'occurrences d'une dimension dans une séquence
+ \item un CG est \textbf{équilibré} ssi :\\
+ \centerline{$\forall i,j\in \{1,...,N\},~|TC_N(i) - TC_N(j)|\le 2$}
+ \item il est \textbf{totalement équilibré} ssi:\\
+ \centerline{$\forall i\in \{1,...,N\},~TC_N(i) = \frac{2^N}{N}$}
+ \end{itemize}
+ \vspace{1em}
+
+ On a montré qu'il existe au moins un choix de $(u_i)$ dans l'algo RC qui
+ donne un CG équilibré.
+ \end{frame}
+}
+
+\frameselect{true}{
+ \begin{frame}
+ \frametitle{Construction de CG équilibrés}
+
+ L'idée est de :
+ \begin{itemize}
+ \item Compter pour chaque dimension, les occurrences générées par l'algo RC :
+ \begin{itemize}
+ \item Pour les dimensions $N-1$ et $N$ on arrive à $l$
+ \item Pour les autres, on établit une formulation dépendant :
+ \begin{itemize}
+ \item des occurrences dans la séquence initiale $S_{N-2}$
+ \item des choix d'inclusion ou non dans les $s_{i_j}$, $u_i$ et $v$ :
+ $TC_N(k)=TC(k, \cup_j(s_{i_j})) + 3\times ( TC(k, \cup_iu_i) + TC(k, v)) + TC_{N-2}(k)$\\
+ \end{itemize}
+ \end{itemize}
+ \item Appliquer la contrainte d'équilibre aux formulations obtenues
+ \end{itemize}
+
+ \begin{center}
+ $\Rightarrow$ On en déduit le nombre d'occurrences de chaque dimension à
+ insérer dans les $s_{i_j}$, $u_i$ et $v$
+ \end{center}
+ \end{frame}
+}
+
+\frameselect{true}{
+ \begin{frame}
+ \frametitle{Construction de CG équilibrés}
+
+ Exemple : $S_2 = (1,2,1,2)$
+ \begin{itemize}
+ \item Pour avoir l'équilibre final, $l$ doit valoir 4
+ \item On en déduit une décomposition de la forme :\\
+ $S_2 = (s_{i_1},u_0,s_{i_2},u_1,s_{i_3},u_2,s_{i_4},v)$ et $s_{i_1}=1$, $u_0=\emptyset$, $s_{i_2}=2$
+ \item Or, on a : $TC_2(1) = 2$ et $TC_2(2)=2$
+ \item Et pour $k=1$ et $k=2$, il faut vérifier :
+ $TC(k, \cup_j(s_{i_j})) + 3\times ( TC(k, \cup_iu_i) + TC(k, v)) + TC_2(k)=4$\\
+ $TC(k, \cup_j(s_{i_j})) + 3\times ( TC(k, \cup_iu_i) + TC(k, v))=2$\\
+ $\Rightarrow TC(k, \cup_iu_i) + TC(k, v) = 0$\\
+ $\Rightarrow TC(k, \cup_j(s_{i_j}))=2$
+ \item Donc $u_0,u_1,u_2$ et $v$ doivent être vides !
+ \end{itemize}
+ \end{frame}
+}
+
+\frameselect{true}{
+ \begin{frame}
+ \frametitle{Construction de CG équilibrés}
+
+ Comme $u_0,u_1,u_2$ et $v$ sont vides, on a :
+ \begin{itemize}
+ \item $u'(u_1,3,4) = (3,4)$
+ \item $u'(u_2,4,3) = (4,3)$
+ \item $U = (1,3,2,3,4,1,4,3,2)$
+ \item $V= (v^R,N,v) = (4)$
+ \item $W=(N-1,S_{N-2},N)=(3,1,2,1,2,4)$
+ \item $W'=(w_2,w_1,W_{[3:]})=(1,3,2,1,2,4)$
+ \item $S_{4} = (U^R, V, W')=(2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4)$
+ \end{itemize}
+ \begin{center}
+ $\Rightarrow$ Fréquences = 4, 4, 4, 4
+ \end{center}
+ \end{frame}
+}
+
+\frameselect{true}{
+ \begin{frame}
+ \frametitle{Algo de construction de CG équilibrés}
+
+ Une fois déterminés les nombres d'occurrences à placer dans les $u_i$, il
+ faut construire la séquence :
+ \begin{itemize}
+ \item Parcours exhaustif :
+ \begin{itemize}
+ \item [$\frownie$] Coûteux
+ \item [$\smiley$] Produit tous les CG équilibrés atteignables par cette méthode
+ \end{itemize}
+ \item Algorithme glouton :
+ \begin{itemize}
+ \item Construction des $u_i$ dans l'ordre
+ \item Choix glouton pour chaque $u_i$ :\\
+ sous-séquence maximale de $S_{N-2}$ vérifiant les nombres totaux
+ d'occurrences déterminés pour les $u_i$
+ \end{itemize}
+ \item [$\frownie$] Ne produit pas tous les CGE possibles !
+ \item [$\smiley$] Produit rapidement un CG pour n'importe quelle dimension !\\
+ (à partir des dimensions 2 et 3)
+ \end{itemize}
+ \end{frame}
+}
+
+\frameselect{true}{
+ \begin{frame}
+ \frametitle{Algo de construction de tous les CG équilibrés}
+
+ Algo basé sur la méthode de M.~Wild :
+ \begin{itemize}
+ \item Basé sur le principe d'exclusion
+ \item Liste des arêtes du N-cube
+ \item Chaque arête prend un état dans l'ensemble $\{0,1,2,g,d\}$ :
+ \begin{itemize}
+ \item 0 pour supprimée, 1 pour incluse, 2 pour indéterminé (initial)
+ \item $g$ pour un ensemble d'arêtes dont une seule est incluse
+ \item $d$ pour un ensemble d'arêtes dont deux sont incluses
+ \end{itemize}
+ \item Ajouts successifs des noeuds en appliquant :
+ \begin{itemize}
+ \item Condition locale (chaque noeud) : degré 2
+ \item Conditions globales : \\
+ cycle max : nb arêtes à 1 = nb sommets\\
+ cycles inf : pas de cycles < nb sommets
+ \item [$\Rightarrow$] élagage dès qu'une contrainte n'est pas vérifiée
+ \end{itemize}
+ \end{itemize}
+ \end{frame}
+}
+
+\frameselect{true}{
+ \begin{frame}
+ \frametitle{Adaptation au contexte de N-cube}
+
+ \begin{itemize}
+ \item Ajout de la contrainte d'équilibre dans l'élagage
+ \item Utilisation d'une forme canonique des CG :\\
+ \begin{itemize}
+ \item [$\Rightarrow$] Unicité des représentants
+ \item [$\Rightarrow$] Ordre global sur les représentants :
+ \begin{itemize}
+ \item Détection efficace des doublons
+ \item Stockage minimal
+ \end{itemize}
+ \end{itemize}
+ \end{itemize}
+ \end{frame}
+}
+
+\frameselect{true}{
+ \begin{frame}
+ \frametitle{Forme canonique des CG}
+
+ \begin{itemize}
+ \item Alignement sur début d'une sous-séquence avec \textbf{écart max} :
+ \begin{itemize}
+ \item Plus grand intervalle entre 2 occurrences d'une même dimension
+ \end{itemize}
+ \item Écart max sur l'ensemble des dimensions = \textbf{équilibre local}
+ \item Renumérotation des dimensions :
+ \begin{itemize}
+ \item Affectation dans l'ordre croissant des n° \hfill$\Rightarrow$ débuts = (1,2)
+ \item Équivalent à des isomorphismes du N-cube
+ \item Donne un ordre global \hfill$\Rightarrow$ tri possible
+ \end{itemize}
+ \item Travaux en cours :
+ \begin{itemize}
+ \item Unicité de la forme canonique pour une classe d'isomorphismes
+ \item Deux formes canoniques distinctes ne sont pas isomorphes
+ \end{itemize}
+ \end{itemize}
+ \begin{center}
+ $\Rightarrow$ Génération exhaustive en accord avec la théorie (dims $\le$ 5)
+ \end{center}
+ \end{frame}
+}
+
+\end{document}
