Macchine di Turing.
La macchina universale.
Cenni di calcolabilità.
Nozioni logiche fondamentali di sintassi e semantica delle formule CNF della logica di Boole.
La Classe NP, i problemi NP completi.
D.Mundici, "Dalla macchina di Turing a P/NP", McGraw-Hill, 2013
Altri testi consigliati:
Garey, Johnson, "Computers and intractability",1979
Le dispense P. Crescenzi: le trovate suo sito. E' un libro per informatici, per cui presenta molto più materiale di quanto vediamo al corso.
Per chi volesse approfondire la complessità di Kolmogorov e l'entropia di Shannon: T. Cover, J. Thomas "Elements of information theory" Wiley (2006)
Per chi volesse approfondire le Zero-Knowledge Proofs: Goldreich, O. "Foundations of Cryptography"
Obiettivi Formativi
Analisi e sintesi di macchine di Turing.
Conoscenza dei teoremi fondamentali della calcolabilita' e della teoria della complessita'.
Capacita' di valutare la complessita' computazionale di un problema.
Prerequisiti
Il corso e' accessibile a chiunque abbia familiarita’ con le dimostrazioni per induzione e per assurdo. E' utile avere una conoscenza di base della programmazione
Metodi Didattici
Insegnamento frontale, Tutoring, Esercitazioni, Seminari degli studenti
Altre Informazioni
La frequenza e' consigliata.
Modalità di verifica apprendimento
Esame orale
Programma del corso
La Turing calcolabilita'. Funzioni basilari. Conservazione della Turing calcolabilita' per composizione, ricorsione, minimizzazione. Le funzioni primitive ricorsive. Le funzioni e gli insiemi/predicati ricorsivi. Operazioni su insiemi/predicati ricorsivi (unione, intersezione, quantificazione limitata). Tesi di Church-Turing (in particolare ricorsivo= Turing-calcolabile). Teorema di Turing sulla macchina universale. Teorema sull'indecidibilita' della fermata. Sintassi e semantica delle formule CNF nella logica di Boole. Distinzione tra procedure di calcolo proibitive e procedure abbordabili. La classe NP. I problemi NP-completi. Il problema P/NP. NP-completezza di CNFSAT, KNAPSACK, COLORABILITY, CLIQUE, INDEPENDENT SET, VERTEX COVER, TRAVELING SALESMAN, e altri: indicativamente, 3 DIMENSIONAL MATCHING, PARTITION, HAMILTON CIRCUIT.
Esempi di problemi in P (indicativamente: connessione di un grafo; stable marriages problem)
Argomenti extra (cenni): altre classi di complessità (BPP, etc.) e/o complessità di Kolmogorov