CODICE 80303 ANNO ACCADEMICO 2025/2026 CFU 6 cfu anno 3 INFORMATICA 8759 (L-31) - GENOVA SETTORE SCIENTIFICO DISCIPLINARE INF/01 LINGUA Italiano SEDE GENOVA PERIODO 2° Semestre MATERIALE DIDATTICO AULAWEB PRESENTAZIONE L'insegnamento 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 le nozioni di automa, riconoscimento di linguaggi, funzione calcolabile. Saper classificare i linguaggi a seconda degli automi in grado di riconoscerli. Essere in grado di valutare se un problema è decidibile/semi-decidibile. OBIETTIVI FORMATIVI (DETTAGLIO) E RISULTATI DI APPRENDIMENTO Al termine dell'insegnamento lo studente/la studentessa sarà in grado di: Conoscere alcuni concetti e risultati fondamentali nella cultura di un informatico (macchina astratta, riconoscimento di linguaggi, funzione calcolabile, decidibilità, halting problem). Sviluppare semplici automi, anche attraverso l'utilizzo di simulatori. PREREQUISITI Nozioni base su insiemi e funzioni; esperienza di programmazione in qualche linguaggio. MODALITA' DIDATTICHE Lezioni frontali. 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 ARNAUD HENRI PAUL SANGNIER Ricevimento: Ricevimento su appuntamento via mail. FRANCESCO DAGNINO 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.
