Informazioni in aggiornamento fino al 30/06/2026 CODICE 80303 ANNO ACCADEMICO 2026/2027 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 FRANCESCO DAGNINO Ricevimento: Su appuntamento per email PAOLA MAGILLO Ricevimento: Ricevimento su appuntamento concordabile via email (paola.magillo@unige.it) LEZIONI INIZIO LEZIONI In accordo con il calendario didattico approvato dal Consiglio dei Corsi di Studio in Informatica: https://corsi.unige.it/corsi/8759/studenti-orari Orari delle lezioni L'orario di questo insegnamento è consultabile all'indirizzo: Portale EasyAcademy ESAMI MODALITA' D'ESAME L'esame consiste in una prova scritta e in una prova orale.Per poter sostenere la prova oraleè necessario avere superato la prova scritta. Indicazioni per studenti con certificazione di DSA, di disabilità o di altri bisogni educativi speciali sono disponibili a partire da https://corsi.unige.it/corsi/8759/studenti-disabilita-dsa 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. ALTRE INFORMAZIONI Per ulteriori informazioni, consultare il modulo Aulaweb dell'insegnamento o contattare il docente.
