24/11/2004, mercoledì,

16-18

aula L

Introduzione. Analisi di algoritmi e complessità dei problemi. Classi di complessità classiche.

26/11/2004, venerdì,

16-18

aula L

Riducibilità tra problemi. Complessità dei problemi di ottimizzazione. Relazioni tra le 3 versioni di un problema di ottimizzazione.

29/11/2004, lunedì,

16-18

aula I

Algoritmi di approssimazione. Tecniche per il loro sviluppo: greedy, sequenziale per partizioni

01/12/2004, mercoledì,

16-18

aula Verde

Tecniche per il loro sviluppo: ricerca locale, basati sulla programmazione lineare e programmazione dinamica.

03/12/2004, venerdì,

16-18

aula L

Tecniche per il loro sviluppo: cenno agli algoritmi randomizzati. Soluzioni approssimate di qualità assicurata. Schemi di approssimazione polinomiale e schemi di approssimazione totale. Classi APX e PTAS. Primi risultati di non approssimabilità: tecnica del gap

06/12/2004, lunedì,

16-18

aula I

Richiamo alla Macchine di Turing non deterministica e alla MdT con oracolo. Il modello PCP. Il teorema PCP. Conseguenza del teorema PCP: non approssimabilità di alcuni problemi di ottimizzazione.

10/12/2004, venerdì,

16-18

aula L

Conseguenza del teorema PCP: non approssimabilità di alcuni problemi di ottimizzazione. Approssimabilità dipendente dalla dimensione dell'input. Classi di approssimazione dipendente dall'input.

13/12/2004, lunedì,

16-18

aula I

Riduzione tra problemi approssimati. Concetto di completezza in APX e PTAS.

15/12/2004, mercoledì,

16-18

aula L

Riservata a seminari.

17/12/2004, venerdì,

16-18

aula L

Riservata a seminari.