Salta al contenuto principale della pagina

TEORIA DEGLI AUTOMI E CALCOLABILITÀ

CODICE 80303
ANNO ACCADEMICO 2022/2023
CFU
  • 6 cfu al 3° anno di 8759 INFORMATICA (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

    Commissione d'esame

    ELENA ZUCCA (Presidente)

    DAVIDE ANCONA

    RICCARDO BIANCHINI (Supplente)

    FRANCESCO DAGNINO (Supplente)

    GIORGIO DELZANNO (Supplente)

    LEZIONI

    Orari delle lezioni

    L'orario di tutti gli insegnamenti è consultabile su 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 Ora 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