Introduzione

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

  • Alan Turing web page
  • Un simulatore per automi di vario genere
  • Un simulatore per macchine di Turing

   

  Modalità d'esame

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