INFO 0016-1 Introduction to the Theory of Computation - P. Wolper

General Information

• Information from the university course catalog


• Schedule : 1st quarter, Tuesdays from 8:30 to 12:30
  


• Location: Institut  Montefiore (B28), room R7


• Exam: closed book written exam (no oral exam)
• A bonus is given for active participation in the problem sessions


• Assistant: Isabelle Mainz


• Information on  exercises

Course Notes

• Chapter 1
• Chapter 2
  
• Chapter 3 
  
• Chapter 4 
  
• Chapter 5 
  
• Chapter 6 
  
• Chapter 7 
  
• Chapter 8 

References

• 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. Available at http://doi.acm.org/10.1145/1562164.1562186