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
      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, 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 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.


      John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Automi, linguaggi e calcolabilità.

      URL Aula web
      FONDAMENTI DELL'INFORMATICA
      https://dibris.aulaweb.unige.it/
      URL Orario lezioni
      FONDAMENTI DELL'INFORMATICA
      http://informatica.dibris.unige.it/docenti-corsi-orari-esami/orario-delle-lezioni.html
  • Chi
    • Docenti
    • Elena Zucca
      tel. (+39) 010353 - 6730
      Elena.Zucca@unige.it
    • Commissione d’esame
      80303 - FONDAMENTI DELL'INFORMATICA
      Davide Ancona
      Giorgio Delzanno
      Eugenio Moggi
      Elena Zucca (Presidente)
  • Come
    • MODALITA' DIDATTICHE
      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.

  • Dove e quando
  • Contatti