Algoritmi e strutture dati

adesione sciopero e appello ASD del 12/09

Si avvisano gli studenti che il dot. Gualà aderisce allo sciopero proclamato dal Movimento per la Dignità della Docenza Universitaria. L’agitazione consiste nell’astensione dallo svolgimento degli esami di profitto per un appello (il primo nel periodo dal 28-8 al 31-10-2017). Questo corrisponde, all’appello del corso di Algoritmi e strutture dati del 12-9-2017. Quindi, a meno di revoca dello sciopero stesso, il suddetto appello non avrà luogo. Resta inteso che l’appello successivo del 19-9 si terrà regolarmente e che gli studenti che si sono prenotati per l’appello del 12-9 possono partecipare a quello del 19-9.

Appelli settembre ASD

Si comunica che gli appelli di settembre di Algoritmi e strutture dati sono esclusivi, e quindi uno studente può sostenerne al più uno a sua scelta. 

Cambio giorni e orario lezioni per prossime festività

In occasione delle prossime festitiva', l'orario del  corso subira' le
seguenti modifiche rispetto all'orario standard:
giovedì 20/04 dalle 14.15 alle 16.00 (aula 3a),
giovedì 27/04 dalle 14.15 alle 16.00 (aula 3a),
martedi 02/05 dalle 9.15 alle 11.00 (aula 4 PP2),

giovedi 04/05 dalle 14.15 alle 16.00 (aula 3a).
Quindi le lezioni del 18 e del 24 aprile non avranno luogo.

Cambio aula: anche per questo semestre le lezioni si spostano in aula 4 PP2.

Cambia l'aula delle lezioni di Algoritmi e strutture dati (modulo 2). Tutte le lezioni si terranno in aula 4 edificio PP2.

Esonero di Febbraio

L'esonero di ASD si svolgerà nelle seguenti date:
Scritto: 20/02/2017, ore 11,30, aula T5. Orale: 23/02/2017, ore 10, aula 3A. Gli studenti che intendono sostenerlo devono prenotarsi sulla piattaforma delphi.

cambio aula lezione 16/11.

La lezione del 16/11 è si terrà in aula 2 PP2.

Lezione lunedì 14/11 annullata (ma quella di mercoledì 16 si terrà regolarmente)

Si comunica che la lezione di lunedì 14 novembre è annullata, mentre quella di mercoledì 16 novembre, diversamente da come comunicato a lezione, si terrà regolarmente. 

Cambio aula: le lezioni si spostano in aula 4 PP2.

Cambia l'aula delle lezioni di Algoritmi e strutture dati. Tutte le lezioni si terranno in aula 4 edificio PP2 (tranne quella del 7 novembre che si terrà in aula 3A).

lezione ASD del 10/10 annullata

Si comunica che la lezione di lunedì 10 ottobre non si svolgerà (motivi di salute del docente).

Tabelle Hash: un'alternativa ad un BST per l'implementazione di un dizionario. Scegliere un buona funzione hash. Definizione di famiglia universale di funzioni hash. Usare una famiglia unversale di funzioni hash per progettare un dizionario con complessità attesa costante per operazione. Un esempio di classe universale di funzioni hash. [KT 734 - 741].

Il problema dell’accesso ad una risorsa condivisa (Contention Resolution). Un protocollo distribuito. Analisi del protocollo. [KT 708 - 714]. Un (sorprendente) algoritmo di approssimazione per il problema di max 3SAT. Analisi dell’algoritmo. Stima del numero atteso di clausule soddisfatte. Accenno al metodo probabilistico. Stima del numero atteso di tentatvi prima di trovare una soluzione che soddisfa i 7/8 delle clausule. [KT 719-721, 724-727].

Introduzione agli algoritmi randomizzati. Il problema del calcolo del global mini-cut. Algoritmo di Karger. Dimostrazione che il numero di global min-cut di un grafo di n nodi è al più n(n-1)/2. [KT: pag 714-719].

Esercitazione sui problemi di flusso (Esercitazione 6).

Risolvere problemi trasformandoli in problemi di flusso: matching su grafi bipartiti, flusso massimo con sorgenti e destinazioni multiple, flusso con vincoli di capacità sui nodi.

