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 al problema P/NP".
130 pp., 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’ cone le dimostrazioni per induzione e per assurdo.
Metodi Didattici
Insegnamento frontale, Tutoring, Esercitazioni
Modalità di verifica apprendimento
due esercitazioni in classe durante il corso
Esame orale finale
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.