Structures de Données

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

  • 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