Macchine di Turing.
La macchina universale.
Nozioni logiche fondamentali di sintassi e semantica delle formule CNF della logica di Boole.
La Classe NP, i problemi NP completi.
Introduzione alla crittografia a chiave pubblica.
Comlessita' dell'algoritmo di Euclide.
D.Mundici, "Dalla macchina di Turing a P/NP", McGraw-Hill, 2013
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.
Conoscenza di un sistema crittografico a chiave pubblica.
Prerequisiti
Il corso e' accessibile a chiunque abbia familiarita’ con le dimostrazioni per induzione e per assurdo.
Metodi Didattici
Insegnamento frontale, Tutoring, Esercitazioni
Altre Informazioni
La frequenza e' consigliata.Ricevimento: Mercoledi' 10.30-12.30
Viale Morgagni 65, Firenze
E-mail daniele.mundici@unifi.it
Modalità di verifica apprendimento
Esame orale
Due esercitazioni in classe durante lo svolgimento del corso
Programma del corso
La Turing calcolabilita'.Funzioni basilari. Conservazione della Turing calcolabilita' per composizione, ricorsione, minimizzazione. Le funzioni primitive ricorsive. 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, TRAVELING SALESMAN. Introduzione alla crittografia a chiave pubblica. Complessita' dell'algoritmo di Euclide.