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 8. 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