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. L'exemple vu en cours rationnels.tgz.
  2. Allocation dynamique (suite) : fuites mémoires, double free. Utilitaire valgrind. Mise en œuvre avec des constructeurs et des destructeurs. Listes chaînées.
  3. Complexité.
  4. Piles, files.
  5. Arbres Binaires de Recherche.
  6. Tables de hachage.

Sujets d'examens

GIS3

Progression des 6 cours

  1. Programmation modulaire. Spécification. Implantation. Compilation séparée. Notion de processus. Allocation dynamique. Les deux exemples pris en cours exemple-rationnels-v1.tgz et exemple-rationnels-v2.tgz
  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. L'archive piles-et-files.tgz contenant le code écrit en cours.
  5. Arbres Binaires de Recherche.
  6. Tables de hachage.

Progression des 8 TD et TP

  1. Allocation dynamique. Listes chaînées. TD 1 et TP 1. 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 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