Algoritmi e complessita'
A.A. 2022/2023
Learning objectives
L'insegnamento si propone di sensibilizzare lo studente sul ruolo degli algoritmi di approssimazione e dell'impatto della randomizzazione sul progetto di algoritmi efficienti
Expected learning outcomes
Lo studente deve essere in grado di studiare e progettare algoritmi con le tecniche descritte nell'insegnamento.
Periodo: Primo semestre
Modalità di valutazione: Esame
Giudizio di valutazione: voto verbalizzato in trentesimi
Corso singolo
Questo insegnamento non può essere seguito come corso singolo. Puoi trovare gli insegnamenti disponibili consultando il catalogo corsi singoli.
Course syllabus and organization
Edizione unica
Responsabile
Periodo
Primo semestre
Programma
* Algoritmi di approssimazione
- Classi NPO, APX, PTAS, FPTAS
- Tecniche greedy
-- Problema del bilanciamento del carico (load balancing) [A]
-- Problema della selezione dei centri (center selection) [A]
-- Inapprossimabilità del problema della selezione dei centri [C]
-- Problema della copertura di insiemi (set cover) [A]
- Tecnica di pricing
-- Problema della copertura di vertici (vertex cover) [A]
-- Problema dei cammini disgiunti (disjoint paths) [A]
- Tecniche basate sull'arrotondamento
-- Problema della copertura di vertici mediante arrotondamento [A]
- Altri esempi
-- Algoritmo di Christofides per il TSP metrico [B]
-- Inapprossimabilità del TSP [D.6]
- Schemi di approssimazione in tempo polinomiale e pienamente polinomiale
-- Un PTAS (basato sulla soluzione esaustiva ridotta) per il problema della partizione minima (minimum partition) [G]
-- Un FPTAS (basato sull'arrotondamento) per il problema dello zaino (knapsack) [C]
* Algoritmi probabilistici
- L'algoritmo di Karger per il problema del taglio minimo globale (minimum global cut) [E]
- L'algoritmo di Miller-Rabin per la primalità (senza dimostrazione) [H]
- Un algoritmo basato sull'arrotondamento aleatorio per la copertura di insiemi [D.4]
- Un algoritmo randomizzato per MaxEkSat e la sua derandomizzazione [D.3]
- Teoria della complessità di approssimazione
* Teorema PCP (senza dimostrazione) [F.3, Teorema 1]
- PCP e inapprossimabilità di MaxSat e MaxE3Sat [F.3.1]
- PCP e inapprossimabilità del problema dell'insieme indipendente (independent set) [F.4.4, Claim 13 e Claim 14]
* Strutture succinte, quasi-succinte e compatte
- Strutture succinte per rango e selezione; il "Four-Russians Trick" [D.9, escluso 9.2]
- Strutture succinte per alberi binari [D.10]
- Codifica quasi-succinta di Elias-Fano per sequenze monotone [D.11, esclusi D.11.1 e D.11.2]
- Struttura compatta per le parentesi bilanciate [D.12]
- Funzioni quasi-succinte: la tecnica MWHC [D.13]
- Hash minimali perfetti [D.13]
- Classi NPO, APX, PTAS, FPTAS
- Tecniche greedy
-- Problema del bilanciamento del carico (load balancing) [A]
-- Problema della selezione dei centri (center selection) [A]
-- Inapprossimabilità del problema della selezione dei centri [C]
-- Problema della copertura di insiemi (set cover) [A]
- Tecnica di pricing
-- Problema della copertura di vertici (vertex cover) [A]
-- Problema dei cammini disgiunti (disjoint paths) [A]
- Tecniche basate sull'arrotondamento
-- Problema della copertura di vertici mediante arrotondamento [A]
- Altri esempi
-- Algoritmo di Christofides per il TSP metrico [B]
-- Inapprossimabilità del TSP [D.6]
- Schemi di approssimazione in tempo polinomiale e pienamente polinomiale
-- Un PTAS (basato sulla soluzione esaustiva ridotta) per il problema della partizione minima (minimum partition) [G]
-- Un FPTAS (basato sull'arrotondamento) per il problema dello zaino (knapsack) [C]
* Algoritmi probabilistici
- L'algoritmo di Karger per il problema del taglio minimo globale (minimum global cut) [E]
- L'algoritmo di Miller-Rabin per la primalità (senza dimostrazione) [H]
- Un algoritmo basato sull'arrotondamento aleatorio per la copertura di insiemi [D.4]
- Un algoritmo randomizzato per MaxEkSat e la sua derandomizzazione [D.3]
- Teoria della complessità di approssimazione
* Teorema PCP (senza dimostrazione) [F.3, Teorema 1]
- PCP e inapprossimabilità di MaxSat e MaxE3Sat [F.3.1]
- PCP e inapprossimabilità del problema dell'insieme indipendente (independent set) [F.4.4, Claim 13 e Claim 14]
* Strutture succinte, quasi-succinte e compatte
- Strutture succinte per rango e selezione; il "Four-Russians Trick" [D.9, escluso 9.2]
- Strutture succinte per alberi binari [D.10]
- Codifica quasi-succinta di Elias-Fano per sequenze monotone [D.11, esclusi D.11.1 e D.11.2]
- Struttura compatta per le parentesi bilanciate [D.12]
- Funzioni quasi-succinte: la tecnica MWHC [D.13]
- Hash minimali perfetti [D.13]
Prerequisiti
Un insegnamento di base di algoritmi e strutture dati.
Metodi didattici
Didattica frontale.
Materiale di riferimento
[A] Cap. 11 (escluso 11.7) di Jon Kleinberg, Éva Tardos: Algorithm Design, Pearson, 2013
[B] Dispense di Cornell sull'algoritmo di Christofides
[C] Lucidi di Kevin Wayne
[D] Dispense di Sebastiano Vigna
[E] Lucidi di Stanford sull'algoritmo di Karger
[F] Dispense di Luca Trevisan
[G] Sezione 3.2 di Ausiello et al.: Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer 1999
[H] Algoritmo di Miller-Rabin
[B] Dispense di Cornell sull'algoritmo di Christofides
[C] Lucidi di Kevin Wayne
[D] Dispense di Sebastiano Vigna
[E] Lucidi di Stanford sull'algoritmo di Karger
[F] Dispense di Luca Trevisan
[G] Sezione 3.2 di Ausiello et al.: Complexity and approximation: combinatorial optimization problems and their approximability properties. Springer 1999
[H] Algoritmo di Miller-Rabin
Modalità di verifica dell’apprendimento e criteri di valutazione
Esame orale.
Professor(s)