### Free University of Bolzano/Bozen

Faculty of Computer Science

Master of Science in Computer Science

# Theory of Computing

# Program A.Y. 2006/2007

**Teaching material.**

**[M1]** *Introduction to Automata Theory, Languages, and
Computation (2nd edition).* J.E. Hopcroft, R. Motwani, J.D. Ullman.
Addison Wesley, 2003.

**[M2]** *Lecture Notes for Theory of
Computing*. Diego Calvanese. 2006. Available on the course web page as
scanned pages in pdf.

**Basic notions** [M1: Chapter 1]
- formal proofs (deductive proofs, proofs by contradiction,
equivalences about sets, inductive proofs)
- basic notions about formal languages

**Regular languages**
- finite automata [M1: Chapter 2]
- regular expressions [M1: Chapter 3]
- properties of regular languages [M1: Chapter 4]

**Context-free languages**
- context-free grammars [M1: Chapter 5]
- pushdown automata [M1: Chapter 6]
- properties of context-free languages [M1: Chapter 7]

**Turing Machines and undecidability**
- The "basic" TM, extended TMs, restricted TMs [M1: Chapter 8]
- recursive enumerability [M1: Chapter 9]
- undecidable problems [M1: Chapter 9]

**Computational complexity** [M1: Chapter 10]
- the classes P and NP
- NP-completeness and NP-complete problems
- polynomial space and the polynomial hierarchy

course home page

*Last modified:
Sunday, 7-Oct-2007 19:15:59 CEST
*