Indice degli argomenti

  • Introduzione

    Minimizza tutto Espandi tutto

    Per spiegazioni (oltre alla docente) è disponibile il dott. Francesco Dagnino.

    Obiettivi e contenuti

    Nella prima parte del corso (Teoria degli Automi) si considera il problema del riconoscimento, essenziale per qualunque applicazione informatica. Un automa riconoscitore ha lo scopo di determinare se una stringa appartiene o meno a un certo linguaggio. Si descrivono in particolare  gli automi a stati finiti, riconoscitori per i linguaggi regolari, e gli automi a pila, riconoscitori per i linguaggi context-free. La Teoria degli Automi ha applicazioni ubique: tra queste, modellazione di circuiti, compilatori, trasformazioni di programmi, intelligenza artificiale, database e semantic web, analisi e verifica di sistemi sequenziali e concorrenti. Ha anche applicazioni in campi meno usuali come la biologia e la genetica (automi come modello del comportamento umano, ragionamento su sequenze DNA, ...), i sistemi industriali e la robotica (sistemi ibridi).

    Nella seconda parte del corso (Teoria della Calcolabilità) si considera il problema della calcolabilità. Ossia, lo scopo è quello di rispondere ad alcune domande, sorte con la nascita stessa dell'informatica: è possibile risolvere qualunque problema con un elaboratore? se no, quali sono esempi di problemi che non si possono risolvere? i diversi linguaggi di programmazione, o altri formalismi per esprimere algoritmi, sono tutti ugualmente potenti? In risposta a queste domande, si presentano alcune nozioni e risultati classici, fondamentali per la cultura di un informatico, in particolare si forniscono metodi formali per capire se un problema ha una soluzione algoritmica.  La teoria della calcolabilità è nata con il fondamentale lavoro On computable numbers, with an application to the Entscheidungsproblem di Alan Turing.

    Programma
    • Teoria degli Automi
      • Alfabeti, stringhe, linguaggi, operazioni su linguaggi
      • Automi a stati finiti deterministici (DFA) e non deterministici (NFA)
      • Minimizzazione di DFA, espressioni regolari
      • Proprietà di chiusura dei regolari, pumping lemma
      • Grammatiche context-free, alberi di derivazione, ambiguità
      • 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
      • Cenni alle funzioni mu-ricorsive
       
      Link utili
       
      Modalità d'esame

      Scritto e orale. Il voto sufficiente dello scritto vale per i due appelli successivi.

     

     

  • Calendario lezioni

    1) 26 febbraio: introduzione al corso; alfabeti, stringhe, linguaggi

    2) 27 febbario: automi deterministici (DFA)

    3) 5 marzo: automi non deterministici (NFA), trasformazione da DFA in NFA

    4) 6 marzo: epsilon-NFA, trasformazione da epsilon-NFA in NFA

    5) 12 marzo:   minimizzazione di DFA, espressioni regolari

    6) 13 marzo: trasformazione da espressioni regolari in epsilon-NFA, proprietà dei regolari, pumping lemma  per i regolari

    7) 19 marzo: prova del pumping lemma, esempi, esercizi

    8) 20 marzo: , ripasso grammatiche context-free, provare che una grammatica genera un dato linguaggio, automi a pila (PDA)

    9) 26 marzo: esempi automa a pila, automi a pila deterministici (DPDA)

    10) 27 marzo: equivalenza tra grammatiche context-free e PDA, pumping lemma per i context-free

    11) 2 aprile: pumping lemma per i context-free, proprietà di chiusura dei context-free

    12) 3 aprile: esercizi su context-free, introduzione alla teoria della calcolabilità, funzioni primitive ricorsive (PR)

    13) 9 aprile: esempi di PR, numerazione effettiva, PR non Turing-completo 

    14) 10 aprile: macchine di Turing (MdT) come riconoscitori

    15) 16 aprile: linguaggi ricorsivi e ricorsivamente numerabili (r.e.), MdT come "calcolatori"

    16) 23 aprile: tesi di Church-Turing, numerazione effettiva delle funzioni ricorsive, macchina universale, halting problem

    17) 24 aprile:  insiemi ricorsivi e r.e., teorema di Post, proprietà di chiusura di ricorsivi e r.e.

    18) 30 aprile: caratterizzazione insiemi r.e., tecnica a zig-zag, esercizi su primitive ricorsive

    19) 7 maggio: insieme delle funzioni totali non ricorsivamente numerabile, riduzione, esempi

    20) 8 maggio: proprietà della riduzione, completezza di H e K, esercizi

    21) 14 maggio: teorema di Rice, esempi di applicazione, prova

    22) 15 maggio: cenni a funzioni mu-ricorsive e MdT non deterministiche, esercizi

    23) 21 maggio: esercizi

    24) 22 maggio: esercizi

     

  • Calendario esami