Informatica Teorica

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

Lezioni svolte:

24/2/2025: Introduzione al corso. Enumerabilità, computabilità, decidibilità e mutue relazioni (2 ore).
26/2/2025: Funzioni ricorsive primitive (2 ore).
3/3/2025: Esempi di funzioni ricorsive primitive, operatori di somma e prodotto limitati (2 ore).
6/3/2025: Relazioni ricorsive primitive, minimalizzazione limitata (2 ore).
10/3/2025: La funzione di Ackermann (2 ore).
12/3/2025: 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).
13/3/2025: Esempi di macchine di Turing, macchine di Turing come accettatori di linguaggi (2 ore).
17/3/2025: Macchine di Turing multitraccia, limitate a sinistra e multinastro, esempio di macchina di Turing multinastro (2 ore).
20/3/2025: Macchine di Turing non deterministiche, funzioni parziali computabili e tau-ricorsive, tesi di Church generalizzata (2 ore).
24/3/2025: Codifica binaria delle macchine di Turing, teorema dell'arresto, gödelizzazione, macchina universale (2 ore).
26/3/2025: Riducibilità fra linguaggi, esempi, indecidibilità del problema del nastro vuoto (2 ore).
27/3/2025: Proprietà di linguaggi semidecidibili, teorema di Rice, osservazioni ed esempi sul teorema di Rice, ogni funzione mu-ricorsiva è Turing-calcolabile (2 ore).
2/4/2025: Complessità in tempo di una macchina di Turing deterministica, complessità di macchine di Turing multitraccia e multinastro, esempi (2 ore).
7/4/2025: Complessità di macchine di Turing non deterministiche, esempi, le classi P ed NP, problema del circuito hamiltoniano in un grafo diretto (2 ore).
9/4/2025: Complessità del problema del circuito hamiltoniano in un grafo diretto, riducibilità polinomiale fra linguaggi, le classi dei problemi NP-difficili ed NP-completi, impatto della codifica di un problema sulla valutazione della sua complessità (2 ore).
10/4/2025: Polinomi booleani e funzioni booleane, forma normale congiuntiva di un polinomio booleano, problema SAT (2 ore).
14/4/2025: Teorema di Cook (SAT è NP-completo) (2 ore).
16/4/2025: Problemi NP-completi: 3-SAT e VERTEX COVER (2 ore).
23/4/2025: Problemi NP-completi: CLIQUE e HAM (2 ore).
24/4/2025: Polinomialità di 2-SAT. Classi di complessità NPI e co-NP (2 ore).
2/5/2024: Test di primalità. Esercizi su complessità computazionale (2 ore).

Attenzione!!! Il giorno mercoledì 30 aprile 2025 non ci sarà lezione!

La prossima lezione del corso di Informatica Teorica si terrà lunedì 5 maggio 2025, alle ore 11.20, in aula 005, e durerà 2 ore.

Nella prossima lezione tratteremo i seguenti argomenti: Classi di complessità EXP e NEXP.

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,

Pierluigi Crescenzi, Informatica Teorica, piluc.dsi.unifi.it/piluc/?page_id=111.

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.

Le date dei prossimi esami sono le seguenti:

I appello estivo:
-) scritto: 10/6/2025, ore 10.30, aula anfiteatro;
-) orale: 16/6/2025, ore 10.30, aula anfiteatro.

II appello estivo:
-) scritto: 1/7/2025, ore 14.30, aula anfiteatro;
-) orale: 17/7/2025, ore 14.30, aula anfiteatro.

Appello autunnale:
-) scritto: 5/9/2025, ore 10.30, aula anfiteatro;
-) orale: 10/9/2025, ore 10.30, aula anfiteatro.