Calcolabilità e complessità computazionale
A.A. 2024/2025
Obiettivi formativi
Un primo obiettivo dell'insegnamento è quello di introdurre la nozione di calcolabilità usando semplici linguaggi di programmazione. Ricordiamo che una funzione si dice calcolabile (e un problema decidibile) se esiste un algoritmo che la calcola (lo risolve). In particolare vogliamo illustrare e motivare la tesi di Church, lo studio dei problemi indecidibili, i risultati fondamentali della teoria della ricorsività. Un secondo obiettivo riguarda invece la classificazione dei problemi decidibili in base alla loro complessità computazionale, ovvero la quantità di tempo di calcolo e/o spazio di memoria necessari per risolverli. In particolare si intende presentare e motivare lo studio dei problemi NP-completi.
Risultati apprendimento attesi
Comprensione dei principali concetti di calcolabilità e decidibilità. Capacità di riconoscere l'indecidibilità e la difficoltà dei problemi nei casi principali. Capacità di studiare e formalizzare modelli di calcolo.
Periodo: Primo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento può essere seguito come corso singolo.
Programma e organizzazione didattica
Edizione unica
Responsabile
Periodo
Primo semestre
Programma
Introduzione alla calcolabilità: le funzioni intuitivamente calcolabili, esistenza di funzioni non calcolabili, la funzione coppia e le sue estensioni. Sintassi e semantica del linguaggio RAM ridotto. Sintassi e semantica del linguaggio While. Esempio di funzione compilatore e di funzione interprete. Equivalenza computazionale tra linguaggio RAM e linguaggio While. Aritmetizzazione dei programmi RAM. Funzioni ricorsive parziali. Tesi di Church.
Sistemi di programmazione accettabili. Il teorema di ricorsione e il teorema di isomorfismo. I problemi indecidibili. Problemi particolari: arresto, totalità, equivalenza. Insiemi ricorsivi e ricorsivamente numerabili. Caratterizzazioni principali degli insiemi ricorsivamente numerabili. Riducibilità tra insiemi e insiemi completi. Insiemi che rispettano le funzioni. Il teorema di Rice.
Linguaggi e grammatiche formali. Gerarchia di Chomsky: linguaggi regolari, liberi da contesto, dipendenti da contesto, di tipo 0. Automi a stati finiti deterministici, non deterministici e loro proprietà di simulazione. Linguaggi regolari: lemma di iterazione e proprietà di chiusura rispetto alle operazioni booleane.
Macchine di Turing. Macchine deterministiche e non deterministiche. Proprietà di simulazione tra modelli. Classi di complessità in tempo. Classi P e NP. Riducibilità in tempo polinomiale e suoi esempi notevoli. I problemi NP-completi. Il teorema di Cook. Introduzione alla complessità in spazio: le classi L, NL, Pspace. Complessità del problema della raggiungibilità. Il teorema di Savitch. Teorema di Immermann-Szelepscényi
Sistemi di programmazione accettabili. Il teorema di ricorsione e il teorema di isomorfismo. I problemi indecidibili. Problemi particolari: arresto, totalità, equivalenza. Insiemi ricorsivi e ricorsivamente numerabili. Caratterizzazioni principali degli insiemi ricorsivamente numerabili. Riducibilità tra insiemi e insiemi completi. Insiemi che rispettano le funzioni. Il teorema di Rice.
Linguaggi e grammatiche formali. Gerarchia di Chomsky: linguaggi regolari, liberi da contesto, dipendenti da contesto, di tipo 0. Automi a stati finiti deterministici, non deterministici e loro proprietà di simulazione. Linguaggi regolari: lemma di iterazione e proprietà di chiusura rispetto alle operazioni booleane.
Macchine di Turing. Macchine deterministiche e non deterministiche. Proprietà di simulazione tra modelli. Classi di complessità in tempo. Classi P e NP. Riducibilità in tempo polinomiale e suoi esempi notevoli. I problemi NP-completi. Il teorema di Cook. Introduzione alla complessità in spazio: le classi L, NL, Pspace. Complessità del problema della raggiungibilità. Il teorema di Savitch. Teorema di Immermann-Szelepscényi
Prerequisiti
Conoscenza generale degli algoritmi di base, delle strutture dati principali e di almeno un linguaggio di programmazione di tipo imperativo, avendo svolto una corrispondente attività di programmazione elementare.
Si consiglia quindi di aver superato l'esame di un insegnamento di Programmazione e di uno di Algoritmi, svolti nell'ambito di un corso di laurea triennale.
Si consiglia quindi di aver superato l'esame di un insegnamento di Programmazione e di uno di Algoritmi, svolti nell'ambito di un corso di laurea triennale.
Metodi didattici
Il corso sarà erogato mediante lezioni tradizionali.
Materiale di riferimento
- Sito web dell'insegnamento: http://users.mat.unimi.it/users/goldwurm/Calcolabilita
dove sarà riportato anche il link alla pagina MyAriel del corso per il nuovo anno accademico.
- Dispense del Corso:
M. Goldwurm, Computabilità e complessità computazionale, Università degli Studi di Milano, Gennaio 2019, scaricabili dai siti sopra menzionati.
- Testi di riferimento:
A. Bertoni, Introduzione alla calcolabilità, Dispense del corso di Informatica Teorica, parte 1, Univ. degli Studi di
Milano, 1990.
A. Kfoury, R. Moll, M. Arbib, A Programming Approach to Computability, Springer-Verlag, 1982.
Versione italiana (stessi autori): Programmazione e computabilità, Etas Libri, 1986.
J. Hopcroft, J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1997.
C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
J. Hopcroft, R. Motwani, J. Ullman, Introduction to Automata Theory, Languages, and Computation, 2001.
dove sarà riportato anche il link alla pagina MyAriel del corso per il nuovo anno accademico.
- Dispense del Corso:
M. Goldwurm, Computabilità e complessità computazionale, Università degli Studi di Milano, Gennaio 2019, scaricabili dai siti sopra menzionati.
- Testi di riferimento:
A. Bertoni, Introduzione alla calcolabilità, Dispense del corso di Informatica Teorica, parte 1, Univ. degli Studi di
Milano, 1990.
A. Kfoury, R. Moll, M. Arbib, A Programming Approach to Computability, Springer-Verlag, 1982.
Versione italiana (stessi autori): Programmazione e computabilità, Etas Libri, 1986.
J. Hopcroft, J. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 1997.
C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.
J. Hopcroft, R. Motwani, J. Ullman, Introduction to Automata Theory, Languages, and Computation, 2001.
Modalità di verifica dell’apprendimento e criteri di valutazione
L'esame consiste di una prova orale riguardante gli argomenti inclusi nel programma. Ai candidati è richiesta la conoscenza precisa delle definizioni delle nozioni fondamentali elencate nel programma, la capacità di fornire esempi significativi delle loro proprietà e di presentare la dimostrazione dei risultati principali.
Il voto è espresso in trentesimi e verrà comunicato immediatamente al termine della prova orale.
Il voto è espresso in trentesimi e verrà comunicato immediatamente al termine della prova orale.
INF/01 - INFORMATICA - CFU: 6
Lezioni: 42 ore
Docente:
Goldwurm Massimiliano
Turni:
Turno
Docente:
Goldwurm MassimilianoSiti didattici
Docente/i
Ricevimento:
su appuntamento (accordi per e-mail).
dip. Matematica, via Saldini 50 (ufficio al secondo piano).