TEORIA DEGLI AUTOMI E CALCOLABILITÀ

TEORIA DEGLI AUTOMI E CALCOLABILITÀ

_
iten
Codice
80303
ANNO ACCADEMICO
2021/2022
CFU
6 cfu al 3° anno di 8759 INFORMATICA (L-31) GENOVA

6 CFU al 2° anno di 9011 MATEMATICA (LM-40) GENOVA

SETTORE SCIENTIFICO DISCIPLINARE
INF/01
LINGUA
Italiano
SEDE
GENOVA (INFORMATICA )
periodo
1° Semestre
materiale didattico

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à.

Modalità 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

Ricevimento: Su appuntamento.

Commissione d'esame

ELENA ZUCCA (Presidente)

DAVIDE ANCONA

GIORGIO DELZANNO (Supplente)

FRANCESCO DAGNINO (Supplente)

RICCARDO BIANCHINI (Supplente)

LEZIONI

Modalità didattiche

Tradizionale

ORARI

L'orario di tutti gli insegnamenti è consultabile su EasyAcademy.

ESAMI

Modalità d'esame

Scritto e orale

Modalità 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.