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:
Le note delle lezioni sono disponibili su Aulaweb. Per approfondimenti potete consultare:
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