merge

Sun, 15 May 2011 19:41:41 +0200

author
Vincent Duvert <vincent.duvert@etu.enseeiht.fr>
date
Sun, 15 May 2011 19:41:41 +0200
changeset 4
a5339dbcaac8
parent 3
92fd258fe14c
parent 2
ddac91e1f761
child 5
8a42bdc479a6

merge

     1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/rapport/Makefile	Sun May 15 19:41:41 2011 +0200
     1.3 @@ -0,0 +1,23 @@
     1.4 +all: rapport.pdf
     1.5 +
     1.6 +rapport.pdf: rapport.tex arbre-1.pdf graphe-1.pdf graphe-2.pdf
     1.7 +
     1.8 +arbre-1.pdf: arbre-1.dot
     1.9 +graphe-1.pdf: graphe-1.dot
    1.10 +graphe-2.pdf: graphe-2.dot
    1.11 +
    1.12 +%.pdf: %.tex
    1.13 +	xelatex -shell-escape $<
    1.14 +	xelatex -shell-escape $<
    1.15 +
    1.16 +%.pdf: %.dot
    1.17 +	dot -Tpdf $< > $*.pdf
    1.18 +
    1.19 +%.pdf: %.dia
    1.20 +	dia $< -t pdf -e $*.pdf
    1.21 +
    1.22 +clean:
    1.23 +	rm -f *.{log,aux,toc,bib,pyg}
    1.24 +
    1.25 +mrproper: clean
    1.26 +	rm -f *.pdf
     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/rapport/arbre-1.dot	Sun May 15 19:41:41 2011 +0200
     2.3 @@ -0,0 +1,9 @@
     2.4 +graph exemble_arbre {
     2.5 +	root -- n1;
     2.6 +	n1 -- n2;
     2.7 +	n1 -- n3;
     2.8 +	n3 -- n4;
     2.9 +	n3 -- n5;
    2.10 +	root -- n6;
    2.11 +	n6 -- n7;
    2.12 +}
     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/rapport/graphe-1.dot	Sun May 15 19:41:41 2011 +0200
     3.3 @@ -0,0 +1,5 @@
     3.4 +digraph exemple1 {
     3.5 +	root -> n1;
     3.6 +	n1 -> n2;
     3.7 +	n2 -> n1;
     3.8 +}
     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/rapport/graphe-2.dot	Sun May 15 19:41:41 2011 +0200
     4.3 @@ -0,0 +1,6 @@
     4.4 +digraph exemple1 {
     4.5 +	root -> n1;
     4.6 +	n1 -> n2;
     4.7 +	n2 -> n1;
     4.8 +	n2 -> root;
     4.9 +}
     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/rapport/rapport.tex	Sun May 15 19:41:41 2011 +0200
     5.3 @@ -0,0 +1,153 @@
     5.4 +\documentclass{article}
     5.5 +
     5.6 +\usepackage[
     5.7 +	a4paper
     5.8 +]{geometry}
     5.9 +
    5.10 +\usepackage{ifpdf}
    5.11 +
    5.12 +% Choix des packages de langue et de fonte
    5.13 +\ifpdf % si pdfLaTeX
    5.14 +	\usepackage[french]{babel}
    5.15 +	\usepackage[utf8]{inputenc}
    5.16 +	\usepackage{lmodern}
    5.17 +	\usepackage{textcomp}
    5.18 +\else % si XeLaTeX
    5.19 +	\usepackage{polyglossia}
    5.20 +	\setdefaultlanguage{french}
    5.21 +	\usepackage{xunicode,xltxtra}
    5.22 +	\usepackage{fontspec}
    5.23 +	\defaultfontfeatures{Mapping=tex-text,Scale=MatchLowercase}
    5.24 +	\setmainfont{Linux Libertine O}
    5.25 +\fi
    5.26 +
    5.27 +\usepackage{multicol}
    5.28 +\usepackage{graphicx}
    5.29 +\usepackage{minted}
    5.30 +\usepackage{textcomp}
    5.31 +\usepackage{amsmath}
    5.32 +
    5.33 +\title{{\itshape\large Spécification formelle et validation}\\ Sérialisation de structures de données}
    5.34 +\author{Vincent Duvert \and Antoine Lubineau}
    5.35 +\date{\today}
    5.36 +
    5.37 +\begin{document}
    5.38 +
    5.39 +	\maketitle
    5.40 +	
    5.41 +	\begin{abstract}
    5.42 +		
    5.43 +	\end{abstract}
    5.44 +
    5.45 +	\vfill
    5.46 +	
    5.47 +	\tableofcontents
    5.48 +
    5.49 +	\newpage
    5.50 +
    5.51 +	\section{Introduction}
    5.52 +
    5.53 +
    5.54 +
    5.55 +		\subsection{Notations}
    5.56 +
    5.57 +	\newpage
    5.58 +
    5.59 +	\section{Recherche bibliographique}
    5.60 +
    5.61 +		\subsection{Matrice d'adjacence}
    5.62 +
    5.63 +		À 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.
    5.64 +
    5.65 +		\begin{multicols}{2}
    5.66 +
    5.67 +			\centering\includegraphics[width=0.6\linewidth]{arbre-1.pdf}
    5.68 +
    5.69 +			\columnbreak
    5.70 +
    5.71 +			\[ \begin{pmatrix}
    5.72 +			0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 \\
    5.73 +			1 & 0 & 1 & 1 & 0 & 0 & 0 & 0 \\
    5.74 +			0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\
    5.75 +			0 & 1 & 0 & 0 & 1 & 1 & 0 & 0 \\
    5.76 +			0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
    5.77 +			0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\
    5.78 +			1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \\
    5.79 +			0 & 0 & 0 & 0 & 0 & 0 & 1 & 0
    5.80 +			\end{pmatrix} \]
    5.81 +
    5.82 +		\end{multicols}
    5.83 +
    5.84 +		Cette représentation est certainement la plus coûteuse en terme de mémoire.
    5.85 +
    5.86 +		\subsection{Liste de fils}
    5.87 +
    5.88 +		% exemple d'un arbre
    5.89 +
    5.90 +		\subsection{Liste de paires d'adjacence}
    5.91 +
    5.92 +		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).
    5.93 +
    5.94 +		% exemple
    5.95 +		
    5.96 +		\subsection{XML (et autres dérivés de SGML)}
    5.97 +
    5.98 +		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}.
    5.99 +
   5.100 +		Voici un exemple de sérialisation XML d'un arbre. Les données utiles de chaque nœud pourraient être mises en attribut.
   5.101 +
   5.102 +		\begin{multicols}{2}
   5.103 +
   5.104 +			\centering\includegraphics[width=0.7\linewidth]{arbre-1.pdf}
   5.105 +
   5.106 +			\columnbreak
   5.107 +
   5.108 +			\begin{minted}{xml}
   5.109 +<node id="root">
   5.110 +  <node id="n1">
   5.111 +    <node id="n2" />
   5.112 +      <node id="n3">
   5.113 +        <node id="n4" />
   5.114 +        <node id="n5" />
   5.115 +      </node>
   5.116 +    </node>
   5.117 +    <node id="n6">
   5.118 +      <node id="n7" />
   5.119 +  </node>
   5.120 +</node>
   5.121 +			\end{minted}
   5.122 +
   5.123 +		\end{multicols}
   5.124 +
   5.125 +		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.
   5.126 +
   5.127 +		\begin{multicols}{2}
   5.128 +		
   5.129 +		\centering\includegraphics[width=0.4\linewidth]{graphe-1.pdf}
   5.130 +
   5.131 +		\columnbreak
   5.132 +
   5.133 +		\begin{minted}{xml}
   5.134 +<node id="root">
   5.135 +  <node id="n1">
   5.136 +    <node id="n2" next="n1" />
   5.137 +  </node>
   5.138 +</node>
   5.139 +		\end{minted}
   5.140 +
   5.141 +		\end{multicols}
   5.142 +
   5.143 +
   5.144 +		\subsection{K-formules}\label{sub:kformules}
   5.145 +
   5.146 +		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.
   5.147 +
   5.148 +		L'occupation mémoire peut être jusqu'à deux fois inférieure à celle de la représentation par liste de paires d'adjacence.
   5.149 +
   5.150 +		\subsection{Autres possibilités}
   5.151 +
   5.152 +	\section{Développement par raffinement}
   5.153 +	
   5.154 +	\section{Conclusion}
   5.155 +
   5.156 +\end{document}

mercurial