Università degli Studi di Firenze
Informatica Teorica.
Laurea
Magistrale
Titolare: Prof. Alessandro Fantechi
Programma
del corso
- Concetti Introduttivi
Richiami su concetti matematici di base - La chiusura transitiva il
principio della piccionaia - la diagonalizzazione - Espressioni regolari.
- Linguaggi Formali
Operazioni sui linguaggi - La gerarchia di Chomsky.
- Linguaggi Regolari
Automi a stati finiti - Automi a stati finiti non deterministici -
Eliminazione del non determinismo - Espressioni regolari e Grammatiche
regolari -il pumping lemma.
- Linguaggi non contestuali
Proprietà di chiusura dei linguaggi non contestuali - Automi a pila -
automi a pila non deterministici - Algoritmi di parsing- Le grammatiche
LL(k) - riconoscitori a discesa ricorsiva.
- Modelli di Calcolo
La Macchina di Turing - Macchina di Turing a nastro singolo - La Macchina
di Turing non deterministica - Cenni sulla riduzione delle macchine di
Turing - La Macchina di Turing Universale - La macchina RAM, analisi
della complessitèè con costi uniformi e costi logaritmici.
- Elementi di teoria della
calcolabilità
La tesi di Church-Turing - Il problema della terminazione - Problemi
indecidibili
- Complessità computazionale
Classi di complessità - La classe P - La classe NP - Esempi di problemi -
Riduzioni polinomiali - La classe NP-completa - Teorema di Cook - Esempi
di problemi - Algoritmi approssimati
Testi
di riferimento
[1] G. Ausiello, F. D'Amore, G.
Gambosi: Linguaggi Modelli e Complessità, Franco Angeli Editore, 2003.
[2] J. Hopcroft, R. Motawani, J.D. Ullman: Automi Linguaggi e Calcolabilità, Pearson, Addison Wesley, 2009.
[3] H.R. Lewis,
C.H. Papadimitriou: Elements of the theory of Computation, Mc
Prentice-Hall, 1998.
Modalità d'esame
L'esame sarà svolto come prova orale. Lo studente, oltre a prepararsi sul programma svolto, dovrà presentare come discussione orale un approfondimento su un argomento concordato con il docente. L'approfondimento sarà condotto autonomamente dallo studente sui testi consigliati o su altri testi disponibili.
In particolare, lo studente potrà scegliere, e indicare all'atto dell'iscrizione sul sito di ateneo, o mediante mail al docente, uno degli argomenti elencati in
questo documento . Il docente potrà chiedere di modificare la scelta in caso le scelte non siano uniformemente distribuite.
Altri documenti utili:
La macchina RAM
Materiale Didattico
(il materiale didattico è derivato da quello preparato dal Prof. Soda negli a.a. precedenti. Ogni modulo corrisponde ad una lezione tenuta nell'a.a. 11-12)
Modulo 1
Modulo 2
Modulo 3
Modulo 4
Modulo 5
Modulo 6
Modulo 7
Modulo 8
Modulo9
Modulo10
Modulo11
Modulo12
Modulo13
Modulo14
Modulo15
Modulo16
Modulo17
Modulo18
Modulo19
Modulo20
Modulo21
Modulo22
Ricevimento
Ricevimento studenti. NUOVO ORARIO DAL 2/11/2011
Prof. Fantechi: Mer. 16:30--17:30, Ven. 9.30-10.30
Calendario
esami
Vedere sito della Facoltà
oppure
chiedere al docente
Alessandro Fantechi