Algorithmique 4

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

Présentation


  • Algorithmes gloutons.
  • Programmation dynamique.
  • Algorithmes de traitement du texte.
  • Couplages et mariages. Algorithme de Gale-Shapley.

Organisation

  • 7 cours de deux heures
  • Algorithmes gloutons pdf
  • Programmation dynamique pdf
  • Recherche de motif dans un texte pdf
  • Flot maximal. Coupe minimale pdf
  • Couplages pdf
  • Couplages stables pdf
  • 9 TD de deux heures
  • 9 séances de Travaux Dirigés avec Marie-Pierre Béal et Claire David
  • Contrôle
    • un examen écrit qui compte 1/2.
    • le sujet du projet est sur le elearning
    • 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