Algorithmique L.3.1

Présentation

Organisation

• Douze cours de deux heures
  Polycopié de Maxime Crochemore
  • Parcours en largeur d'un arbre binaire à l'aide dune file d'attente FIFO.
    Un code C set_Element_Tree.h, tree.h, fifo.h,
    tree.c, liste.h, liste.c, fifo.c, parcours.c,
    compiler avec gcc -Wall tree.c liste.c fifo.c parcours.c ou faire un makefile.
  • Arbres AVL. (aux formats pdf ou ppt)
    
    Un code C tree.h, tree.c, essai.c,
    compiler avec gcc -Wall tree.c essai.c
    
  • B-arbres. (aux formats pdf ou ppt)
    Un code C pour l'insertion avec l'exemple du cours tree.h, tree.c, essai.c,
    compiler avec gcc -Wall tree.c essai.c
  • Arbres rouge-noir. Transparents de Érik Demaine et Charles Leiserson, Open Course du MIT pdf
  • Graphes. Parcours (aux formats pdf ou ppt)
    • Exemple d'exploration en profondeur (en pdf) exploration.pdf,
    • Trouver son chemin dans un labyrinthe sans tourner à gauche,
    • Un code C pour l'exploration en profondeur récursive graphe.h, graphe.c, compiler avec gcc -Wall graphe.c
  • Graphes. Clôture (aux formats pdf ou ppt)
  • Graphes. Plus courts chemins (aux formats pdf ou ppt)
  • Graphes. Arbres recouvrants de coût minimal ARCM (aux formats pdf ou ppt)
  • Graphes. Flots (aux formats pdf ou ppt)
  • Automates. Minimisation. Égalité. Équivalence. (aux formats pdf ou ppt)
  • Hachage (aux formats pdf ou ppt)
  • Programmation dynamique. Sous-mots/ (aux formats pdf ou ppt)
  • Douze séances de Travaux Dirigés avec Nicolas Bedon, et Marc Zipstein.
  • Contrôle
    • un examen écrit qui compte 1/2. Un sujet de l'année 2007.
    • un projet qui compte 1/2.

Références principales

• H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and C. Stein Introduction to Algorithms Second edition, MIT Press and McGraw-Hill, 2001.
  Voir aussi les superbes transparents du cours Introduction to Algorithms de Érik Demaine et Charles Leiserson, Open Course du MIT 6-046JFall-2005, puis Video Lectures (Video et pdf). Disponible sur ITunes U.
• D. Beauquier, J. Berstel et Ph. Chrétienne, Éléments d'algorithmique, Masson, 1992, 463 pages.
• A.V. Aho, J.E. Hopcroft et J.D. Ullman, Structures de données et algorithmes, InterEditions, 1988.