CODICE 80303 ANNO ACCADEMICO 2022/2023 CFU 6 cfu anno 3 INFORMATICA 8759 (L-31) - GENOVA SETTORE SCIENTIFICO DISCIPLINARE INF/01 LINGUA Italiano SEDE GENOVA 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 Apprendere i concetti e i risultati fondamentali della teoria degli automi e della teoria della calcolabilità. 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 ELENA ZUCCA Ricevimento: Su appuntamento. Commissione d'esame ELENA ZUCCA (Presidente) DAVIDE ANCONA RICCARDO BIANCHINI (Supplente) FRANCESCO DAGNINO (Supplente) GIORGIO DELZANNO (Supplente) LEZIONI 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 Data appello Orario 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