Dettagli sull'Insegnamento per l'A.A. 2013/2014

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.

Obiettivi

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à.

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.

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

• A.A. 2011/2012
• A.A. 2012/2013
• A.A. 2013/2014
• A.A. 2014/2015
• A.A. 2015/2016
• A.A. 2016/2017
• A.A. 2017/2018
• A.A. 2018/2019
• A.A. 2019/2020