From François Boulier

Main: Structures de Données

(:notabs:)

Je suis responsable du cours Structures de Données à Polytech'Lille, dans la filière Génie Informatique et Statistique 3ème année. Il s'agit d'une série de six cours magistraux, de sept séances de travaux dirigés et de huit séances de travaux pratiques de deux heures.

Progression des 6 cours

1. Allocation dynamique. Programmation modulaire. Spécification. Implantation. L'exemple pris en cours du type rationnel.
2. Listes chaînées. Piles et files. Implantations. L'exemple pris en cours d'une pile d'entiers, implantée par tableaux redimensionnables et par listes chaînées.
3. Complexité. Fichiers de mesures. Résolution de récurrences en MAPLE. Estimation de paramètres avec GNUPLOT.
4. Files de priorité. Implantation avec un minimier (appelé aussi « tas »).
5. Dictionnaires. Arbre Binaires de Recherche. L'extrait d'implantation donné en cours : ABR.tgz.
6. Tables de hachage.

Progression des 7 TD et 8 TP

1. Allocation dynamique. Listes chaînées. TD 1 et TP 1. Le code du module liste_double. Un squelette de Makefile.
2. Suite des feuilles 1. Approfondissement éventuel autour de l'UTF-8.
3. Complexité. TD 3 et TP 3. Le code C pour la méthode de Karatsuba.
4. Files de priorité. TD 4 et TP 4. Le code C du module de files de priorité et celui d'une implantation minimaliste des graphes.
5. Arbres Binaires de Recherche. TD 5 et TP 5.
6. Suite des feuilles 5. En TD 6, l'algorithme des nœuds chapeaux (arbres binaires). Éventuellement, le codage de Huffman (files de priorité et arbres binaires).
7. Tables de hachage. TD 7 et TP 7.
8. Suite des feuilles 7. Pas de TD. Fin du TP sur les tables de hachage.

Sujets d'examen des années précédentes

• L'épreuve de 2011.
• L'épreuve de 2012.

Documents

• Mes notes de cours.
• Principaux ouvrages cités dans le support de cours