Presentazione

Organizzazione della Didattica

DM270
INFORMATICA ORD. 2009

Algoritmi di approssimazione

6

Corsi comuni

 

Frontali Esercizi Laboratorio Studio Individuale
ORE: 40 8 0 102

Periodo

AnnoPeriodo
II anno1 trimestre

Frequenza

Facoltativa

Erogazione

Convenzionale

Lingua

Italiano

Calendario Attività Didattiche

InizioFine
01/10/201307/12/2013

Tipologia

TipologiaAmbitoSSDCFU
caratterizzanteDiscipline informaticheINF/016


Responsabile Insegnamento

ResponsabileSSDStruttura
Prof. COLUSSI LIVION.D.

Altri Docenti

Non previsti

Attività di Supporto alla Didattica

Non previste

Bollettino

Conoscenze di base di algoritmi e strutture dati, delle principali tecniche algoritmiche e dell'analisi della complessità degli algoritmi. L'insegnamento non prevede propedeuticità

Per molti problemi computazionali di interesse pratico si sa che non esistono algoritmi efficienti per la loro risoluzione. Tali problemi si possono quindi risolvere soltanto per istanze molto piccole ma non nei casi pratici di interesse. In questo caso si può talvolta ricorrere ad algoritmi di approssimazione i quali calcolano soltanto una "approssimazione" della soluzione del problema ma fanno ciò in modo molto più efficiente e quindi risultano utilizzabili effettivamente nei casi pratici. In questo corso si studieranno le tecniche per ottenere degli algoritmi di approssimazione.

Lezioni frontali.

Prima parte: Algoritmi on-line. - Analisi competitiva per gli algoritmi on-line. - Paginazione: Competitività di LRU. Algoritmo off-line ottimo. Limite inferiore per la competitività degli algoritmi on-line. Algoritmi on-line randomizzati. Analisi di MARKING. Limite inferiore per algoritmi on-line randomizzati. Tipi di avversari e competitività contro i vari tipi di avversari. Analisi di RANDOM. - K server: Riassunto dei risultati noti e algoritmi on-line ingenui. ATTIVI, un algoritmo k-competitivo sugli alberi. RWALK, un algoritmo k-competitivo sugli spazi metrici resistivi. L'algoritmo della funzione lavoro (2k-1)-competitivo su spazi metrici generali (senza dimostrazione della competitività). Seconda parte: Algoritmi di approssimazione. - Risultati negativi: Caratterizzazioni delle classi P ed NP in termini di verificatori. Teorema di Cook: 3SAT è NP-completo (senza dimostrazione). Riduzione di 3SAT a 3COLOR. Verificatori probabilistici. Il teorema PCP di Arora (senza dimostrazione). Caratterizzazione di Arora della classe NP in termini di verificatori probabilistici. Risultati di non approssimabilità derivati dal teorema di Arora. Caratterizzazione di Faggin della classe NP e problemi MAX-SNP-completi. - Progetto di algoritmi approssimati: Algoritmo di Cristofides per il problema TSP euclideo. La tecnica del rilassamento. Rilassamento di tipo LP. Il problema del minimo ricoprimento di vertici. Algoritmi di Hochbaum e di Bar-Yehuda ed Even. Il metodo primale-duale. Il problema del matching perfetto di costo minimo. Algoritmo di Goemans e Williamson. Uso di rilassamenti non lineari. Il problema del taglio massimo. L'algoritmo 0.878. - Gli schemi di approssimazione e le classi PAS, FPAS, PAAS ed FPAAS. I problemi dell'impacchettamento e della schedulazione e il problema di decisione associato. Comportamento diverso dei due problemi rispetto all'approssimabilità. Un PAS per il problema della schedulazione.

Esame orale.

La prova orale accerterà la conoscenza degli algoritmi e delle tecniche algoritmiche spiegate a lezione.

David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms. : Cambridge University Press, 2010 Vijay V. Vazirani, Approximation algorithms. : Springer, 2001

Dispense del docente.

Conoscenze di base di algoritmi e strutture dati, delle principali tecniche algoritmiche e dell'analisi della complessità degli algoritmi. L'insegnamento non prevede propedeuticità

Per molti problemi computazionali di interesse pratico si sa che non esistono algoritmi efficienti per la loro risoluzione. Tali problemi si possono quindi risolvere soltanto per istanze molto piccole ma non nei casi pratici di interesse. In questo caso si può talvolta ricorrere ad algoritmi di approssimazione i quali calcolano soltanto una "approssimazione" della soluzione del problema ma fanno ciò in modo molto più efficiente e quindi risultano utilizzabili effettivamente nei casi pratici. In questo corso si studieranno le tecniche per ottenere degli algoritmi di approssimazione.

Lezioni frontali.

Prima parte: Algoritmi on-line. - Analisi competitiva per gli algoritmi on-line. - Paginazione: Competitività di LRU. Algoritmo off-line ottimo. Limite inferiore per la competitività degli algoritmi on-line. Algoritmi on-line randomizzati. Analisi di MARKING. Limite inferiore per algoritmi on-line randomizzati. Tipi di avversari e competitività contro i vari tipi di avversari. Analisi di RANDOM. - K server: Riassunto dei risultati noti e algoritmi on-line ingenui. ATTIVI, un algoritmo k-competitivo sugli alberi. RWALK, un algoritmo k-competitivo sugli spazi metrici resistivi. L'algoritmo della funzione lavoro (2k-1)-competitivo su spazi metrici generali (senza dimostrazione della competitività). Seconda parte: Algoritmi di approssimazione. - Risultati negativi: Caratterizzazioni delle classi P ed NP in termini di verificatori. Teorema di Cook: 3SAT è NP-completo (senza dimostrazione). Riduzione di 3SAT a 3COLOR. Verificatori probabilistici. Il teorema PCP di Arora (senza dimostrazione). Caratterizzazione di Arora della classe NP in termini di verificatori probabilistici. Risultati di non approssimabilità derivati dal teorema di Arora. Caratterizzazione di Faggin della classe NP e problemi MAX-SNP-completi. - Progetto di algoritmi approssimati: Algoritmo di Cristofides per il problema TSP euclideo. La tecnica del rilassamento. Rilassamento di tipo LP. Il problema del minimo ricoprimento di vertici. Algoritmi di Hochbaum e di Bar-Yehuda ed Even. Il metodo primale-duale. Il problema del matching perfetto di costo minimo. Algoritmo di Goemans e Williamson. Uso di rilassamenti non lineari. Il problema del taglio massimo. L'algoritmo 0.878. - Gli schemi di approssimazione e le classi PAS, FPAS, PAAS ed FPAAS. I problemi dell'impacchettamento e della schedulazione e il problema di decisione associato. Comportamento diverso dei due problemi rispetto all'approssimabilità. Un PAS per il problema della schedulazione.

Esame orale.

La prova orale accerterà la conoscenza degli algoritmi e delle tecniche algoritmiche spiegate a lezione.

David P. Williamson and David B. Shmoys, The Design of Approximation Algorithms. : Cambridge University Press, 2010 Vijay V. Vazirani, Approximation algorithms. : Springer, 2001

Dispense del docente.