presPRNG.tex

   1 \documentclass[compress]{beamer}
   2
   3 \usetheme[compress]{Ilmenau}
   4 \setbeamertemplate{items}[ball]
   5 \usenavigationsymbolstemplate{}
   6
   7 \usepackage{thumbpdf}
   8 \usepackage[T1]{fontenc}
   9 \usepackage[latin1]{inputenc}
  10 \usepackage{pifont}
  11 \usepackage{amsmath}
  12 \usepackage{wasysym}
  13 \usepackage{amsfonts}
  14 \usepackage{tabularx}
  15 \usepackage{graphicx}
  16 \usepackage{ifthen}
  17 \usepackage[francais]{babel}
  18 \usepackage{rotating}
  19
  20 \graphicspath{{Figures/}}
  21
  22 %\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}
  23 %\includeonlyframes{6}
  24
  25 \newboolean{acroread}
  26 \setboolean{acroread}{true}
  27 \newcommand{\N}{\mathbb N}
  28 \newcommand{\R}{\mathbb R}
  29 \newcommand{\Z}{\mathbb Z}
  30 \newcommand{\Q}{\mathbb Q}
  31 \newcommand{\C}{\mathbb C}
  32 \newlength{\tl}
  33 \newcommand{\attention}{%
  34   \settowidth{\tl}{$\triangle$}%
  35   \makebox[0pt][l]{$\triangle$}%
  36   \makebox[\tl][c]{\raisebox{.2ex}{\tiny\string!}}}
  37 \newcommand{\hauteur}[2]{\raisebox{0pt}[#1][-#1]{#2}}
  38 \def\oeuvre{\oe uvre }
  39 \def\oeuvrepv{\oe uvre}
  40
  41 %\newenvironment{myitemize}[1]{
  42 %%  \setlength{\topsep}{#1mm}
  43 %  \begin{itemize}
  44 %%    \setlength{\partopsep}{#1mm}
  45 %    \setlength{\itemsep}{#1}
  46 %  }
  47 %  {\end{itemize}
  48 %}
  49
  50 %\newcounter{selection}
  51 %\setcounter{selection}{0}
  52 %\newcounter{num}
  53 %\setcounter{num}{0}
  54
  55 \newcommand{\frameselect}[2]{
  56   % \addtocounter{num}{1}
  57   \ifthenelse{\boolean{#1}}%\value{selection}=0 \or
  58     % \value{num}=\value{selection}}
  59   {
  60     #2
  61   }{}
  62 }
  63
  64 \newenvironment{algo}[0] {
  65   \begin{quotation}
  66   \begin{tabbing}
  67   \hspace{5mm}\=\hspace{5mm}\=\hspace{5mm}\=\hspace{5mm}\= \kill} %
  68  { \end{tabbing}\end{quotation}}
  69
  70 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  71 % TITRE
  72 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  73 \author{Jean-François Couchot$^1$ et Sylvain Contassot-Vivier$^2$}
  74
  75 \title{Construction de codes de Gray équilibrés \\et forme canonique}
  76 %\subtitle{Habilitation à Diriger des Recherches}
  77
  78 \date{1 - Équipe AND - FEMTO-ST - Univ. Bourgogne Franche-Comté\\
  79   2 - Équipe Simbiot - LORIA - Université de Lorraine
  80 }
  81
  82 \begin{document}
  83
  84 \frameselect{true}{
  85   \begin{frame}[label=1]
  86     \titlepage
  87   \end{frame}
  88 }
  89
  90 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  91 % Méthode R-C
  92 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
  93 \frameselect{true}{
  94   \begin{frame}[label=2]
  95     \frametitle{Méthode R-C de construction de CG}
  96
  97     Méthode de Robinson-Cohn :
  98     \begin{itemize}
  99     \item Méthode inductive
 100     \item Produit un CG à N bits à partir d'un CG à N-2 bits
 101       \begin{itemize}
 102       \item Séquence connue de transitions $S_{N-2} = (s_1,...,s_{2^{N-2}})$
 103       \item Codées par la dimension empruntée lors de chaque déplacement du code\\
 104         $\Rightarrow$ $1\le s_i \le N-2$
 105       \end{itemize}
 106     \end{itemize}
 107
 108     Définitions :
 109     \begin{itemize}
 110     \item $u^R$ est le renversé de la séquence $u$
 111     \item $u'(u, x, y) = (u,x,u^R,y,u)$
 112     \end{itemize}
 113   \end{frame}
 114 }
 115
 116 \frameselect{true}{
 117   \begin{frame}
 118     \frametitle{Méthode R-C de construction de CG}
 119     Algorithme :
 120     \begin{enumerate}
 121     \item Pour $l$ un entier pair, décomposer $S_{N-2}$ en une séquence :\\
 122       \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})$}
 123       où les $u_i$ sont des ss-séqs éventuellement vides de $S_{N-2}$\\
 124       et $u_0 = \emptyset$, $i_1 = 1$, $i_2 = 2$ et $v$ éventuellement $\emptyset$.
 125     \item Obtenir une nouvelle séquence $U$ en remplaçant :
 126       \begin{itemize}
 127       \item $u_0$ par $N-1$
 128       \item $u_{2i+1}$ par $u'(u_{2i+1},N-1,N)$
 129       \item $u_{2i}$ par $u'(u_{2i},N,N-1)$
 130       \end{itemize}
 131     \item Construire les séquences :\\
 132       \begin{itemize}
 133       \item $V=(v^R,N,v)$
 134       \item $W=(N-1,S_{N-2},N)$
 135       \item $W'=(w_2,w_1,W_{[3:]})$ \hfill(inversion des 2 1ers élts de $W$)
 136       \end{itemize}
 137     \item $S_{N} = (U^R, V, W')$
 138     \end{enumerate}
 139   \end{frame}
 140 }
 141
 142 \frameselect{true}{
 143   \begin{frame}
 144     \frametitle{Méthode R-C de construction de CG}
 145     \textbf{Exemple 1} : $N = 5$ et $S_3 = (1,2,1,3,1,2,1,3)$
 146     \begin{enumerate}
 147     \item le choix $l=2$ implique : $S_3=(s_{1}, \underline{u_0}, s_{2},v)$\\
 148       avec $v = (s_3,...,s_{2^{N-2}}) = (1,3,1,2,1,3)$
 149     \item on obtient $U = (s_1, 4, s_2, s_3,...,s_{2^{N-2}}) = (1,4,2,1,3,1,2,1,3)$
 150     \item et les séquences :\\
 151       \begin{itemize}
 152       \item $V= (v^R,N,v) = (3,1,2,1,3,1,5,1,3,1,2,1,3)$
 153       \item $W=(N-1,S_{N-2},N)=(4,1,2,1,3,1,2,1,3,5)$
 154       \item $W'=(w_2,w_1,W_{[3:]})=(1,4,2,1,3,1,2,1,3,5)$
 155       \end{itemize}
 156     \item $S_{N} = (U^R, V, W')=(\underline{3,1,2,1,3,1,2,4,1},$\\
 157       \hspace{9em} $3,1,2,1,3,1,5,1,3,1,2,1,3,$\\
 158       \hspace{9em} $1,4,2,1,3,1,2,1,3,5)$
 159     \end{enumerate}
 160
 161     Fréquences = 14, 6, 8, 2, 2
 162   \end{frame}
 163 }
 164
 165 \frameselect{true}{
 166   \begin{frame}
 167     \frametitle{Méthode R-C de construction de CG}
 168     \textbf{Exemple 2} : $N = 5$ et $S_3 = (1,2,1,3,1,2,1,3)$
 169     \begin{enumerate}
 170     \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)$\\
 171       on choisit $u_1=(1,3)$, donc $s_{i_3}=1$\\
 172       et $u_2=(2)$, donc $s_{i_4}=1$ et $v =(3)$
 173     \item on a $u'(u_1,4,5) = (1,3,4,3,1,5,1,3)$\\
 174       et $u'(u_2,5,4) = (2,5,2,4,2)$\\
 175       et donc $U = (1,4,2,\underline{1,3,4,3,1,5,1,3},1,\underline{2,5,2,4,2},1,3)$
 176     \item et les séquences :\\
 177       \begin{itemize}
 178       \item $V= (v^R,N,v) = (3,5,3)$
 179       \item $W$ et $W'$ comme précédemment
 180       \end{itemize}
 181     \item $S_{N} = (U^R, V, W')=(\underline{3,1,2,4,2,5,2,1,3,1,5,1,3,4,3,}$\\
 182       \hspace{9em} $\underline{1,2,4,1},3,5,3,$\\
 183       \hspace{9em} $1,4,2,1,3,1,2,1,3,5)$
 184     \end{enumerate}
 185
 186     Fréquences = 10, 6, 8, 4, 4
 187   \end{frame}
 188 }
 189
 190 \frameselect{true}{
 191   \begin{frame}
 192     \frametitle{Problématique des CG équilibrés}
 193
 194     L'algo précédent n'est pas \textbf{constructif}\\
 195     $\rightarrow$ pas d'indication sur le choix de $l$ et des $u_i$ !
 196     \vspace{1em}
 197
 198     Formalisation de l'équilibre d'un CG :
 199     \begin{itemize}
 200     \item Soit $TC_N : \{1,\dots, N\} \rightarrow \{0, \ldots, 2^N\}$\\
 201       nb d'occurrences d'une dimension dans une séquence
 202     \item un CG est \textbf{équilibré} ssi :\\
 203       \centerline{$\forall i,j\in \{1,...,N\},~|TC_N(i) - TC_N(j)|\le 2$}
 204     \item il est \textbf{totalement équilibré} ssi:\\
 205       \centerline{$\forall i\in \{1,...,N\},~TC_N(i) = \frac{2^N}{N}$}
 206     \end{itemize}
 207     \vspace{1em}
 208
 209     On a  montré qu'il existe au  moins un choix  de $(u_i)$ dans l'algo  RC qui
 210     donne un CG équilibré.
 211   \end{frame}
 212 }
 213
 214 \frameselect{true}{
 215   \begin{frame}
 216     \frametitle{Construction de CG équilibrés}
 217
 218     L'idée est de :
 219     \begin{itemize}
 220     \item Compter pour chaque dimension, les occurrences générées par l'algo RC :
 221       \begin{itemize}
 222       \item Pour les dimensions $N-1$ et $N$ on arrive à $l$
 223       \item Pour les autres, on établit une formulation dépendant :
 224         \begin{itemize}
 225         \item des occurrences dans la séquence initiale $S_{N-2}$
 226         \item des choix d'inclusion ou non dans les $s_{i_j}$, $u_i$ et $v$ :
 227           $TC_N(k)=TC(k, \cup_j(s_{i_j})) + 3\times ( TC(k, \cup_iu_i) + TC(k, v)) + TC_{N-2}(k)$\\
 228         \end{itemize}
 229       \end{itemize}
 230     \item Appliquer la contrainte d'équilibre aux formulations obtenues
 231     \end{itemize}
 232
 233     \begin{center}
 234       $\Rightarrow$ On en déduit le nombre d'occurrences de chaque dimension à
 235       insérer dans les $s_{i_j}$, $u_i$ et $v$
 236     \end{center}
 237   \end{frame}
 238 }
 239
 240 \frameselect{true}{
 241   \begin{frame}
 242     \frametitle{Construction de CG équilibrés}
 243
 244     Exemple : $S_2 = (1,2,1,2)$
 245     \begin{itemize}
 246     \item Pour avoir l'équilibre final, $l$ doit valoir 4
 247     \item On en déduit une décomposition de la forme :\\
 248       $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$
 249     \item Or, on a : $TC_2(1) = 2$ et $TC_2(2)=2$
 250     \item Et pour $k=1$ et $k=2$, il faut vérifier :
 251       $TC(k, \cup_j(s_{i_j})) + 3\times ( TC(k, \cup_iu_i) + TC(k, v)) + TC_2(k)=4$\\
 252       $TC(k, \cup_j(s_{i_j})) + 3\times ( TC(k, \cup_iu_i) + TC(k, v))=2$\\
 253       $\Rightarrow TC(k, \cup_iu_i) + TC(k, v) = 0$\\
 254       $\Rightarrow TC(k, \cup_j(s_{i_j}))=2$
 255     \item Donc $u_0,u_1,u_2$ et $v$ doivent être vides !
 256     \end{itemize}
 257   \end{frame}
 258 }
 259
 260 \frameselect{true}{
 261   \begin{frame}
 262     \frametitle{Construction de CG équilibrés}
 263
 264     Comme $u_0,u_1,u_2$ et $v$ sont vides, on a :
 265     \begin{itemize}
 266     \item $u'(u_1,3,4) = (3,4)$
 267     \item $u'(u_2,4,3) = (4,3)$
 268     \item $U = (1,3,2,3,4,1,4,3,2)$
 269     \item $V= (v^R,N,v) = (4)$
 270     \item $W=(N-1,S_{N-2},N)=(3,1,2,1,2,4)$
 271     \item $W'=(w_2,w_1,W_{[3:]})=(1,3,2,1,2,4)$
 272     \item $S_{4} = (U^R, V, W')=(2,3,4,1,4,3,2,3,1,4,1,3,2,1,2,4)$
 273     \end{itemize}
 274     \begin{center}
 275       $\Rightarrow$ Fréquences = 4, 4, 4, 4
 276     \end{center}
 277   \end{frame}
 278 }
 279
 280 \frameselect{true}{
 281   \begin{frame}
 282     \frametitle{Algo de construction de CG équilibrés}
 283
 284     Une fois  déterminés les nombres d'occurrences  à placer dans les  $u_i$, il
 285     faut construire la séquence :
 286     \begin{itemize}
 287     \item Parcours exhaustif :
 288       \begin{itemize}
 289       \item [$\frownie$] Coûteux
 290       \item [$\smiley$] Produit tous les CG équilibrés atteignables par cette méthode
 291       \end{itemize}
 292     \item Algorithme glouton :
 293       \begin{itemize}
 294       \item Construction des $u_i$ dans l'ordre
 295       \item  Choix  glouton  pour  chaque  $u_i$ :\\
 296         sous-séquence  maximale  de  $S_{N-2}$   vérifiant  les  nombres  totaux
 297         d'occurrences déterminés pour les $u_i$
 298       \end{itemize}
 299     \item [$\frownie$] Ne produit pas tous les CGE possibles !
 300     \item [$\smiley$] Produit rapidement un CG pour n'importe quelle dimension !\\
 301       (à partir des dimensions 2 et 3)
 302     \end{itemize}
 303   \end{frame}
 304 }
 305
 306 \frameselect{true}{
 307   \begin{frame}
 308     \frametitle{Algo de construction de tous les CG équilibrés}
 309
 310     Algo basé sur la méthode de M.~Wild :
 311     \begin{itemize}
 312     \item Basé sur le principe d'exclusion
 313     \item Liste des arêtes du N-cube
 314     \item Chaque arête prend un état dans l'ensemble $\{0,1,2,g,d\}$ :
 315       \begin{itemize}
 316       \item 0 pour supprimée, 1 pour incluse, 2 pour indéterminé (initial)
 317       \item $g$ pour un ensemble d'arêtes dont une seule est incluse
 318       \item $d$ pour un ensemble d'arêtes dont deux sont incluses
 319       \end{itemize}
 320     \item Ajouts successifs des noeuds en appliquant :
 321       \begin{itemize}
 322       \item Condition locale (chaque noeud) : degré 2
 323       \item Conditions globales : \\
 324         cycle max : nb arêtes à 1 = nb sommets\\
 325         cycles inf : pas de cycles < nb sommets
 326       \item [$\Rightarrow$] élagage dès qu'une contrainte n'est pas vérifiée
 327       \end{itemize}
 328     \end{itemize}
 329   \end{frame}
 330 }
 331
 332 \frameselect{true}{
 333   \begin{frame}
 334     \frametitle{Adaptation au contexte de N-cube}
 335
 336     \begin{itemize}
 337     \item Ajout de la contrainte d'équilibre dans l'élagage
 338     \item Utilisation d'une forme canonique des CG :\\
 339       \begin{itemize}
 340       \item [$\Rightarrow$] Unicité des représentants
 341       \item [$\Rightarrow$] Ordre global sur les représentants :
 342         \begin{itemize}
 343         \item Détection efficace des doublons
 344         \item Stockage minimal
 345         \end{itemize}
 346       \end{itemize}
 347     \end{itemize}
 348   \end{frame}
 349 }
 350
 351 \frameselect{true}{
 352   \begin{frame}
 353     \frametitle{Forme canonique des CG}
 354
 355     \begin{itemize}
 356     \item Alignement sur début d'une sous-séquence avec \textbf{écart max} :
 357       \begin{itemize}
 358       \item Plus grand intervalle entre 2 occurrences d'une même dimension
 359       \end{itemize}
 360     \item Écart max sur l'ensemble des dimensions = \textbf{équilibre local}
 361     \item Renumérotation des dimensions :
 362       \begin{itemize}
 363       \item Affectation dans l'ordre croissant des n° \hfill$\Rightarrow$ débuts = (1,2)
 364       \item Équivalent à des isomorphismes du N-cube
 365       \item Donne un ordre global \hfill$\Rightarrow$ tri possible
 366       \end{itemize}
 367     \item Travaux en cours :
 368       \begin{itemize}
 369       \item Unicité de la forme canonique pour une classe d'isomorphismes
 370       \item Deux formes canoniques distinctes ne sont pas isomorphes
 371       \end{itemize}
 372     \end{itemize}
 373     \begin{center}
 374       $\Rightarrow$ Génération exhaustive en accord avec la théorie (dims $\le$ 5)
 375     \end{center}
 376   \end{frame}
 377 }
 378
 379 \end{document}