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.
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
- 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
Link utili
- 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 (o quiz) e orale.
Ritorno alla pagina precedente