Informatica Teorica II

Prof. G. Ausiello

A.A. 2007-2008


Obiettivi del corso

Il corso e' finalizzato a dare agli studenti una conoscenza approfondita di concetti di complessita' computazionale e di algoritmica con riferimento ad algoritmi paralleli, algoritmi probabilistici ed algoritmi approssimati per problemi di ottimizzazione complessi.

Corsi propedeutici: Modelli e Complessita' di Calcolo (Informatica Teorica I), Ricerca Operativa.

Programma dettagliato del corso

Riferimento ai testi:

AdG Ausiello, d'Amore, Gambosi, Linguaggi, Modelli, Complessitą, Franco Angeli, 2003
BC Bovet, Crescenzi, Teoria della Complessitą Computazionale, Franco Angeli, 1991
ACGKMP Ausiello, Crescenzi, Gambosi, Kann, Marchetti-Spaccamela, Protasi, Complexity and Approximation, 1999
AB Ausiello, Becchetti, On-Line Algorithms, 2004

PARTE I - Complessitą di calcolo

1. La classe P. Algoritmi paralleli e la classe NC. La classe LOGSPACE. Problemi P-completi.
2. La gerarchia polinomiale. Problemi PSPACE-completi.

Slide delle lezioni e delle esercitazioni.
AdG - Cap. 9: Sez. 9.1, 9.2, 9.5, 9.6, 9.7
BC - Cap. 15: Sez. 15.4, Cap. 16: tutto

PARTE II - Algoritmi di approssimazione

1. Complessitą di problemi di ottimizzazione.
2. Vari tipi di algoritmi di approssimazione: algoritmi approssimati, PTAS, FPTAS e relativi esempi.
3. Classi di approssimabilitą.
4. Primi risultati di non approssimabilitą.
5. Tecniche fondamentali per algoritmi di approssimazione: algoritmi greedy, algoritmi sequenziali, ricerca locale.
6. Tecniche per PTAS e per FPTAS.
7. Tecniche basate su programmazione lineare e tecnica primale-duale.
8. Algoritmi approssimati per problemi particolari: bin packing, scheduling, TSP.
(9. Dimostrazioni avanzate di non approssimabilitą) non in programma.

Slide delle lezioni e delle esercitazioni.
BC - Cap. 8
ACGKMP - Cap 2: tutto tranne Sezione 2.1.2, Sezione 2.2.3
Cap. 3: tutto tranne Teoremi 3.9, 3.10, 3.11 e Sezione 3.3.2
Cap. 4: solo Sezione 4.2.2
Cap. 5: Sezione 5.1, Sezione 5.2 (esclusa la dimostrazione del Lemma 5.2) e Sezione 5.4

PARTE III - Algoritmi probabilistici

1. Paradigmi e tipi di algoritmi probabilistici.
2. Esempi di algoritmi probabilistici.
3. Classi di complessitą di linguaggi accettati da macchine probabilistiche.

Slide delle lezioni e delle esercitazioni.
BC - Cap. 12: tutto tranne il Teorema 12.2 e l'Esempio 12.3
Cap 13: tutto tranne la Sezione 13.2.2 e la Sezione 13.3.