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.


AulaWeb a.a. 21/22

AulaWeb a.a. 20/21

AulaWeb a.a. 19/20

AulaWeb a.a. 18/19

Precedenti edizioni del corso con il nome Fondamenti dell'Informatica:

AulaWeb a.a. 17/18

AulaWeb a.a. 16/17

AulaWeb a.a. 15/16


Programma