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

Theory of Computing

Final Program A.Y. 2014/2015

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. 2013. 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] The Convenience of Tilings. Peter van Emde Boas. In Complexity, Logic, and Recursion Theory, volume 187 of Lecture Notes in Pure and Applied Mathematics, pages 331-363, 1997.

  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. Tiling problems

Back to course home page
Last modified: Friday, 16-Oct-2015 19:39:25 CEST