### Free University of Bozen-Bolzano

Faculty of Computer Science

Master of Science in Computer Science

# Theory of Computing

# Final Program A.Y. 2009/2010

**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:
Sunday, 31-Jan-2010 21:42:51 CET
*