Informatica teorica
A.A. 2025/2026
Obiettivi formativi
L'insegnamento introduce le basi della teoria della calcolabilità e della complessità, presentando i necessari strumenti teorici utili anche per affrontare in maniera rigorosa numerose altre problematiche in ambito informatico. Viene caratterizzato rigorosamente il concetto di problema risolubile per via algoritmica ed esplorata la classe dei problemi non risolubili. Vengono poi studiati i problemi in base alla richiesta di risorse computazionali impiegate per la soluzione automatica, definendo rigorosamente il concetto di efficienza algoritmica. In tale ambito, viene affrontata la famosa questione P = NP.
Risultati apprendimento attesi
Lo studente acquisirà conoscenze specifiche di calcolabilità e complessità, fondamentali in qualunque percorso di ricerca informatica e, più in generale, nell'analisi rigorosa di problemi di varia natura e relative soluzioni algoritmiche. Sarà anzitutto in grado di formulare e modellare correttamente i problemi, quindi di analizzare formalmente da diversi punti di vista le relative soluzioni algoritmiche.
Periodo: Primo quadrimestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Programma e organizzazione didattica
Edizione unica
Responsabile
Periodo
Primo quadrimestre
Programma
Teoria della calcolabilità
· Prerequisiti matematici
· Funzione coppia
· Linguaggi di programmazione RAM e while
· Sintassi e semantica operazionale
· Compilatori
· Aritmetizzazione di programmi
· Interprete e funzione universale
· Eliminazione del "goto"
· Funzioni ricorsive parziali
· Tesi di Church
· Esistenza di problemi non decidibili
· Passaggio automatico di parametri
· Sistemi di programmazione accettabili
· Teorema di ricorsione
· Insiemi ricorsivi e ricorsivamente numerabili
· Proprietà di chiusura
· Teorema di Rice
Teoria della complessità
· Introduzione alla complessità sequenziale
· Prerequisiti matematici: la notazione "O grande"
· Macchine di Turing deterministiche
· Risorse computazionali: tempo e spazio
· Classi di complessità in tempo e spazio
· Le classi L, P, PSPACE
· Tesi di Church ristretta
· Macchine di Turing nondeterministiche: tempo e spazio
· Le classi NL, NP, NPSPACE
· Teorema di Savitch
· Riduzioni tra problemi e completezza
· Problemi NP-completi, P-completi, PSPACE-completi
· Teorema di Cook ed esempi di riduzione
· Prerequisiti matematici
· Funzione coppia
· Linguaggi di programmazione RAM e while
· Sintassi e semantica operazionale
· Compilatori
· Aritmetizzazione di programmi
· Interprete e funzione universale
· Eliminazione del "goto"
· Funzioni ricorsive parziali
· Tesi di Church
· Esistenza di problemi non decidibili
· Passaggio automatico di parametri
· Sistemi di programmazione accettabili
· Teorema di ricorsione
· Insiemi ricorsivi e ricorsivamente numerabili
· Proprietà di chiusura
· Teorema di Rice
Teoria della complessità
· Introduzione alla complessità sequenziale
· Prerequisiti matematici: la notazione "O grande"
· Macchine di Turing deterministiche
· Risorse computazionali: tempo e spazio
· Classi di complessità in tempo e spazio
· Le classi L, P, PSPACE
· Tesi di Church ristretta
· Macchine di Turing nondeterministiche: tempo e spazio
· Le classi NL, NP, NPSPACE
· Teorema di Savitch
· Riduzioni tra problemi e completezza
· Problemi NP-completi, P-completi, PSPACE-completi
· Teorema di Cook ed esempi di riduzione
Prerequisiti
Nessun particolare prerequisito richiesto.
Metodi didattici
L'insegnamento è costituito da lezioni frontali erogate in modo tradizionale. In tali lezioni vengono proposte anzitutto le basi matematiche necessarie per la formalizzazione precisa dei fondamenti della Teoria della Calcolabilità e della Complessità. Oltre ai concetti relativi alle due discipline, vengono proposti e discussi esercizi e problemi che mirano a consolidare la teoria e a stimolare l'interesse verso argomenti più avanzati che richiedono e sviluppano una certa maturità scientifica.
Materiale di riferimento
Testi:
· Dispense e lucidi reperibili al sito dell'insegnamento (vedi sotto)
· Teoria della calcolabilità:
- A.J. Kfoury, R.N. Mall, M.A. Arbib. Programmazione e computabilità. Etas libri, 1986.
· Teoria della Complessità:
- M.R. Garey, D.S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman, 1979.
Sito web:
- sito del corso sulla piattaforma di ateneo myAriel
· Dispense e lucidi reperibili al sito dell'insegnamento (vedi sotto)
· Teoria della calcolabilità:
- A.J. Kfoury, R.N. Mall, M.A. Arbib. Programmazione e computabilità. Etas libri, 1986.
· Teoria della Complessità:
- M.R. Garey, D.S. Johnson. Computers and intractability. A guide to the theory of NP-completeness. W.H. Freeman, 1979.
Sito web:
- sito del corso sulla piattaforma di ateneo myAriel
Modalità di verifica dell’apprendimento e criteri di valutazione
L'esame consiste di una colloquio orale che copre il più completamente possibile tutti gli argomenti trattati nell'insegnamento di Informatica Teorica. Verranno proposte domande su entrambe le parti che caratterizzano l'insegnamento: teoria della calcolabilità e teoria della complessità. Le domande saranno volte ad accertare la padronanza, da parte dello studente, sia dei concetti base sia della capacità di formalizzare gli stessi nella maniera più precisa possibile. Verranno anche proposte domande in cui si chiederà un contributo "originale" da parte dello studente, al fine di cogliere una certa maturità scientifica. La durata della prova orale è di circa 40 minuti. Il voto finale è espresso in trentesimi. Una valutazione tra 18 e 23 indica un'adeguata conoscenza dei concetti che stanno alla base dell'informatica teorica. Una valutazione tra 24 e 27 indica una buona conoscenza di tali concetti. Valutazioni superiori indicano ottima conoscenza e una certa dose di originalità nell'applicare le bai dell'informatica teorica.
Docente/i
Ricevimento:
su appuntamento via mail
Ufficio S 6008, VI piano, Dip. Informatica "Giovanni Degli Antoni", via Celoria 18, 20133 Milano, Italy