- Docente: Fabio Zanasi
- Credits: 6
- SSD: ING-INF/05
- Language: Italian
- Teaching Mode: Traditional lectures
- Campus: Bologna
-
Corso:
First cycle degree programme (L) in
Mathematics (cod. 8010)
Also valid for First cycle degree programme (L) in Computer Science (cod. 8009)
-
from Feb 21, 2024 to May 16, 2024
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