PRESENTAZIONE

Il corso 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 i concetti e i risultati fondamentali della teoria degli automi e della teoria della calcolabilità.

OBIETTIVI FORMATIVI (DETTAGLIO) E RISULTATI DI APPRENDIMENTO

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. 

PREREQUISITI

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

MODALITA' DIDATTICHE

Tradizionale

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

ELENA ZUCCA SCHILLANI (Presidente)

DAVIDE ANCONA

RICCARDO BIANCHINI (Supplente)

FRANCESCO DAGNINO (Supplente)

GIORGIO DELZANNO (Supplente)

LEZIONI

INIZIO LEZIONI

In accordo con il calendario didattico approvato dal Consiglio dei Corsi di Studio in Informatica

Orari delle lezioni

L'orario di questo insegnamento è consultabile all'indirizzo: Portale EasyAcademy

ESAMI

MODALITA' D'ESAME

Scritto e orale

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.

Calendario appelli