Teoria della calcolabilità: la tesi di Church-Turing, decidibilità, riducibilità. Automi e linguaggi: linguaggi regolari, linguaggi liberi dal contesto. Teoria della complessità: complessità temporale, complessità spaziale, le classi P e NP, le classi EXP e PSPACE.
P. Crescenzi, Informatica teorica, 2011 (dispense disponibili sul web).
Obiettivi Formativi
Conoscenze:
Il corso ha come scopo principale quello di determinare che cosa può essere calcolato e che cosa non può esserlo, con quale modello di calcolo e quanto velocemente.
Competenze acquisite:
Il corso fornirà principi teorici rilevanti anche nella pratica, per la progettazione, lo sviluppo e la gestione di sistemi informatici. In particolare verranno presentate le idee fondamentali dell'informatica teorica, relative ai linguaggi formali, alla teoria della calcolabilità e a quella della complessità.
Capacità acquisite (al termine del corso):
Attraverso lo studio di questi argomenti, gli studenti saranno in grado di affrontare problemi computazionali di notevole portata.
Prerequisiti
Insegnamenti contenenti i prerequisiti (vincolanti e/o consigliati)
Corsi vincolanti: Algoritmi e Strutture Dati, Architetture degli Elaboratori, Matematica Discreta e Logica, Programmazione.
Corsi raccomandati: Algoritmi e Strutture Dati, Architetture degli Elaboratori, Matematica Discreta e Logica, Programmazione.
Metodi Didattici
Numero di ore totali del corso: 225
Numero di ore per studio personale e altre attività formative di tipo individuale: 153
Numero di ore relative alle attività in aula: 72
Altre Informazioni
Frequenza delle lezioni ed esercitazioni: Raccomandata
Strumenti a supporto della didattica UniFi E-Learning: http://e-l.unifi.it
Orario di ricevimento:
Martedì e mercoledì, 14:30 -16:30, oppure su appuntamento.
Viale Morgagni, 65 - 50134 Firenze
Tel. 055 4237452
Fax 055 4796363 - 4237436
E-mail pierluigi.crescenzi@unifi.it
Modalità di verifica apprendimento
Prova scritta e prova orale
Programma del corso
Teoria della calcolabilità: la tesi di Church-Turing (macchine di Turing e loro varianti, concetto di algoritmo), decidibilità (linguaggi decidibili, il problema dell'alt), riducibilità (esempi di problemi indecidibili).
Automi e linguaggi: linguaggi regolari (automi a stati finiti, non determinismo, espressioni regolari, linguaggi non regolari), linguaggi liberi dal contesto (grammatiche libere dal contesto, automi a pila, linguaggi non liberi dal contesto).
Teoria della complessità: complessità temporale (la classe P, la classe NP, NP-completezza), complessità spaziale (teorema di Savitch, la classe PSPACE), classe EXP.