Avancement… (Il faudrait continuer la conclusion, mais je ne suis pas très inspiré)

Fri, 20 May 2011 12:32:09 +0200

author
Vincent Duvert <vincent.duvert@etu.enseeiht.fr>
date
Fri, 20 May 2011 12:32:09 +0200
changeset 11
f58b68722923
parent 10
08280bf887b3
child 12
b7266befe0ae

Avancement… (Il faudrait continuer la conclusion, mais je ne suis pas très inspiré)

rapport/rapport.tex file | annotate | diff | revisions
     1.1 --- a/rapport/rapport.tex	Fri May 20 01:45:26 2011 +0200
     1.2 +++ b/rapport/rapport.tex	Fri May 20 12:32:09 2011 +0200
     1.3 @@ -58,7 +58,7 @@
     1.4  		
     1.5  		Ce projet a pour but de présenter diverses manières d’effectuer la sérialisation d’un arbre ou d’un graphe, et d’implémenter l’une d’entre elles en TLA.
     1.6  		
     1.7 -		\subsection{Notations}
     1.8 +		%\subsection{Notations}
     1.9  
    1.10  	\newpage
    1.11  
    1.12 @@ -74,7 +74,7 @@
    1.13  
    1.14  		\subsection{Matrice d'adjacence}
    1.15  		
    1.16 -		À 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. \cite{mat_adj}
    1.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 les coefficients $1$ de la matrice peuvent être considérés comme des pointeurs vers celles-ci. \cite{mat_adj}
    1.18  
    1.19  		\begin{figure}
    1.20  		\[ \begin{pmatrix}
    1.21 @@ -126,7 +126,7 @@
    1.22  
    1.23  		\subsection{XML (et autres dérivés de SGML)}
    1.24  
    1.25 -		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}.
    1.26 +		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}. XML peut être utilisé pour sérialiser des données \cite{serial_xml}.
    1.27  
    1.28  		Voici un exemple de sérialisation XML d'un arbre. Les données utiles de chaque nœud pourraient être mises en attribut.
    1.29  
    1.30 @@ -189,7 +189,7 @@
    1.31  
    1.32  		\end{multicols}
    1.33  
    1.34 -		L'occupation mémoire peut être jusqu'à deux fois inférieure à celle de la représentation par liste de paires d'adjacence.
    1.35 +		Cette représentation peut être considérée comme une forme de compression d’une liste de paires d’adjacence; par rapport à celles-ci, l'occupation mémoire peut être jusqu'à deux fois inférieure. \cite{k-formule}
    1.36  
    1.37  		\subsection{Chemins de Dyck}
    1.38  
    1.39 @@ -235,13 +235,52 @@
    1.40  	\newpage
    1.41  
    1.42  	\section{Développement par raffinement}
    1.43 +	Nous avons décider de développer la méthode des liste de paires d’adjacence
    1.44 +	en TLA, afin de vérifier qu’elle raffine bien un graphe quelconque.
    1.45 +	
    1.46 +	Les paires d’adjacence sont des tuples, elle-mêmes placées dans une \texttt{Sequence}.
    1.47 +	
    1.48 +	\begin{itemize}
    1.49 +		\item Pour créer un nœud $y$ d’arité $n$ fils du nœud $x$, on ajoute à la séquence, $n$ fois, le tuple $\langle x, \texttt{UNDEF} \rangle$ (\texttt{UNDEF} représentant une arête ne menant temporairement nulle part). On modifie ensuite une des paires libres représentant les nœuds fils de $x$ pour y placer $y$ (voir plus loin).
    1.50 +		
    1.51 +		\item Pour obtenir un fils du nœud $x$, de numéro $o$, on parcourt de manière récursive la liste des paires:
    1.52 +		\begin{itemize}
    1.53 +			\item Si on trouve $\langle x, y \rangle$ et que $o = 1$, on renvoie $y$.
    1.54 +			\item Si on trouve $\langle x, \_ \rangle$ et que $o > 1$, on continue la recherche dans la suite de la liste (appel par récurrence) en prenant $o \leftarrow o - 1$.
    1.55 +			\item Sinon, on continue la recherche dans la suite de la liste (appel par récurrence) sans modifier $o$.
    1.56 +		\end{itemize}
    1.57 +		Les préconditions sont:
    1.58 +		\begin{itemize}
    1.59 +			\item $x$ est bien un nœud du graphe
    1.60 +			\item $x$ a bien au moins $o$ fils
    1.61 +			\item L’arête numéro $o$ partant de $x$ n’est pas \texttt{UNDEF}
    1.62 +		\end{itemize}
    1.63 +		
    1.64 +		\item Pour ajouter le nœud $y$ comme fils numéro $o$ du nœud $x$, on procède de manière analogue à la recherche de fils, par parcours de liste:
    1.65 +		\begin{itemize}
    1.66 +			\item Si on trouve $\langle x, \texttt{UNDEF}  \rangle$ et que $o = 1$, on renvoie $\langle x, y \rangle$ accolé à la suite de la liste.
    1.67 +			\item Si on trouve $\langle x, \_ \rangle$ et que $o > 1$, on effectue l’ajout dans la suite de la liste (appel par récurrence) en prenant $o \leftarrow o - 1$ puis on renvoie l’élément courant accolé au résultat de l’ajout.
    1.68 +			\item Sinon, on effectue l’ajout dans la suite de la liste (appel par récurrence) sans modifier $o$, puis on renvoie l’élément courant accolé au résultat de l’ajout.
    1.69 +		\end{itemize}
    1.70 +		
    1.71 +		Les préconditions sont:
    1.72 +		\begin{itemize}
    1.73 +			\item $x$ est bien un nœud du graphe
    1.74 +			\item $x$ a bien au moins $o$ fils
    1.75 +			\item L’arête numéro $o$ partant de $x$ est \texttt{UNDEF}
    1.76 +		\end{itemize}
    1.77 +	\end{itemize}
    1.78  	
    1.79  	\section{Conclusion}
    1.80 +	Les méthodes de sérialisation de données sont nombreuses et adaptées aux différents besoins: Nécessité de représenter des graphes quelconques, d’une représentation la plus compacte possible, ou lisible par un humain…
    1.81  
    1.82  	\begin{thebibliography}{9}
    1.83  	\bibitem{serialisation} \url{http://fr.wikipedia.org/wiki/Sérialisation}
    1.84 +	\bibitem{arbres_enracines} \url{http://fr.wikipedia.org/wiki/Arbre_enraciné}
    1.85  	\bibitem{graphes_orientes} \url{http://fr.wikipedia.org/wiki/Graphe_orienté}
    1.86  	\bibitem{mat_adj} \url{http://fr.wikipedia.org/wiki/Matrice_d%27adjacence}
    1.87  	\bibitem{liste_adj} \url{http://en.wikipedia.org/wiki/Adjacency_list}
    1.88 +	\bibitem{serial_xml} \url{http://msdn.microsoft.com/en-us/library/182eeyhh(v=vs.71).aspx}
    1.89 +	\bibitem{k-formule} \url{http://comjnl.oxfordjournals.org/content/19/4/326.full.pdf#page=1&view=FitH}
    1.90  	\end{thebibliography}
    1.91  \end{document}

mercurial