Programma di Algoritmi e Strutture Dati 2 (6cr) A.A. 2013/14
Tecniche algoritmiche:
· Divide et impera: Ricorrenze. Metodi risolutivi. Teorema fondamentale. Dimostrazione. Case study: Moltiplicazione veloce di interi, moltiplicazione fra matrici, Il problema della coppia più vicina. [CGGR cap 3 §§ 3.1-3.2, 3.5-3.6-3.7]
· Tecnica greedy: Struttura delle tecniche greedy. Problemi di scheduling. Scheduling ad intervallo. Problema della gestione della cache. Caching offline. [KT cap 4 §§4.1-4.2-4.3]
· Programmazione dinamica: Paradigma della programmazione dinamica. Successione di Fibonacci. Complessità dell'algoritmo ricorsivo. Versione in programmazione dinamica dell'algoritmo e complessità. Problema del resto. Algoritmo greedy per il problema del resto ed esempi di ottimalità e non ottimalità. [CGGR cap 6 §6.1-6.2] Sequenza ottima di moltiplicazioni (Lucidi). Sotto-sequenza comune più lunga. Partizione di un insieme di interi. Problema della bisaccia e della bisaccia rilassato. [CGGR cap 6 §6.3-6.5]. Pseudo polinomialità e programmazione dinamica. [CGGR cap 6 §6.8]. Struttura secondaria dell’RNA. [KT cap 6 §6.5]
· Allineamento di sequenze: Confronto fra sequenze. Allineamento globale. Allineamento di sequenze in spazio lineare. Allineamento locale e penalità di gap. [KT cap 6 §§6.6-6.7]
Analisi Ammortizzata: Tecniche di analisi ammortizzata. Problema giocattolo: incremento di un contatore. Metodo dei crediti: Array dinamici. Metodo di aggregazione:
Unione e appartenenza di insiemi disgiunti(Union-Find). Metodo del potenziale. [Lucidi e CGGR cap 5 §§5.3 e 5.5].
Union-Find: definizione del problema: QuickFind, QuickUnion, algoritmi di bilanciamento per gli algoritmi di QuickFind e QuickUnion e analisi ammortizzata con il metodo dell'aggregazione
Algoritmi on-line e analisi competitiva. Definizione. Ski-rental, Compravendita di azioni. Liste ad auto-organizzazione, algoritmo MTF [Lucidi e CGGR cap 5 §5.4]. Algoritmi TRANS (transpose FC (frequency count). Problema del paging. Algoritmo LRU (Last Recentely Used) Analisi e ottimalità (Lucidi).
Algoritmi probabilistici: Definizioni e proprietà. Quicksort randomizzato: descrizione ed analisi. Selezione randomizzata: descrizione e analisi [Lucidi e CGGR cap 5 §5.1 ]. Risoluzione dei conflitti in un sistema distribuito: analisi di un protocollo randomizzato. Taglio minimo: descrizione ed analisi dell’algoritmo randomizzato [KT cap 13 §§13.1 e13.2]. Problema 2-sat: Algoritmo polinomiale e algoritmo deterministico Algoritmo probabilistico per 2-sat: descrizione ed analisi (Lucidi). Passeggiate aleatorie; algoritmi Las Vegas e Montecarlo (lucidi).
NP-completezza e Complessità di problemi di ottimizzazione. Problemi intrattabili. Classi P e NP. Certificati polinomiali. Problemi NP-completi. Riducibilità polinomiale. NP completezza. Definizione dei problemi di ottimizzazione. Relazione fra i problemi di decisione. Classe PO e NPO.[CGGR Cap.8 §§8.1-8.4, 8.6, Lucidi]
Algoritmi approssimati e schemi di approssimazione: Definizione, rapporto di approssimazione e errore relativo, algoritmi r-approssimanti. Algoritmi di approssimazione per Max-Sat. Problemi approssimabili e non approssimabili. Problema del commesso viaggiatore: NP completezza e non approssimabilità. Tecnica del gap e risultati di non approssimabilità. TSP Euclideo. Algoritmo di Christofides (lucidi). Vertex Cover: definizione; algoritmo di approssimazione basato su una tecnica greedy con rapporto di approssimazione logaritmico; algoritmo di approssimazione con rapporto di approssimazione. [CGGR Cap.8 §§ 8.10,8.11, lucidi]
Schemi di approssimazione PTAS e FPTAS. Partition : Esempio di schema di approssimazione. polinomiale. Esempio di schema di approssimazione pienamente polinomiale: Knapsack. [Lucidi]
Classi di approssimabilità: APX, PTAS e FPTAS e relazioni fra di esse. [Lucidi]
|