http://www.inf.unibz.it/~calvanese/teaching/04-05-tc/

## Free University of Bolzano/Bozen

Faculty of Computer Science - Master of Science in Computer Science

# Home page of the course

Theory of Computing

## A.A. 2004/05

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. 2004. 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 E412, 4rd floor, Ser E (typically)

See RIS
calendar for changes.

The course is taught in the 1st semester: from October 6th 2004 to
January 29th 2005.

**Exercises**:
Wednesday: 16:00-18:00, Seminar Room E412, 4th floor, Building E

**Teaching assistant**:
Andrea Calì

**Additional teaching material**

**Exams**

teaching page of Diego Calvanese

*Last modified:
Wednesday, 13-Jul-2005 0:29:32 CEST
*