Cours de M1 "Algorithmes et Complexité"

Références bibliographiques:

• Livre "Introduction to Algorithms", de T.H. Cormen, C.E. Leiserson et R.L. Rivest, The MIT Press, 1990.
• Livre "Computers and Intractability, a Guide to the Theory of NP-Completeness", de M.R. Garey et D.S. Johnson, Freeman, 1991.
• Livre "Approximation Algorithms", de Vijay V. Vazirani, Springer, 2001.
• Cours de Francois Lemieux
• Survols & Exposés de Pierre Béjian
• Cours de Yves Robert
• Cours de Johanne Cohen

1ière partie: René Schott

2ième partie: Olivier Bournez

• Cours 1:
  • Programmation Dynamique (jusqu'à fin matrice)
• Cours 2:
  • Programmation Dynamique (suite)
  • Algorithmes Gloutons (introduction)
• Cours 3:
  • Algorithmes Gloutons (jussqu'à fin Kruskal).
• Cours 4:
  • (Bonus: Motivation de la Théorie de la Complexité)
  • NP-complétude (jusqu'à NP)
• Cours 5
  • NP-complétude (suite).
  • Algorithmes d'Approximation (intro)
• Cours 6
  • Algorithmes d'approximation (suite).

Science fiction:

Archives

• Sujet d'examen 2005-2006:
  • Session 1
  • Session 2
• Corrigé du TD2 "Algorithmes Gloutons"

• Un td sur approximation et ordonnancement

Auteur: Olivier Bournez
Pour toute remarque: Olivier.Bournez@loria.fr