Data Structures
I am in charge of the lectures Data Structures in GIS3. The course is made of seven lectures, seven exercise periods and eight practice periods, of two hours each.
Progression des 6 cours
- Allocation dynamique. Programmation modulaire. Spécification. Implantation. L'exemple pris en cours du type rationnel.
- 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.
- Complexité. Fichiers de mesures. Résolution de récurrences en MAPLE. Estimation de paramètres avec GNUPLOT.
- Files de priorité. Implantation avec un minimier (appelé aussi « tas »). Exemple pour GIS2A : file-priorite.tgz
- Dictionnaires. Arbre Binaires de Recherche. L'extrait d'implantation donné en cours : ABR.tgz. Exemple pour GIS2A : arbres.tgz.
- Tables de hachage. Exemple pour GIS2A : hachage.tgz.
Progression des 7 TD et 8 TP
- Allocation dynamique. Listes chaînées. TD 1 et TP 1. Le code du module liste_double. Un squelette de Makefile.
- Suite des feuilles 1. Approfondissement éventuel autour de l'UTF-8.
- Complexité. TD 3 et TP 3. Le code C pour la méthode de Karatsuba.
- 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.
- 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.
- 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).
- Tables de hachage. TD 7 et TP 7.
- Suite des feuilles 7. Pas de TD. Fin du TP sur les tables de hachage.
Sujets d'examen des années précédentes
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
