Quaderni di Informatica
Parte II: The Chomsky Hierarchy, Decidability and Closure Properties, Context–Free Languages & Pushdown Automata, Regular Languages & Finite Automata, Context–Free Parsing

Area 09 – Ingegneria industriale e dell'informazione

I Quaderni di Informatica, Parte II-IV, affrontano alcuni problemi di base dell’informatica teorica. In particolare nella Parte II vengono illustrati i linguaggi regolari, i linguaggi context–free e le proprietà di decidibilità e chiusura di varie classi di linguaggi formali. Nella Parte III si studiano le macchine di Turing, le macchine a contatori, le funzioni parziali ricorsive, e si approfondisce l’analisi dei linguaggi regolari. Nella Parte IV si presentano le idee di base sulla complessità degli algoritmi, la riduzione tra problemi e l’NP–completezza. Si presentano inoltre i principali algoritmi di ordinamento, ricerca e selezione e gli algoritmi per la moltiplicazione tra interi, polinomi, matrici e il calcolo della trasformata veloce di Fourier.Alberto Pettorossi è professore associato di Informatica teorica presso il Dipartimento di Informatica, Sistemi e Produzione dell’Università degli Studi di Roma “Tor Vergata”. Ha svolto attività di ricerca e attività didattica presso università italiane e straniere nel campo della verifica e dello sviluppo automatico dei programmi funzionali e logici, della teoria della programmazione concorrente e dei sistemi di riscrittura. Home page: http://www.iasi.cnr.it/~adp/

SINTESI