From 79f46c777f6ef3202c2fb25194822518cad3e32c Mon Sep 17 00:00:00 2001 From: Sylvain C-V Date: Tue, 6 Dec 2016 16:13:50 +0100 Subject: [PATCH 1/1] =?utf8?q?Ajout=20diapos=20pr=C3=A9sentation=20PRNG?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- presPRNG.tex | 379 +++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 379 insertions(+) create mode 100644 presPRNG.tex diff --git a/presPRNG.tex b/presPRNG.tex new file mode 100644 index 0000000..bbb82e9 --- /dev/null +++ b/presPRNG.tex @@ -0,0 +1,379 @@ +\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} -- 2.39.5