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
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.
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.
Cenni su altre classi di complessità (BPP, etc.)