Algoritmi e strutture dati

Docente: Luciano Guala'

Comunicazioni

lezione ASD martedý 22/03 annullata

19-03-2016 16:51

Si comunica che la lezione di Algoritmi e Strutture Dati (dot. Gualà) di martedì 22/03 non si terrà.


nuovo cambio aula lezioni ASD

01-12-2015 11:47

Si comunica che le lezione di Algoritmi e Strutture Dati si svolgeranno nuovamente in aula 3A.


cambio aula lezioni ASD

24-11-2015 11:18

Si comunica che le lezione di Algoritmi e Strutture Dati di questo semestre si svolgeranno in aula 1 edificio PP2.


lezione ASD mercoledý 4/11 annullata

02-11-2015 09:21

Si comunica che la lezione di Algoritmi e Strutture Dati di mercoledì 4/11/2015 è annullata.


lezione ASD mercoledý 21/10 annullata

19-10-2015 15:58

Si comunica che la lezione di Algoritmi e Strutture Dati di mercoledì 21/10/2015 è annullata.


Lezioni

4801-06-2016

Randomized Caching. Definizione di un algoritmo online (Least Recently Used). Definizione di un Marking Algorithm e analisi del numero di miss rispetto all'ottimo. Definizione del Randomized Caching Algorithm e analisi del numero di miss rispetto all'ottimo. [KT 750-757].

4731-05-2016

Tabelle Hash: un'alternativa ad un BST per l'implementazione di un dizionario. Definizione ed esempio di famiglia universale di funzioni hash. Analisi dello spazio inutilizzato [KT 734 - 740]. Analisi della lista più lunga [KT 760 - 761]. Accenno al Metodo Probabilistico [KT 718 - 719].

4625-05-2016

Esercitazione. Ancora sul Massimo Flusso. Esercizio: Assegnare programmatori su progetti software (Problema 14). Esercizio: progettare un corso di laurea: assegnare docenti ai corsi (Problema 15). Esercizio: un problema di trasporto di merci (Problema 16).

4517-05-2016

Introduzione agli algoritmi randomizzati. Problema dell'accesso concorrente ad una risorsa [KT 707-713]. Algoritmo di ricerca del Global Minimum Cut [KT 714-718].

4411-05-2016

Esercitazione. Ricondurre problemi da risolvere al problema del massimo flusso. Esercizio: Car Sharing equo fra studenti (Problema 11). Esercizio: far socializzare famiglie diverse ad una festa (Problema 12). Esercizio: determinare se una piata di un appartamento è ergonomica (Problema 13).

4310-05-2016

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

4204-05-2016

Massimo flusso e minimo taglio: un teorema importante. Ottimalità dell'algoritmo di Ford-Fulkerson [KT 346 - 351].

4103-05-2016

Introduzione al problema del Massimo Flusso. Algoritmo di Ford-Fulkerson. Prima analisi sulla terminazione [KT 337-345].

4027-04-2016

Esercitazione. Applicazione della tecnica Greedy Stays Ahead (Problema 9). Esempio di esecuzione dell'algoritmo di Huffman (Problema 10).

3926-04-2016

Compressione Dati [KT 161-176]. Codifiche a lunghezza variabile. Codici prefissi e alberi binari. La codifica di Huffman. Ottimalita' della codifica di Huffman.

3820-04-2016

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

3719-04-2016

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

3613-04-2016

Esercitazione. Esercizio uno (Prob. 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 (Probl. 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.

3512-04-2016

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.

3406-04-2016

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

3305-04-2016

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.

3230-03-2016

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.

3123-03-2016

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.

3016-03-2016

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.

2915-03-2016

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.

2809-03-2016

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.

2708-03-2016

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.

2602-03-2016

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.

2501-03-2016

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.

2418-01-2016

Correzione Problem Set 3.

2313-01-2016

Esercitazione sulla programmazione dinamica. Dare il resto usando il minimo numero di monete. Il problema del distributore automatico: minimizzare il numero di monete nel dare il resto (Es. 12). Algoritmo greedy (goloso): non sempre funziona. Algoritmo di programmazione dinamica che risolve il problema. Aiutate Homer a mangiare più donut possibile (Es. 13).

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

2121-12-2015

Correzione Problem Set 2.

2016-12-2015

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

1914-12-2015

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.

1809-12-2015

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

1707-12-2015

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.

1602-12-2015

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 relativo alla possibilità di usare un vettore posizionale anche per alberi non completi (vedere slide cap. 3). Correzione esercizio di progettazione di un algoritmo per ri-radicare un albero (vedere slide cap. 3).

1530-11-2015

Esercitazione (svolta da Francesco). Primo esercizio: valutare l'infrangibilità di un certo tipo di bicchiere (Es 6). Secondo esercizio: dato un array di n valori reali. Trovare la coppia di indici i e j con i<j che massimizza A[j]-A[i] (Es. 7).

1425-11-2015

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 proposto: progettare un algoritmo che,  preso un albero e in intero h, restituisce il numero di nodi dell'albero di profondità almeno h (Es 5).

1323-11-2015

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.

1218-11-2015

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 bit, progettare un algoritmo che in tempo O(n) trova un indice k tale che il numero di zeri in A[1;k] è uguale al numero di uni in A[k+1,n] (Es. 3).

1116-11-2015

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.

1011-11-2015

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.

909-11-2015

Algoritmo di ordinamento 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. Correzione Esercizio 3 del primo problem set.

802-11-2015

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

728-10-2015

Problema dell’ordinamento. Selection Sort. Insertion Sort: due varianti. Algoritmo di ordinamento MergeSort.

626-10-2015

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

Teorema Fondamentale delle Ricorrenze (Master). Semplici esempi. Quando non si può applicare. Metodo del cambiamento di variabile. Metodo che usa l’albero della ricorsione.

414-10-2015

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 della sostituzione.

312-10-2015

Discussione della complessità spaziale degli algoritmi ricorsivi Fibonacci2 e Fibonacci6. 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.

207-10-2015

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.

105-10-2015

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 accademico2015-2016
Crediti12
SettoreINF/01
Anno2
Semestre1-2
PropedeuticitàAnalisi Matematica. Matematica discreta. Programmazione dei calcolatori con laboratorio.

Programma

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


Testi di riferimento

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


Ricevimento studenti

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


Modalità di esame

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