Théorie de la complexité

Agrégation de mathématique - option informatique - ENS Cachan Antenne de Bretagne - Année 2012/2013

11 décembre 2012	NP-complétude Transparents I) Non-déterminisme. Définition de NP. II) Les problèmes les plus durs de NP. III) Le pouvoir de la logique propositionnelle. 1) Problème SAT 2) Machines de Turing Exemple d'une machine de Turing - Fiche à compléter 3) Théorème de Cook (SAT est NP-complet) III) Des réductions pour montrer la NP-dureté 1) 3SAT 2) 3-COLORIAGE
18 décembre 2012	PSPACE Transparents I) Définition II) QBF et théorème de Savitch III) Le paysage IV) Jeux à deux joueurs. a) QBF-sat
25 janvier 2013 13h30 à 15h30	Normalement était prévu... b) Jeu de géographie. V) Description d'une exécution a) Non-universalité d'une expression régulière b) Pavages Aller plus loin I) EXPTIME a) Des problèmes non tractables b) Un problème EXPTIME (admis) II) LOGSPACE a) Définitions b) Problème d'accessibilité III) Autres sujets intéressants Machines alternantes Pavages Complexité d'approximation, probabilistes Mais on a plutôt fait ce TD.

Computational Complexity. Papadimitriou : (une référence. Un peu lourd dans ses manipulations de machine de Turing.)
The Design and Analysis of Computer Algorithms, Aho, Hopcroft, Ullman (une référence. Le problème de la non-universalité d'une expression régulière. Un peu lourd dans ses manipulations de machine de Turing)
Introduction à l'algorithmique, T. H. Cormen, C. E. Leiserson, R. L. Rivest, Dunod. (dommage qu'il ne traite pas les machines de Turing, lourd avec ses circuits etc.)
Algorithms de S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani. (une approche claire et motivée, dommage qu'il ne traite pas les machines de Turing)
Introduction to the theory of computation. Michael Sipser. (un livre propre, qui introduit PSPACE et ose parler de jeux !)