| 48 | 04-06-2018
Esercitazione su programmazione dinamica
|
| 47 | 31-05-2018
Algoritmi di approssimazione
- Problema del Load Balancing
- Algoritmo 2-approssimato
- Algoritmo 3/2-approssimato
- Problema del Knapsack
- Algoritmo (1-epsilon)-approssimato.
|
| 46 | 28-05-2018
- Concetto di equivalenza fra problemi NP-completi (ripasso)
- Problemi di Ottimizzazione: definizione formale ed esempi
- Relazione tra problemi di ottimizzazione e loro versione decisionale
- Problemi di ottimizzazione NP-Hard
- Concetto di algoritmo approssimante: definizione formale
- Un algoritmo 2-approssimante per VC
Testo: KT. |
| 45 | 24-05-2018
- Problemi NP-completi
- Il problema 3-SAT è in NP
- NP-completezza di 3-SAT (senza dimostrazione)
- Il problema Independent Set è in NP
- La riduzione polinomiale 3-SAT < IS: la tecnica dei GADGETS
- Il problema Vertex Cover
- Relazione tra VC e IS: equivalenza.
Testo: KT. |
| 44 | 21-05-2018
Il problema dell’accesso ad una risorsa condivisa (Contention Resolution). Un protocollo distribuito. Analisi del protocollo.
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.
Testo: KT, pag 708-714, 719-721, 724-727.
|
| 43 | 17-05-2018
Lezione del 17/05
-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.
Testo: KT, pag 714-719. |
| 42 | 14-05-2018
- Definizione formale di Certificatori efficienti
- Definizione formale della classe NP
- Relazione di NP con P ed EXP
- Esempi di problemi e di certificatori per essi
- Riducibilità polinomiale: versioni di Cook e Karp
- Proprietà della riducibilità di Karp: chiusura rispetto a P
Testo: KT. |
| 41 | 10-05-2018
- Programmazione dinamica: il problema del Sequence Alignment
- Modellazione del Problema e principali applicazioni
- Un primo approccio sbagliato di Programmazione Dinamica ad una variabile
- L'approccio a due variabili corretto
- Complessità e correttezza: lo spazio utilizzato
- La trasformazione a problemi di cammini minimi
- Introduzione alla classe NP
- Problemi efficientemente verificabili: esempi
- Ripasso della Pseudopolinomialità
Testo: KT. |
| 40 | 07-05-2018
Esercitazione sulla programmazione dinamica. I due esercizi discussi possono essere trovati nelle seguenti note:
http://www.mat.uniroma2.it/~guala/discussi_2017.pdf |
| 39 | 03-05-2018
- programmazione dinamica: calcolare cammini minimi in grafi con pesi negativi
- cammini minimi in grafi pesati
- problema dei cammini minimi a singola sorgente (o singola destinazione)
- grafi con pesi negativi: false partenze
- un algoritmo di programmazione dinamica: algoritmo di Bellman-Ford (BF) con complessità temporale O(mn) e spaziale O(n^2)
- ridurre la memoria a O(n)
- modificare l'algoritmo di BF per rilevare cicli di peso negativo
Testo: KT. |
| 38 | 26-04-2018
- Programmazione dinamica: ripasso degli esempi precedenti e valutazioni generali sulle condizioni di applicabilità
- Programmazione dinamica: Il problema della Bisaccia.
- Un approccio di programazione dinamica con un parametro che non funziona
- Un approccio a due parametri che funziona
- Analisi dell'ottimalità
- Implementazione dell'algoritmo ricorsivo
- Analisi della complessità
- Gli algoritmi pseudopolinomiali
Testo: KT. |
| 37 | 23-04-2018
- Il problema Weighted Interval Scheduling (continua)
- Come calcolare la soluzione ottima da OPT(J)
- La versione ricorsiva efficiente dell'algoritmo di programmazione dinamica: analisi della complessità mediante la misura progresso Φ.
- Il problema Segmented Least Squares
- Introduzione informale e definizione rigorosa.
- Esempi
- Formulazione del problema in termini di programmazione dinamica
- L'algoritmo ottimale: versione iterativa ed analisi della complessità
Testo: KT. |
| 36 | 19-04-2018
- La programmazione dinamica
- cenni storici ed applicazioni principali
- Descrizione informale
- Il problema Weighted Interval Scheduling
- Non ottimalità di alcuni approcci greedy
- Un possibile ordinamento dell'istanza e relativi sottoproblemi
- La struttura dell'ottimo OPT(j)
- Formulazione ricorsiva di OPT(j)
- Un algoritmo di programmazione dinamica ricorsivo non efficiente: analisi del caso peggiore.
- Un algoritmo iterativo efficiente: analisi del caso peggiore.
Testo: KT. |
| 35 | 16-04-2018
- Compressione dati (Riepilogo lezione precendente)
- La struttura dell'ottimo: proprietà
- L'approccio BOTTOM-UP
- Algoritmo e codici di Huffman
- Esempi di esecuzione dell'Algoritmo di Huffman
- Analisi della complessità dell'Algoritmo
- Implementazione efficiente dell'Algoritmo mediante struttura Heap
Testo: KT. |
| 34 | 12-04-2018
- Compressione dati mediante codici prefissi: definizione formale
- Rappresentazione di codici prefissi mediante alberi binari etichettati
- La funzione ABL(C) definita su codici ed alberi associati
- Progetto di algoritmi greedy per la costruzione di codici ottimali
- La struttura dell'ottimo: alberi full
- L'approccio TOP-DOWN (Codici di Shannon-Fano)
Testo: KT. |
| 33 | 09-04-2018
- Il problema del k-clustering: Definizione formale & Esempi
- Il modellamento dell’istanza come grafo completo pesato
- L’approccio Greedy basato sul MST e l’algoritmo di Kruskal
- Dimostrazione dell’ottimalità dell’Algoritmo Greedy
- Il problema della Compressione Dati
- Cenni storici, motivazioni, applicazioni moderne
- Il problema della codifica: definizione informale
- La codifica binaria di un testo a lunghezza variabile e la sua inefficienza su testi ridondanti
- I codici prefissi: definizione.
Testo: KT. |
| 32 | 05-04-2018
- Maximum Latency: definizione del problema di ottimizzazione
- Approcci greedy
- L'algoritmo greedy deadline-first D
- Struttura dell'ottimo
- Ottimalità dell'algoritmo D
- Riepilogo dei tools generali di progettazione ed analisi di algoritmi greedy
- Il problema del CLUSTERING
- Motivazioni e considerazioni generali.
- Una possibile definizione formale di problema in termini di spazi metrici e k-partizioni.
Fonte: KT. |
| 31 | 29-03-2018
Esercitazione sul metodo greedy e sulle sue tecniche di analisi.
L’esempio del grafo con i pesi al quadrato (Es. 2a, KT, pag 189).
L’esercizio del minimizzare il n. di tappe di un percorso lineare (Solved Exercise 1, KT pag. 183).
Considerazioni generali sull’approccio greedy. |
| 30 | 26-03-2018
Il problema Interval Partitioning.
il concetto di Depth(I) di una istanza I.
Un utile lower bound per Depth(I).
Un algoritmo Greedy ottimale.
Implementazione ed analisi della complessità.
Dimostrazione di ottimalità: confronto con il lower bound su depth(I).
Fonti: capitolo su GREEDY ALGORITHMS del KT. |
| 29 | 22-03-2018
1. Introduzione ai problemi di scheduling
2. Descrizione tecnica Greedy
3. Il problema Interval Scheduling
4. Approcci Greedy
5. L'Algoritmo Greedy ottimale basato sul finish time
6. Analisi della complessità
7. Dimostrazione di ottimalità: "Greedy stays ahead''
8. La riduzione del problema al problema Max Independent Set su (Interval) Graphs
Fonti: capitolo su GREEDY ALGORITHMS del KT. |
| 28 | 19-03-2018
1. Riepilogo Algoritmo A(G,e)
2. La Struttura Dati Union-Find
3. Definizione delle operazioni ammesse
4. Esempi
5. Soluzione mediante Foreste
6. Una soluzione non efficiente
7. La struttura Quick-Find
8. Analisi della complessità ammortizzata della struttura Quick-Find
9. Applicazione: L'Algoritmo di Kruskal K
10. Implementazione di K mediante Quick-Find
11. Analisi della complessità e della correttezza di K
Fonti: Union-Find: libro di Demetrescu et al (si vedano anche le slide a.a.2016-17). Algoritmo di Kruskal: libro KT. |
| 27 | 14-03-2018
Esercitazione.
1. La relazione tra Shortest Path Tree (SPT) e Minimum Spanning Tree (MST).
2. Esempi di grafi che evidenziano la differenza.
3. Algoritmo A(G,e) per la verifica dell’appartenenza di un fissato arco ad un MST di un grafo pesato connesso (Es. n 3, p. 187 di [KT]).
4. Dimostrazione della correttezza ed analisi della complessità dell’Algoritmo A(G,e). |
| 26 | 12-03-2018
1. IL problema del MST
2. Definizione formale come probl. di ott.
3. Applicazioni principali (cenni)
4. Proprietà del Taglio e MST
5. Proprietà del Ciclo e MST
6. Proprietà dell'intersezione tra Cicli e Tagli
7. Tre approcci Greedy
8. l'Algoritmo di Prim (Visita)
9. Correttezza dell'algoritmo di Prim mediante la Propr. 4
10. Implementazione dell'Algoritmo
11. Esempio di esecuzione
12. Analisi della complessità temporale
13. Testo: Keliberg & Tardos, Algorithm Design
14. Slides del Prof. Clementi (file mst-andy-lesson1.pdf) |
| 25 | 08-03-2018
1. Introduzione generale al II modulo, modalità dell'esame.
2. Def. del problema dei cammini minimi come problema di ottimizzazione.
3. Proprietà dei cammini minimi e dei loro sottocammini.
4. Algoritmo di Dijkstra per cammini minimi.
5. Correttezza e Complessità dell'Algoritmo.
6. Libro: Demetrescu, Finocchi, Italiano, Algoritmi e Strutture Dati, McGraw-Hill.
7. Slides del Dr. Gualà (file Dijkstra2017). |
| 24 | 11-01-2018
Discussione (ancora) sull’esercizio 3 del Problem Set 3 e correzione Esercizio 2. Esercizio: andare allo stadio con un amico spendendo il meno possibile (Esercizio 10). |
| 23 | 08-01-2018
Correzione Esercizio 1 e Esercizio 3 del Problem Set 3. |
| 22 | 14-12-2017
Esercitazione. Spendere il meno possibile per andare ad una festa con regalo (Esercizio 9). Una soluzione di costo O(mn+n^2 log n). Una migliore soluzione di costo O(m+n log n). Una soluzione alternativa di costo O(m+n log n): tecnica della riduzione e utilizzo di grafi ausiliari. |
| 21 | 11-12-2017
Cammini minimi in grafi pesati. Il problema del calcolo dei cammini minimi a singola sorgente. Un algoritmo veloce quando il grafo ha pesi non negativi: l'algoritmo di Dijkstra. |
| 20 | 07-12-2017
Discussione sul Problem Set 2: correzione Esercizio 3; discussione Esercizio 4. |
| 19 | 04-12-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. |
| 18 | 30-11-2017
Strutture dati per rappresentare un grafo. Matrice di adiacenza e Liste di adiacenza. Visite di un grafo. Visita in ampiezza (BFS): cammini minimi da una sorgente. Visita in profondità (DFS): uscire da un labirinto. |
| 17 | 27-11-2017
I Grafi (diretti, non diretti, pesati). Nozioni preliminari. Cammini, distanze, diametro. Alberi. Grafi Euleriani. I grafi come linguaggio potente per descrivere scenari e problemi. Esempi di scenari/problematiche descrivibili come grafi/problemi su grafi (reti stradali/di trasporto, reti sociali, reti “delle dipendenze”). |
| 16 | 23-11-2017
Il problema della Coda con priorità. d-Heap, Heap Binomiali, (cenni sugli) Heap di Fibonacci. |
| 15 | 20-11-2017
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. 7). 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. 8). |
| 14 | 16-11-2017
Il problema del Dizionario: secondo episodio. Alberi AVL: definizione ed esempi. Dimostrazione della delimitazione superiore dell’altezza di un albero AVL (che usa la nozione di albero di Fibonacci). Operazioni sugli alberi AVL: search, insert, delete. |
| 13 | 13-11-2017
Il problema del Dizionario. 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 3 del Problem Set 1. |
| 12 | 09-11-2017
Esercitazione sulle visite di alberi. Progettazione di un algoritmo che, preso un albero con valori 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). Altro esercizio: preso un albero binario con valori, calcola il numero di nodi per cui la somma dei valori degli antenati è uguale alla somma dei valori dei discendenti (Es. 6). |
| 11 | 06-11-2017
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. |
| 10 | 02-11-2017
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). |
| 9 | 30-10-2017
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. |
| 8 | 26-10-2017
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). |
| 7 | 23-10-2017
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. |
| 6 | 19-10-2017
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. |
| 5 | 16-10-2017
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. |
| 4 | 12-10-2017
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. |
| 3 | 09-10-2017
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 | 05-10-2017
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 | 02-10-2017
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. |