Cours de Calculabilité et décidabilité
Licence en Informatique — Université de Paris 13
2011/2012
Intervenants
- Michele
Pagani (Cours et TD G1)
- Etienne
Duschesne (TD G2 et TD G3)
Texte de référence
Sections I et II du livre de Neil Jones
“Computability and Complexity”, MIT Press 1997, ISBN 0-262-10064-9,
disponible en ligne ici
Sujets de TD
-
TD 1: 26 janvier
rappel des propriétés élémentaires des fonctions et ensembles, essentielles pour la suite du cours.
-
TD 2: 2 février
ensembles dénombrables, argument de la diagonale de Cantor.
-
TD 3: 9 février
Le langage WHILE: expressions booléennes, listes, entiers naturels.
-
TD 4: 16 février
Sémantique des programmes de WHILE: expressions, commandes, programmes.
-
TD 5: 16 février et 8 mars
Éléments de théorie de la calculabilité:
décidable, indécidable, théorème de Rice.
-
TD 6: 15 mars
Correction du pre-partiel.
-
TD 7: 29 mars, 5 et 12 avril
Autres modèles de calcul: GOTO, CM, RAM, TM.
-
TD 8: 3 mai
Correction du partiel.
-
TD 9: 10 mai
Correction du pre-examen.