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.

Dalle dispense vanno esclusi i capitoli 1, 2, la dimostrazione di correttezza dell'algoritmo di Miller–Rabin, il capitolo 8.3, il capitolo 9.2 e il capitolo 14.

Per quanto riguarda gli algoritmi probabilistici e randomizzati, c'è il materiale nelle dispense più l'algoritmo di Karger (ma non il Karger–Stein).

Per quanto riguarda la parte di inapprossimabilità, dalla rassegna di Trevisan ci sono la definizione della classe PCP, i teoremi 1, 2, 3 (gli ultimi due, con dimostrazione) e i Claim 13 e 14 del capitolo 4.4 (riduzione diretta da PCP a insieme independente) con dimostrazione.

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

Testi consigliati