| 48 | 01-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]. |
| 47 | 31-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]. |
| 46 | 25-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). |
| 45 | 17-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]. |
| 44 | 11-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). |
| 43 | 10-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]. |
| 42 | 04-05-2016
Massimo flusso e minimo taglio: un teorema importante. Ottimalità dell'algoritmo di Ford-Fulkerson [KT 346 - 351]. |
| 41 | 03-05-2016
Introduzione al problema del Massimo Flusso. Algoritmo di Ford-Fulkerson. Prima analisi sulla terminazione [KT 337-345]. |
| 40 | 27-04-2016
Esercitazione. Applicazione della tecnica Greedy Stays Ahead (Problema 9). Esempio di esecuzione dell'algoritmo di Huffman (Problema 10). |
| 39 | 26-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. |
| 38 | 20-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. |
| 37 | 19-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). |
| 36 | 13-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. |
| 35 | 12-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. |
| 34 | 06-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. |
| 33 | 05-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. |
| 32 | 30-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. |
| 31 | 23-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. |
| 30 | 16-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. |
| 29 | 15-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. |
| 28 | 09-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. |
| 27 | 08-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. |
| 26 | 02-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. |
| 25 | 01-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. |
| 24 | 18-01-2016
Correzione Problem Set 3. |
| 23 | 13-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). |
| 22 | 11-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). |
| 21 | 21-12-2015
Correzione Problem Set 2. |
| 20 | 16-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). |
| 19 | 14-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. |
| 18 | 09-12-2015
Code con priorità. d-Heap, Heap Binomiali, (cenni sugli) Heap di Fibonacci. |
| 17 | 07-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. |
| 16 | 02-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). |
| 15 | 30-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).
|
| 14 | 25-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). |
| 13 | 23-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. |
| 12 | 18-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). |
| 11 | 16-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.
|
| 10 | 11-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. |
| 9 | 09-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. |
| 8 | 02-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. |
| 7 | 28-10-2015
Problema dell’ordinamento. Selection Sort. Insertion Sort: due varianti. Algoritmo di ordinamento MergeSort. |
| 6 | 26-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. |
| 5 | 19-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. |
| 4 | 14-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.
|
| 3 | 12-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. |
| 2 | 07-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. |
| 1 | 05-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. |