Faculty of Computer Science

Master of Science in Computer Science

Theory of Computing

**9/10/2008**: The results of the final exam of 30/9/2008 are available.

**Objectives.** The objective of the Theory of Computing course is to
introduce and study abstract, mathematical models of computation (such as
Turing machines, formal grammars, recursive functions), and to use the abstract
computation 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
computations 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 (3rd edition).J.E. Hopcroft, R. Motwani, J.D. Ullman. Addison Wesley, 2007.

[M2]Lecture Notes for Theory of Computing. Diego Calvanese. 2007. Will be made available on the course web page as scanned pages in pdf.

*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**- Teaching assistant:
Kurt
Ranalter (follow the link for the office hours)
- Schedule: The course is taught in the 1st semester: from October 8th 2007
to January 19th 2008.
**Lectures**: Seminar Room E221, 2nd floor, Ser E (typically)- Monday 10:30-12:30
- Wednesday 8:30-10:30

**Exercises**: Wednesday: 16:00-18:00,- A-K: Seminar Room E221, 2nd floor, Building E, Diego Calvanese

- L-Z: Seminar Room E420, 4th floor, Building E, Kurt Ranalter

- A-K: Seminar Room E221, 2nd floor, Building E, Diego Calvanese

Some lectures and exercises have been rescheduled, as specified here (lectures and exercises that are outside the regular schedule are marked in yellow).

See also RIS calendar for changes.

**Additional teaching material**- Lecture notes (made available during the course)
- Esercises solved in class (made available during the course)

**Exams**- course program
- exam esercises from the last years (in part with solutions) -- Note that part 1 of the exams deals with topics that are not covered anymore in this course

teaching page of Diego Calvanese