Theory of Computation
Part IV

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.

SOMMARIO1. Complexity Analysis of Sorting and Searching – 2. Recursion and Backtracking – 3. Computational Complexity and NP-complete Problems – 4. Multiplication of Integers, Polynomials, and Matrices. Fast Fourier Transform.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