Free University of Bozen-Bolzano
Faculty of Computer Science
Master of Science in Computer Science

Theory of Computing

Final Program A.Y. 2009/2010

Prof. Diego Calvanese

Teaching material.

[M1] Introduction to Automata Theory, Languages, and Computation (3rd edition). J.E. Hopcroft, R. Motwani, J.D. Ullman. Addison Wesley, 2007.

[M2] Lecture Notes for Theory of Computing. Diego Calvanese. 2008. Available on the course web page as scanned pages in pdf.

[M3] Languages and Machines (3rd edition). Thomas A. Sudkamp. Addison Wesley, 2005. Only Chapter 13.

[M4] Complexity Theory. Ingo Wegener. Springer, 2005. Only Chapter 14.

  1. Basic notions [M1: Chapter 1]
  2. Turing Machines [M1: Chapter 8]
  3. Decidability and undecidability [M1: Chapter 9]
  4. Recursive functions [M3]
  5. P, NP, NP-completeness [M1: Chapter 10]
  6. Polynomial Hierarchy and PSPACE [M1: Chapter 11, M2]
  7. Logarithmic space
  8. Circuits and complexity of non-uniform problems [M4, M2]

Back to course home page
Last modified: Sunday, 31-Jan-2010 21:42:51 CET