INFO 0016-1 Introduction à la calculabilité - P. Wolper

Informations générales

• Informations figurant dans le programme des cours.

• Horaire : 1er semestre, le jeudi de 14:00 à 18:00. 

• Local : Institut Montefiore, R3  

• Examen : examen écrit livres fermés (pas d'oral); une interrogation est organisée au cours du semestre (le jeudi 27 octobre 2011 à 16:15) .

• Assistant : Julien Brusten

• Page web consacrée aux exercices

Notes de cours et références

• Transparents (en anglais) 

  • chapitre 1

  • chapitre 2

  • chapitre 3 

  • chapitre 4 

  • chapitre 5 

  • chapitre 6 

  • chapitre 7 

  • chapitre 8 

• Ouvrages de référence:

  • P. Wolper, Introduction à la calculabilité (3ième édition), Dunod, 2006. 

  • Michael Sipser, Introduction to the Theory of Computation, Second Edition, Course Technology, 2005.

  • Lance Fortnow, The status of the P versus NP problem, Communications of the ACM, Volume 52 ,  Issue 9  (September 2009), Pages 78-86
    http://doi.acm.org/10.1145/1562164.1562186