Panneau de gestion des cookies
NOTRE UTILISATION DES COOKIES
Des cookies sont utilisés sur notre site pour accéder à des informations stockées sur votre terminal. Nous utilisons des cookies techniques pour assurer le bon fonctionnement du site ainsi qu’avec notre partenaire des cookies fonctionnels de sécurité et partage d’information soumis à votre consentement pour les finalités décrites. Vous pouvez paramétrer le dépôt de ces cookies en cliquant sur le bouton « PARAMETRER » ci-dessous.

Complexity Theory

Ects : 3

Enseignant responsable :

Volume horaire : 15

Description du contenu de l'enseignement :

The course is about complexity of algorithms fundamentals. It mainly handles intractability, reducibility, and notions of completeness/hardness for complexity classes.

Compétence à acquérir :

  • Problems ’ intractability
  • Reductions and class inclusion preservation
  • Role of the parameters in the evaluation of a problem's complexity
  • Complexity classes wrt parameter “ size of instance ” : P, NP, co-NP, Karp and Turing reductions, NP-completeness
  • Complexity classes wrt parameter “ solution value ” , XP, FPT, W[ ]-hierachy, FPT reductions

Bibliographie, lectures recommandées

Bibliography S. Arora, B. Barak, Computational Complexity. A modern approach, Cambridge University Press, 2009. 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.