1. Home
  2. Corsi
  3. Insegnamenti dei corsi di laurea
  4. Informatica teorica

Informatica teorica

A.A. 2024/2025
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.

Periodo: Secondo semestre

Orari delle lezioni

Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi

Calendario degli appelli

Corso singolo

Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.

Cerca un corso singolo
Programma e organizzazione didattica

Edizione unica

Responsabile
Mereghetti Carlo
Periodo
Secondo semestre

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.
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:
- myAriel https://myariel.unimi.it/course/view.php?id=2431
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.
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
Docente: Mereghetti Carlo
Turni:
Turno
Docente: Mereghetti Carlo
Docente/i
Mereghetti Carlo
Sito web
Ricevimento:
su appuntamento via mail
Uff. S 6008, VI piano, Dip. Informatica "Giovanni Degli Antoni", via Celoria 18, 20133 Milano, Italy