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 huit séances de travaux dirigés et de huit séances de travaux pratiques de deux heures.

GIS2A3

Progression des cours

  1. Compilation séparée. Structure d'un fichier d'entête. Implantation. Spécification d'une implantation. Type abstrait. Prototype d'une fonction.
  2. Allocation dynamique (suite) : fuites mémoires, double free. Utilitaire valgrind. Mise en œuvre avec des constructeurs et des destructeurs. Listes chaînées. listes.tgz.
  3. Complexité.
  4. Piles, files.
  5. Arbres Binaires de Recherche. arbres.tgz.
  6. Tables de hachage.

Sujets d'examens

GIS3

Progression des 6 cours

  1. Programmation modulaire. Spécification. Implantation. Compilation séparée. L'exemple vu dans le premier demi-cours d'une heure rationnels.tgz. Notion de processus. Allocation dynamique.
  2. Allocation dynamique. Les listes chaînées seront vues en TD: liste_double.tgz.
  3. Complexité. Fichiers de mesures. Résolution de récurrences en MAPLE. Estimation de paramètres avec GNUPLOT.
  4. Piles et files.
  5. Arbres Binaires de Recherche. Le code écrit en cours ABR.tgz.
  6. Tables de hachage.

Progression des 8 TD et TP

  1. Allocation dynamique. Listes chaînées. TD 1 et TP 1. Le TD 1 bis sur les spécifications des structures de données et son corrigé TD 1 bis corrigé. Un squelette de Makefile. Un dictionnaire Esperanto-Francais.utf8 (adapté de cette page-ci avec l'aimable autorisation de son auteur) pour la partie optionnelle du TP.
  2. Suite des feuilles 1. Listes chaînées. Variantes d'implantation.
  3. Complexité. TD 3 et TP 3. Le calcul de la complexité de l'algorithme de Karatsuba resolution-td3.pdf. Le code C pour la méthode de Karatsuba.
  4. Préparation du TP sur l'algorithme de Graham. TP 4. L'archive Graham.tgz.
  5. Arbres Binaires de Recherche. TD 5 et TP 5.
  6. Cours-TD sur les tables de hachage et TD 6 et TP 6.
  7. Étude de cas : td7-Yale.pdf td7-FHJ.pdf td7-diacritique.pdf td7-noeuds-chapeaux.pdf.
  8. Étude de cas.

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

  • L'épreuve de 2017.
  • L'épreuve de 2016.
  • L'épreuve de 2015.
  • L'épreuve de 2014.
  • L'épreuve de 2013.
  • L'épreuve de 2012.
  • L'épreuve de 2011.

Documents

  • Mes notes de cours.
  • L'archive linker.tgz contenant le code du projet qui illustre le support de cours.
  • Le programme tirage_loto.c qui sert à illustrer le fonctionnement du debugger gdb.
  • Principaux ouvrages cités dans le support de cours