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. Exemple pour GIS2A : pile-file.tgz.
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 »). Exemple pour GIS2A : file-priorite.tgz
5. Dictionnaires. Arbre Binaires de Recherche. L'extrait d'implantation donné en cours : ABR.tgz. Exemple pour GIS2A : arbres.tgz.
6. Tables de hachage. Exemple pour GIS2A : hachage.tgz.

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. L'archive exemples-arbres.tar contient des exemples d'arbres utiles pour la section 2 du TP.
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.
• L'épreuve de 2013.

Documents

• Mes notes de cours. L'archive linker.tgz contenant le code du projet qui illustre le support de cours.
• Principaux ouvrages cités dans le support de cours