[ Aymeric Vincent's home page ]
Calculabilité et complexité
Cours d'introduction à la calculabilité et à la complexité dispensé en
deuxième année en filière informatique (IF228).
Cours
| Fragments de notes de cours |
[HTML] |
Séance du 17 janvier 2012
- Présentation, objectifs, bibliographie
- Rappels sur les mots et les langages
- Problème, algorithme
- Formalisation
- Machines de Turing
- Exemple : +1 sur un nombre binaire
Séance du 20 janvier 2012
- Exécution maximale et résultat d'une machine
- Thèse de Church-Turing
- Langage reconnu
- Langage décidé
- L r.e. et Comp(L) r.e. alors L récursif
- Machines à plusieurs rubans
- Exemple : tester si un mot est un palindrome
Séance du 23 janvier 2012
- Machine de Turing universelle
- Preuve qu'il existe des langages qui ne sont pas récursivement
énumérables
- Preuve que HALT est récursivement énumérable mais pas récursif
- Notion de réduction
- Théorème de Rice
Séance du 27 janvier 2012
- Notations TIME, SPACE
- Retour sur les machines de Turing non-déterministes
- Notations NTIME, NSPACE
- Notations grand-O, grand-Omega, theta
- Preuve que P est inclus dans NP
- Notion de vérificateur et preuve d'équivalence vérificateur
déterministe dans P -- appartenance à NP
- Retour sur la notion de réduction
- Doivent se faire en LOGSPACE pour les classes de complexité qui
nous intéressent
-
- Transitivité plus difficile à prouver
- L'ensemble des réductions forme un pré-ordre
- Notions de problème dur, facile, et complet pour une classe
- Introduction aux formules booléennes et au problème SAT
Séance du 7 février 2012
- Formules booléennes
- Théorème de Cook-Levin : SAT est NP-complet
- Exemple de réduction : CLIQUE est NP-complet
- Théorème de Savitch : ACCESSIBILITE appartient à SPACE(log(n)^2)
- Relations entre des classes TIME/SPACE/NTIME/NSPACE
- PSPACE
Bibliographie
- Computational Complexity, Christos Papadimitriou, Addison
Wesley Longman
- Introduction à la calculabilité, Pierre Wolper,
InterEditions
- Introduction to the theory of computation, Michael Sipser,
Course technology