- Docente: Andrea Asperti
- Credits: 12
- 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)
Second cycle degree programme (LM) in Philosophical Sciences (cod. 8773)
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
The programma is essentially divided in two modules, respectively
devoted to Computability and Complexity Theory.
Computability:
Subrecursive languages: primitve recursion, system T;
incompleteness of total formalisms;
Turing Machines and equivalent models of computations;
Church Thesis.
The halting problem and other undecidable problems; Rice
Theorem.
Recursive and recursively enumerable sets; the Rice-Shapiro
Theorem.
Kleene's fixed point theorems.
Reducibility; productive, creative, immune and simple
sets.
Computability and (in)completeness.
Complexity:
Computational problems;
Machines Models and Complexity Measures;
Complexity Classes and their hierarchy; major classes;
reduction;
P vs NP and other open problems;
Oracle machines and the polynomial hierarchy.
Readings/Bibliography
Notes by the teacher.
Additional texts:
N.J.Cutland. Computability. Cambridge University Press.
S.Arora, B.Barak. Computational Complexity: a modern approach.
Cambridge University Press, 2009.
Complexity: C. H. Papadimitriou. Computational Complexity. Addison
Wesley, 1994.
Teaching methods
Frontal lessons. There are slides but I often work at the blackboard.
Assessment methods
Written and oral examination.
Office hours
See the website of Andrea Asperti