Programma

Il corso si compone delle seguenti parti:

Per informazioni/chiarimenti, dopo avere letto alcune indicazioni di base potete scrivere al docente (Sebastiano Vigna).

Modalità d'esame

L'esame è orale. La data è fissata tramite appuntamento (gli appelli sono, di fatto, puramente nominali).

Per quanto riguarda la parte di approssimazione, il materiale è quello del capitolo 11 del libro di Jon Kleinberg e Éva Tardos, con l'esclusione del paragrafo avanzato 11.7, dell'analisi dell'algoritmo per Set Cover, dell'analisi del caso c > 1 del problema dei cammini disgiunti (“Designing and Analyzing a Pricing Algorithm”) e dell'analisi di Knapsack. È inoltre incluso l'algoritmo di Christofides e la dimostrazione dell'inapprossimabilità di Center Selection.

Per quanto riguarda la parte di inapprossimabilità, c'è il materiale nelle dispense, ad eccezione delle dimostrazioni del capitolo 7 e di MAXSNP. Dalla rassegna di Trevisan ci sono la definizione della classe PCP e i teoremi 1, 2, 3 (gli ultimi due, con dimostrazione).

Per quanto riguarda la parte sulle strutture succinte, c'è il materiale nelle dispense, ad eccezione dei dettagli delle strutture o(n) per rango e selezione, e dell'algoritmo broadword per la selezione.

Testi consigliati