Faculty of Computer Science

Master of Science in Computer Science

Theory of Computing

**13/09/2009**: The results of the final Theory of Computing exam of 10/9/2009 are available.

There will be an office hour on Monday 14/9/2009 at 17:30 in my office in via della Mostra 4, where students can discuss their exam and the corrections. After that date, the marks will be finalized.

**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. 2008. 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.*The Church-Turing Thesis.*Copeland, B. Jack. The Stanford Encyclopedia of Philosophy. Fall 2008 Edition.

- Andrew Hodges Alan Turing Home Page.
- For info on simple Turing Machines with complex behaviour, consult Heiner Marxen's web page on Busy Beavers.
- The Lego Turing Machine.

**Office hours**- Teaching assistant:
Kurt Ranalter (follow the
link for the office hours)
- Schedule: The course is taught in the 1st semester: from October 7th
2008 to January 27th 2009.
**Lectures**: Seminar Room C3.6, 3rd floor, Sernesi C (typically)- Tuesday 10:30-12:30
- Wednesday 10:30-12:30

**Exercises**: Tuesday: 15:00-17:00,- A-K: Seminar Room D003, ground floor, Sernesi D, Diego
Calvanese

- L-Z: Seminar Room E221, 2nd floor, Sernesi E, Kurt Ranalter

- A-K: Seminar Room D003, ground floor, Sernesi D, Diego
Calvanese

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)
- course program
- exam esercises from the last years (in
part with solutions).

Note that Part 1 of the exams up to June 2007 deals with topics that are not covered anymore in this course.

**Rules for the written exam**- At the exam, the student has to solve exercises and/or to answer questions on the course topics in written form.
- The exam is divided into two parts, each with a duration of 90
minutes, with 15 minutes break between the two parts:
- Part 1 covers topics 1-4 of the course program;
- Part 2 covers topics 5-8 of the course program.

- The two parts of the exam can be taken together in the same exam session, or separately in different exam sessions.
- Even when the two parts of the exam are taken together, they can be passed separately.
- For a part to be passed, a minimum of 18/30 points is required (half marks are rounded upwards).
- A passed part of the exam (or the passed midterm) is valid until the end of academic year (i.e., exam session of September). If the other part is not passed by then, the passed part is lost and cannot be carried over to the next academic year.
- During the exam, it will
**not**be possible to consult any kind of material, to use pocket calculators or palm PCs, or to leave the exam room before the break/end of the exam.

teaching page of Diego Calvanese