CODICE 80303 ANNO ACCADEMICO 2020/2021 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 Introduzione a linguaggi formali e alla teoria degli automi e calcolabilità background considerato core tier nel curriculum ACM/IEEE 2013 e utile in vari contesti quali: compilatori, intelligenza artificiale, database, linguaggi per il web e metodi formali per l'analisi di sistemi 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 caloclatore 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 20/01/2021 09:00 GENOVA Scritto 08/02/2021 09:00 GENOVA Scritto 15/06/2021 09:00 GENOVA Scritto 08/07/2021 09:00 GENOVA Scritto 13/09/2021 09:00 GENOVA Scritto