L'insegnamento presenta concetti e risultati della Teoria degli Automi e della Teoria della Calcolabilità di importanza fondamentale nel bagaglio culturale di un informatico.
Apprendere le nozioni di automa, riconoscimento di linguaggi, funzione calcolabile. Saper classificare i linguaggi a seconda degli automi in grado di riconoscerli. Essere in grado di valutare se un problema è decidibile/semi-decidibile.
Al termine dell'insegnamento lo studente/la studentessa sarà in grado di:
Conoscere alcuni concetti e risultati fondamentali nella cultura di un informatico (macchina astratta, riconoscimento di linguaggi, funzione calcolabile, decidibilità, halting problem).
Sviluppare semplici automi, anche attraverso l'utilizzo di simulatori.
Nozioni base su insiemi e funzioni; esperienza di programmazione in qualche linguaggio.
Lezioni frontali.
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
FRANCESCO DAGNINO (Presidente 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.
