PRESENTAZIONE

L'insegnamento presenta concetti e risultati della Teoria degli Automi e della Teoria della Calcolabilità di importanza fondamentale nel bagaglio culturale di un informatico.

OBIETTIVI E CONTENUTI

OBIETTIVI FORMATIVI

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.

OBIETTIVI FORMATIVI (DETTAGLIO) E RISULTATI DI APPRENDIMENTO

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. 

PREREQUISITI

Nozioni base su insiemi e funzioni; esperienza di programmazione in qualche linguaggio.

MODALITA' DIDATTICHE

Lezioni frontali.

PROGRAMMA/CONTENUTO

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

TESTI/BIBLIOGRAFIA

Note a cura del docente.

DOCENTI E COMMISSIONI

Commissione d'esame

FRANCESCO DAGNINO (Presidente)

ARNAUD HENRI PAUL SANGNIER (Presidente)

LEZIONI

INIZIO LEZIONI

In accordo con il calendario didattico approvato dal Consiglio dei Corsi di Studio in Informatica: https://corsi.unige.it/corsi/8759/studenti-orari

ESAMI

MODALITA' D'ESAME

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

MODALITA' DI ACCERTAMENTO

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.

ALTRE INFORMAZIONI

Per ulteriori informazioni, consultare il modulo Aulaweb dell'insegnamento o contattare il docente.