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

• Responsable pour 2012--2013: Xavier Provençal
• Xavier Provençal (CM/TD/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): 10 septembre. Introduction à la théorie de la complexité, notion de problèmes et instances.
• (Cours 2): 12 septembre. Mesures de complexité, notations O, Omega, Theta.
• (Cours 3): 12 septembre. Temps polynomial VS temps exponentiel.
• (Cours 4): 14 septembre. Problèmes de décision VS problèmes d'optimisation, classes P, EXP, NP.
• (Cours 5): 17 septembre. Classe coNP, démonstrantion d'appartenance à NP/coNP.
• (Cours 6): 18 septembre. Réduction polynomiale, NP-Complétude.
• (Cours 7): 19 septembre. Introduction au Théorème de Cook. Modèles de machines de Turing et modèle RAM.
• (Cours 8): 24 septembre. RAM vs MTD (suite), MTN et classe NP, logique booléenne.
• (Cours 9): 25 septembre. Preuve du théorème de Cook, CSAT est NP-Complet.
• (Cours 10): 1 octobre. 3-SAT est NP-Complet, Coloriage de graphe est NP-Complet (I).
• (Cours 11): 2 octobre. Coloriage de graphe est NP-Complet. Résolution par énumération des certificats, résultion par backtrack.
• (Cours 12): 9 octobre. Complexité d'un algorithme de backtrack, Clique, CS et EI sont équivalents.
• (Cours 13): 12 octobre. Attribution des sujets de TP, résolution du Sudoku par les liens dansants (dancing links).
• (TP 1): 15 octobre. Démonstration de NP-Complétude (I).
• (TP 2): 23 octobre. Démonstration de NP-Complétude (II).