Fondamenti dell'Informatica (SSIS)
Contenuto e Struttura del corso
2007

 

 

(Ultimo aggiornamento: 7 Febbraio 2007)

Docente: Alessandro Sperduti




Note introduttive

Questo corso fornisce i concetti fondamentali della teoria degli automi e dei linguaggi formali, mostrando la loro applicazione ai compilatori. Inoltre, introduce le nozioni di indecidibilita' e intrattabilita'. Gli argomenti principali del corso sono: automi a stati finiti, espressioni e linguaggi regolari, grammatiche e linguaggi liberi dal contesto, automi a pila, macchine di Turing, concetto di indecidibilita', problemi intrattabili, classi P e NP, relazione con i compilatori.

Testo di riferimento:

  1. Automi, Linguaggi e calcolabilita' J. E. Hopcroft, R. Motwani, J. D. Ullman, Addison Wesley, 2003.

  2.  

Modalita' di esame

Scritto obbligatorio con orale opzionale.


LUCIDI E NOTE DEL CORSO:

Lucidi della lezione del 27 Gennaio, 3 e 9 Febbraio