Algoritmi e strutture dati

Modalità d'esame ASD 2018-19 (NEWS)

A seguito delle richieste pervenute dai rappresentanti degli studenti, si stabilisce quanto segue:

1) Le prove d'esame  del I modulo e quelle del II modulo possono essere svolte in ordine arbitrario. Tuttavia, al fine di migliorare l'apprendimento di alcuni argomenti avanzati del II modulo, si consiglia fortemente di studiare e conseguire l'esame del I modulo prima o in parallelo a quello del secondo.

2) Nella sessione estiva, a chi consegna lo scritto al primo appello e riceve una votazione inferiore a 15/30 è consigliato non sostenere il secondo appello della stessa sessione. Per le sessioni successive, gli appelli sono esclusivi, come da regolamento del Corso di Laurea.

spostamento lezione esercitazione ASD del 27/05

Si comunica che la lezione di esercitazione di Algoritmi e Strutture Dati di lunedì 27/05 è stata spostata a giovedì 30/05, causa sospensione della didattica per elezioni europee. 

lezione ASD del 28/03 annullata

Si avvisa che la lezione di ASD di giovedì 28/03 (prof. Clementi) è annullata, causa lutto familiare.

Cambio aula per le lezioni del lunedì

Si comunica che per l'intero semestre la lezione di ASD del lunedì mattina (ore 9-11) si terrà in Aula B2, edificio didattica a Ingegneria. 

appellli ASD sessione invernale

