Il corso presenta concetti e risultati della Teoria degli Automi e della Teoria della Calcolabilità di importanza fondamentale nel bagaglio culturale di un informatico.
Apprendere i concetti e i risultati fondamentali della teoria degli automi e della teoria della calcolabilità.
Al termine dell'insegnamento gli studenti avranno acquisito alcuni concetti e risultati fondamentali nella cultura di un informatico (macchina astratta, riconoscimento di linguaggi, funzione calcolabile, decidibilità, halting problem) e saranno in grado di sviluppare semplici automi, anche attraverso l'utilizzo di simulatori.
Nozioni base su insiemi e funzioni; esperienza di programmazione in qualche linguaggio.
Tradizionale
Automi e Linguaggi Alfabeti, stringhe, linguaggi Automi a stati finiti deterministici (DFA) e non deterministici (NFA) Minimizzazione di DFA, espressioni regolari Proprietà di chiusura dei linguaggi regolari, pumping lemma Grammatiche context-free, 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
Note a cura del docente.
Ricevimento: Su appuntamento.
ELENA ZUCCA SCHILLANI (Presidente)
DAVIDE ANCONA
RICCARDO BIANCHINI (Supplente)
FRANCESCO DAGNINO (Supplente)
GIORGIO DELZANNO (Supplente)
In accordo con il calendario didattico approvato dal Consiglio dei Corsi di Studio in Informatica
Scritto e orale
La prova scritta verifica la capacità dello studente di mettere in pratica le nozioni viste a lezione. La prova orale verifica la comprensione dei concetti e la capacità di illustrarli in modo appropriato.
