CODICE | 80303 |
---|---|
ANNO ACCADEMICO | 2022/2023 |
CFU |
|
SETTORE SCIENTIFICO DISCIPLINARE | INF/01 |
LINGUA | Italiano |
SEDE |
|
PERIODO | 1° Semestre |
MATERIALE DIDATTICO | AULAWEB |
Il corso presenta concetti e risultati della Teoria degli Automi e della Teoria della Calcolabilità di importanza fondamentale nel bagaglio culturale di un informatico.
Apprendere i concetti e i risultati fondamentali della teoria degli automi e della teoria della calcolabilità.
Tradizionale
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: Su appuntamento.
ELENA ZUCCA (Presidente)
DAVIDE ANCONA
RICCARDO BIANCHINI (Supplente)
FRANCESCO DAGNINO (Supplente)
GIORGIO DELZANNO (Supplente)
L'orario di tutti gli insegnamenti è consultabile su EasyAcademy.
Scritto e orale
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.
Data | Ora | Luogo | Tipologia | Note |
---|---|---|---|---|
13/01/2023 | 09:00 | GENOVA | Scritto | |
03/02/2023 | 09:00 | GENOVA | Scritto | |
14/06/2023 | 09:00 | GENOVA | Scritto | |
27/07/2023 | 09:00 | GENOVA | Scritto | |
12/09/2023 | 09:00 | GENOVA | Scritto |