Si avvisa che i due appelli di ASD del 28/01 e del 19/02 sono esclusivi per entrambi i moduli, ovvero uno stesso modulo può essere sostenuto una sola volta in uno solo degli appelli (a piacere dello studente). Inoltre, si ricorda che, per gli studenti degli anni precedenti, al fine di verbalizzare l'esame in questa sessione, è necessario superare entrambi i moduli entro la sessione stessa, pena la perdita del risultati ottenuti nei singoli moduli.
Invece, gli studenti interessati a sostenere solo il modulo 1 (che sarà mantenuto per l'intero anno accademico in corso) devono necessariamente presentarsi al primo appello (28/01) che coincide con la prova di esonero per l'a.a. 2018/19.

lezione ASD giovedì 20/12 ore 9:00

Si comunica che la leione di Algoritmi e Strutture Dati (Gualà) di giovedì 20/12 ore 9:00 si terrà in aula 3A.

lezione ASD del 19/11 annullata

Si comunica che la lezione di ASD del giorno 19/11 non si terrà.

Cambio aula.

Da lunedì 6 ottobre le lezioni di ASD si terranno in aula 6 edificio PP2. 

1. Gli algoritmi di approssimazione per problemi NP-Hard.

2. Definizione formale di algoritmo di approssimazione.

3. L'algoritmo 2-apx per Min-VC basato su Maximal Matching: progetto ed analisi.

4. L'algoritmo 2-apx per Load Balancing basato sull'approccio Greedy.

5. L'algoritmo (1.5)-apx per Load Balancing basato sull'approccio Greedy.

6. Risultati di Apx-Hardness: introduzione.

7. Apx-hardness per Min-TSP: La Gap Technique (descrizione ed analisi).

8. Conclusione del Corso.

1. Dimostrazione formale di 3-SAT < INDEPENDENT SET.

2. Il problema VERTEX COVER.

3. VERTEX COVER E INDEPENDENT SET: Proprietà combinatoriche.

4. Equivalenza VERTEX COVER = INDEPENDENT SET.

5. Le tecnica di riduzione: Generalization.

6. La riduzione VERTEX COVER < SET COVER.

7. Cenni sul concetto di approssimazione di problemi NP-hard.

1. Problemi non in NP (forse): la classe co-NP.

2. La struttura P ⊆ NP ∩ co-NP.

3. Il Thm di Pratt e la dimostrazione che PRIME e' in NP ∩ co-NP.

4. Riduzioni Polinomiali mediante  tecnica dei Gadget: 3-SAT < INDEPENDENT SET.

1. Definizione di Cook-Riduzione Polinomiale (mediante Oracolo).

2. Definizione di Cook-Riduzione Polinomiale (trasformazione polinomiale).

3. Proprietà transitiva delle riduzioni polinomiali e sua "efficienza".

4. Chiusura della classe P rispetto alle riduzioni polinomiali.

5. Problemi NP-completi e loro collocazione nel caso P # NP.

6. Un primo problema NP-Completo: CIRCUIT-SAT.

7. La riduzione CIRCUIT-SAT < 3-SAT.

1. NP: certificazione efficiente delle soluzioni di un problema decisione.

2. NP: certificatori efficienti.

3. NP: esempi di problemi decisionali che ammettono certificatori efficienti (3-SAT).

4. NP: definizione formale e confronto con le Macchine di Turing Non-Deterministiche.

5. NP: asimmetria nel criterio di accettazione.

6. P < NP < EXP (dimostrazione delle relazioni tra le tre classi).

7. Riduzioni polinomiali (Introduzione).

1. Programmazione Dinamica: Sequence Alignment.

2. Struttura di un'ottimo alignment: proprietà fondamentali.

3. Organizzazione efficiente dei calcoli: Calcolo della Matrice 2-dimensionale.

4. Introduzione alla classe NP.

Esercitazione su Compressione Dati e Programmazione Dinamica:

1. Esecuzione dell'Algoritmo di Huffman.

2. Non-ottimalità dell'algoritmo di Shannon-Fano (controesempi).

3. Altri esempi di programmazione dinamica.

1. Il problema del Segmented Least Squares (SLS): ripasso della formalizzazione.

2. SLS: struttura della soluzione ottima.

3. SLS: definizione corretta dei sottoproblemi per un approccio di programmazione dinamica.

4. SLS: formula ricorsiva ed iterativa della soluzione ottimale.

5. SLS: descrizione della matrice e dell'algoritmo.

6. SLS: complessità dell'algoritmo.

7. Il problema KnapSack (KS): introduzione e definizione formale.

8. Un approccio greedy non ottimale.

9. Un approccio errato di programmazione dinamica con un solo parametro.

10. Strutturazione dell'ottimo usando sottoproblemi con due parametri.

11. Verifica della struttura ricorsiva a due parametri: prova della correttezza.

12. Organizzazione efficiente dei calcoli: Calcolo della Matrice 2-dimensionale.

13. Pseudopolinomialità.

1. Il problema Weighted Interval Scheduling (WIS): Definizione formale.

2. L’approccio di programmazione dinamica per WIS.

3. Ordinamento dell’istanza.

4. La definizione rigorosa dei sottoproblemi WIS(j).

5. Un’equazione ricorsiva per il costo  OPT(j) per WIS(j).

6. Dimostrazione dell’equazione.

7. Algoritmo ricorsivo: il suo worst-case esponenziale.

8. Come rimuovere  la Ridondanza dei calcoli: la Memoization.

9. Calcolo della Matrice/Vettore M(j).

10. Analisi della complessità della versione iterativa.

11. Come costruire anche la soluzione ottima, non solo il suo costo.

12. Il problema del Segmented Least Squares (SLS): introduzione e definizione formale.

1. Compressioni Dati e Codici prefissi: Ripasso.

2. La struttura della soluzione ottima: proprietà greedy.

3. L'approccio Bottom-Up (Huffman).

4. Implementazione dell’Algoritmo di Huffman HUF in forma ricorsiva.

5. Esecuzione di HUF su un esempio concreto ed osservazioni sul processo di costruzione dell’albero.

6. Analisi della complessità di HUF.

7. Ottimalità della soluzione generata da HUF.

8. Introduzione alla Programmazione Dinamica.

9. Il problema Weighted Interval Scheduling: considerazioni iniziali.

1. Il problema della compressione dati: Definizione formale.

2. I codici prefissi, la misura ABL.

3. la rappresentazione mediante alberi etichettati.

4. Proprietà delle strutture ottime.

5. Un primo approccio Top-Down (Shannon-Fano).

6. L'approccio Bottom-Up (Huffman).

1. Interval Partitioning: rivisitazione della dimostrazione di ottimalità del greedy.

2. Minimizing Lateness: definizione del problema.

3. Approcci greedy non buoni.

4. Approccio greedy ottimali: deadline time.

5. Dimostrazione di ottimalità: soluzioni canoniche (no idle time).

6. Dimostrazione di ottimalità: rimozione di inversioni.

7. Dimostrazione di ottimalità: exchange argument.

8. Considerazioni generali sull'approccio greedy.

9. Il problema della compressione dati: Introduzione.

Esercitazione su MST e algoritmi greedy (Esercitazione 1).

1. Interval Scheduling :Rivisitazione della prova di ottimalità del greedy.

2. Interval Partitioning: definizione del problema.

3. Interval Partitioning: analisi di approcci greedy ed esaustivi.

4. Interval Partitioning: un lower bound per l'ottimo.

5. Interval Partitioning: un approccio greedy ottimale.

6. Interval Partitioning: dimostrazione di ottimalità del greedy.

7. Esercizio: Minimizzare il numero di stazioni (the car traveling problem).

1. k-clustering: Ripasso della  Dimostrazione di ottimalità della soluzione MST.

2. l'approccio greedy: considerazioni generali.

3. Problemi di Scheduling.

4. Interval Scheduling: definizione del problema

5. Approcci greedy non buoni

6. Approccio greedy ottimali: finish time

7. Dimostrazione di ottimalità: greedy stays ahead

1. Algoritmo A(G,e) per la verifica dell’appartenenza di un fissato arco ad un MST di un grafo pesato connesso (Es. n 3, p. 187 di [KT]).

2. Dimostrazione della correttezza ed analisi della complessità dell’Algoritmo A(G,e)

3. Il problema del Clustering

4. Soluzione efficiente del Clustering mediante MST

http://www.mat.uniroma2.it/%7Eguala/2018_ASD_02_mst_prim.pdf

1. Strutture dati per operazioni Union&Find.

2. Implementazione mediante foreste

3. Analisi ammortizzata del tempo su una sequenza arbitraria di operazioni

4. La relazione tra Shortest Path Tree (SPT) e Minimum Spanning Tree (MST)

5. Esempi di grafi che evidenziano la differenza

Link per slides

http://www.mat.uniroma2.it/%7Eguala/2018_ASD_02_mst_prim.pdf

http://www.mat.uniroma2.it/%7Eguala/2018_ASD_03_union_find.pdf

1. Correttezza dell'algoritmo di Prim.

2. Implementazione dell'Algoritmo.

3. Esempio di esecuzione.

4. Analisi della complessità temporale.

5. Algoritmo di Kruskal: Correttezza.

6. Algoritmo di Kruskal: Complessità e gestione delle componenti 

connesse.

7. La stuttura dati UNION & FIND (introduzione).

1. Il problema del MST.

2. Definizione formale come probl. di ottimizzazione.

3. Applicazioni principali (cenni).

4. Proprietà del Taglio e MST.

5. Proprietà del Ciclo e MST.

6. Proprietà dell'intersezione tra Cicli e Tagli.

7. Tre approcci Greedy.

8. L'algoritmo di Prim (Visita).

9. Correttezza dell'algoritmo di Prim mediante la Propr. 4.

10. Implementazione dell'Algoritmo.

11. Esempio di esecuzione.

12. Analisi della complessità temporale.

13. Testo: Kleinberg & Tardos, Algorithm Design.

1. Introduzione generale al II modulo . Conoscenze  necessarie per gli 

studenti.

2. Linguaggio logico e matematico, pseudocodice, e nozioni fondamentali  

utilizzati nelle lezioni e richiesti come obiettivi formativi essenziali 

del corso.

3. Un argomento già visto nel I modulo, rivisitato sotto la luce dei 

suddetti obiettivi: L’algoritmo di Dijkstra per i cammini minimi.

4. Definizione formale del problema.

5. Lo Shortest Path Tree (SPT).

6. Il Principio di Sub-Ottimalità dei cammini minimi.

7. Lo schema dell'algoritmo di D.

8. Correttezza dello schema.

9. Dettagli implementativi e complessità.

Correzione Esercizio 4 del Problem Set 2. Esercizio: i due docenti del corso vanno a vedere la Roma a costo minimo (Esercizio 13). Discussione Esercizio 14 (lasciato come lavoro per casa). 

Esercitazione. Spendere il meno possibile per andare ad una festa con regalo (Esercizio 11). Una soluzione di costo O(mn+n^2 log n). Una migliore soluzione di costo O(m+n log n). Una soluzione alternativa di costo O(m+n log n): tecnica della riduzione e utilizzo di grafi ausiliari. Trovare la sequenza più corta di mosse per un gioco di spostamento di moneta su un grafo (Esercizio 12).

Correzione Esercizio 3 del Problem Set 3.

Correzione esercizi 1 e 2 del Problem Set 3. 

Cammini minimi in grafi pesati. Il problema del calcolo dei cammini minimi a singola sorgente. Un algoritmo veloce quando il grafo ha pesi non negativi: l'algoritmo di Dijkstra.

Usi meno comuni della visita DFS. Catalogare per tipo gli archi del grafo. Individuare un ciclo in grafi diretti. Grafi diretti aciclici (DAG) e ordinamento topologico. Usare la visita DFS per trovare un ordinamento topologico di un DAG. Componenti fortemente connesse: un algoritmo lineare per calcolarle.

Strutture dati per rappresentare un grafo. Matrice di adiacenza e Liste di adiacenza. Visite di un grafo. Visita in ampiezza (BFS): cammini minimi da una sorgente. Visita in profondità (DFS): uscire da un labirinto.

I Grafi (diretti, non diretti, pesati). Nozioni preliminari. Cammini, distanze, diametro. Alberi. Grafi Euleriani. I grafi come linguaggio potente per descrivere scenari e problemi. Esempi di scenari/problematiche descrivibili come grafi/problemi su grafi (reti stradali/di trasporto, reti sociali, reti “delle dipendenze”). 

Esercitazione. Progettare un algoritmo che, dato un vettore ordinato A[1:n] di n bit, trova il numero k di zero presenti in A. Algoritmo con complessità O(log n). Un miglior algoritmo con tempo O(log k) (Es. 9). Progettare un algoritmo con complessità lineare che, dato un vettore A[1:n] di n bit, trova l’indice k tale che il numero di zeri in A[1:k] è uguale al numero di uni in A[k+1:n] (Es. 10).

Il problema della Coda con priorità. d-Heap, Heap Binomiali, (cenni sugli) Heap di Fibonacci e complessità ammortizzata.

Il problema del Dizionario: secondo episodio. Alberi AVL: definizione ed esempi. Dimostrazione della delimitazione superiore dell’altezza di un albero AVL (che usa la nozione di albero di Fibonacci). Operazioni sugli alberi AVL: search, insert, delete.

Esercitazione: ricerca binaria e tecnica del divide et impera. Es. 7 e Es. 8. 

Il problema del Dizionario. Alberi binari di ricerca. Definizione. Visita in ordine simmetrico di un BST. Ricerca, inserimento, cancellazione (ricerca del massimo, del minimo, del predecessore e del successore di un nodo). Correzione Esercizio 3 del Problem Set 1.

Esercitazione sulle visite di alberi. Progettazione di un algoritmo che, preso un albero con valori e colori (rosso e nero), trova il valore del cammino rosso di tipo nodo-radice di valore massimo (Es 4). Altro esercizio: progettare un algoritmo che,  preso un albero e in intero h, restituisce il numero di nodi dell'albero di profondità almeno h (Es 5). Altro esercizio: preso un albero binario con valori, calcola il numero di nodi per cui la somma dei valori degli antenati è uguale alla somma dei valori dei discendenti (Es. 6).

Strutture dati elementari: rappresentazioni indicizzate e rappresentazioni collegate. Implementazione di un dizionario con array ordinato/non ordinato e lista ordinata/non ordinata. Rappresentazioni di alberi. Algoritmi di visita di un albero: profondità versione iterativa, profondità versione ricorsiva (preordine, postordine, ordine simmetrico), ampiezza. Algoritmo per calcolare l’altezza di un albero.

Esercitazione. Primo esercizio: dato un array di n interi compresi fra 1 e k, costruire in tempo O(n+k) un oracolo (struttura dati) che sia in grado di rispondere in tempo costante a domande del tipo "quanti interi nell'array sono compresi fra a e b?"(Esercizio e soluzioni a fine delle slide sull'IntegerSort). Secondo esercizio: dato un vettore A di n numeri, progettare un algoritmo che in tempo O(n) trova due indici i e j con i<j che massimizzano A[j]-A[i] (Es. 3).

Esercitazione. Esercizio: dimostrare o confutare una relazione asintotica (Es. 1). Esercizio di progettazione di un algoritmo che, dato un vettore ordinato A di n interi distinti e un valore x, trova (se esistono) due elementi di A che sommano a x. Soluzione banale con complessità quadratica, soluzione di complessità O(n log n) e soluzione con tempo O(n) (Es. 2).

Delimitazioni superiori e inferiori di algoritmi e problemi. Un lower bound alla complessità temporale necessaria per ordinare n elementi (per una classe di algoritmi ragionevoli, quelli basati su confronti). Algoritmi veloci per ordinare interi: IntegerSort, BucketSort, RadixSort.

Progettare algoritmi efficienti attraverso la progettazione di strutture dati efficienti. Un esempio: l'HeapSort - che ordina in loco n elementi in tempo O(n log n) nel caso peggiore.

Il Problema dell’ordinamento. Un algoritmo semplice ma inefficiente: il Selection Sort. Un algoritmo migliore: il MergeSort. Un altro algoritmo che usa la tecnica divide et impera: il QuickSort: analisi del caso peggiore, migliore, e intuizioni sul caso medio. Discussione versione randomizzata del QuickSort e differenza fra complessità nel caso medio e tempo atteso di un algoritmo randomizzato.

Ancora sulle equazioni di ricorrenza. Metodo della sostituzione. Teorema Fondamentale delle Ricorrenze (Master). Semplici esempi. Quando non si può applicare. Metodo del cambiamento di variabile.

Analisi della complessità nel caso medio: un esempio. Il problema della ricerca di un elemento in un insieme: ricerca sequenziale e ricerca binaria. Equazioni di ricorrenza. Metodo dell’iterazione. Metodo che usa l’albero della ricorsione.

Modello di calcolo RAM. Costi uniformi e logaritmici. Complessità caso peggiore, migliore, medio. Notazioni asintotiche: O-grande, Omega-grande, Theta. O-piccolo, Omega-piccolo. Definizioni e semplici esempi. Proprietà. Usare la notazione asintotica nelle analisi della complessità computazionale degli algoritmi.

Il problema del calcolo dell’n-esimo numero di Fibonacci. Un algoritmo numerico e un algoritmo ricorsivo. Analisi della complessità temporale dell’algoritmo ricorsivo. Un algoritmo iterativo di complessità temporale O(n) e di complessità spaziale O(n) (Fibonacci3). Portare la memoria a O(1): Fibonacci4. Introduzione informale alla notazione asintotica. Algoritmo con complessità O(log n) per il calcolo dell’n-simo numero di Fibonacci. Discussione della complessità spaziale degli algoritmi ricorsivi Fibonacci2 e Fibonacci6.

Introduzione al corso. Motivazioni e concetti fondamentali. Un primo esempio: il problema di trovare una moneta falsa (più pesante) fra n monete usando una bilancia a due piatti.