Data Structures

I am in charge of the lectures Data Structures in GIS3. The course is made of seven lectures, eight exercise periods and eight practice periods, of two hours each.

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