Source: http://informatica.uniroma2.it/f0?fid=220&srv=0&os=2015&cdl=0&id=ASD2
Timestamp: 2017-09-21 15:35:30+00:00

Document:
Docente: Paola Vocca
ASD 2-Appello straordinario
Verd' 1° aprile alle ore 10 in studio ci sarà un appello straordinario di ASD2
Domani lunedì 18 gennaio si terrà regolarmente lezione
ASD 2-Annullamento lezione
Lunedì 14 dicembre non ci sarà lezione. Le lezioni riprenderanno regolarmente mercoledì 16.
ASD2-Spostamento lezione
Domani giovedì 3 dicebre verrà recuperata la lezione di lunedì alle 14:00 in aula 3A.
A causa di un impegno improvviso, domani 30 novembre non si terrà lezione.
Lunedì 26 ottobre non si terrà lezione.
ASD-Spostamento lezione
Mercoledì 14 ottobre non si terrà lezione. La lezione verà recuperata giovedì 15 alle 14:00 in aula 3A.
ASD-Annullamento lezione
Mercoledì 7 ottobre non si terrà lezione. Le lezioni riprenderanno regolarmente lunedì 12 ottobre.
21 18-01-2016
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
20 13-01-2016
Algoritmi probabilistici: Algoritmo probabilistico per 2-sat: descrizione ed analisi. Passeggiate aleatorie; algoritmi Las Vegas e Montecarlo
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.
19 11-01-2016
Algoritmi probabilistici:. Risoluzione dei conflitti in un sistema distribuito: analisi di un protocollo randomizzato. Problema 2-sat: Algoritmo polinomiale.
18 21-12-2015
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
17 16-12-2015
Union-find: Algoritmi di compressione dei cammini: path compressio, splitting e halving. Analisi dell’algoritmo union by rank con path compression: complessità O(m log*n). Descrizione dell’algoritmo di Tarjan di complessità O(m∙α(m,n)+n) (no dimostrazione).
16 09-12-2015
Union-Find: Union by rank: proprietà e analisi. Path compression. Union by rank e path compression. Analisi dell'algoritmo di costo O(mlog* n).
15 03-12-2015
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.
14 02-12-2015
Liste ad auto-organizzazione, algoritmo MTF con modello di costo. Algoritmi TRANS (transpose) e FC (frequency count).
13 25-11-2015
Problema del paging. Algoritmo LRU (Last Recentely Used) Analisi e ottimalità.
12 23-11-2015
Algoritmi on-line e analisi competitiva. Definizione. Ski-rental, Compravendita di azioni. Liste ad auto-organizzazione, algoritmo MTF
11 18-11-2015
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).
10 16-11-2015
Allineamento di sequenze: Allineamento di sequenze in spazio lineare. Allineamento locale e penalità di gap
Allineamento di sequenze: Confronto fra sequenze. Allineamento globale.
Programmazione dinamica: Struttura secondaria dell’RNA.
Programmazione dinamica: Partizione di un insieme di interi. Problema della bisaccia e della bisaccia rilassato. Pseudo polinomialità e programmazione dinamica.
Programmazione dinamica: Sequenza ottima di moltiplicazioni. Sotto-sequenza comune più lunga.
5 28-11-2015
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à.
4 21-10-2015
Problema della gestione della cache. Caching offline.
Partizione di intervalli. Scheduling che minimizzano il ritardo massimo.
Tecnica greedy: Struttura delle tecniche greedy. Problemi di scheduling. Scheduling ad intervallo.
Teorema fondamentale. Dimostrazione. Case study: Moltiplicazione veloce di interi, moltiplicazione fra matrici, Il problema della coppia più vicina.
0 05-10-2015
Divide et impera: Ricorrenze. Metodi risolutivi.
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. Vertex Cover: definizione; algoritmo di approssimazione basato su una tecnica greedy con rapporto di approssimazione logaritmico; algoritmi di approssimazione con rapporto di approssimazione costante.
Schemi di approssimazione PTAS e FPTAS. Partition : Esempio di schema di approssimazione. polinomiale. Esempio di schema di approssimazione pienamente polinomiale: Knapsack.
Classi di approssimabilità: APX, PTAS e FPTAS e relazioni fra di esse.
Algoritmi probabilistici: Definizioni e proprietà. Quicksort randomizzato: descrizione ed analisi. Selezione randomizzata: descrizione e analisi. Risoluzione dei conflitti in un sistema distribuito: analisi di un protocollo randomizzato. Taglio minimo: descrizione ed analisi dell’algoritmo randomizzato. Problema 2-sat: Algoritmo polinomiale e algoritmo deterministico Algoritmo probabilistico per 2-sat: descrizione ed analisi. Passeggiate aleatorie; algoritmi Las Vegas e Montecarlo
Union-Find: definizione del problema: QuickFind, QuickUnion, algoritmi di bilanciamento per gli algoritmi di QuickFind e analisi ammortizzata con il metodo dell'aggregazione. Algoritmi di bilanciamento per il QuickUnion: union by rank e union by size, descrizione e analisi della complessità. Algoritmi di compressione dei cammini: path compressio, splitting e halving. Analisi dell’algoritmo union by rank con path compression: complessità O(m log*n). Descrizione dell’algoritmo di Tarjan di complessità O(m∙α(m,n)+n)
Algoritmi on-line e analisi competitiva. Definizione. Ski-rental, Compravendita di azioni. Liste ad auto-organizzazione, algoritmo MTF. Analisi del rapporto di competività secondo diversi modelli di cposto. Algoritmi TRANS (transpose FC (frequency count).di costo per Problema del paging. Algoritmo LRU (Last Recentely Used) Analisi e ottimalità.
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.
Allineamento di sequenze: Struttura secondaria dell’RNA.Confronto fra sequenze. Allineamento globale. Allineamento di sequenze in spazio lineare. Allineamento locale e penalità di gap. [KT cap 6 §§6.6-6.7]
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à. Sequenza ottima di moltiplicazioni. Sotto-sequenza comune più lunga. Partizione di un insieme di interi. Problema della bisaccia e della bisaccia rilassato. Pseudo polinomialità e programmazione dinamica.
Tecnica greedy: Struttura delle tecniche greedy. Problemi di scheduling. Scheduling ad intervallo. Partizione di intervalli. Scheduling che minimizzano il ritardo massimo. Problema della gestione della cache. Caching offline.
Divide et impera: Ricorrenze. Metodi risolutivi. Teorema fondamentale. Dimostrazione. Case study: Moltiplicazione veloce di interi, moltiplicazione fra matrici, Il problema della coppia più vicina.
Programma di Algoritmi e Strutture Dati 2 (6cr) A.A. 2015/16
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]
[CGGR] Crescenzi - Gambosi - Grossi - Rossi STRUTTURE DI DATI E ALGORITMI (Progettazione, analisi e programmazione ) -PEARSON EDUCATION ITALIA -2012.
[KT] Kleinberg- Tardos "Algoritm Design" PEARSON International Edition-2006
Al termine delle lezioni oppure su appuntamento tramite e-mail a vocca@unitus.it
L’esame si compone di una verifica orale su tutto il programma del corso comprese le dimostrazioni ove non specificato diversamente. Il voto potrà essere migliorato da una tesina di approfondimento di una parte del corso, con eventuale implementazione degli algoritmi proposti.

References: §5
 §6
 §6
 §6
 §6
 §5
 §5