| 49 | 03-06-2015
Esercitazione: risoluzione degli esercizi del Problem Set |
| 48 | 01-06-2015
Linear programming e rounding come tecnica per progettare algoritmi approssimanti per problemi NP-hard. Esempio: un algoritmo 2-approssimante per Weighted Vertex Cover |
| 47 | 27-05-2015
Verificare l'ottimalità di una soluzione di un linear program: il problema duale. I giochi a somma zero e la programmazione lineare. |
| 46 | 25-05-2015
Linear programming: interpretazione geometrica del problema. Le variabili slack e risoluzione tramite il simplex method. Cosa succede nel caso in cui il linear program è unbounded. Cenni a come trovare (se esiste) una soluzione feasible da cui far partire l'algoritmo. |
| 45 | 20-05-2015
Esercitazione su Network Flow |
| 44 | 18-05-2015
Il running time dell'algoritmo di Ford e Fulkerson. La variante con capacity scaling per rendere l'algoritmo polinomiale. Cenni ad altri modi di scegliere i cammini aumentanti (massimo bottleneck e visita in ampiezza) |
| 43 | 13-05-2015
Flusso massimo e taglio minimo: dimostrazione dell'ottimalità dell'algoritmo di Ford e Fulkerson. |
| 42 | 11-05-2015
Il problema Max-Flow e l'algoritmo di Ford e Fulkerson: correttezza e cenni sul tempo di completamento. |
| 41 | 06-05-2015
Esercitazione sulla tecnica greedy |
| 40 | 04-05-2015
Dimostrazione dell'ottimalità dell'algoritmo di Huffman. La tecnica greedy per progettare algoritmi approssimanti per problemi NP-hard. Esempio: il problema Load Balancing. |
| 39 | 29-04-2015
Codifiche a lunghezza variabile. Codici prefissi e alberi binari. La codifica di Huffman. |
| 38 | 27-04-2015
Dimostrare l'ottimalità di algoritmi Greedy: la tecnica Exchange Argument. Esempio di applicazione della tecnica all'analisi di un algoritmo per il problema Scheduling to Minimize Lateness. |
| 37 | 22-04-2015
Dimostrare l'ottimalità di algoritmi Greedy: la tecnica Greedy Stays Ahead. Esempio di applicazione della tecnica all'analisi di un algoritmo per il problema Interval Scheduling. Cenni ad alcune varianti del problema: Interval Partitioning e Weighted Interval Scheduling. |
| 36 | 20-04-2015
Correzione degli esercizi 2, 3 e 4 del Problem Set 4. |
| 35 | 15-04-2015
Algoritmo di Prim. Il problema del calcolo dei minimi antenati comuni in un albero. Algoritmo di Tarjan. Esercizio (ordinamenti topologici e programmazione dinamica) (Probl. 6): 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. |
| 34 | 13-04-2015
Il problema del minimo albero di copertura (minimum spanning tree). Definizione del problema, motivazioni, proprietà fondamentali su cicli e tagli. L'algoritmo di Kruskal. Discussione degli esercizi 1 e 3 del Problem Set 4. |
| 33 | 08-04-2015
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 | 01-04-2015
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 | 30-03-2015
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 | 25-03-2015
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 | 23-03-2015
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 | 18-03-2015
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 | 16-03-2015
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 | 11-03-2015
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 | 09-03-2015
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 | 21-01-2015
Correzione Problem Set 3. |
| 23 | 19-01-2015
Esercitazione sulla programmazione dinamica. Aiutate Homer a mangiare più donut possibile (Es. 11). 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. |
| 22 | 14-01-2015
Code con priorità. d-Heap, Heap Binomiali, (cenni sugli) Heap di Fibonacci. |
| 21 | 12-01-2015
Discussione soluzione dell'esercizio sul calcolo della sottosequenza crescente più lunga di un vettore. Insieme indipendente di peso massimo di un grafo: un algoritmo polinomiale per trovare un tale insieme indipendente vale un milione di dollari (e la gloria eterna fra gli scienziati). Un algoritmo di programmazione dinamica per calcolare un insieme indipendente di peso massimo di un albero (Es. 9). Esercizio: il Signor Marche va in vacanza fra Roma e Firenze: aiutatelo a spendere il meno possibile (Es. 10). |
| 20 | 07-01-2015
Correzione Problem Set 2. |
| 19 | 17-12-2014
Ancora sulla tecnica della programmazione dinamica. Calcolo della distanza fra due parole. Esercizio: calcolo della sottosequenza crescente più lunga di un vettore (Es. 8): una prima discussione. |
| 18 | 15-12-2014
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. |
| 17 | 10-12-2014
Esercitazione. 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. 6). Esercizio su albero AVL e "distanza" fra chiavi (Es. 7). |
| 16 | 03-12-2014
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. |
| 15 | 01-12-2014
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). |
| 14 | 26-11-2014
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 5). |
| 13 | 17-11-2014
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 | 12-11-2014
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. 4). |
| 11 | 10-11-2014
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 | 05-11-2014
Progettare algoritmi efficienti attraverso la progettazione di strutture dati efficienti. Un esempio: l'HeapSort - che ordina n elementi in tempo O(n log n) nel caso peggiore utilizzando memoria ausiliaria costante. |
| 9 | 03-11-2014
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. Esercizio: dato un vettore ordinato di bit, trovare in tempo O(log k) l'indice k dell'ultimo zero (Es. 3). Discussione Esercizio 4 del secondo problem set. |
| 8 | 29-10-2014
Esercitazione. Esercizio: mettere in ordine le funzioni per velocità crescenti. 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). |
| 7 | 27-10-2014
Problema dell’ordinamento. Selection Sort. Insertion Sort: due varianti. Algoritmo di ordinamento MergeSort. |
| 6 | 22-10-2014
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 | 20-10-2014
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 | 15-10-2014
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. Discussione sull'importanza di lavorare sui Problem Set. |
| 3 | 13-10-2014
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 | 08-10-2014
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. |
| 1 | 06-10-2014
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. |