Free University of Bolzano/Bozen
Faculty of Computer Science - Master of Science in Computer Science
Theory of Computing
Preliminary program A.A. 2004/2005
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. 2004. 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:
Tuesday, 26-Oct-2004 15:16:37 CEST