INFO724 : Algorithmique avancée, graphes et NP-Complétude
Aller à la navigation
Aller à la recherche
- Responsable pour 2012--2013: Xavier Provençal
- Xavier Provençal (CM/TD/TP), Pierre-Étienne Meunier (TP), Florian Hatat (TP)
Quelques ressources bibliographiques
- Hopcroft et Ullman, Introduction to automata theory, languages, and computation. (1979).
- Garey et Johnson, Computers and intractability a guide to the theory of NP-completeness. (1979).
- Cormen, Leiserson et Rivest, Introduction à l'algorithmique, (1994).
- Paschos, Complexité et approximation polynomiale, (2004).
- Wilf, Algorithms and Complexity, (1994). Disponible en ligne
Exemples vus en classe
- Programme sage qui calcule les nombres de Ramsey ... mais il faut de la patience !
Déroulement (2012-2013)
- (Cours 1): lundi 10 septembre. Introduction à la théorie de la complexité, notion de problèmes et instances.
- (Cours 2): Mercredi 12 septembre. Mesures de complexité, notations O, Omega, Theta.
- (Cours 3): Mercredi 12 septembre. Temps polynomial VS temps exponentiel.
- (Cours 4): Vencredi 14 septembre. Problèmes de décision VS problèmes d'optimisation, classes P, EXP, NP.
- (Cours 5): Lundi 17 septembre. Classe coNP,
- (Cours 6): Mardi 18 septembre.
- (Cours 7): Mercredi 19 septembre.