Free University of Bozen-Bolzano
Faculty of Computer Science
Master of Science in Computer Science
Theory of Computing
Final Program A.Y. 2014/2015
[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.
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.
- Basic notions [M1: Chapter 1]
- basic notions about functions, relations, mathematical logic,
- formal proofs (deductive proofs, proofs by contradiction,
equivalences about sets, inductive proofs)
- Turing Machines [M1: Chapter 8]
- The "basic" TM model
- extended TMs
- Decidability and undecidability [M1: Chapter 9]
- recursive, recursively-enumerable, and non recursively enumerable
- the diagonal and universal languages
- arithmetization of TMs
- Recursive functions [M3]
- primitive recursive functions
- mu-recursive functions
- relationship between TMs and recursive functions
- P, NP, NP-completeness [M1: Chapter 10]
- the classes P and NP
- NP-completeness and NP-complete problems
- Polynomial Hierarchy and PSPACE [M1: Chapter 11, M2]
- complements of languages in NP
- polynomial hierarchy
- the classes PSPACE and NPSPACE
- Logarithmic space
- logspace reductions
- composition of function computations
- the classes L and NL
- Tiling problems
- definition of tiling problems
- encoding Turing machine computations as tilings
course home page
Friday, 16-Oct-2015 19:39:25 CEST