Richiami sull’ottimalità dell’algoritmo di Ford Fulkerson. Rendere polinomiale l'algoritmo di Ford-Fulkerson: Scaling Max-Flow Algorithm [KT 352 - 356] e il Cammino aumentante di lunghezza minima [Dispense le prof. Gambosi http://www.mat.uniroma2.it/~guala/asd_2013.pdf pag 22 -25].

Introduzione al problema del Massimo Flusso. Algoritmo di Ford-Fulkerson. Prima analisi sulla terminazione [KT 337-345]. Massimo flusso e minimo taglio: un teorema importante. Ottimalità dell'algoritmo di Ford-Fulkerson [KT 346 - 351].

Esercitazione algoritmi greedy (Esercitazione 5).

Esercitazione algoritmi greedy (Esercitazione 4).

Analisi dell'algoritmo per il problema di Optimal Caching. Compressione Dati [KT05, pp 161-176]. Codifiche a lunghezza variabile. Codici prefissi e alberi binari. La codifica di Huffman. Ottimalità della codifica di Huffman.

Dimostrare l'ottimalità degli algoritmi Greedy: l'Exchange Argument [KT05, pp 125-136]. Progettazione ed analisi dell'algoritmo per il problema di Minimize Lateness. Progettazione dell'algoritmo per il problema di Optimal Caching.

Dimostrare l'ottimalità degli algoritmi Greedy: la tecnica Greedy
Stays Ahead [KT05, pp 116 - 124]. Applicazione della tecnica all'analisi di un
algoritmo per il problema Interval Scheduling. Un problema correlato:
Scheduling all Intervals. The survivals Run ([KT05] Solved Exercise 1).

Esercitazione. Esercizio uno (Problema 6): dato un grafo G=(V,E,w) e un arco e, rispondere in tempo lineare alla domanda: l'MST di G contiene o meno l'arco e? Esercizio due (Problema 7): trovare il miglior albero ricoprente vincolato ad avere certi nodi come nodi foglie. Esercizio tre (ordinamenti topologici e programmazione dinamica) (Probl.8): dato un dag G e due nodi s e t, calcolare in tempo lineare il numero di cammini distinti in G da s a t.

Algoritmo di Prim. Il problema del calcolo dei minimi antenati comuni in un albero. Algoritmo di Tarjan: un uso interessante delle struttura dati Union-Find.

Il problema del minimo albero di copertura (minimum spanning tree). Definizione del problema, motivazioni, proprietà fondamentali su cicli e tagli. L'algoritmo di Kruskal.

Mantenere efficientemente degli insiemi disgiunti: il problema Union-Find. Due approcci: QuickFind e Quick Union. Euristiche per l'operazione di Union. Stato dell'arte sul problema, una complessità che dipende dalla funzione inversa della funzione di Ackermann.

Esercitazione. Esercizio uno (Probl. 4): dato grafo G non orientato con pesi positivi sugli archi, e dato un sottoinsieme di k nodi detti centri, partizionare i nodi di G in k insiemi in modo che l'insieme i contenga i nodi che sono più vicini all'i-esimo centro che ad ogni altro. Esercizio due (Probl. 5): dato un grafo orientato G con pesi positivi sugli archi e che ha un sottoinsieme di archi detti blu, trovare il cammino di costo minimo da un certo nodo s a un certo nodo t che usa al più k archi blu.

Cammini minimi in grafi pesati: episodio III. Calcolare le distanze fra tutte le coppie di nodi. Algoritmo di Foyd e Warshall, e algoritmo di Johson.

Cammini minimi in grafi pesati: episodio II. Ancora sul problema del calcolo dei cammini minimi a singola sorgente. Un algoritmo per grafi con pesi negativi (ma non cicli negativi): algoritmo di Bellman e Ford. Usare l'algoritmo di Bellman e Ford per rilevare un ciclo di peso negativo. Trovare i cammini minimi a singola sorgente in un DAG in tempo lineare.

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

