Informatica Teorica

Informatica Teorica (corso di laurea in Informatica) - Anno accademico 2025/2026

Lezioni svolte:

23/2/2026: Introduzione al corso. Enumerabilità, computabilità, decidibilità e mutue relazioni (2 ore).
25/2/2026: Funzioni ricorsive primitive (2 ore).
26/2/2026: Esempi di funzioni ricorsive primitive, operatori di somma e prodotto limitati (2 ore).
2/3/2026: Relazioni ricorsive primitive, minimalizzazione limitata (2 ore).
4/3/2026: La funzione di Ackermann (2 ore).
5/3/2026: Funzioni mu-ricorsive, tesi di Church per funzioni totali mu-ricorsive, macchine di Turing, esempi, funzioni tau-ricorsive, tesi di Church per funzioni totali tau-ricorsive (2 ore).
9/3/2026: Esempi di macchine di Turing, macchine di Turing come accettatori di linguaggi (2 ore).
11/3/2026: Macchine di Turing multitraccia, limitate a sinistra e multinastro, esempio di macchina di Turing multinastro (2 ore).
12/3/2026: Macchine di Turing non deterministiche, funzioni parziali computabili e tau-ricorsive, tesi di Church generalizzata (2 ore).
16/3/2026: Codifica binaria delle macchine di Turing, teorema dell'arresto, gödelizzazione (2 ore).
18/3/2026: Macchina universale, riducibilità fra linguaggi, esempi, indecidibilità del problema del nastro vuoto (2 ore).
26/3/2026: Proprietà di linguaggi semidecidibili, teorema di Rice, osservazioni ed esempi sul teorema di Rice, ogni funzione mu-ricorsiva è Turing-calcolabile (2 ore).
30/3/2026: Complessità in tempo di una macchina di Turing deterministica, complessità di macchine di Turing multitraccia e multinastro, esempi (2 ore).
1/4/2026: Complessità di macchine di Turing non deterministiche, esempi, le classi P ed NP, problema del circuito hamiltoniano in un grafo diretto (2 ore).

La prossima lezione del corso di Informatica Teorica si terrà giovedì 9 aprile 2026, alle ore 11.30, in aula 005, e durerà 2 ore.

Nella prossima lezione tratteremo i seguenti argomenti: complessità del problema del circuito hamiltoniano in un grafo diretto, riducibilità polinomiale fra linguaggi, la classe dei problemi NP-difficili ed NP-completi, rapporti fra la codifica di un problema e la sua complessità.

Programma del corso

Teoria della calcolabilità: enumerabilità, computabilità, decidibilità; funzioni ricorsive primitive; relazioni ricorsive primitive; funzione di Ackermann, funzioni mu-ricorsive, tesi di Church; macchine di Turing, funzioni tau-ricorsive; macchine di Turing come accettatori di linguaggi formali; macchine di Turing multitraccia, multinastro, non deterministiche; problema dell'arresto, macchina universale; riducibilità tra linguaggi, teorema di Rice.
Teoria della complessità: complessità in tempo di una macchina di Turing; problemi trattabili e intrattabili; le classi P ed NP; riducibilità polinomiale e NP-completezza; teorema di Cook; esempi di problemi NP-completi; test di primalità; altre classi di complessità: classe co-NP, classi EXP e NEXP; complessità spaziale, classe PSPACE, teorema di Savitch; complessità dei problemi di conteggio: classi FP e #P.

Testi di consultazione.

Sanjeev Arora, Boaz Barak, Complexity Theory: A Modern Approach,

Daniel Bovet, Pierluigi Crescenzi, Introduction to the Theory of Complexity, https://www.pilucrescenzi.it/files/books/itc.pdf.

Massimiliano Goldwurm, Introduzione ai Problemi NP-completi, http://homes.di.unimi.it/goldwurm/algo/npcomp.pdf.

John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley.

Daniele Mundici, Dalla macchina di Turing a P/NP, McGraw-Hill.

Michael Sipser, Introduzione alla teoria della computazione, Maggioli Editore.

Thomas A. Sudkamp, Languages and Machines, Addison-Wesley.

Risultati prove scritte

Modalita' d'esame.

L’esame prevede una prova scritta e un colloquio orale.