http://www.inf.unibz.it/~calvanese/teaching/06-07-tc/

### Free University of Bozen-Bolzano

Faculty of Computer Science

Master of Science in Computer Science

# Home page of the course

Theory of Computing

## A.Y. 2006/2007

Course presentation form

**Objectives.** The objective of the Theory of Computing course is to
introduce and study abstract, mathematical models of computation (such as
finite state machines, push down machines, and Turing machines), and to use the
abstract machine models to study the ability to solve computational problems,
by identifying both the intrinsic limitations of computing devices, and the
practical limitations due to limited availability of resources (time and
space). A second objective is to show how to reason and prove properties about
computing in a precise, formal, abstract way.

**Prerequisites.** There are no prerequisites in terms of courses to
attend. Students should be familiar with notions of mathematics and set theory,
and with basic proof techniques, as taught in the mathematics courses of a
bachelor in computer science.

**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.

**Further reading material**
*Elements of the Theory of Computation (2nd edition).*
H.R. Lewis, C.H. Papadimitriou. Prentice Hall. 1998.
*Introduction to the Theory of Computation.* M. Sipser. PWS
Publishing Company. 1997.
*Computational Complexity.* C.H. Papadimitriou. Addison Wesley.
1995.

**Office hours**

**Lectures**: Monday and Wednesday,
10:30-12:30, Seminar Room E221, 2nd floor, Ser E (typically)

See RIS
calendar for changes.

The course is taught in the 1st semester: from October 4th 2006 to
January 17th 2007.

**Exercises**:
Wednesday: 14:00-16:00, Seminar Room E411, 4th floor, Building E

**Additional teaching material**

**Exams**

teaching page of Diego Calvanese

*Last modified:
Sunday, 7-Oct-2007 17:59:00 CEST
*