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

  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