Calculabilité et complexité
Pierre Wolper est l'auteur de l'ouvrage
Introduction à la calculabilité publié chez Dunod sur lequel
ce cours est basé.
Les transparents ont été rédigés par
Jean-François Raskin.
Plan
Indécidabilité du problème de l'arrêt
Cardinalité
- dénombrabilité, technique de la diagonale de Cantor
- applications : exemples d'ensembles infinis dénombrables et non-dénombrables
Automates finis (rappels)
Machines de Turing
- définitions des MTD et MTND,
exemple 1,
exemple 2 (format SVG)
et exemple 3 (format PNG)
- langage accepté, langage décidé
- la thèse de Church-Turing
- extensions des MT et simulation des extensions
- machines de Turing universelles :
Décidabilité - Indécidabilité
- les classes R et RE, R ⊆ RE
- L0 n'est pas dans RE, le complément de L0 est dans RE
- technique de réduction, LU et son complément, H et son complément
- énumération des mots acceptés par une MT
Complexité d'algorithmes classiques
Théorie de la complexité
- définition de la classe P, justification de la robustesse de P
- définition des problèmes TS et HC, transformation polynomiale, HC α TS
- langages polynomialement équivalents
- définition NP, NP-complet et NP-dur
- P ⊆ NP, statut de P = NP
- preuve du théorème : si un langage de NPC est dans P alors P = NP
- définition de SAT, théorème de Cook, schéma de sa preuve
- définition 3SAT, VC, tous deux dans NPC
Culture générale
- quelques scientifiques de renom et leurs apports à l'informatique
PDF
Fiches d'exercices
Evaluation
En contrôle continu : deux partiels sans document ni appareil électronique.
Revoir tous les exercices corrigés en cours et TD et apprendre
toutes les questions de cours listées ci dessus.
Annales
Ressources
Fred Mesnard
