Algoritmi e complessita'

A.A. 2020/2021
6
Crediti massimi
48
Ore totali
SSD
INF/01
Lingua
Italiano
Obiettivi formativi
Il corso consiste nella discussione di algoritmi di approssimazione per problemi NP-difficili; difficoltà di approssimazione dei problemi (in particolare, di alcuni affrontati nella prima parte); cenni della teoria della complessità di approssimazione (in particolare, il PCP); strutture dati succinte.
Risultati apprendimento attesi
Non definiti
Programma e organizzazione didattica

Edizione unica

Responsabile
Periodo
Primo semestre
Videolezioni sincrone.
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]
Prerequisiti
Algoritmi.
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
Modalità di verifica dell’apprendimento e criteri di valutazione
Esame orale.
INF/01 - INFORMATICA - CFU: 6
Lezioni: 48 ore
Docente: Boldi Paolo
Siti didattici
Docente/i
Ricevimento:
Su appuntamento
Stanza 5019, Piano 5, via Celoria 18