Dettagli sull'Insegnamento per l'A.A. 2015/2016

Le informazioni che state leggendo si riferiscono all'anno accademico 2015/2016. Per questo molti collegamenti non sono disponibili e i dati potrebbero essere incompleti. Per leggere le informazioni correnti sul corso, se ancora erogato, consulta il catalogo corsi di ateneo. Per consultare le informazioni relative ad altri anni accademici, usa la lista in fondo a questa pagina.

A. Accademico:

2015/2016

Nome:

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

Tipo:

Corso singolo

Informazioni

Codice:

F0150

SSD:

INF/01

Crediti:

: Bachelor Degree in Computer Science 6 CFU (b)

Periodo:

1^st semester

Erogazione:

Bachelor Degree in Computer Science 3^rd anno curriculum General Compulsory

Lingua:

Italiano

Docenti:

Michele Flammini

Propedeuticità:

Algoritmi e Strutture Dati con Laboratorio

Prerequisiti

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, sia in modo ricorsivo, sia utilizzando strutture di dati classiche come code e pile.

Obiettivi

Il corso ha lo scopo di fornire motivazioni, definizioni e tecniche di base della Teoria della Calcolabilità e della Teoria della Complessità. Alla fine del corso, dopo avere superato l'esame, lo studente deve essere in grado di conoscere la nozione di algoritmo in molte sue declinazioni equivalenti e le limitazioni di tale nozione. Deve conoscere le principali classi di linguaggi, sia nella Teoria della Calcolabilità che nella Teoria della Complessità e le loro principali proprietà. Deve inoltre conoscere i principali strumenti tecnici utilizzati in queste teorie, come, ad esempio le tecniche di diagonalizzazione, le riduzioni e le riduzioni polinomiali

Sillabo

Elementi di teoria della calcolabilita': numerabilita', modelli di calcolo e tesi di Church, macchina di Turing, calcolo non deterministico. Macchine a contatori.
Funzioni e linguaggi calcolabili e non calcolabili, insiemi ricorsivi e ricorsivamente enumerabili. Linguaggi e problemi, accettabilita' e decidibilita' di linguaggi.
Tecniche di diagonalizzazione, riduzioni, linguaggio universale, Teorema di Rice.
Elementi di Teoria della complessita': misure statiche e dinamiche, classi di complessita' spaziali e temporali, le classi di problemi P ed NP. La congettura P=NP? NP-completezza.
Riduzioni polinomiali. Teoremi riguardanti la NP-completezza. Enunciato del teorema di Cook. CSAT, 3SAT e altri problemi NP-completi.
Classe PS e NPS, Teorema di Savitch. Cenni di aritmetica modulare e crittografia.

Descrittori di Dublino

Alla fine del corso, lo studente dovrebbe

have acquired motivation, definitions and basic techniques of the Theory of Computability and of the Complexity Theory. The student should be able to understand and read literature concerning the basics of both theories . The student should be able to use the language adopted by the scientific community that concerns these two theories.
be able to recognize and organize autonomously basic topics of both theories treated in the course in related applications. In particular the student should know the notion of algorithm and several of its equivalent formulations. The student should also know the boundaries of this notion. The student should know the main classes of languages and their main properties both in Theory of Computability and in Complexity Theory. The student should also know the main techniques used in these theories, such as the techniques of diagonalization, the notion of reduction and of polynomial reduction. The student should be able to apply this knowledge mainly in order to avoid impossible or almost impossible requests (such as "create a program that checks if another generic program perform the desired task" or "create a fast program that tell us if a TSP instance has an affermative answer) and direct his energy in other directions that can be valid under stronger assumption.
be able to understand that the choice of a particular programming language depends mainly on the productivity and not on its computational power. The student should also be able to assess the relevance the main topics of both theories and to link the theoretical aspects of both theories with the practical aspects.
be able to describe the main results of the Theory of Computability and of the Complexity Theory to other non-specialist people in the scientific community.
be able to read and understand books and papers concerning the arguments treated in the course. The student should be able, using also the knowledge acquired in this course, to follow more advanced studies in Computer Science (such as masters or second-level university degrees) and also other more complex courses and/or seminars related to both theories treated in the course.

Testi di riferimento

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

Modalità d'esame

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.

Note

In questo corsi si affrontano le tematiche di base della teoria della Calcolabilità e della teoria della Complessità e alcune relazioni tra le due teorie.

Aggiornamenti alla pagina del corso

Le informazioni sulle editioni passate di questo corso sono disponibili per i seguenti anni accademici:

Per leggere le informazioni correnti sul corso, se ancora erogato, consulta il catalogo corsi di ateneo.

Ultimo aggiornamento delle informazioni sul corso: 12 novembre 2015, 17:11