Free University of Bozen-Bolzano
Faculty of Computer Science
Master of Science in Computer Science
Theory of Computing
Final Program A.Y. 2014/2015
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.
- Basic notions [M1: Chapter 1]
- basic notions about functions, relations, mathematical logic,
formal languages
- 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
languages
- 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
- reductions
- 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
Last modified:
Friday, 16-Oct-2015 19:39:25 CEST