Calcolabilità: enumerabilità, computabilità, decidibilità; funzioni ricorsive primitive; funzione di Ackermann, funzioni mu-ricorsive, tesi di Church; macchine di Turing, funzioni tau-ricorsive; problema dell'arresto, macchina universale; teorema di Rice e problema della corrispondenza di Post.
Complessità: problemi trattabili e intrattabili; le classi P, NP; riducibilità polinomiale, NP-completezza; teorema di Cook; problemi NP-completi; altre classi di complessità; complessità spaziale.
-Thomas A. Sudkamp, "Languages and Machines", Addison-Wesley.
-Giorgio Ausiello, Fabrizio D'Amore, Giorgio Gambosi, "Linguaggi, modelli, complessità", FrancoAngeli.
-John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, "Introduction to Automata Theory, Languages and Computation", Addison-Wesley.
-Massimiliano Goldwurm, "Introduzione ai Problemi NP-completi", http://homes.di.unimi.it/goldwurm/algo/npcomp.pdf.
Obiettivi Formativi
Scopo del corso Ë quello di presentare il concetto di algoritmo, descrivendone diverse formalizzazioni in dettaglio,
quali funzioni ricorsive e macchine di Turing.
Inoltre, si studierà la complessità strutturale degli algoritmi, vale a dire, fissata una quantità di risorse, si cercherà
di individuare la classe dei problemi risolubili da algoritmi che usano al più tale quantità.
Al termine del corso lo studente avrà acquisito una conoscenza di base relativa alla teoria della computabilità e della
complessità e sarà in grado di affrontare problemi di media difficoltà in questi campi, nonché di approfondire la sua
conoscenza della materia per poi affrontare problemi di elevata difficoltà.
Prerequisiti
Algoritmi e Strutture Dati, Matematica Discreta e Logica, Programmazione, Architetture degli Elaboratori
Altre Informazioni
Frequenza delle lezioni: Raccomandata
Orario di ricevimento: su appuntamento, per email (luca.ferrari@unifi.it) o telefono (055 2751484).
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 ed enumeratori di linguaggi formali; problema dell'arresto, macchina universale; teorema di Rice e
problema della corrispondenza di Post.
Teoria della complessità: problemi trattabili e intrattabili; la classe P; la classe NP; riducibilità polinomiale e
NP-completezza; teorema di Cook; esempi di problemi NP-completi; altre classi di complessità; complessità spaziale.