Salta al contenuto principale della pagina

TEORIA DEGLI AUTOMI E CALCOLABILITÀ

CODICE 80303
ANNO ACCADEMICO 2019/2020
CFU 6 cfu al 3° anno di 8759 INFORMATICA (L-31) GENOVA
SETTORE SCIENTIFICO DISCIPLINARE INF/01
LINGUA Italiano
SEDE GENOVA (INFORMATICA )
PERIODO 1° Semestre
MATERIALE DIDATTICO AULAWEB

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

Introduzione a linguaggi formali e alla teoria degli automi e calcolabilità background considerato core tier nel curriculum ACM/IEEE 2013 e utile in vari contesti quali: compilatori, intelligenza artificiale, database, linguaggi per il web e metodi formali per l'analisi di sistemi

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, alberi di derivazione, ambiguità
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 caloclatore
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.


John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Automi, linguaggi e calcolabilità.

DOCENTI E COMMISSIONI

Commissione d'esame

ELENA ZUCCA (Presidente)

DAVIDE ANCONA

FRANCESCO DAGNINO

GIORGIO DELZANNO

EUGENIO MOGGI

LEZIONI

MODALITA' DIDATTICHE

Tradizionale

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

Data Ora Luogo Tipologia Note
22/01/2020 09:00 GENOVA Scritto
10/02/2020 09:00 GENOVA Scritto
16/06/2020 09:00 GENOVA Scritto
09/07/2020 09:00 GENOVA Scritto
14/09/2020 09:00 GENOVA Scritto