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

Quelques ressources bibliographiques

Ouvrage de référence :

Cormen, Leiserson, Rivest et Stein, Algorithmique, 3e edition (2009). ( Aussi appelé "Introductino à l'algorithmique" pour les deux premières éditions )

Autres références bibliographiques :

Wilf, Algorithms and Complexity, (1994). Disponible en ligne
Garey et Johnson, Computers and intractability a guide to the theory of NP-completeness. (1979).
Paschos, Complexité et approximation polynomiale, (2004).
Hopcroft et Ullman, Introduction to automata theory, languages, and computation. (1979).

(à venir)

(Cours 1): 9 septembre. Introduction à la théorie de la complexité, notion de problèmes et instances.

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