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 approssimante per problemi di ottimizzazione combinatoria 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 | 03/04/07 Aula 'L' |
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, codifica, modelli precisi e modelli approssimati. Problemi computazioni di ottimizzazione. Esempi di problemi computazionali. |
--- | Roberto Posenato |
| 2 | 04/04/07 Aula 'L' |
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. | --- | Roberto Posenato |
| 3 | 11/04/07 Aula 'L' |
2 | 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. Analisi complessità. Esempi di applicazione: prodotto tra due numeri, |
[Dasgupta et al., cap. 2] | Roberto Posenato |
| 4 | 12/04/07 Aula 'L' |
1 | Prodotto fra due matrici. Introduzione al prodotto fra due polinomi. | [Cormen et al., cap. 30] | Roberto Posenato |
| 5 | 17/04/07 Aula 'L' |
2 | Schema divide et impera per il prodotto di due polinomi. Uso
delle radici primitive complesse per la valutazione veloce di un
polinomio: Trasformata veloce di Fourier (FFT). Uso di FFT anche per
l'interpolazione. Introduzione al problema della mediana e, generalizzazione, al problema della selezione. |
[Cormen et al., cap. 30], [Dasgupta et al., cap. 2] |
Roberto Posenato |
| 6 | 18/04/07 Aula 'L' |
2 | Risoluzione del problema della selezione. Illustrazione di
altri problemi risolvibili con la tecnica divide et impera: ricerca
massimo di un piano, ricerca della coppia di punti più vicina. Paradigma greedy Richiamo struttura. Esempio di applicazione per il problema dell'albero minimo di ricoprimento. Richiamo sulla struttura dati per insiemi disgiunti. |
[Bertossi, cap. 13], [Dasgupta et al., cap. 5] |
Roberto Posenato |
| 7 | 19/04/07 Aula 'L' |
1 | Esercizi sulla tecnica divide et impera. | --- | Roberto Posenato |
| 8 | 02/05/07 Aula 'L' |
2 | Esempio di applicazione per il problema dei cammini minimi
da sorgente singola (algoritmo di Dijkstra). Introduzione ai matroidi: definizione, proprietà fondamentali. Problema del Massimo di un matroide pesato. |
[Bertossi, cap. 13], [Cormen et al., cap 16] |
Roberto Posenato |
| 9 | 03/05/07 Aula 'L' |
1 | Dimostrazione che la tecnica greedy determina sempre la
soluzione ottima per il problema del Massimo di un matroide pesato. Valutazione due soluzioni all'esercizio di ricerca elemento in una matrice ordinata. |
--- | Roberto Posenato |
| 10 | 08/05/07 Aula 'L' |
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 matrodidi. Esercizi. Tecnica backtracking Introduzione. Schema generale. Aspetti cruciali. |
[Bertossi, cap. 12] | Roberto Posenato |
| 11 | 09/05/07 Aula 'L' |
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. |
--- | Roberto Posenato |
| 12 | 10/05/07 Aula 'L' |
1 | Esercizio di applicazione tecnica greedy al problema del resto di monete. | --- | Roberto Posenato |
| 13 | 15/05/07 Aula 'L' |
2 | Uso della tecnica backtracking al problema del string
matching: algoritmo di Knuth, Morris & Pratt. Tecnica branch & bound Introduzione. Schema generale. Aspetti cruciali. |
[Cormen et al., cap. 32.5] [Bertossi, cap. 23] |
Roberto Posenato |
| 14 | 16/05/07 Aula 'L' |
2 | 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 e al problema dello zaino. |
--- | Roberto Posenato |
| 15 | 17/05/07 Aula 'L' |
1 | Formalizzazione soluzione del problema del minimo resto. | --- | Roberto Posenato |
| 16 | 22/05/07 Aula 'L' |
2 | Applicazione della tecnica al problema del commesso
viaggiatore come esempio di funzione lower bound non banale. Paradigma programmazione dinamica Introduzione. Schema generale. Aspetti cruciali. Applicazione della tecnica al problema della massima sottosequenza crescente. |
[Bertossi, cap. 14], [Cormen et al., cap. 15], [Dasgupta et al., cap. 6] |
Roberto Posenato |
| 17 | 23/05/07 Aula 'L' |
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. |
--- | Roberto Posenato |
| 18 | 24/05/07 Aula 'L' |
1 | Tecnica memoization (annotazione) Introduzione e analisi vantaggi svantaggi. Tecnica ricerca locale Introduzione e studio caso applicazione al problema dell'albero minimo di ricoprimento. |
[Bertossi, cap. 15] | Roberto Posenato |
| 19 | 29/05/07 Aula 'L' |
2 | Risoluzione del problema dell'ordinamento mediante tecnica
di ricerca locale: ordinamento per inserimento e ShellSort. Algoritmi di approssimazione Classi NPO e PO. Errore relatio e indice di performance. Algorimo 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] | Roberto Posenato |
| 20 | 30/05/07 Aula 'L' |
2 | Simulated annealing Tabù search |
[Bertossi, cap. 24] | Roberto Posenato |
| 21 | 31/05/07 Aula 'L' |
1 | Esercitazione | --- | Roberto Posenato |
| 22 | 05/06/07 Aula 'L' |
2 | Algoritmi probabilistici Definizione. Algoritmi probabilistici numerici, algoritmi di Monte Carlo e algoritmi di Las Vegas. Esempi di problemi risolti con tali algoritmi: Buffon's needle, Pattern Matching e Universal hashing. |
[Brassard e Bratley, cap. 10] | Roberto Posenato |
| 23 | 06/06/07 Aula 'L' |
2 | Algoritmi quantistici Introduzione ai concetti di qubit, stato di sistema quantistico, codifica di informazioni con i qubit, algoritmo quantistico. Determinazione della trasformata di Fourier mediante algoritmo quantistico. |
[Dasgupta et al., cap. 10] | Roberto Posenato |
| 24 | 07/06/07 Aula 'L' |
1 | Esercitazione prova esame | --- | Roberto Posenato |
L'errata corrige del corso si trova alla pagina http://profs/~posenato/courses/algavanzati/lucidi.