Home » Archivo » Archvio 2013 » ALGORITMI DI APPROSSIMAZIONE - 2013/2014

Laurea Magistrale

Salta il menu di secondo livello

ALGORITMI DI APPROSSIMAZIONE - 6 CFU - A.A. 2013/2014

Insegnante

Sig. Livio Colussi

Periodo

II Anno - 1 Trimestre | 01/10/2013 - 07/12/2013

Ore: 48 (8 esercitazione, 40 lezione)

Torna su ▲

Prerequisiti

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

Conoscenze e abilità da acquisire

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.

Modalità di esame

Esame orale.

Criteri di valutazione

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

contenuti

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.

Attività di apprendimento previste e metodologie di insegnamento

Lezioni frontali.

Eventuali indicazioni sui materiali di studio

Dispense del docente.

Testi di riferimento

Torna su ▲