Theory of Computation
Part III

Area 09 – Ingegneria industriale e dell'informazione

I volumi “Quaderni di Informatica. Parte II”, “Theory of Computation. Part III” e “Theory of Computation. Part 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.


SOMMARIO

1. Mathematical Preliminaries – 2. Turing Machines – 3. Partial Recursive Functions – 4. Decidability – 5. Semantics of Programming Languages – 6. Böhm-Jacopini Theorem – 7. More on Recursion and Parsing – 8. More on Finite Automata and Machines – 9. More on Propositional Calculus and Boolean Algebras.


Alberto Pettorossi è professore associato di Informatica teorica presso il Dipartimento di Informatica, Sistemi e Produzione dell’Università 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