Algorithmique 4

Marie-Pierre.Beal@univ-mlv.fr
Université Paris-Est Marne-la-Vallée, Janvier 2013

Présentation


Organisation

  • Neuf cours de deux heures
    • Algorithmes gloutons. pdf
    • Programmation dynamique. Calcul de sous-mots. pdf
    • Algorithme de base sur les automates. Minimisation. Egalité. Equivalence. pdf
    • Minimisation de Hopcroft et minimisation d'automates acycliques. pdf
    • Flots (slides de Maxime Crochemore) pdf
    • Couplages. Théorie de Dilworth. pdf
    • Algorithme de Gale-Shapley. pdf
    • Optimisation et réseaux de transports. pdf
    • Réductions polynomiales pdf
  • Neuf séances de Travaux Dirigés avec Marie-Pierre Béal et Claire David
  • Contrôle
    • un examen écrit qui compte 1/2.
    • un projet qui compte 1/2.
    • Le sujet du projet 2013-2014 pdf
  • Examen année 2012-2013
    • Le sujet 2012-2013 pdf

Références principales

  • H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Ronald L., Stein, Clifford, Introduction to Algorithms, (3rd Edition), MIT Press and McGraw-Hill, 2009.
    Voir aussi les superbes transparents du cours Introduction to Algorithms de Érik Demaine et Charles Leiserson, Open Course du MIT 6-046JFall-2005, puis Lecture Notes.
  • Jon Kleinberg and Èva Tardos, Algorithm Design, Addison Wesley, 2005
  • Robert Sedgewick and Kevin Wayne, Algorithms, 4th Edition, Addison.Wesley, 2011.url
  • 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.
Institut Gaspard-Monge, Laboratoire d'informatique Gaspard-Monge, Marie-Pierre Béal