INFO724 : Algorithmique avancée, graphes et NP-Complétude

• Responsable pour 2012--2013: Xavier Provençal
• Xavier Provençal (CM/TD/TP), Pierre-Étienne Meunier (TP), Florian Hatat (TP)

Quelques ressources bibliographiques

1. Hopcroft et Ullman, Introduction to automata theory, languages, and computation. (1979).
2. Garey et Johnson, Computers and intractability a guide to the theory of NP-completeness. (1979).
3. Cormen, Leiserson et Rivest, Introduction à l'algorithmique, (1994).
4. Paschos, Complexité et approximation polynomiale, (2004).
5. Wilf, Algorithms and Complexity, (1994). Disponible en ligne

Exemples vus en classe

1. 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, démonstrantion d'appartenance à NP/coNP.
• (Cours 6): Mardi 18 septembre. Réduction polynomiale, NP-Complétude.
• (Cours 7): Mercredi 19 septembre. Introduction au Théorème de Cook. Modèles de machines de Turing et modèle RAM.
• (Cours 8): Lundi 24 septembre. RAM vs MTD (suite), MTN et classe NP, logique booléenne.
• (Cours 9): Mardi 25 septembre. Preuve du théorème de Cook, CSAT est NP-Complet.