Le rapport avance.

Thu, 19 May 2011 21:58:38 +0200

author
Antoine Lubineau <antoine.lubinea@etu.enseeiht.fr>
date
Thu, 19 May 2011 21:58:38 +0200
changeset 5
8a42bdc479a6
parent 4
a5339dbcaac8
child 6
ccee2034ba11

Le rapport avance.

rapport/Makefile file | annotate | diff | revisions
rapport/rapport.tex file | annotate | diff | revisions
     1.1 --- a/rapport/Makefile	Sun May 15 19:41:41 2011 +0200
     1.2 +++ b/rapport/Makefile	Thu May 19 21:58:38 2011 +0200
     1.3 @@ -1,17 +1,18 @@
     1.4  all: rapport.pdf
     1.5  
     1.6 -rapport.pdf: rapport.tex arbre-1.pdf graphe-1.pdf graphe-2.pdf
     1.7 +rapport.pdf: rapport.tex arbre-1.pdf graphe-1.pdf graphe-2.pdf liste-fils.pdf
     1.8  
     1.9  arbre-1.pdf: arbre-1.dot
    1.10  graphe-1.pdf: graphe-1.dot
    1.11  graphe-2.pdf: graphe-2.dot
    1.12 +liste-fils.pdf: liste-fils.dot
    1.13  
    1.14  %.pdf: %.tex
    1.15  	xelatex -shell-escape $<
    1.16  	xelatex -shell-escape $<
    1.17  
    1.18  %.pdf: %.dot
    1.19 -	dot -Tpdf $< > $*.pdf
    1.20 +	dot -Tpdf $< > $*.pdf || true
    1.21  
    1.22  %.pdf: %.dia
    1.23  	dia $< -t pdf -e $*.pdf
     2.1 --- a/rapport/rapport.tex	Sun May 15 19:41:41 2011 +0200
     2.2 +++ b/rapport/rapport.tex	Thu May 19 21:58:38 2011 +0200
     2.3 @@ -15,6 +15,7 @@
     2.4  \else % si XeLaTeX
     2.5  	\usepackage{polyglossia}
     2.6  	\setdefaultlanguage{french}
     2.7 +	\setotherlanguage{english}
     2.8  	\usepackage{xunicode,xltxtra}
     2.9  	\usepackage{fontspec}
    2.10  	\defaultfontfeatures{Mapping=tex-text,Scale=MatchLowercase}
    2.11 @@ -26,9 +27,10 @@
    2.12  \usepackage{minted}
    2.13  \usepackage{textcomp}
    2.14  \usepackage{amsmath}
    2.15 +\usepackage{tikz}
    2.16  
    2.17  \title{{\itshape\large Spécification formelle et validation}\\ Sérialisation de structures de données}
    2.18 -\author{Vincent Duvert \and Antoine Lubineau}
    2.19 +\author{Vincent \textsc{Duvert} \and Sanaa \textsc{Essaid} \and Antoine \textsc{Lubineau}}
    2.20  \date{\today}
    2.21  
    2.22  \begin{document}
    2.23 @@ -47,6 +49,7 @@
    2.24  
    2.25  	\section{Introduction}
    2.26  
    2.27 +		\subsection{Méthodes de sérialisation}
    2.28  
    2.29  
    2.30  		\subsection{Notations}
    2.31 @@ -57,11 +60,11 @@
    2.32  
    2.33  		\subsection{Matrice d'adjacence}
    2.34  
    2.35 -		À tout graphe, orienté ou non, on peut associer une matrice d'adjacence qui décrit complètement les \emph{relations} entre les nœuds (à condition qu'il n'y ait pas plus d'une arête orientée ayant les mêmes extrémités). On ne spécifie pas comment désigner la données associée à chaque nœud, mais $\times$ peut être un pointeur sur celle-ci.
    2.36 +		À tout graphe, orienté ou non, on peut associer une matrice d'adjacence qui décrit complètement les \emph{relations} entre les nœuds (à condition qu'il n'y ait pas plus d'une arête orientée ayant les mêmes extrémités). On ne spécifie pas comment désigner la données associée à chaque nœud, mais $1$ peut être un pointeur sur celle-ci.
    2.37  
    2.38  		\begin{multicols}{2}
    2.39  
    2.40 -			\centering\includegraphics[width=0.6\linewidth]{arbre-1.pdf}
    2.41 +			\centering\includegraphics[width=0.7\linewidth]{arbre-1.pdf}
    2.42  
    2.43  			\columnbreak
    2.44  
    2.45 @@ -78,18 +81,41 @@
    2.46  
    2.47  		\end{multicols}
    2.48  
    2.49 -		Cette représentation est certainement la plus coûteuse en terme de mémoire.
    2.50 +		Cette représentation est certainement la plus coûteuse en terme de mémoire ($n^2$ pointeurs).
    2.51  
    2.52  		\subsection{Liste de fils}
    2.53  
    2.54 -		% exemple d'un arbre
    2.55 +		Ici on stocke un tableau avec tous les nœuds du graphe, et à chaque nœud est associée une liste chaînée contenant des pointeurs sur tous les enfants de ce nœud.
    2.56 +
    2.57 +		\begin{multicols}{2}
    2.58 +
    2.59 +			\centering\includegraphics[width=0.7\linewidth]{arbre-1.pdf}
    2.60 +
    2.61 +			\columnbreak
    2.62 +
    2.63 +			\includegraphics[width=\linewidth]{liste-fils.pdf}
    2.64 +
    2.65 +		\end{multicols}
    2.66 +
    2.67 +		Les listes d'adjacence peuvent être stockées successivement, à la suite du tableau des nœuds, par exemple. L'occupation mémoire est de $n + 2p$ pointeurs, donc bien plus intéressante que la précédente. De plus les listes chaînes permettent facilement d'ajouter et de supprimer des nœud (on préférera modéliser l'ensemble des nœuds par une liste chaînée, et l'occupation mémoire sera alors de $2n + 2p$ pointeurs).
    2.68  
    2.69  		\subsection{Liste de paires d'adjacence}
    2.70  
    2.71  		Cette méthode de sérialisation est très simple: on liste toutes les relations du graphe, et on écrit pour chacune les deux sommets associés (on peut se baser sur l'ordre pour indiquer le sens d'une relation).
    2.72  
    2.73 -		% exemple
    2.74 -		
    2.75 +		Avec le même exemple que précédemment, on obtient
    2.76 +		\begin{verbatim}
    2.77 +[
    2.78 +  (root, n1),
    2.79 +  (root, n6),
    2.80 +  (n1, n2),
    2.81 +  (n1, n3),
    2.82 +  (n3, n4),
    2.83 +  (n3, n5),
    2.84 +  (n6, n7)
    2.85 +]
    2.86 +		\end{verbatim}
    2.87 +
    2.88  		\subsection{XML (et autres dérivés de SGML)}
    2.89  
    2.90  		XML (\begin{english}\emph{Extensible Markup Language}\end{english}) est un langage de la famille de SGML, conçu pour stocker et transférer des données textuelles.  Le langage peut être adapté à l'aide de \emph{schémas}.
    2.91 @@ -144,7 +170,43 @@
    2.92  
    2.93  		L'occupation mémoire peut être jusqu'à deux fois inférieure à celle de la représentation par liste de paires d'adjacence.
    2.94  
    2.95 -		\subsection{Autres possibilités}
    2.96 +		\subsection{Chemins de Dyck}
    2.97 +
    2.98 +		On réalise un parcours en profondeur de l'arbre, et à chaque changement de nœud, on note \verb|+1| si la profondeur augmente et \verb|-1| si elle diminue. Ce parcours peut être représenté comme ceci:
    2.99 +
   2.100 +		\begin{tikzpicture}
   2.101 +			\draw[black!20] (-1,-1) grid (13,4);
   2.102 +			\node[draw] at (0,0) (o0) {root};
   2.103 +			\node[draw] at (1,1) (o1) {n1};
   2.104 +			\node[draw] at (2,2) (o2) {n2};
   2.105 +			\node[draw] at (3,1) (o3) {n1};
   2.106 +			\node[draw] at (4,2) (o4) {n3};
   2.107 +			\node[draw] at (5,3) (o5) {n4};
   2.108 +			\node[draw] at (6,2) (o6) {n3};
   2.109 +			\node[draw] at (7,3) (o7) {n5};
   2.110 +			\node[draw] at (8,2) (o8) {n3};
   2.111 +			\node[draw] at (9,1) (o9) {n1};
   2.112 +			\node[draw] at (10,0) (o10) {root};
   2.113 +			\node[draw] at (11,1) (o11) {n6};
   2.114 +			\node[draw] at (12,2) (o12) {n7};
   2.115 +			\draw (o0) -- (o1);
   2.116 +			\draw (o1) -- (o2);
   2.117 +			\draw (o2) -- (o3);
   2.118 +			\draw (o3) -- (o4);
   2.119 +			\draw (o4) -- (o5);
   2.120 +			\draw (o5) -- (o6);
   2.121 +			\draw (o6) -- (o7);
   2.122 +			\draw (o7) -- (o8);
   2.123 +			\draw (o8) -- (o9);
   2.124 +			\draw (o8) -- (o9);
   2.125 +			\draw (o9) -- (o10);
   2.126 +			\draw (o10) -- (o11);
   2.127 +			\draw (o11) -- (o12);
   2.128 +		\end{tikzpicture}
   2.129 +
   2.130 +		Une sérialisation possible de cet arbre est \verb|[ +2, -1, +2, -1, +1, -3, +2 ]|. Cette liste comporte autant de nœuds qu’il y a de sommets, ce qui est l'occupation mémoire optimale pour un graphe.
   2.131 +
   2.132 +		Un inconvénient de cette méthode est qu'elle ne s'applique qu'aux arbres.
   2.133  
   2.134  	\section{Développement par raffinement}
   2.135  	

mercurial