Course Details for A.Y. 2013/2014

The information on this page refer to the academic year 2013/2014. Therefore, several links are not available and data may be incomplete. To read the current information on the course, if it is still available, go to the university course catalogue . To read information relating other academic years, use the list at the bottom of this page.

A. Year:

2013/2014

Name:

Teoria della Calcolabilità e Complessità / Introduction to Computability and Complexity

Type:

Course

Basic information

Code:

F0150

Sector:

INF/01

Credits:

: Laurea in Informatica 6 CFU (b)

Term:

1° semestre

Degree(s):

Laurea in Informatica 3° anno curriculum Generale Obbligatorio

Language:

Italian

Teacher(s):

Filippo Mignosi

Propaedeutics:

Algorithms and Data Structures with Lab

Course Objectives

Sapere e avere capito che il concetto di algoritmo è "robusto". Capire e conoscere i limiti di cosa si può fare e cosa non si può fare con un computer. Conoscere le principali classi di complessità con le loro proprietà.

Course Content

The Theory of computability. Countability, models of computation and Church's thesis, Turing machine, nondeterministic computation. Counters machine.
Calculable and non-calculable functions and languages, recursive and recursively enumerable sets. Languages and problems, acceptability and decidability of languages.
Diagonalization techniques, reductions, universal language, Rice's theorem.
Elements of the theory of complexity : static and dynamic measures, time and space complexity classes, the classes P and NP. The conjecture P = NP? NP-completeness.
Polynomial reductions. Theorems concerning NP-completeness. Statement of the Cook's theorem. CSAT, 3SAT and other NP-complete problems.
Class PS and NPS, Savitch's theorem. Elements of modular arithmetic and cryptography.

Prerequisites and Learning Activities

Lo studente deve avere avuto esperienze di programmazione e avere la conoscenza intuitiva di cosa sia un algoritmo. Deve conoscere bene la ricorsione e le visite di alberi e grafi.

Assessment Methods and Criteria

Scritto e orale. Lo scritto è "taglia-basso", ovvero serve a escludere dall'orale chi non possiede a livello accettabile le definizioni fondamentali e alcuni teoremi di base. L'orale è lungo e spazia su tutta la materia.

Textbooks

Hopcroft, Motwani, Ullman, AUTOMI LINGUAGGI E CALCOLABILITA' , Pearson, Addison Wesley. PARTE DEI CAPITOLI 1, 8, 9, 10 e 11.
Arora Barak, Computational Complexity: a modern approach , Cambridge University press. Testo di approfondimento

Notes

This course treats some aspects of the theory of Computability and of the Complexity theory and, further, some relations among these two theories.

Course page updates

This course page is available (with possible updates) also for the following academic years:

To read the current information on this course, if it is still available, go to the university course catalogue .

Course information last updated on: 17 ottobre 2013, 10:13