Esercitazione. Primo esercizio (Probl. 1): dato un insieme di esami e un insieme di propedeuticità, progettare un algoritmo che determina quali esami fare in ogni sessione in modo minimizzare il numero di sessioni. Secondo esercizio (Probl. 2): due robot telecomandabili si possono muovere su un grafo; in ogni istante si può sposare lungo un arco solo uno dei due robot e i robot non possono essere troppo vicini fra loro (per motivi di interferenza delle antenne); trovare la sequenza più corta di mosse che spostano i due robot dalle posizioni iniziali a due date posizioni finali. Terzo esercizio (Probl. 3): si vogliono posizionare più monete possibile su un grafo; la mossa che si può fare è mettere una moneta su un nodo libero e (necessariamente) farla scorrere lungo un arco verso un altro nodo libero; trovare un algoritmo che determina la strategia ottima.

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. Visite di un grafo. Visita in ampiezza (BFS): cammini minimi da una sorgente. Visita in profondità (DFS): uscire da un labirinto.

Teoria dei grafi, problemi su grafi, algoritmi su grafi. Nozioni preliminari. Grafi Euleriani. Il problema della colorazione di un grafo. Un algoritmo greedy per colorare un grafo.

Correzione Esercizio 3 Problem Set 2.

Correzione esercizi 2 e 4 del Problem Set 2.

Esercitazione sulla programmazione dinamica. Algoritmo di programmazione dinamica per il problema del distributore automatico (Es. 13). Aiutate Homer Simpson a mangiare più donut possibile (Es. 14).

Esercitazione sulla programmazione dinamica. Il signor Marche e il suo lavoro a cottimo (Es. 12). Il problema del distributore automatico: minimizzare il numero di monete nel dare il resto (Es. 13). Algoritmo greedy (goloso): non sempre funziona. Algoritmo di programmazione dinamica che risolve il problema (discussione).

Ancora sulla tecnica della programmazione dinamica. Calcolo della distanza fra due parole. Esercizio: il Signor Marche va in vacanza fra Roma e Firenze: aiutatelo a spendere il meno possibile (Es. 11).

Ancora sulla tecnica della programmazione dinamica. Esercizio: aiutate il Re Imprenditore (Es. 8). Altro esercizio: vendere al meglio una stecca di cioccolata (Es. 9). Il problema della sottosequenza crescente più lunga di un vettore (Es. 10).

Tecnica della programmazione dinamica. Un primo problema per vederla all'opera: calcolare un insieme indipendente di peso massimo in un cammino. Principi generali della programmazione dinamica.

Code con priorità. d-Heap, Heap Binomiali, (cenni sugli) Heap di Fibonacci.

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

Alberi AVL: definizione ed esempi. Alberi di Fibonacci. Dimostrazione della delimitazione superiore dell’altezza di un albero AVL. Operazioni sugli alberi AVL: search, insert, delete.

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 di progettazione di un algoritmo per ri-radicare un albero (vedere slide cap. 3).

Esercitazione sulle visite di alberi. Ricostruire un albero, dati gli ordini di visita simmetrica e in preordine dei nodi (Problema 3.7 del libro di testo). Dimostrazione che la sequenze di visita in preordine più quella in postordine non sono sufficienti in generale per ricostruire l'albero. Progettazione di un algoritmo che, preso un albero con chiavi 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).

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

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.

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). Discussione Esercizio 2 primo Problem Set.

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.

Equazioni di ricorrenza: uno scenario meno comune. Picture-Hanging Puzzles, ovvero come appendere un quadro in modo perverso arrotolando un corda intorno a dei chiodi in modo tale che, rimuovendo uno qualsiasi dei chiodi, il quadro cada. Soluzione per due chiodi. Soluzione ricorsiva per n chiodi che usa corda esponenzialmente lunga. E soluzione che usa corda di lunghezza polinomiale.

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.

http://www.mat.uniroma2.it/~guala/ASDL_2016.htm

http://www.mat.uniroma2.it/~guala/ASDL_2016.htm

Il corso è diviso in due moduli da 6 cfu. Per ogni modulo ci sarà una prova scritta e una prova orale. La prova orale deve essere sostenuta nello stesso appello in cui si sostiene lo scritto. (si vedano anche le slide sul sito relative alla prima lezione.)