\documentclass{article}
\usepackage[latin1]{inputenc}
\usepackage{a4}
\usepackage{fullpage}
\usepackage{amsfonts}

\title{TD 3 d'Algorithmique}
\date{Mercredi 5 octobre 2004}

\begin{document}
\maketitle

\section{Tables}

On rappelle le principe d'une table, parfois appelée dictionnaire. On
appelle $E$ l'espace des entrées possibles et $V$ l'espace des valeurs
possibles. Une table $T \subseteq E \times V$ est une structure sur
laquelle on dispose des opérations suivantes:

\begin{itemize}

\item l'accès en lecture à une entrée: $(k, v) \in E \times V
\rightarrow v$,
\item l'ajout d'une entrée,
\item la modification d'une entrée,
\item la liste des entrées présentes,
\item l'effacement d'une entrée.

\end{itemize}

\begin{enumerate}

\item Indiquez des exemples de tables que vous avez déjà rencontrées.
Quels en étaient l'espace des entrées? Des valeurs? Quel était le coût
de chacune des opérations?

\item Écrivez une structure de table permettant de manipuler tout type
d'entrées et tout type de valeurs en utilisant un tableau. Quels sont
les avantages de cette méthode? Les limitations?

\item Utilisez une méthode empruntée aux \emph{filesystems} pour
s'affranchir des problèmes de taille.

\item Même question en utilisant une liste plutôt qu'un tableau.

\end{enumerate}

\section{Tables de hachage}

On suppose qu'on dispose d'une fonction de hachage $h$ de $E$ dans
$[0, n-1]$, et qu'on stocke les valeurs dans la case du tableau dont
l'indice correspond à la valeur de la fonction de hachage de cette
entrée.

\begin{enumerate}

\item On décide de gérer les doublons en stockant une liste de valeur
dans chaque case. Écrivez les structures et les fonctions nécessaires
pour manipuler une telle table.

\item Quel est le coût de chacune des opérations? Quel est le pire
cas?

\item On suppose maintenant que la fonction de hachage ne donne pas
uniquement une valeur d'indice, mais une permutation des indices, pour
gérer le cas des doublons. Par exemple, si le premier indice retourné
par $h(clef)$ est occupé, on regarde dans le deuxième et ainsi de
suite. On suppose que $m$ cases du tableau sont déjà occupées et on
note $\alpha = \frac{m}{n}$. En supposant que les éléments déjà
présents sont uniformément répartis dans le tableau, montrez que le
nombre moyen de sondages lors d'une recherche infructueuse vaut au
plus $\frac{1}{1-\alpha}$.

\end{enumerate}

\section{Exemples d'insertion}

On considère l'insertion des mots 10, 22, 31, 4, 15, 28, 17, 88, 59
dans une table de hachage de longueur $n=11$.

\begin{enumerate}

\item Illustrez l'opération d'insertion lorsque la fonction de hachage
est $h(w,i) = w + i~\mathrm{mod}~n$.

\item Même question avec $h(w,i) = w + i + 3 i^2~\mathrm{mod}~n$.

\end{enumerate}

\section{Matrices creuses}

On souhaite travailler sur des matrices de nombres flottants de
grande taille mais ayant peu de coefficients non nuls. On choisit de
représenter une matrice comme un tableau de listes de coefficients.
\begin{enumerate}

\item Écrivez le type d'une matrice. On suppose qu'on travaille sur
des matrices carrées dont la taille est fixée et connue à la
compilation.

\item Écrivez une fonction écrivant une matrice creuse dans un
fichier, et une fonction lisant une matrice creuse dans un fichier
écrite dans le même format (que vous choisirez).

\item Écrivez les fonctions de multiplication matrice $\times$
vecteur, matrice $\times$ matrice.

\item Écrivez la fonction \verb+somme+ de deux matrices.

\item Quelle serait la place mémoire occupée par une matrice carrée
d'entiers de dimension $1000 \times 1000$ si un entier occupe $4$
octets avec une représentation classique (\emph{i.e.} complète aussi
appelé dense) des coefficients?

\item On suppose que la matrice contient uniquement $100$ coefficients
non nuls par ligne. Estimez la place gâchée par une représentation
dense dans ce cas là par rapport à la place prise par notre
représentation.

\end{enumerate}

\end{document}