Acquisire un'adeguata conoscenza dei principali paradigmi avanzati di algoritmi per problemi di ottimizzazione combinatorica con particolare attenzione per i paradigmi che permettono di determinare soluzione approssimate per problemi di ottimizzazione NP-difficili.
Il corso viene svolto in 40 ore di lezione frontale.
Il programma è diviso in lezioni. La colonna Rif. indica i paragrafi o i capitoli dei libri adottati per il corso.
| N. | Data Luogo |
N. ore | Argomento | Rif. | Firma |
|---|---|---|---|---|---|
| 1 | 08/04/08 Aula I |
2 | Introduzione al corso Presentazione del corso: programma, testi di riferimento e modalità d'esame. Richiamo dei principali concetti inerenti ai problemi computazionali: descrizione, istanze, modelli precisi e modelli approssimati. Problemi computazionali di ottimizzazione. Problemi nel continuo e problemi nel discreto. Versioni dei problemi di ottimizzazione. Esempi di problemi computazionali. |
Roberto Posenato | |
| 2 | 09/04/08 Aula I |
2 | Richiamo dei principali concetti inerenti agli algoritmi: risorse computazionali, codifica dell'input,
dimensione dell'input, definizione di tempo computazionale. Analisi caso peggiore e caso medio.
Tempo di calcolo e ordini di grandezza: possibili insidie. Tempi di calcolo e miglioramenti hardware:
relazioni principali. Algoritmi efficienti e problemi trattabili. Paradigma divide et impera Richiamo struttura. |
Roberto Posenato | |
| 3 | 10/04/08 Aula I |
1 | Analisi complessità. Esempi di applicazione: prodotto tra due numeri e prodotto fra due matrici. | Cormen et al., Dasgupta et al. cap. 2 | Roberto Posenato |
| 4 | 15/04/08 Aula I |
2 | Prodotto fra due polinomi: schema divide et impera e sua implementazione mediante la trasformata veloce di Fourier (FFT). | Cormen et al. cap. 30 | Roberto Posenato |
| 5 | 16/04/08 Aula I |
2 | Introduzione al problema della mediana e, generalizzazione, al problema della selezione. Risoluzione del problema
della selezione. Paradigma greedy Richiamo struttura. Esempio di applicazione per il problema dell'albero minimo di ricoprimento. Esempio di applicazione per il problema dei cammini minimi da sorgente singola (algoritmo di Dijkstra). |
Dasgupta et al. cap.5, Bertossi, cap. 13 |
Roberto Posenato |
| 6 | 17/04/08 Aula I |
1 | Introduzione ai matroidi: definizione, proprietà fondamentali. Problema del Massimo di un matroide pesato. Dimostrazione che la tecnica greedy determina sempre la soluzione ottima per il problema del Massimo di un matroide pesato. | Cormen et al. cap. 16 | Roberto Posenato |
| 7 | 22/04/08 Aula I |
2 | Uso dei matroidi per la risoluzione del problema di programmazione di task unitari su singolo processore.
Limiti della rappresentazione con i matroidi. Esempi di problemi risolvibili con tecnica greedy che non sono
rappresentabili da matroidi. Tecnica backtracking Introduzione. Schema generale. Aspetti cruciali. |
Roberto Posenato | |
| 8 | 23/04/08 Aula I |
2 | Applicazione della tecnica al problema dello zaino con ripetizione. Analisi correttezza e complessità. Introduzione uso della tecnica al problema dell'inviluppo convesso: algoritmo di Graham. |
Bertossi cap. 12 | Roberto Posenato |
| 9 | 24/04/08 Aula I |
1 | Esercizi sulla tecnica dividi et impera e sul greedy. | Roberto Posenato | |
| 10 | 29/04/08 Aula I |
2 |
Uso della tecnica backtracking al problema del string matching: algoritmo di Knuth, Morris & Pratt. Tecnica branch & bound Introduzione. Schema generale. Aspetti cruciali. Scelta ordine di visita dei figli: strategia hill climbing. Tecnica come nuova tecnica ricerca in un albero: strategia best-first. Applicazione della tecnica al problema dell'assegnamento |
Cormen et al. cap. 32.5, Lee et al. cap. 5 |
Roberto Posenato |
| 11 | 30/04/08 Aula I |
2 | Applicazione della tecnica branch & bound al problema dello zaino.
Applicazione della tecnica al problema del commesso viaggiatore come esempio di funzione lower bound non
banale. Esercizi sulle equazioni di ricorrenza. |
Roberto Posenato | |
| 12 | 06/05/08 Aula I |
2 |
Paradigma programmazione dinamica Introduzione. Schema generale. Aspetti cruciali. |
Bertossi cap. 14, Cormen et al. cap. 15, Dasgupta et al. cap. 6 |
Roberto Posenato |
| 13 | 07/05/08 Aula I |
2 | Applicazione della tecnica al problema della massima sottosequenza crescente. | Roberto Posenato | |
| 14 | 08/05/08 Aula I |
1 | Esercizi sulla tecnica divide et impera. | Roberto Posenato | |
| 15 | 13/05/08 Aula I |
2 | Applicazione della tecnica al problema del string matching approssimato e al problema dello zaino. Analisi di esempi di applicazione. Pattern ricorrenti per la determinazione di sottoproblemi. Tecnica memoization (annotazione) Introduzione e analisi vantaggi svantaggi. |
Roberto Posenato | |
| 16 | 14/05/08 Aula I |
2 | Algoritmi probabilistici Definizione. Algoritmi probabilistici numerici con esempio: Buffon's needle. |
Brassard e Bratley, cap. 10 Bertossi cap. 20 |
Roberto Posenato |
| 17 | 15/05/08 Aula I |
1 | Esercizi sugli algoritmi greedy. | Roberto Posenato | |
| 18 | 20/05/08 Aula I |
2 | Algoritmi di Monte Carlo con esempio: test di primalità. Algoritmi di Las Vegas con esempio: universal hashing. |
Roberto Posenato | |
| 19 | 22/05/08 Aula I |
1 | Esercizi sugli algoritmi greedy. | Roberto Posenato | |
| 20 | 27/05/08 Aula I |
2 |
Tecnica ricerca locale Introduzione e studio caso applicazione al problema dell'albero minimo di ricoprimento. Risoluzione del problema dell'ordinamento mediante tecnica di ricerca locale: ordinamento per inserimento e ShellSort. Simulated annealing: introduzione alla tecnica. |
Bertossi cap. 15 | Roberto Posenato |
| 21 | 28/05/08 Aula I |
2 | Esempio di algoritmo di simulated annealing applicato al problema SAT: Algoritmo di Spears. Introduzione alla Tabu search. Tipi di proibizioni: fissa, casuale e reattiva. Esempio di algoritmo tabu search con proibizione fissa: Algoritmo per BISEZIONE. |
Bertossi cap. 24 | Roberto Posenato |
| 22 | 29/05/08 Aula I |
1 | Esempio di tabu search con proibizione casuale e reattiva: algoritmo per BISEZIONE. | Roberto Posenato | |
| 23 | 03/06/08 Aula I |
2 | Introduzione ai problemi di vincoli temporali (Temporal Constraint Problems): definizione e principali tecniche risolutive. | Roberto Posenato | |
| 24 | 04/06/08 Aula I |
2 | Algoritmi di approssimazione Classi NPO e PO. Errore relativo e indice di performance. Algoritmo r-approssimante. Problema r-approssimabile. Studio dell'approssimabilità del problema Min Vertex Cover: dall'algoritmo greedy all'algoritmo pseudo-casuale. |
Cormen et al. cap. 35, Brassard e Bratley cap. 13, Bertossi cap. 22 |
Roberto Posenato |
| 25 | 05/06/08 Aula I |
1 | Esercizi. | Roberto Posenato | |
| Totale ore | 42 | ||||