Corso di Teoria degli Automi e Calcolabilità (Laurea Triennale in Informatica L-31)
Docente: Elena Zucca
Obiettivo
Presentare gli aspetti sintattici ed algoritmici dei linguaggi (riconoscimento di stringhe a seconda del tipo di linguaggio), e introdurre alcuni risultati chiave di calcolabilità (studio dell'espressività computazionale degli elaboratori), relativi alla decidibilità dei problemi, che ne definiscono potenzialità e confini.
Perché è importante?
La Teoria degli Automi e dei Linguaggi ha applicazioni ubique: modellazione di circuiti, linguaggi di programmazione e compilatori, trasformazioni di programmi e modelli di software, sistemi operativi e scripting, intelligenza artificiale e linguaggio naturale, database e semantic web, semantica, modellazione, analisi e verifica di sistemi sequenziali e concorrenti. Inoltre ha applicazioni in campi meno usuali come la biologia e la genetica (automi come modello del comportamento umano, ragionamento su sequenze DNA, ...), nei sistemi industriali e robotica (sistemi ibridi).
La Teoria della Calcolabilità permette di capire cosa si può fare con un elaboratore e cosa invece non si può fare. In particolare dato un particolare problema fornisce metodi formali per capire se il problema ha una soluzione algoritmica completa ed effettiva o se si può risolvere solo in maniera parziale o approssimata. La calcolabilità quindi è propedeutica allo studio della complessità degli algoritmi. La teoria della calcolabilità è nata con il fondamentale lavoro On computable numbers, with an application to the Entscheidungsproblem di Alan Turing.
I contenuti del corso sono inseriti nel corso considerato core AL/Basic Automata Computability and Complexity del Computer Science Curriculum dell'ACM/IEEE (link).
Precedenti edizioni del corso con il nome Fondamenti dell'Informatica:
Programma
- Automi e Linguaggi
- Alfabeti, stringhe, linguaggi, operazioni su linguaggi
- Automi a stati finiti deterministici (DFA) e non deterministici (NFA)
- Minimizzazione di DFA, espressioni regolari
- Proprietà di chiusura dei regolari, pumping lemma
- Grammatiche context-free, alberi di derivazione, ambiguità
- Automi push-down deterministici e non deterministici
- Equivalenza di PDA e grammatiche CF
- Proprietà di chiusura dei linguaggi CF, pumping lemma
- [Gerarchia di Chomsky, linguaggi context-sensitive, risultati di semi-decidibilità e decidibilità]
- Calcolabilità
- Nozione di algoritmo e funzioni ricorsive primitive
- Macchine di Turing e funzioni ricorsive
- Tesi di Church-Turing, numerazione algoritmica delle funzioni ricorsive
- Macchina di Turing universale e calcolatore
- Problema dell'arresto, insiemi ricorsivi e ricorsivamente enumerabili, problemi decidibili e indecidibili
- Riducibilità e teorema di Rice
- Altri modelli di calcolo: funzioni mu-ricorsive, varianti delle macchine di Turing
Testi e link di riferimento
Le note delle lezioni sono disponibili su Aulaweb. Per approfondimenti potete consultare:
- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Automi, linguaggi e calcolabilità (versione in inglese: Introduction to Automata Theory, Languages, and Computation)
- Alan Turing web page
- Un simulatore per automi di vario genere
- Un simulatore macchine di Turing online (se ne trovano molti)
Modalità d'esame
Scritto e orale. Lo scritto consiste di due parti, ognuna della quali può non essere svolta da chi ha già superato il corrispondente compitino. I voti delle due parti fanno media, per superare l'esame scritto il voto di ognuna delle due parti deve essere >= 15 e il voto medio >= 18. Un voto sufficiente allo scritto può essere conservato per i due appelli successivi. I voti dei compitini valgono per tutto l'anno accademico. Durante l'esame scritto è possibile consultare le note.
Ritorno alla pagina precedente
Ultima modifica: 18 ottobre 2019