Algoritmi e strutture dati 2

Docente: Paola Vocca

Comunicazioni

ASD 2-Appello straordinario

15-03-2016 11:43

Verd' 1° aprile alle ore 10 in studio ci sarà un appello straordinario di ASD2


ASD 2

17-01-2016 19:16

Domani lunedì 18 gennaio si terrà regolarmente lezione


ASD 2-Annullamento lezione

09-12-2015 14:55

Lunedì 14 dicembre non ci sarà lezione. Le lezioni riprenderanno regolarmente mercoledì 16.

 


ASD2-Spostamento lezione

02-12-2015 14:12

Domani giovedì 3 dicebre verrà recuperata la lezione di lunedì alle 14:00 in aula 3A. 


ASD 2-Annullamento lezione

29-11-2015 20:03

A causa di un impegno improvviso, domani 30 novembre non si terrà lezione.


ASD 2-Annullamento lezione

22-10-2015 13:00

Lunedì 26 ottobre non si terrà lezione.


ASD-Spostamento lezione

12-10-2015 14:34

Mercoledì 14 ottobre non si terrà lezione. La lezione verà recuperata giovedì 15 alle 14:00 in aula 3A. 


ASD-Annullamento lezione

06-10-2015 10:23

Mercoledì 7 ottobre non si terrà lezione. Le lezioni riprenderanno regolarmente lunedì 12 ottobre.


Lezioni

2118-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

2013-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.

1911-01-2016

Algoritmi probabilistici:. Risoluzione dei conflitti in un sistema distribuito: analisi di un protocollo randomizzato. Problema 2-sat: Algoritmo polinomiale.

1821-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

1716-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).

1609-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).

1503-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.

1402-12-2015

Liste ad auto-organizzazione, algoritmo MTF con modello di costo. Algoritmi TRANS (transpose) e FC (frequency count).

1325-11-2015

Problema del paging. Algoritmo LRU (Last Recentely Used) Analisi e ottimalità.

1223-11-2015

Algoritmi on-line e analisi competitiva. Definizione. Ski-rental, Compravendita di azioni. Liste ad auto-organizzazione, algoritmo MTF

1118-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).

1016-11-2015

Allineamento di sequenze: Allineamento di sequenze in spazio lineare. Allineamento locale e penalità di gap

911-11-2015

Allineamento di sequenze: Confronto fra sequenze. Allineamento globale.

809-11-2015

Programmazione dinamica: Struttura secondaria dell’RNA.

704-11-2015

Programmazione dinamica: Partizione di un insieme di interi. Problema della bisaccia e della bisaccia rilassato. Pseudo polinomialità e programmazione dinamica.

602-11-2015

Programmazione dinamica: Sequenza ottima di moltiplicazioni. Sotto-sequenza comune più lunga.

528-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à.

421-10-2015

Problema della gestione della cache. Caching offline.

319-10-2015

Partizione di intervalli. Scheduling che minimizzano il ritardo massimo.

215-10-2015

Tecnica greedy: Struttura delle tecniche greedy. Problemi di scheduling. Scheduling ad intervallo. 

112-10-2015

Teorema fondamentale. Dimostrazione. Case study: Moltiplicazione veloce di interi, moltiplicazione fra matrici, Il problema della coppia più vicina. 

005-10-2015

Presentazione corso.

Divide et impera: Ricorrenze. Metodi risolutivi. 


Materiale didattico

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.

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 del corso

Informazioni

Anno accademico2015-2016
Crediti6
SettoreINF/01
Anno3
Semestre1
PropedeuticitàAlgoritmi e strutture dati.

Programma

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]

 

 


Testi di riferimento

  • [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
  • Lucidi e dispense 

Ricevimento studenti

Al termine delle lezioni oppure su appuntamento tramite e-mail a vocca@unitus.it


Modalità di esame

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.