[2018-12-14]
The lecture notes have been re-updated, see below. Please check the Changelog.
[2018-12-12]
There is no need to register to the second partial test. All students who passed the first one will be automatically admitted.
[2018-11-13]
The second partial test will take place on Friday 21 december from 5:30pm to 7:30pm in room B107.
[2018-11-12]
Final exam dates are available: see below.
[2018-07-31]
In order to receive urgent updates (e.g., about moved or cancelled lectures), please subscribe to the
comp3 Telegram channel.
From Friday, 2018-09-14 to Friday, 2018-12-21
Exceptions:
Friday, 2018-10-12 (Bachelor graduation session)
Friday, 2018-11-02 (All-saints extended holiday)
Mauro Brunato < mauro.brunato@unitn.it>
Please email me if you want to set up a meeting.
In order to receive urgent updates (e.g., about moved or cancelled lectures), please subscribe to the comp3 Telegram channel.
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
.(See the lecture notes for details)
The exam consists of a written test, with exercises and theoretical questions. Examples will be provided in due time in the lecture notes. The “Computability” part will account for about 1/3rd of the final mark, “Computational Complexity” for the remaining 2/3rds.
Exam dates (still subject to revisions by the administration):
During the course, there will be two partial tests, the first on the Computability part (see below), the second on Complexity. Only students passing the first partial test with a minimum 15/30 mark will be admitted to the second one.
Students passing both partial tests will receive the weighted average of their partial marks as their final course mark.