\input{../.headers/cours.tex}

\baselineskip15pt

\begin{center}
\shadowbox{\LARGE \bf \textsc{\supline Structures de donn\'ees abstraites\subline}}\\
\end{center}

\section{Structure de donn\'ees}

\dfn[Structure de donn\'ee]
Une structure de donn\'ees est un type muni d'op\'erations.
\nfd

\exs
Les listes cha\^in\'ees et les tableaux constituent deux exemples de structures de donn\'ees.\\
Elles jouent cependant un r\^ole \`a part car ce sont des structures de donn\'ees de tr\`es bas niveau.\\
Voyons n\'eanmoins comment on pourrait les expliciter.
\begin{itemize}
\item Pour la structure "liste cha\^in\'ee", les op\'erations sont~:
\begin{enumerate}
\item \texttt{nil}~: cr\'eer une liste vide~;
\item \texttt{cons}~: cr\'eer une liste \`a partir d'une t\^ete et d'une queue~;
\item \texttt{tete}~: obtenir la t\^ete d'une liste~;
\item \texttt{queue}~: obtenir la queue d'une liste.
\end{enumerate}
\item Pour la structure "tableau", les op\'erations sont~:
\begin{enumerate}
\item \texttt{initialiser}~: cr\'eer un tableau de longueur donn\'ee~;
\item \texttt{longueur}~: obtenir la longueur du tableau~;
\item \texttt{acceder}~: obtenir l'\'el\'ement d'indice donn\'e du tableau~;
\item \texttt{modifier}~: modifier l'\'el\'ement d'indice donn\'e du tableau.
\end{enumerate}
\end{itemize}
\sxe


\exx\ \\
Vous avez essentiellement impl\'ement\'e la structure de donn\'ees "polyn\^ome" en TP d'informatique de tronc commun. Cette impl\'ementation repose sur la repr\'esentation dense des polyn\^omes.\\[-0.2cm]
%Vous avez essentiellement impl\'ement\'e la structure de donn\'ees "polyn\^ome" dans l'exercice 4 du concours blanc. Cette impl\'ementation repose sur le repr\'esentation creuse des polyn\^omes.
\xxe

%\bigskip

On retient d\'ej\`a~:

\rmq \uuline{Il n'y a pas unicit\'e de l'impl\'ementation} d'une structure de donn\'ees.
\qmr

\bigskip

\dfn
Une structure de donn\'ees est dite modifiable (ou imp\'erative) lorsque ses objets peuvent \^etre modifi\'es en place par les op\'erations de la structure.\\[0.15cm]
Une structure de donn\'ees est dite persistante (ou immuable) lorsque ses op\'erations ne la modifient pas en place (mais peuvent renvoyer nouvelles instances de la structure).
\nfd

\textit{A priori}, {\bf toutes les structures de donn\'ees se d\'eclinent en deux variantes}, une modifiable et une persistante.

\newpage
\section{Les structures de donn\'ees du programme}

%Chacune des structures de donn\'ees que l'on va voir ici pourraient exister, en tant que variantes, en version persistante ou en version immuable.\\
%Ceci m'oblige \`a ne pas donner pr\'ecis\'ement les types des op\'erations dans les exemples qui suivent pour englober les deux cas.

\subsection{Arbres}

On les a d\'ej\`a vus. Les op\'erations sont~:
\begin{enumerate}
\item \texttt{creer\_feuille}~: cr\'ee un arbre compos\'ee d'une seule feuille~;
\item \texttt{creer\_n\oe ud}~: cr\'ee un arbre compos\'ee d'un n\oe ud, 'un fils gauche et d'un fils droit~;
\item \texttt{fils\_gauche}~: retourne le fils gauche de l'arbre~;
\item \texttt{fils\_droit}~: retourne le fils droit de l'arbre~;
\item \texttt{etiquette}~: retourne l'\'etiquette du n\oe ud de l'arbre, ou de sa feuille si c'est une feuille.\\[-0.2cm]
\end{enumerate}
%Les arbres de Caml sont \unepetiteligne\\%[0.2cm]
%
%Cela donne les signatures suivantes~: \\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\


\subsection{Piles}

C'est le type des piles d'assiettes qui s'accumulent \`a c\^ot\'e de l'\'evier en attendant d'\^etre lav\'ees. C'est une structure LIFO (last in first out).\\

Exemples d'utilisation de pile en informatique~:
\begin{itemize}
	\item Pile d'appels d'un runtime
	\item Analyse syntaxique (parsers)
\end{itemize}

\medskip

Les op\'erations sont~:
\begin{enumerate}
\item \texttt{creer\_pile\_vide}~: cr\'eer une pile vide~;
\item \texttt{est\_vide}~: teste si une pile est vide~;
\item \texttt{empiler}~: ajoute un \'el\'ement sur le sommet de la pile~;
\item \texttt{d\'epiler}~: enl\`eve l\'el\'ement du sommet de la pile et le retourne.
\end{enumerate}

Deux variantes pour d\'eplier~: on peut avoir une structure modifiable et d\'epiler modifie la pile, ou bien une structure persistante et d\'epiler retourne le couple (\'el\'ement au sommet, pile restante) ou bien se d\'ecline en deux op\'erations.\\%\\[0.2cm]

Cela donne les signatures suivantes~:\\[0.2cm]

%\begin{tabular*}{20cm}{c|cc}
%\begin{minipage}{9cm}
%\phantom{Espace\\[-0.4cm]}
%Pour la version immuable~:\\[0.4cm]
%creer\_pile\_vide~: unit $\rightarrow$ 'a pile\\[0.2cm]
%est\_vide~: 'a pile $\rightarrow$ bool\\[0.2cm]
%empiler~: 'a $\rightarrow$ 'a pile $\rightarrow$ 'a pile\\[0.2cm]
%d\'epiler~: 'a pile $\rightarrow$ 'a * 'a pile\\[0.2cm]
%\end{minipage} &
%\begin{minipage}{2cm}
%\phantom{Espace}
%\end{minipage} &
%\begin{minipage}{9cm}
%\phantom{Espace\\[-0.4cm]}
%Pour la version imp\'erative~:\\[0.4cm]
%creer\_pile\_vide~: unit $\rightarrow$ 'a pile\\[0.2cm]
%est\_vide~: 'a pile $\rightarrow$ bool\\[0.2cm]
%empiler~: 'a $\rightarrow$ 'a pile $\rightarrow$ unit\\[0.2cm]
%d\'epiler~: 'a pile $\rightarrow$ 'a\\[0.2cm]
%\end{minipage}
%\end{tabular*}\\[0.2cm]


\begin{tabular*}{20cm}{cc}
\begin{minipage}{9cm}
Pour la version immuable~:\\[0.2cm]
\begin{description}
	\item[\ocaml{creer_liste_vide}]: \ocaml{unit -> 'a pile}
	\item[\ocaml{est_vide}]: \ocaml{'a pile -> bool} 
	\item[\ocaml{empiler}]: \ocaml{'a -> 'a pile -> 'a pile} 
	\item[\ocaml{dépiler}]: \ocaml{'a pile -> 'a * 'a pile} 
\end{description}
\end{minipage}&
\begin{minipage}{9cm}
Pour la version imp\'erative~:\\[0.2cm]
\begin{description}
	\item[\ocaml{creer_liste_vide}]: \ocaml{unit -> 'a pile}
	\item[\ocaml{est_vide}]: \ocaml{'a pile -> bool} 
	\item[\ocaml{empiler}]: \ocaml{'a -> 'a pile -> unit} 
	\item[\ocaml{dépiler}]: \ocaml{'a pile -> 'a} 
\end{description}
\end{minipage}
\end{tabular*}\\[0.2cm]


\rmq
Les piles immuables ne sont autre que \unemicroligne %les listes cha\^in\'ees~!
\qmr
\newpage


\subsection{Files}

C'est le type des files d'attente. C'est une structure FIFO (first in first out).\\

Exemples d'utilisation de file en informatique~:
\\[0.1cm]\uneligne\\
\begin{itemize}[$\bullet$]
\item file d'attente d'impression pour une imprimante partag\'ee (ou pas)~;
\item impl\'ementation efficace d'un parcours en largeur~;
\item $\ldots$
\end{itemize}

\medskip

Les op\'erations sont~:
\begin{enumerate}
\item \texttt{creer\_file\_vide}~: cr\'eer une file vide~;
\item \texttt{est\_vide}~: teste si une file est vide~;
\item \texttt{enfiler}~: ajoute un \'el\'ement \`a la fin de la file~;
\item \texttt{d\'efiler}~: enl\`eve l\'el\'ement du d\'ebut de la file et le retourne.
\end{enumerate}
Deux variantes pour d\'eflier~: on peut avoir une structure modifiable et d\'efiler modifie la file, ou bien une structure persistante et d\'efiler retourne le couple, ou se d\'ecline en deux op\'erations.\\%\\

\exo \'Ecrire les types pr\'ecis de toutes les op\'erations pour chaque version.\bigsubline %\\

%\rmq
%Pour l'impl\'ementation des files, on verra en TP deux m\'ethodes~: en utilisant un tableau circulaire, ou en utilisant deux listes cha\^in\'ees.
%\qmr

\subsection{Files de priorit\'e}

C'est le type des choses-\`a-faire. Chaque chose \`a faire vient avec une date \`a laquelle elle doit \^etre faite et on traite prioritairement les choses \`a faire les plus urgentes.\\


Les op\'erations sont~:
\begin{enumerate}
\item \texttt{creer\_fp\_vide}~: cr\'eer une file de priorit\'e vide~;
\item \texttt{est\_vide}~: teste si une file de priorit\'e est vide~;
\item \texttt{inserer}~: ajoute un \'el\'ement (avec sa priorit\'e) \`a la file de priorit\'e~;
\item \texttt{retire\_prioritaire}~: retire un \'el\'ement avec la plus grande priorit\'e et le retourne.
\end{enumerate}
L\`a encore, deux variantes pour la derni\`ere op\'eration.\\[0.2cm]

\exo \'Ecrire les types pr\'ecis de toutes les op\'erations pour chaque version.\\

%\rmq
%Pour l'impl\'ementation des files de priorit\'e, on peut utiliser \unemicroligne.
%\qmr



\subsection{Dictionnaires (ou tableaux associatifs)}

C'est la structure vue en Python. \`A chaque cl\'e est associ\'ee une valeur.\\

Les op\'erations sont~:
\begin{enumerate}
\item \texttt{creer\_dico\_vide}~: cr\'eer une file de priorit\'e vide~;
\item \texttt{est\_vide}~: teste si une file de priorit\'e est vide~;
\item \texttt{inserer}~: ajoute un couple (cl\'e,valeur) au dictionnaire~;
\item \texttt{supprimer}~: retire un couple (cl\'e,valeur) au dictionnaire~;
\item \texttt{modifier}~: modifie la valeur d'une cl\'e.;
\item \texttt{accéder}~: accéder à une valeur à partir d'une cl\'e.;
\item \texttt{a\_clé}~: tester si une clé est dans le dictionnaiare;
\end{enumerate}

\exo \'Ecrire les types pr\'ecis de toutes les op\'erations pour les versions imp\'erative et modifiable.\megasubline

%\rmq On a d\'ej\`a impl\'ement\'e la version modifiable en utilisant des arbres binaires de recherche, mais c'est seulement au programme en seconde ann\'ee. Si tout va bien, on verra aussi une impl\'ementation de la version imp\'erative en TP~: les {\bf tables de hachage}.\megasubline
%\qmr


\section{Impl\'ementation d'une SDD}

L'id\'ee ici est de coder une structure de donn\'ees~; soit en utilisant d'autres strutures de donn\'ees d\'ej\`a cod\'ees, soit en utilisant les m\'ecanismes fondamentaux de cr\'eation de type vus avant les vacances (ou les deux).

\medskip

\exx On a d\'ej\`a impl\'ement\'e une structure de donn\'ees du programme~: les files de priorité.
Il suffit d'utiliser des tas (codable par des listes ou des tableaux)
\xxe\ \\

%\exx On a d\'ej\`a impl\'ement\'e une structure de donn\'ee du programme~: les files de priorit\'e~! En effet, elles peuvent s'impl\'ementer par des tas, qu'on peut eux-m\^emes coder par des tableaux.
%\xxe\ \\

\medskip

L'id\'ee est de faire en sorte que les op\'erations structurelles {\bf soient les plus rapides possibles}. En effet, lorsqu'on manipule une structure de donn\'ee sans savoir comment elle est impl\'ement\'ee, le mod\`ele choisi pour les calculs de complexit\'e est de compter le nombre d'op\'erations structurelles effectu\'ees.\\

Sur l'exemple des files de priorit\'e~: %\unemicroligne~:
\begin{enumerate}
	\item Une première idée est de les implémenter par des listes. Pb: le retrait de l'élément de priorité maximale est en $O(n)$
	\item Avec des listes triées: l'\emph{insertion} coûte cher.
	\item Pour les tas, on peut faire ces deux ops en $O(\log n)$
\end{enumerate}

%Sur l'exemple des files de priorit\'e~:
%\begin{enumerate}
%\item Une premi\`ere id\'ee est de les impl\'ementer par des listes. \\Probl\`eme~: le retrait de l'\'el\'ement de priorit\'e maximale est en $O(n)$.
%\item Pour r\'esoudre le probl\`eme on peut les impl\'ementer par des listes {\bf tri\'ees}. \\Probl\`eme~: l'ajout d'un nouvel \'el\'ement est dans le pire des cas en $O(n)$.
%\item La solution retenue \`a l'aide des tas permet de r\'ealiser ces deux op\'erations en temps $O(\lg(n))$. C'est la f\^ete.
%\end{enumerate}

Pour les autres exemples du programme~:
\begin{enumerate}
\item Piles~: d\'ej\`a dit pour la version immuable, ce sont simplement des ${}_{........................................................}$.
\item Files~: on verra en TP deux m\'ethodes~; en utilisant un tableau circulaire (pour la version persistante), ou en utilisant deux listes cha\^in\'ees (pour la version immuable).
\item Dictionnaires~: on verra deux m\'ethodes~; en utilisant des tables de hachage (pour la version persistante), ou en utilisant des arbres binaires de recherche (pour la version immuable). Cela, la seconde est seulement au programme en seconde ann\'ee, et pour la premi\`ere, ce sera sans doute le tout premier TP de sp\'e.\megasubline 
\end{enumerate}



\section{Manipulation d'une structure de donn\'ee abstraite}

L'id\'ee ici est de manipuler une structure de donn\'ees 
\begin{itemize}
\item {\it y compris sans qu'on l'ait impl\'ement\'ee, et m\^eme,}
\item {\it \underline{y compris sans qu'on ait la moindre id\'ee de comment l'impl\'ementer}}.
\end{itemize}

\medskip

Un exemple est dans le sujet des Mines de 2016 o\`u on nous fait manipuler plusieurs structures de donn\'ees abstraites, en imaginant qu'elles ont \'et\'e impl\'ement\'ees, et sans information sur cette impl\'ementation.

%\includegraphics[scale=0.25]{./Mines2016Rouge.jpg}

\medskip

Faute d'information, lorsqu'on manipule une structure de donn\'ees sans savoir comment elle a \'et\'e impl\'ement\'ee, le mod\`ele choisi pour les calculs de complexit\'e est de consid\'er chaque d'op\'eration structurelle comme une op\'eration \'el\'ementaire.

%\newpage
\exx Prenons un autre exemple~: le {\bf parcours en largueur d'un arbre}.\\[0.2cm]
Rappel de l'algorithme~:
\begin{itemize}[$\bullet$]
\item on consid\`ere une liste d'arbres qui initialement a un seul \'el\'ement, l'arbre que l'on souhaite parcourir, et une liste d'\'el\'ements initialement vide, correspondant \`a la liste du parcours~;
\item lorsqu'on rencontre un arbre non vide dans la liste, on ajoute l'\'etiquette de son n\oe ud dans la liste des \'el\'ements, puis on rajoute {\bf \`a la fin} de la liste d'arbres les fils gauche et droit de l'arbre~;
\item lorsque la liste d'arbres est vide, on retourne la liste d'\'el\'ements.
\end{itemize}
Faisons, puis faisons mieux~:
%\inputminted[ocaml]{cours.ml}
\xxe

\end{document}
