Course Details for A.Y. 2013/2014
Name:
Teoria della Calcolabilità e Complessità / Introduction to Computability and Complexity
Basic information
Credits:
: Laurea in Informatica 6 CFU (b)
Degree(s):
Laurea in Informatica 3° anno curriculum Generale Obbligatorio
Language:
Italian
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