Algoritmi e strutture dati

Docente: Luciano Guala'

Comunicazioni

Cambio giorni e orario lezioni per prossime festività

14-04-2017 16:19

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.

07-03-2017 14:56

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

02-02-2017 09:43

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.

16-11-2016 08:41

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


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

14-11-2016 10:04

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.

24-10-2016 18:44

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

09-10-2016 22:02

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


Lezioni

4830-05-2017

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

4729-05-2017

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

4623-05-2017

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

4522-05-2017

Esercitazione sui problemi di flusso (Esercitazione 6).

4416-05-2017

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.

4315-05-2017

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

4209-05-2017

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

4108-05-2017

Esercitazione algoritmi greedy (Esercitazione 5).

4004-05-2017

Esercitazione algoritmi greedy (Esercitazione 4).

3902-05-2017

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.

3827-04-2017

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.

3720-04-2017

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

3611-04-2017

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.

3510-04-2017

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.

3404-04-2017

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

3303-04-2017

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.

3228-03-2017

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.

3127-03-2017

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.

3021-03-2017

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.

2920-03-2017

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.

2814-03-2017

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.

2713-03-2017

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.

2607-03-2017

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.

2506-03-2017

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.

2416-01-2017

Correzione Esercizio 3 Problem Set 2.

2311-01-2017

Correzione esercizi 2 e 4 del Problem Set 2.

2209-01-2017

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

2121-12-2016

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

2019-12-2016

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

1914-12-2016

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

1812-12-2016

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.

1707-12-2016

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

1605-12-2016

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

1530-11-2016

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.

1428-11-2016

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

1323-11-2016

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

1221-11-2016

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.

1116-11-2016

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

1009-11-2016

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.

907-11-2016

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.

802-11-2016

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.

726-10-2016

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.

624-10-2016

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.

519-10-2016

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.

417-10-2016

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.

312-10-2016

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.

205-10-2016

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.

103-10-2016

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.


Materiale didattico

Informazioni

Anno accademico2016-2017
Crediti12
SettoreINF/01
Anno2
Semestre1-2
PropedeuticitàAnalisi Matematica. Matematica discreta. Programmazione dei calcolatori con laboratorio.

Programma

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


Testi di riferimento

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


Ricevimento studenti

null

Modalità di esame

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