Free University of Bozen-Bolzano
Faculty of Computer Science
Master of Science in Computer Science
Theory of Computing
Final Program A.Y. 2011/2012
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.
- 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
- Circuits and complexity of non-uniform problems [M4, M2]
- circuits and boolean functions
- non-uniform complexity classes
- non-uniform TMs and their relationship to circuits
- Binary Decision Diagrams and their relationship to non-uniform TMs
course home page
Last modified:
Monday, 16-Jan-2012 11:41:01 CET