Calcolabilità e complessità computazionale

A.A. 2021/2022
6
Crediti massimi
42
Ore totali
SSD
INF/01
Lingua
Italiano
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.
Programma e organizzazione didattica

Edizione unica

Responsabile
Periodo
Primo semestre
In relazione alle modalità di erogazione delle attività formative per l'anno 2021/22, verranno date informazioni più specifiche nei prossimi mesi, in base all'evoluzione della situazione sanitaria.
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 e il teorema di Savitch.
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.
E' fortemente consigliato 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
- Si prevede di attivare un sito Ariel del presente insegnamento nel portale di Ateneo (https://ariel.unimi.it/).

- 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 citati nel programma.
Il voto è espresso in trentesimi e verrà comunicato immediatamente al termine della prova orale.
INF/01 - INFORMATICA - CFU: 6
Lezioni: 42 ore
Docente/i
Ricevimento:
martedì dalle 9:30 alle 11:30, oppure su appuntamento (accordi per e-mail).
dip. Matematica, via Saldini 50 (ufficio al secondo piano).