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.
  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