An updated version of the notes is available in the Course materials section (see the included Changelog for details).
The exam schedule has been confirmed, dates can be found in the Exams section.
Fall semester, from Monday, September 11 to Tuesday, December 19; four hours per week.
The course sets the theoretical bases for being able to discuss two fundamental properties of computational problems.
Given a problem, we will initially be concerned about its computability:
When a problem is found out to be solvable, we can wonder how efficiently it can be done.
Basic notions of mathematical logic
At the end of the course, the students will be able to:
For the actual program, see below.
The following books may be useful, but none is mandatory. References to online material will be provided in the course program section.
Computational Complexity: A Modern Approach. Cambridge University Press, 2009. ISBN 9780521424264 [Draft of the book]and .
Introduction to Automata Theory, Languages and Computation. Pearson new International Edition, 2013. ISBN: 9781292039053, , and .
Computational complexity. Addison Wesley (Pearson College Div.), 1994. ISBN 9780020153085.
This section will contain course material and exercises.
Nota bene — The initial material is based on previous editions of the course, and will likely change during the Semester.
(See the lecture notes for details)
The exam consists of a written test, with exercises and theoretical questions. Examples are provided in the lecture notes.
|First call||Monday, January 8 2024, 09:00—12:00||Room A103|
|Second call||Monday, February 19 2024, 09:00—12:00||Room A103|