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 1° 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. Gli studenti con certificazioni valide per Disturbi Specifici dell’Apprendimento (DSA), per disabilità o altri bisogni educativi sono invitati a contattare il docente e il referente di Scuola per la disabilità all’inizio dell’insegnamento per concordare eventuali modalità didattiche che, nel rispetto degli obiettivi dell’insegnamento, tengano conto delle modalità di apprendimento individuali. I contatti del referente di Scuola per la disabilità sono disponibili al seguente link https://unige.it/commissioni/comitatoperlinclusionedeglistudenticondisabilita. 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://easyacademy.unige.it/portalestudenti/index.php?view=easycourse&_lang=it&include=corso 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. Gli studenti con certificazioni valide per Disturbi Specifici dell’Apprendimento (DSA) possono richiedere adattamenti in sede d'esame, con almeno 7 giorni di anticipo rispetto alla data dell’esame, compilando il "modulo richieste adattamenti" (dai servizi online https://modulionline.unige.it/richiesta-adattamenti#no-back) che verrà inviato in automatico dal sistema al/alla docente responsabile dell’insegnamento e al/alla docente referente per gli studenti con disabilità e con DSA della propria Scuola/Area. Lo studente riceverà una copia della sua richiesta.
