Cours de Calculabilité et décidabilité

Licence en Informatique — Université de Paris 13
2012/2013

Intervenants

Michele Pagani (Cours et TD)

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

• TD 1: 18 et 25 janvier
  rappel des propriétés élémentaires des fonctions et ensembles, essentielles pour la suite du cours.
  • énoncé TD 1

• TD 2: 31 janvier
  Le langage WHILE: expressions booléennes, listes, entiers naturels.
  • énoncé TD 2

• TD 3: 14 et 21 février
  Sémantique des programmes de WHILE: expressions, commandes, programmes.
  • énoncé TD 3

• TD 4: 28 février
  Éléments de théorie de la calculabilité: décidable, indécidable, théorème de Rice.
  • énoncé TD 4

• PRE-PARTIEL: 14 mars
  
  • énoncé avec solutions

• TD 5: 4 et 11 avril
  
  • énoncé TD 5

• TD 6: 18 et 25 avril
  
  • énoncé TD 6

• PRE-EXAMEN: 16 mai
  
  • énoncé avec solutions