ASD 2-Appello straordinario

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

ASD 2

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. 

ASD 2-Annullamento lezione

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

ASD 2-Annullamento 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.

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

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.

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

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

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

Union-Find: Union by rank: proprietà e analisi. Path compression. Union by rank e path compression. Analisi dell'algoritmo di costo O(mlog* n).

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.

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

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

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

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

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.

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

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. 

Presentazione corso.

Divide et impera: Ricorrenze. Metodi risolutivi. 

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

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.