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

Theory of Computing

Final Program A.Y. 2011/2012

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: Monday, 16-Jan-2012 11:41:01 CET