- Docente: Fabio Zanasi
- Credits: 6
- SSD: INF/01
- Language: Italian
- Teaching Mode: Traditional lectures
- Campus: Bologna
-
Corso:
First cycle degree programme (L) in
Computer Science (cod. 8009)
Also valid for First cycle degree programme (L) in Mathematics (cod. 8010)
-
from Feb 21, 2023 to Apr 26, 2023
Learning outcomes
The student will learn the main notions and results of Computability and Complexity Theory. At the end of course the student will be aware of the theoretical and practical limits of computation, and will be able to use and apply methodologies and techniques typical of formal methods to the study and solution of a wide range of algorithmic problems.
Course contents
- Turing machines and equivalent computational models; the Church-Turing thesis
- the Halting problem and other undecidable problems; Rice’s theorem
- Basic Complexity Theory, reductions, P vs NP and other open problems
Readings/Bibliography
- Introduction To The Theory Of Computation - Michael Sipser
- N.J.Cutland. Computability. Cambridge University Press.
Teaching methods
Frontal lessons and exercise sessions.
Assessment methods
Written examination.
Teaching tools
Slides
Office hours
See the website of Fabio Zanasi