Calcolabilita e Complessita (DM 509)
Obiettivi Formativi
Il modulo si propone di fornire le conoscenze di base della teoria della calcolabilità e della complessità.
Al termine del modulo, gli studenti saranno in grado di capire cos’è un problema indecidibile o intrinsecamente difficile ed eventualmente dimostrarne tali proprietà mediante l’applicazione dei teoremi studiati durante il corso o mediante l’uso di tecniche basate sulla riduzione tra problemi.
Programma e Articolazione del Modulo
- Introduzione al corso, testi consigliati, svolgimento dell’esame. Dagli algoritmi ai problemi. Ciò che si può risolvere e ciò che non si può risolvere (Calcolabilità) Ciò che si può risolvere: a che costo? (Complessità)
- La tecnica della diagonalizzazione. Applicazione al Power Set dei numeri naturali.
- Introduzione ai linguaggi. Linguaggi e problemi di decisione.
- Indecidibilità del problema HELLO-WORLD e riducibilità tra problemi.
- Esercitazione sulle riduzioni tra problemi. Introduzione alla macchina di Turing.
- Esercitazione sulle macchine di Turing (es.: riconoscere i linguaggi ww^r e wcw)
- Macchine di Turing multitraccia e multinastro. Simulazione di una macchina multinastro con una mononastro e costi di esecuzione.
- Introduzione alle macchine di Turing non deterministiche.
- Esercitazione sulle macchine di Turing non deterministiche: data una coppia di stringhe, decidere se la prima è una sottostringa della seconda; colorabilità di un grafo.
- Linguaggi ricorsivamente enumerabili, linguaggi ricorsivi. Teoremi sul complemento dei linguaggi. Il linguaggio Ld ed il linguaggio Lu.
- Ancora sulla indecidibilità: il Teorema di Rice
- Valutazione dei costi di esecuzione in termini di tempo e di spazio. Una gerarchia di classi di complessità.
- Problemi Polinomiali e problemi NP.
- Concetto di riduzione polinomiale tra problemi. Problemi NP-ardui ed NP-completi.
- Esercitazione sulle riduzioni tra problemi.
- Il teorema di Cook.
- Altre classi di complessità. La classe co-NP. Problemi nell’intersezione tra NP e co-NP.
Modalità di Svolgimento dell'Esame
L’esame consiste di una prova scritta obbligatoria e di una prova orale facoltativa (obbligatoria nel caso in cui non sia stata conseguita una soglia minima nella parte scritta).
Materiale Didattico
Altro materiale è disponibile sulla pagina dedicata al corso di Informatica Teorica su icampus (occorre registrarsi)
Orario di Ricevimento
Prof. Francesco Scarcello: mercoledì mattina presso il suo studio (DIMES, cubo 41/C, III piano).