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

\title{TD 2 d'Algorithmique}
\date{Mercredi 29 septembre 2004}

\begin{document}
\maketitle

\section{Files en C}

Il existe plusieurs façons de définir les files en \verb+C+, nous
allons en voir quelques unes.

\subsection*{Première méthode}

On réutilise la structure de liste vue la dernière fois:

\begin{verbatim}

struct queue_s {
    liste debut;
    liste fin;
};

typedef struct queue_s queue;
\end{verbatim}

Écrivez les fonctions suivantes:
\begin{enumerate}
\item \verb+new_queue+ (créer une nouvelle file),
\item \verb+is_empty+ (tester si une file est vide),
\item \verb+add+ (ajouter un élément en fin d'une file),
\item \verb+get+ (récupérer l'élément de tête d'une file),
\end{enumerate}

\subsection*{Seconde méthode}

On simule la file par deux listes $l_1$ et $l_2$, de telle sorte que
l'ordre dans la file soit $concat(l_2, miroir(l_1))$.

Écrivez les fonctions suivantes:
\begin{enumerate}
\item \verb+new_queue+ (créer une nouvelle file),
\item \verb+is_empty+ (tester si une file est vide),
\item \verb+add+ (ajouter un élément en fin d'une file),
\item \verb+get+ (récupérer l'élément de tête d'une file),
\end{enumerate}

\subsection*{Troisième méthode}

On simule une file par un tableau de taille fixe.
Écrivez les fonctions suivantes:
\begin{enumerate}
\item \verb+new_queue+ (créer une nouvelle file),
\item \verb+is_empty+ (tester si une file est vide),
\item \verb+add+ (ajouter un élément en fin d'une file),
\item \verb+get+ (récupérer l'élément de tête d'une file),
\end{enumerate}

\subsection*{Un peu de recul}

Devisez doctement sur les avantages comparés des 3 choix
d'implémentation d'une file. Semi question de cours: et comment on
définit une pile?

\section{Les files et piles en action}

Dans un TD Unix récent, on voulait connaitre le nombre total de lignes
des fichiers de source \verb+C+ contenus dans un répertoire et tous
ses sous-répertoires.

\begin{enumerate}

\item Rappelez la structure utilisée par le filesystem unix pour
représenter les fichiers. Proposez une définition en \verb+C+ d'une
telle structure (en supposant que chaque dossier n'a qu'un nombre
maximal fixé par le filesystem de sous-dossiers et de fichiers).

\item Écrivez un algorithme récursif de parcours de cette structure.
On fera un parcours en profondeur.

\item Comment éviter la récursion? Écrivez l'algorithme qui en
découle.

\item On souhaite faire un parcours en largeur (étage par étage).
Quelle est la bonne structure à utiliser? Écrivez l'algorithme pour le
faire.

\end{enumerate}

\section{Les tours de Hanoï: Pile... ou file?}

On rappelle le principe des tours de Hanoï : le joueur dispose de n
anneaux et de trois tours.  Ces anneaux sont de tailles toutes
différentes et à tout moment, au-dessus de tout anneau, il n'y a que
des anneaux plus petits que lui. Initialement tous les anneaux sont
disposés sur la première tour et on veut les déplacer sur la
troisième, en les déplaçant un par un d'une tour à l'autre. 

\begin{enumerate}

\item Indiquez une solution au problème. Combien de coups faut-il
faire, au moins? Combien y'a-t-il de solutions avec un coup minimal?

\item On considère qu'algorithme qui résoud le problème des tours de
Hanoï indique les opérations successives à effectuer, par exemple:
\begin{verbatim}
Déplacer disque de 1 vers 3
Déplacer disque de 2 vers 1
\end{verbatim}

Écrire un tel algorithme récursif.

\item On veut numéroter les disques et pouvoir afficher à tout moment
l'état des tours. Quelle est la bonne structure?

\item On veut résoudre le problème de façon itérative. Quelles
informations stocker dans l'algorithme, et dans quelle structure? En
fait on peut le faire aussi bien avec une pile qu'avec une file;
comparez les méthodes.

\item Encore plus fort: comment résoudre le problème sans mémoire
auxiliaire (ou plutôt, avec un espace mémoire de taille constante)?

\end{enumerate}

\end{document}