Calcolabilità: enumerabilità, computabilità, decidibilità; funzioni e relazioni ricorsive primitive; funzione di Ackermann, funzioni mu-ricorsive, tesi di Church; macchine di Turing; problema dell'arresto, macchina universale; riducibilità tra linguaggi, teorema di Rice.
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.
- Massimiliano Goldwurm, Introduzione ai Problemi NP-completi, http://homes.di.unimi.it/goldwurm/algo/npcomp.pdf.
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley.
- Daniele Mundici, Dalla macchina di Turing a P/NP, McGraw-Hill.
- Michael Sipser, Introduzione alla teoria della computazione, Maggioli Editore.
Obiettivi Formativi
CONOSCENZA E COMPRENSIONE - 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 studiare la classe dei problemi risolubili da algoritmi che usano al più tale quantità.
CAPACITA' DI APPLICARE CONOSCENZA E COMPRENSIONE - 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
Metodi Didattici
Lezioni frontali.
Altre Informazioni
Frequenza delle lezioni: Raccomandata.
Orario di ricevimento: su appuntamento, per email (luca.ferrari@unifi.it) o telefono (055 2751484). Pagina web del docente (contenente anche informazioni relative al corso): http://web.math.unifi.it/users/ferrari/
Modalità di verifica apprendimento
Prova scritta (una domanda sulla parte di computabilità, una domanda sulla parte di complessità, da svolgere in 1,5 ore); prova orale (una domanda sulla parte di computabilità, una domanda sulla parte di complessità). Il voto finale sarà la media dei voti di parte scritta e parte orale. Tra i parametri di valutazione ci sono: capacità di organizzare discorsivamente la
conoscenza; capacità di ragionamento critico sullo studio realizzato; qualità
dell’esposizione; competenza nell’impiego del lessico specialistico, efficacia,
linearità.
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 di linguaggi formali; macchine di Turing multitraccia, multinastro, non deterministiche; problema dell'arresto, macchina universale; riducibilità tra linguaggi, teorema di Rice.
Teoria della complessità: complessità in tempo di una macchina di Turing; problemi trattabili e intrattabili; la classe P; la classe NP; riducibilità polinomiale e NP-completezza; teorema di Cook; esempi di problemi NP-completi (3-SAT, VERTEX COVER, CLIQUE, il problema del circuito Hamiltoniano); altre classi di complessità: classe co-NP, classi EXP e NEXP; complessità spaziale, teorema di Savitch; complessità dei problemi di conteggio: classi FP e #P. Cenni a test di primalità.