Rapport : corrections diverses, ajout des k-formules

Fri, 20 May 2011 01:38:24 +0200

author
Antoine Lubineau <antoine.lubineau@etu.enseeiht.fr>
date
Fri, 20 May 2011 01:38:24 +0200
changeset 8
43be9212b04e
parent 6
ccee2034ba11
child 9
484282a8bc80

Rapport : corrections diverses, ajout des k-formules

rapport/graphe-1.dot file | annotate | diff | revisions
rapport/graphe-2.dot file | annotate | diff | revisions
rapport/rapport.tex file | annotate | diff | revisions
     1.1 --- a/rapport/graphe-1.dot	Thu May 19 22:17:39 2011 +0200
     1.2 +++ b/rapport/graphe-1.dot	Fri May 20 01:38:24 2011 +0200
     1.3 @@ -2,4 +2,5 @@
     1.4  	root -> n1;
     1.5  	n1 -> n2;
     1.6  	n2 -> n1;
     1.7 +	n2 -> root;
     1.8  }
     2.1 --- a/rapport/graphe-2.dot	Thu May 19 22:17:39 2011 +0200
     2.2 +++ b/rapport/graphe-2.dot	Fri May 20 01:38:24 2011 +0200
     2.3 @@ -1,6 +1,7 @@
     2.4 -digraph exemple1 {
     2.5 -	root -> n1;
     2.6 -	n1 -> n2;
     2.7 -	n2 -> n1;
     2.8 -	n2 -> root;
     2.9 +digraph exemple2 {
    2.10 +	a -> b;
    2.11 +	a -> c;
    2.12 +	c -> a;
    2.13 +	c -> b;
    2.14 +	c -> c;
    2.15  }
     3.1 --- a/rapport/rapport.tex	Thu May 19 22:17:39 2011 +0200
     3.2 +++ b/rapport/rapport.tex	Fri May 20 01:38:24 2011 +0200
     3.3 @@ -58,44 +58,43 @@
     3.4  
     3.5  	\section{Recherche bibliographique}
     3.6  
     3.7 +		\textsc{Remarque:} dans l'ensemble de cette section, sauf mention contraire, les exemples de sérialisation donnés se rapportent à l'exemple suivant:
     3.8 +
     3.9 +		\begin{figure}[!h]
    3.10 +			\centering
    3.11 +			\includegraphics[width=0.5\linewidth]{arbre-1.pdf}
    3.12 +			\caption{Exemple d'arbre}
    3.13 +		\end{figure}
    3.14 +
    3.15  		\subsection{Matrice d'adjacence}
    3.16  
    3.17  		À 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.
    3.18  
    3.19 -		\begin{multicols}{2}
    3.20 +		\begin{figure}
    3.21 +		\[ \begin{pmatrix}
    3.22 +		0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\
    3.23 +		1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\
    3.24 +		0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
    3.25 +		0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
    3.26 +		0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
    3.27 +		0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
    3.28 +		1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
    3.29 +		0 & 0 & 0 & 0 & 0 & 0 & 1 & 0
    3.30 +		\end{pmatrix} \]
    3.31 +		\caption{Matrice d'adjacence du graphe d'exemple}
    3.32 +		\end{figure}
    3.33  
    3.34 -			\centering\includegraphics[width=0.7\linewidth]{arbre-1.pdf}
    3.35 -
    3.36 -			\columnbreak
    3.37 -
    3.38 -			\[ \begin{pmatrix}
    3.39 -			0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\
    3.40 -			1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\
    3.41 -			0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
    3.42 -			0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
    3.43 -			0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
    3.44 -			0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
    3.45 -			1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
    3.46 -			0 & 0 & 0 & 0 & 0 & 0 & 1 & 0
    3.47 -			\end{pmatrix} \]
    3.48 -
    3.49 -		\end{multicols}
    3.50 -
    3.51 -		Cette représentation est certainement la plus coûteuse en terme de mémoire ($n^2$ pointeurs).
    3.52 +		Cette représentation est certainement la plus coûteuse en terme de mémoire ($n^2$ pointeurs), mais toutes les opérations d'accès, d'ajout et de suppression d'arêtes peuvent se faire en temps constant. En revanche, l'ajout et la suppression d'un nœud sont des opérations lourds, même en utilisant une structure de données moins naïve qu'un simple tableau de tableaux.
    3.53  
    3.54  		\subsection{Liste de fils}
    3.55  
    3.56  		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.
    3.57  
    3.58 -		\begin{multicols}{2}
    3.59 -
    3.60 -			\centering\includegraphics[width=0.7\linewidth]{arbre-1.pdf}
    3.61 -
    3.62 -			\columnbreak
    3.63 -
    3.64 -			\includegraphics[width=\linewidth]{liste-fils.pdf}
    3.65 -
    3.66 -		\end{multicols}
    3.67 +		\begin{figure}[!h]
    3.68 +			\centering
    3.69 +			\includegraphics[width=0.7\linewidth]{liste-fils.pdf}
    3.70 +			\caption{Sérialisation avec des listes chaînées de fils}
    3.71 +		\end{figure}
    3.72  
    3.73  		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).
    3.74  
    3.75 @@ -104,6 +103,7 @@
    3.76  		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).
    3.77  
    3.78  		Avec le même exemple que précédemment, on obtient
    3.79 +		\begin{figure}
    3.80  		\begin{verbatim}
    3.81  [
    3.82    (root, n1),
    3.83 @@ -115,6 +115,8 @@
    3.84    (n6, n7)
    3.85  ]
    3.86  		\end{verbatim}
    3.87 +		\caption{Liste d'adjacence du graphe d'exemple}
    3.88 +		\end{figure}
    3.89  
    3.90  		\subsection{XML (et autres dérivés de SGML)}
    3.91  
    3.92 @@ -122,12 +124,8 @@
    3.93  
    3.94  		Voici un exemple de sérialisation XML d'un arbre. Les données utiles de chaque nœud pourraient être mises en attribut.
    3.95  
    3.96 -		\begin{multicols}{2}
    3.97 -
    3.98 -			\centering\includegraphics[width=0.7\linewidth]{arbre-1.pdf}
    3.99 -
   3.100 -			\columnbreak
   3.101 -
   3.102 +			\begin{figure}[!h]
   3.103 +			\centering
   3.104  			\begin{minted}{xml}
   3.105  <node id="root">
   3.106    <node id="n1">
   3.107 @@ -142,38 +140,56 @@
   3.108    </node>
   3.109  </node>
   3.110  			\end{minted}
   3.111 -
   3.112 -		\end{multicols}
   3.113 +			\caption{Sérialisation XML de l'arbre d'exemple}
   3.114 +		\end{figure}
   3.115  
   3.116  		On peut aussi sérialiser un graphe en établissant tout d'abord un arbre de recouvrement maximal du graphe: on obtient alors un arbre tel que précédemment. Ensuite, on rajoute les nœuds manquants au même niveau que le nœud racine, et les arêtes manquantes sont construites en ajoutant des attributs aux nœuds existants. Il n’y a donc pas unicité de la sérialisation.
   3.117  
   3.118  		\begin{multicols}{2}
   3.119  		
   3.120 -		\centering\includegraphics[width=0.4\linewidth]{graphe-1.pdf}
   3.121 +		\centering\includegraphics[width=0.6\linewidth]{graphe-1.pdf}
   3.122  
   3.123  		\columnbreak
   3.124  
   3.125  		\begin{minted}{xml}
   3.126  <node id="root">
   3.127    <node id="n1">
   3.128 -    <node id="n2" next="n1" />
   3.129 +    <node id="n2" next="n1,root" />
   3.130    </node>
   3.131  </node>
   3.132  		\end{minted}
   3.133 +		\end{multicols}
   3.134 +		
   3.135 +		On remarquera que XML est très «verbeux». Si on souhaite avoir une sérialisation textuelle plus compacte, on préférera YAML (\emph{YAML Ain't Markup Language}), ou un un sous-ensemble, JSON (\emph{JavaScript Object Notation}).
   3.136 +
   3.137 +		\subsection{K-formules}
   3.138 +
   3.139 +		Notation introduite en 1971 par Berztiss, les k-formules sont une notation permettant de représenter un graphe orienté par une chaîne de caractères, et donc de sérialiser un graphe. Pour un digraphe dont les nœuds sont désignés par $x$ et $y$, on a les propriétés suivantes:
   3.140 +		\begin{itemize}
   3.141 +			\item un symbole de nœud (par exemple $x$) est une k-formule;
   3.142 +			\item $*xy$ est une k-formule si et seulement si il existe une arête allant de $x$ à $y$;
   3.143 +			\item si $\alpha$ et $\beta$ sont des k-formules, alors $\alpha\beta$ est une k-formule si et seulement si il existe une arête reliant le premier nœud-symbole de $a$ à celui de $\beta$.
   3.144 +		\end{itemize}
   3.145 +
   3.146 +		\begin{multicols}{2}
   3.147 +
   3.148 +		\centering\includegraphics[width=0.6\linewidth]{graphe-2.pdf}
   3.149 +
   3.150 +		\columnbreak
   3.151 +
   3.152 +		K-formule associée au graphe ci-contre:
   3.153 +
   3.154 +		\verb|**ab***ccab|
   3.155  
   3.156  		\end{multicols}
   3.157  
   3.158 -
   3.159 -		\subsection{K-formules}\label{sub:kformules}
   3.160 -
   3.161 -		Notation introduite en 1971 par Berztiss, les k-formules sont une notation permettant de représenter un graphe orienté par une chaîne de caractères, et donc de sérialiser un graphe.
   3.162 -
   3.163  		L'occupation mémoire peut être jusqu'à deux fois inférieure à celle de la représentation par liste de paires d'adjacence.
   3.164  
   3.165  		\subsection{Chemins de Dyck}
   3.166  
   3.167 -		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:
   3.168 +		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 suit: horizontalement, chaque étape du parcours, et verticalement la profondeur courante.
   3.169  
   3.170 +		\begin{figure}[!h]
   3.171  		\begin{tikzpicture}
   3.172  			\draw[black!20] (-1,-1) grid (13,4);
   3.173  			\node[draw] at (0,0) (o0) {root};
   3.174 @@ -203,6 +219,8 @@
   3.175  			\draw (o10) -- (o11);
   3.176  			\draw (o11) -- (o12);
   3.177  		\end{tikzpicture}
   3.178 +		\caption{Parcours en profondeur de l'arbre d'exemple}
   3.179 +		\end{figure}
   3.180  
   3.181  		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.
   3.182  

mercurial