Objectifs de l’enseignement:
Etendre les connaissances en algorithmique, et de résoudre des problèmes complexes et faire connaissances des notions de calculabilité et complexité.
Connaissances préalables recommandées:
Algorithmique et structures de données
Contenu de la matière :
- Complexité et optimalité ; premier algorithme de tri
- La récursivité et le paradigme « diviser pour régner »
- Algorithmes de tri
- Structures de données élémentaires
- Programmation dynamique
- Algorithmes gloutons
- NP-complétude
- Heuristiques
Mode d’évaluation : 60%Examen, 40 % Travail personnel.
Références:
- Robert Cori and Jean-Jacques Lévy. Algorithmes et programmation. http://www.enseignement.polytechnique.fr/profs/informatique/Jean-Jacque%s.Levy/poly/. Cours de l’École Polytechnique.
- Thomas Cormen, Charles Leiserson, and Ronald Rivest. Introduction à l’algorithmique. Dunod, 1994.
- Donald Knuth. Seminumerical Algorithms, volume 2 of The Art of Computer Programming. Addison Wesley,1969.
- Donald Knuth. Sorting and searching, volume 3 of The Art of Computer Programming.AddisonWesley, 1973.
