\documentclass[a4]{exam}

\usepackage[utf8]{inputenc}
\usepackage[french]{babel}
\usepackage{fullpage}
\usepackage[a4paper]{geometry}
\geometry{top=2cm, bottom=2cm, left=2cm, right=2cm}
\usepackage{url}
\usepackage{amsfonts}
\usepackage{amsmath}

\renewcommand\thequestion{\arabic{section}.\arabic{question}}

\title{Devoir libre~: \'Elimination de doublons dans une liste}
\date{Samedi 12 mars 2011}

\begin{document}
\maketitle
L'objectif de ce devoir est de mettre en place une fonction permettant de construire une liste de chaînes de caractères telle qu'une chaîne donnée ne peut y apparaître plus d'une fois.

\section{Opérations sur les chaînes de caractères}\label{sec:strings}
En C les chaînes de caractères sont codées comme des tableaux dont les éléments sont de type \verb|char|. La fin de la chaîne ne correspond pas à la fin du tableau et est explicitement indiquée par un caractère spécial, le caractère nul \verb|\0|. Ainsi une chaîne de longueur $n$ est codée dans un tableau de longueur au moins $n + 1$. Par exemple la déclaration 
\begin{verbatim}
char s[5] = "abc";
\end{verbatim}
produit en mémoire un pointeur $s$ désignant la première case d'un tableau de la forme 
\begin{tabular}{|c|c|c|c|c|}
  \hline
  'a' & 'b' & 'c' & \verb|\0| & ? \\
  \hline
\end{tabular}. 
Dans cette partie nous proposons d'implémenter plusieurs opérations courantes sur les chaînes.

\begin{questions}
\question La longueur d'une chaîne est le nombre de caractères qu'elle contient. Dans l'exemple précédent, la longueur de \verb|s| est 3. \'Ecrivez la fonction \verb|int strlen(char* s)| qui calcule la longueur d'une chaîne. Quelle est sa complexité en opérations de comparaisons~?
\question \'Ecrivez la fonction \verb|char* strcpy(char* s)| qui produit une copie en mémoire de la chaîne passée en argument. Représentez l'état de la mémoire après les instructions suivantes~:
\begin{verbatim}
char u[5] = "aaa";
char* v = strcpy(u);
\end{verbatim}
\question Enfin, nous aurons besoin d'une fonction de comparaison entre chaînes, devant indiquer pour deux chaînes $u$ et $v$ si $u<v$, $u=v$ ou $u>v$ selon l'ordre lexicographique. La fonction devra retourner respectivement -1, 0 ou 1. Le prototype attendu est \verb|int strcmp(char* u, char* v)|. On donnera une version en style récursif, et une version en style itératif.
\end{questions}

\section{Listes de chaînes de caractères}
\begin{questions}
  \question On souhaite maintenant construire des listes de chaînes de caractères. Ces listes correspondent typiquement aux lignes d'un fichier. Proposer un type \verb|list| permettant de représenter cette structure en mémoire. Il est recommandé de s'inspirer de la structure de liste chaînée vue en cours.
  \question Illustrer votre choix en donnant la représentation en mémoire d'une liste à 2 éléments.
  \question \'Ecrire un constructeur pour vos listes, de prototype \verb|list cons(char* s, list l)|. Attention, on attend du constructeur qu'il copie la chaîne donnée en argument.
  \question Proposer une fonction qui calcule le nombre total de caractères dans une liste.
  \question \'Ecrire une fonction \verb|void free_list(list l)| libérant {\bf toute} la mémoire occupée par une liste.
\end{questions}

\section{Tri de la liste}
La plupart des tris efficaces requièrent de pouvoir accéder rapidement à n'importe quel élément de la séquence à trier. Les listes ne remplissent pas cette condition puisqu'on ne peut accéder aisément qu'à leur premier élément. Une technique courante consiste à transformer, le temps du tri, la liste en tableau.
\begin{questions}
  \question \label{q:arrayfromlist} \'Ecrire une fonction qui transforme une liste de chaînes en un tableau de chaînes, de prototype
\begin{verbatim}
char** array_from_list(list l).
\end{verbatim}
Attention, cette fois les chaînes ne doivent pas être recopiées.
\question Représenter l'état de la mémoire après les instructions suivantes
\begin{verbatim}
list l = cons("Mars", cons("Jupiter", cons("Saturne",NULL)));
char** t = array_from_list(l);
\end{verbatim}
\question \'Ecrivez un tri par insertion pour le tableau produit à la question \ref{q:arrayfromlist}~; le prototype attendu est \verb|sort(char** t, int n)| où \verb|n| correspond à la longueur du tableau \verb|t|. Quelle est la complexité de ce tri en nombre de comparaisons de chaînes (appels à \verb|strcmp|)~?
\question Enfin, écrivez une fonction recréant une liste à patir d'une tableau de chaînes~:
\begin{verbatim}
list list_from_array(char** t, int n)
\end{verbatim}
où \verb|n| est la taille du tableau \verb|t|. Cette fois-ci les chaînes devront être copiées lors de la création de la liste (utilisez l'opération \verb|cons| à cette effet).
\end{questions}

\section{\'Elimination des doublons}
On suppose que l'on dispose de listes triées. Par conséquent, si elles contiennent plusieurs fois le même élément, ses occurrences se suivent dans la liste.
\begin{questions}
  \question Implémenter l'opération \verb|myst| dont la définition abstraite est 
$$\left\{ \begin{array}{ll}
    \mbox{myst} : \mathbb{L} \rightarrow \{ V, F \}\\
    \mbox{myst}(h_1 :: h_2 :: t) = V & \mbox{ si } h_1 = h_2\\
    \mbox{myst}(l) = F & \mbox{ dans tous les autres cas.}\\
  \end{array} \right.$$
où $\mathbb{L}$ désigne l'ensemble des listes. Donnez-lui un nom plus approprié.
\question Implémenter l'opération \verb|list chop(list l)| qui supprime le premier élément d'une liste, libère la mémoire correspondante et retourne la queue de la liste. La fonction retourne la liste vide si l'argument est la liste vide.
\question \`A l'aide des deux précédentes questions, proposez une fonction \verb|list supprime_doublons(list l)| qui attend en argument une liste triée et supprime les éléments de la liste en plusieurs exemplaires, de sorte qu'il n'en reste plus qu'une seule occurrence. Par exemple, la liste 
$$"aa" :: "ab" :: "ab" :: "abc" :: "abd" :: "abd" :: "abd" :: "zz" :: \emptyset$$
devient 
$$"aa" :: "ab" :: "abc" :: "abd" :: "zz" :: \emptyset$$.
\end{questions}

\section*{Conclusion du problème}
\'Ecrire une fonction \verb|list uniq(list l)| qui à une liste quelconque associe une nouvelle liste en mémoire contenant les mêmes chaînes que \verb|l|, mais débarassée de ses doublons, c'est-à-dire contenant chaque chaîne de caractères au plus une fois. Donner sa complexité au pire en nombre d'opérations sur les chaînes (celles vues à la section \ref{sec:strings}). Commentaire~?
\end{document}
