Algorithmique et complexité

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 :

1. Complexité et optimalité ; premier algorithme de tri

2. La récursivité et le paradigme « diviser pour régner »

3. Algorithmes de tri

4. Structures de données élémentaires

5. Programmation dynamique

6. Algorithmes gloutons

7. NP-complétude

8. Heuristiques

Mode d’évaluation :

60%Examen, 40 % Travail personnel.

Références

[1] 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. [2] Thomas Cormen, Charles Leiserson, and Ronald Rivest. Introduction à l’algorithmique. Dunod, 1994. [3] Donald E. Knuth. Seminumerical Algorithms, volume 2 of The Art of Computer Programming. Addison Wesley,1969. [4] Donald E. Knuth. Sorting and searching, volume 3 of The Art of Computer Programming.AddisonWesley, 1973.