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

  • Allocation dynamique. Programmation modulaire. Spécification. Implantation. L'exemple pris en cours du type rationnel. La feuille de TD et celle de TP. Le code du module liste_double. Un squelette de Makefile.
  • 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.
  • Complexité. Fichiers de mesures. Résolution de récurrences en MAPLE. Estimation de paramètres avec GNUPLOT. La feuille de TD et celle de TP. Le code C pour la méthode de Karatsuba.
  • Files avec priorité. Implantation avec un minimier (appelé aussi « tas »). La feuille de TD et celle de TP. Le code C du module de files de priorité et celui d'une implantation minimaliste des graphes.
  • Dictionnaires. Arbre Binaires de Recherche. L'extrait d'implantation donné en cours : ABR.tgz. La feuille de TD et celle de TP. La seconde feuille de TD.
  • Tables de hachage.
  • Cours supprimé : application à l'algorithme de l'éditeur de liens. Le code du projet linker.

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

  • L'épreuve de 2011.

Documents

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