Informatica Teorica
Riferimenti al libro di testo (Hopcroft, Motwani, Ullmann, versione inglese, seconda edizione):
CAPP. 1,2,3,4,5,6,7,8,9,10
CAP 8: leggere 8.1; escluso 8.5
CAP 9: escluso 9.4;
CAP 10: sono richieste solamente le definizioni di classi P,NP e NP completo in termini di macchine di Turing e
il metodo di applicazione delle riduzioni
Altri argomenti trattati a lezione possono essere trovati nell'edizione vecchia del libro (Hopcroft Ullman):
- teorema di Myhill-Nerode (3.4)
- macchine di Turing generatrici (7.7)
e nel libro di Aho, Hopcroft e Ullman: The design and Analysis of Computer Algorithms
- Modelli formali (leggere)
- Pattern Matching Machines
Obiettivi formativi:
Lo studio di modelli di calcolo e delle nozioni di calcolabilita', decidibilita', trattabilita'; delle correlate gerarchie di automi, linguaggi e grammatiche.
Contenuti:
Nozione di Algoritmo e Modelli di Calcolo: macchine ad accesso casuale,macchine a programma memorizzato, macchine di Turing, relazioni fra le macchine di Turing e macchine a programma memorizzato.
Riconoscitori di Linguaggi: alfabeti, stringhe e linguaggi; grafi ed alberi, insiemi e loro relazioni, caratterizzazioni di linguaggi mediante gerarchie di macchine e di grammatiche.
Automi Finiti ed Espressioni Regolari: sistemi a stati finiti, automi finiti non-deterministici, non-deterministici con epsilon-transizioni, deterministici, espressioni regolari. Applicazioni degli automi finiti al riconoscimento di tutte le occorrenze di una stringa in un' altra.
Proprieta' degli insiemi regolari: il lemma di pompaggio per insiemi regolari, proprieta' di chiusura, algoritmi di decisione, il teorema di Myhill-Nerode e la minimizzazione degli automi finiti.
Grammatiche Libere dal Contesto: definizione ed esempi, alberi di derivazione, semplificazione di grammatiche libere dal contesto,forme normali di Chomsky e Greibach. Automi push-down e loro relazione con le grammatiche libere dal contesto.
Proprieta' dei Linguaggi Liberi dal Contesto: lemma di pompaggio per linguaggi liberi dal contesto, proprieta' di chiusura, algoritmi di decisione.
Macchine di Turing: linguaggi e funzioni computabili, tecniche di costruzione per macchine di Turing, varianti, l' ipotesi di Church, macchine di Turing come enumeratori, restrizioni delle macchine di Turing equivalenti.
Indecidibilita': problemi indecidibili, proprieta' dei linguaggi ricorsivi e ricorsivamente enumerabili, macchine di Turing universali, introduzione alla teoria delle funzioni ricorsive.
Intrattabilita': Le classi P e NP, problemi NP-Completi, riduzioni.
