| Crédit : 3 ECTS |
| Langue du cours : anglais
|
|
|
|
Volume horaire
- CM :
15 h
- Volume horaire global (hors stage) :
15 h
Compétences à acquérir
- Learn how to show that a problem does not admit an efficient algorithm
- Learn to recognize different classes of complexity with respect to time and space usage
- Learn the basic relations between deterministic and non-deterministic complexity classes
Description du contenu de l'enseignement
The topic of the course is the fundamentals of computational complexity. Once we have an algorithm for a problem, a question that always poses itself is whether an even better algorithm exists. In this course we will see some of the basic tools of computational complexity theory which allow us to show that certain algorithms cannot be improved. For this, we will discuss complexity classes (including the famous P=NP question), reductions between problems, and prove the basic relations between different classes of complexity.
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.
Enseignant responsable
MICHAIL LAMPIS