Informatica teorica

A.A. 2021/2022
6
Crediti massimi
48
Ore totali
SSD
INF/01
Lingua
Italiano
Obiettivi formativi
L'insegnamento si propone di introdurre le basi della teoria della calcolabilità e della complessità, presentando opportunamente i necessari strumenti teorici utili anche per affrontare in maniera rigorosa numerose altre problematiche in ambito informatico. Viene affrontato rigorosamente il concetto di problema risolubile per via algoritmica ed esplorata la classe dei problemi non risolubili. Vengono poi presentate la classificazione e la suddivisione dei problemi in classi di complessità, definite in termini di limiti alla quantità di risorse computazionali a disposizione per la loro soluzione automatica.
Risultati apprendimento attesi
Lo studente sarà in grado di applicare gli approcci e gli strumenti formali presentati nell'insegnamento all'analisi di problemi di varia natura. Sarà anzitutto in grado di formulare e modellare correttamente il problema, quindi di analizzare formalmente soluzioni algoritmiche proposte non solo in riferimento a problematiche di efficiente calcolabilità ma considerando e valutando qualunque altro aspetto rilevante al problema in oggetto. Lo studente inoltre acquisirà conoscenze specifiche di calcolabilità e complessità fondamentali in qualunque percorso di ricerca informatica.
Programma e organizzazione didattica

Edizione unica

Responsabile
Periodo
Secondo semestre
Sui siti dedicati all'insegnamento (vedi sotto) verranno tempestivamente pubblicati avvisi riportanti le modalità di erogazione per un'eventuale fase di didattica emergenziale.

In caso di teledidattica, le lezioni verranno erogate via Zoom in modo sincrono e contestualmente registrate per un'eventuale fruizione asincrona. Il programma dell'insegnamento e le risorse per la preparazione dell'esame non subiranno modifiche. L'esame avverrà mediante Zoom secondo la forma e i criteri adottati per l'esame in presenza e sotto riportati.
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
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. In aggiunta alle lezioni tradizionali, sono state approntate anche videolezioni fruibili da chi fosse impossibilitato a frequentare le lezioni dal vivo.
Materiale di riferimento
Testi:
· Dispense 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.

Siti web:
- ARIEL https://cmereghettiit.ariel.ctu.unimi.it/v5/home/Default.aspx
- LEZIONI ONLINE: https://vc.di.unimi.it/
Modalità di verifica dell’apprendimento e criteri di valutazione
L'esame consiste, equivalentemente, di una prova scritta o di una discussione orale (a scelta del docente) 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 scritta è di due ore mentre la durata della prova orale è di circa 40 minuti circa. Durante le prove non è consentita la consultazione di alcuna fonte. Il voto finale è espresso in trentesimi.
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
Docente/i
Ricevimento:
su appuntamento via mail
Uff. A/5/C13, Ed. LITA, V piano, Dipartimento di Fisica "Aldo Pontremoli"