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. Cormen, Leiserson, Rivest et Stein, Algorithmique, 3e edition (2009). ( Aussi appelé "Introductino à l'algorithmique" pour les deux premières éditions )
2. Wilf, Algorithms and Complexity, (1994). Disponible en ligne
3. Garey et Johnson, Computers and intractability a guide to the theory of NP-completeness. (1979).
4. Paschos, Complexité et approximation polynomiale, (2004).
5. Hopcroft et Ullman, Introduction to automata theory, languages, and computation. (1979).

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).