Algoritmi e Strutture Dati II
Finalita' del corso.
Il corso ha l'obiettivo di introdurre concetti fondamentali della
NP-completezza e di esplorarne la rilevanza e le ramificazioni.
Verranno poi introdotte le metodologie fondamentali per il progetto
di algoritmi di approssimazione per problemi computazionalmente difficili.
Verranno anche introdotti elementi di algoritmica randomizzata ed on-line.
Programma (parte A):
La classe NP e questioni di intrattabilita' computazionale
Riduzione polinomiale tra problemi
Il concetto di PSPACE e relazioni con NP
Algoritmi randomizzati
Libro di testo:
J. Kleinberg e E. Tardos, Algorithm Design, Pearson
(Cap. 8, 9, 10, 13)
Programma (parte B):
Definizione di algoritmo di approssimazione; Vertex Cover; Massimo Sottografo Aciclico; Maximum Cut
Set Cover; Copertura Massima
Steiner Tree; TSP
K-Centro; PTAS; FPTAS; Zaino 0-1
Algoritmi di approssimazione via arrotondamento della soluzione di sistemi di PL; Vertex Cover; Set Cover; Set Multicover; Hitting Set
Arrotondamento probabilistico; Set Cover; Max-Sat
Principio della Dualita' in Programmazione Lineare; Set Cover via Dual Fitting; Hitting Set via slackness primale
Algoritmi di approssimazione via Primale-Duale; Vertex Cover; Set Cover
Algoritmi on-line; Analisi competitiva di algoritmi; Gestione della Cache; 2-competitivita' di LRU; Ottimalita' di LRU
Accesso e Gestione di Liste dinamiche; 2-competitivit\A di MTF; ottimalita' di MTF
Scheduling on-line; Bin Packing on-line; Analisi competitiva del Problema
dell'affitto di sci e del Problema della Compravendita di azioni
Libri di testo:
V. Vazirani, Approximation Algorithms, Springer-Verlag.
A. Borodin, R. El-Yaniv, Online Computation and Competitive Analysis, Cambridge Univ. Press.