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:
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: Ricevimento su appuntamento via mail.
Ricevimento: Su appuntamento per email
ARNAUD HENRI PAUL SANGNIER (Presidente)
GIORGIO DELZANNO
ELENA ZUCCA SCHILLANI
FRANCESCO DAGNINO (Presidente Supplente)
In accordo con il calendario didattico approvato dal Consiglio dei Corsi di Studio in Informatica: https://corsi.unige.it/corsi/8759/studenti-orari
L'esame consiste in una prova scritta e in una prova orale.Per poter sostenere la prova oraleè necessario avere superato la prova scritta.
Indicazioni per studenti con certificazione di DSA, di disabilità o di altri bisogni educativi speciali sono disponibili a partire da https://corsi.unige.it/corsi/8759/studenti-disabilita-dsa
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.
Per ulteriori informazioni, consultare il modulo Aulaweb dell'insegnamento o contattare il docente.
