Théorie de la complexité

Objectifs : Le but de ce cours est d’enseigner les fondamentaux de la théorie de la complexité algorithmique tels la difficulté intrinsèque d’un problème informatique, les outils de son analyse, les notions de « problèmes plus difficiles que d’autres », …

Contenu :

  • Analyse de la difficulté intrinsèque (complexité) d’un problème

  • Préservation de l’appartenance à une classe de complexité (réductions), problèmes difficiles (complets) pour une classe

  • Rôle des paramètres pour évaluer la complexité d’un problème

  • Classes de complexité (mesurée en considérant la taille de l’instance comme paramètre) : P, NP, co-NP, préservation de l’appartenance à P par réductions de Karp et de Turing et NP-complétude

  • Classes de complexité (mesurée en considérant la valeur de la solution comme paramètre), XP, FPT, hiérarchies W[], réductions FPT

Bibliographie

  • R. G. Downey, M. R. Fellows, Parameterized Complexity, Springer-Verlag, 1999.

  • M.R Garey, D. S. Johnson, Computers and intractability. A guide to the theory of NP-completeness, W. H. Freeman, 1979.

  • C. H. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.

  • V. Th. Paschos, Complexité et Approximation Polynomiale, Hermès, 2004.

Contact

Responsable du master: Daniel VANDERPOOTEN

Secrétariat :
  Bureau : B522
  Tél. : 01 44 05 42 47
 email : master-modoping @ dauphinepong.fr

Adresse :
  Université Paris Dauphine
  Master MODO - Bureau P619
  Place du Maréchal de Lattre de Tassigny
  75775 Paris Cedex 16