Calendario degli appelli d'esame valido per tutti i corsi sottostanti

Ultimo appello a.a. 2005/06 e primo appello 2006/07

Giovedì 25 gennaio 2007

Martedi' 13 febbraio 2007

Martedi' 12 giugno 2007

Venerdì 27 luglio 2007

Martedì 18 settembre 2007

Martedi' 22 gennaio 2008

---

AVVISI

------------------------------------------------------------------------------------------------------

Modifiche orario corso di Complementi di Ricerca Operativa:

martedì 16,45-18,30 auletta 5 (invariato)

venerdì 13,00-14,45 auletta 5 (anticipato)

Modifiche orario corso di Algoritmi e Strutture Dati II:

lunedì 13,45-17,30 aula Alfa (anticipato)

giovedì 16,30-20,00 aula Alfa (invariato)

------------------------------------------------------------------------------------------------------

Gli studenti che hanno superato l'esame di FRO con i le prove in itinere, per poter verbalizzare il voto devono comunque iscriversi ad un appello regolare.

Ricordo le regole presentate all'inizio del corso. Con una votazione nei compitini o in una prova scritta:

- minore o uguale a 16 è necessario ripetere l'esame scritto

- pari a 17 è possibile sostenere un esame orale integrativo

- compresa fra 18 e 27 (estremi inclusi) l'esame orale è facoltativo

- superiore a 27, senza sostenere la prova orale, il voto verbalizzato è 27

---

Orario corsi
Fondamenti di Ricerca Operativa	Aula G22 via Golgi 19 Aula G12 via Golgi 19	Lunedì 13,30 – 15,30 Venerdì 14,30 – 16,30
Simulazione	Auletta 6 via Comelico 39	Lunedì 10,30 – 12,30 Mercoledì 10,30 – 12,30
Complementi di Ricerca Operativa (orario provvisorio)	Auletta 5 via Comelico 39 Auletta 5 via Comelico 39	Martedì 16,30 – 18,30 Venerdì 13,00 – 14,45
Algoritmi e Strutture Dati II mod 1	Aula Alfa via Comelico 39	Lunedì 13,30 – 17,30 Giovedì 16,30 – 20,30
Algoritmi e Strutture Dati II mod 2	Aula Alfa via Comelico 39	Lunedì 13,30 – 17,30 Giovedì 16,30 – 20,30

---

Programma dei corsi per l'a.a. 2006/07 e sommario degli argomenti trattati

---

Fondamenti di Ricerca Operativa
Ore di didattica: 48	Crediti: 6	Semestre: 1°
Modalita’ d’esame: scritto, prova orale

Obiettivi del corso:

Il corso si propone di introdurre i fondamenti della programmazione matematica e le relative tecniche algoritmiche, con particolare attenzione ai modelli di programmazione lineare, a quelli di programmazione lineare intera e a quelli ottimizzazione su grafo. Esempi illustrano i numerosi ambiti di applicazione delle tecniche descritte.

1. Introduzione

Programmazione matematica. Formulazione matematica di problemi di ottimizzazione: modelli di programmazione lineare (PL) e lineare intera (PLI). Cenni alla teoria della complessità computazionale.

2. Programmazione Lineare

Programmazione Lineare : geometria della PL e soluzione grafica. Algoritmo del Simplesso in forma base e Tableau. Metodo delle due Fasi. Dualità in PL. Problema duale. Relazioni primale-duale. Proprietà fondamentali. Condizioni di ottimalità. Simplesso duale. Analisi di sensitività.

3. Programmazione Lineare a Numeri Interi

Matrici unimodulari. Piani di taglio, Tagli di Gomory. Metodo "Branch and Bound". Tecniche per il calcolo dei bounds. Esempi di algoritmi Branch and Bound.

4. Elementi Di Teoria Dei Grafi

Definizioni. Algoritmi per il calcolo dell’albero di supporto di costo minimo. Algoritmi per il calcolo di cammini minimi. Il problema del flusso massimo: Algoritmo di Ford-Fulkerson. Il problema del flusso massimo a costo minimo. Gestione di progetti: metodo del cammino critico.

Bibliografia di riferimento:

M. Fischetti: Lezioni di Ricerca Operativa, Edizioni Libreria Progetto Padova, 1995.

Bibliografia consigliata:

R. Baldacci, M. Dell'Amico: Fondamenti di Ricerca Operativa, Pitagora Editrice Bologna, 2002.

M. Dell’Amico: 120 esercizi di ricerca operativa, Pitagora Editrice Bologna, 1996.

G.L. Nemhauser, L.A. Wolsey: Integer and Combinatorial Optimization, Wiley, 1988.

C.H. Papadimitriou, K. Steiglitz: Combinatorial Optimization: Alghorithms and Complexity, Prentice Hall, 1982.

R.K. Ahuja, T.L. Magnanti, J.B. Orlin: Network Flows, Prentice Hall, 1993.

Prerequisiti:

Elementi di algebra delle matrici.

Materiale integrativo

1. Esercizi di formulazione di modelli di programmazione lineare e programmazione lineare intera ModPL, ModPLI ( file pdf)
2. Esercizi di programmazione lineare e programmazione lineare intera EsPL0, EsPL1, EsPL2, EsPL3, EsPLI0, EsPLI1 (file pdf)
3. Esercizi di ottimizzazione su grafo EsGrafi1, EsGrafi2 (file pdf)
4. Lucidi Complessità Computazionale ComplessitàComputazionale

Appelli di Fondamenti di Ricerca Operativa

Appelli	Testi	Esiti
Prima prova in itinere	Testi241106
Seconda prova in itinere	Testi250107
Primo Appello	Testo250107
Secondo Appello	Testo130207	Esiti130207
Terzo Appello	Testo120607	Esiti120607
Quarto Appello	Testo270707	Esiti270707
Quarto Appello	Testo18/09/07	Esiti180907

Testi di precedenti appelli di Fondamenti di Ricerca Operativa e di Ricerca Operativa

RO100204, RO060404, RO010604, RO270704, RO140904, RO171104, RO110105

FRO111104_A, FRO111104_B, FRO111104_C, FRO111104_D

FRO190105, FRO160205,  FRO130405,  FRO150605, FRO090206, FRO050406, FRO140606

Argomenti trattati

1. Aula 305. Lunedì 02/10/06, 13,30-15,30. Introduzione ed esempi di modelli di Programmazione matematica. Notazione.
2. Aula 305. Venerdì 06/10/06, 14,30-16,30. Definizioni di "insieme convesso", "funzione convessa", "ottimizzazione convessa". Proprietà fondamentali. Teorema Minimo locale=minimo globale (con dimostrazione)
3. Aula 305. Lunedì 09/10/06, 13,30-15,30. Esempi di modelli di PL e PLI. Risoluzione grafica di un modello di Mix produttivo.
4. Aula G12. Venerdì 13/10/06, 14,30-16,30. Esempi di modelli di PL e PLI.
5. Aula G22. Lunedì 16/10/06, 13,30-15,30. Esempi di modelli di PL e PLI.
6. Aula G12. Venerdì 20/10/06, 14,30-16,30. Trasformazione in Forma Standard. Soluzione geometrica di un problema di PL in due variabili. Definizione di iperpiano, semispazio, poliedro, politopo e vertice. Teorema Minkowski-Weyl ristretto ai politopi (enunciato). Teorema Esistenza ottimo finito => esistenza vertice ottimo (con dimostrazione).
7. Aula G22. Lunedì 23/10/06, 13,30-15,30. Definizioni di: Base, soluzione di base, soluzione di base ammissibile. Stima del numero delle soluzioni di base. Teorema x soluzione di base ammissibile se e solo se x vertice (con dimostrazione).
8. Aula G12. Venerdì 27/10/06, 14,30-16,30. Corollario Esistenza ottimo finito => esistenza soluzione di base ottima. Teorema Condizioni di ottimalità di una base (con dimostrazione). Schema dell’algoritmo del simplesso. Individuazione di una variabile entrante e di quella uscente. Il cambio di base o operazione di pivot. Condizioni di illimitatezza. Definizione di forma canonica rispetto ad una base.
9. Aula G22. Lunedì 30/10/06, 13,30-15,30. Forma Tableau dell'algoritmo del simplesso. Convergenza e degenerazione: regola di Bland. Esercizi.

Venerdì 03/11/06, 14,30-16,30. Lezione sospesa.

10. Aula G22. Lunedì 06/11/06, 13,30-15,30. Determinazione di una soluzione iniziale: metodo due fasi. Esercizi.
11. Aula G12. Venerdì 10/11/06, 14,30-16,30. Dualità. Lemma di Farkas (con dimostrazione). Relazioni primali duali. Teorema di dualità debole (con dimostrazione). Interpretazione economica della dualità: variabili duali e prezzi ombra.
12. Aula G22. Lunedì 13/11/06, 13,30-15,30. Dualità in termini economici: esempio del problema del trasporto. Teorema di dualità forte. Teorema sulle condizioni di scarto complementare (con dimostrazione). Rivisitazione del tableau in forma canonica.
13. Aula G12. Venerdì 17/11/06, 14,30-16,30. Esercizi in preparazione alla prova in itinere
14. Aula G22. Lunedì 20/11/06, 13,30-15,30. Esercizi in preparazione alla prova in itinere. Analisi di sensitività per via algebrica.
15. Aula G12. Venerdì 24/11/06, 14,30-16,30. Prima prova in itinere.
16. Aula G22. Lunedì 27/11/06, 13,30-15,30. Introduzione alla Programmazione Lineare Intera. Definizione di conv(S). Definizione di rilassamento continuo. Definizioni di matrice Unimodulare (UM) e Matrice Totalmente Unimodulare (TUM). Come riconoscere una matrice TUM. Esercizio per casa: i problemi di Assegnamento e Trasporto.
17. Aula G12. Venerdì 01/12/06, 14,30-16,30. Altre proprietà delle matrici TUM. Metodo dei Piani di Taglio. I tagli di Chvatal. La chiusura di Chvatal. Il rango di Chvatal. I tagli di Gomory.
18. Aula G22. Lunedì 04/12/06, 13,30-15,30. I tagli di Gomory. Il metodo del simplesso duale. Un esempio numerico.
19. Aula G22. Lunedì 11/12/06, 13,30-15,30. I tagli di Gomory. Il metodo del simplesso duale. Il caso di soluzione ammissibile vuota. Introduzione al metodo del Branch & Bound. La fase di branching.

Aula G12. Venerdì 15/12/06, 14,30-16,30. Lezione sospesa.

20. Aula G22. Lunedì 18/12/06, 13,30-15,30. Introduzione al Branch and Bound. Tecniche di "bounding": rilassamento per eliminazione di vincoli, rilassamento continuo, rilassamento lagrangiano, rilassamento surrogato. Relazioni fra i rilassamenti.

Aula G12. Venerdì 22/12/06, 14,30-16,30. Lezione sospesa. Introduzione ai grafi: definizioni come esercizio per casa.

21. Aula G22. Lunedì 08/01/07, 13,30-15,30. Esercizi sulla tecnica di Branch & Bound
22. Aula G12. Venerdì 12/01/07, 14,30-16,30 Problema dell’albero di supporto di costo minimo (Minimum Spanning Tree). Modello di PLI per il MST. Teorema che caratterizza i lati appartenenti ad alberi di costo minimo. Algoritmo di Prim-Dijkstra: versione O(n²). Esercizio.
23. Aula G22. Lunedì 15/01/07, 13,30-15,30. MST: Algoritmo di Kruskal. Il problema dei cammini minimi su grafo orientato. Formulazione matematica. Teorema che caratterizza gli archi appartenenti a cammini di costo minimo. Algoritmo di Dijkstra. Esercizio.
24. Aula G12. Venerdì 19/01/07, 14,30-16,30 Il problema del flusso massimo in una rete. Formulazione matematica. Algoritmo di Ford-Fulkerson. Esercizio.
25. Aula G22. Lunedì 22/01/07, 13,30-15,30.Esercizi di preparazione al secondo compitino.

Giovedì 25/01/07 Secondo compitino aula G24 via Golgi 19 ore 10,30. Argomenti: Programmazione Lineare a Numeri Interi e Ottimizzazione su Grafo.

---

Complementi di Ricerca Operativa
Ore di didattica: 48	Crediti: 6	Semestre: 2°
Modalità d’esame: progetto (per i frequentanti), prova orale

Obiettivi del corso:

Il corso si propone di ampliare i fondamenti della programmazione matematica introdotti nel corso di Fondamenti di Ricerca Operativa. In primo luogo vengono introdotte le principali tecniche disponibili per affrontare modelli di programmazione non lineare. Vengono successivamente illustrate tecniche avanzate per la soluzione di problemi di programmazione lineare di grandi dimensioni: tecniche di decomposizione e tecniche di generazione di colonne (column generation). Vengono illustrati esempi di applicazione del metodo dei piani di taglio (cutting plane) e vengono descritti gli algoritmi esatti basati su tali tecniche: Branch & Price e Branch & Cut. Viene descritta e illustrata con esempi la principale tecnica per il calcolo dei valori ottimi dei moltiplicatori duali Lagrangiani (tecnica del sottogradiente). Infine vengono illustrati alcuni ambiti di applicazione della Ricerca Operativa: problemi di localizzazione e problemi di instradamento (Vehicle routing).

1. Programmazione Non Lineare

Elementi di teoria dell'ottimizzazione non vincolata: condizioni del primo e secondo ordine. Elementi di teoria dell'ottimizzazione vincolata condizioni del primo e secondo ordine. Algoritmi per problemi di ottimizzazione non vincolata in una sola variabile ed in più variabili. Algoritmi per problemi di ottimizzazione vincolata.

2. Tecniche avanzate di programmazione lineare a numeri interi

Branch & Price e Branch & Cut.

3. Un linguaggio di modellizzazione: AMPL

4. Problemi di localizzazione

Introduzione. Il problema p-median. Il problema p-center. Set covering. Altri modelli di localizzazione.

5. Problemi di instradamento

Introduzione. Tipologie di Trasporto. Vehicle Routing e Vehicle Routing con finestre temporali. Modelli di programmazione matematica. Metodi euristici ed esatti. Problemi di arc routing.

Bibliografia di riferimento:

R.Tadei, F. Della Croce, Ricerca Operativa e ottimizzazione, Progetto Leonardo, II edizione 2002.

Prerequisiti:

E' fortemente consigliato aver seguito il corso di Fondamenti di Ricerca Operativa.

Argomenti trattati

01) Mar. 06/03/07 Introduzione alla programmazione non lineare, PNL. Definizione di problema di ottimizzazione non lineare. Ottimizzazione non vincolata. Esempi: la PL, PLI, PL binaria come casi particolari di PNL. Richiami di analisi. Definizioni: minimo globale, minimo locale, punto di sella. Proprietà di esistenza di punti di minimo per funzioni continue su insiemi chiusi e limitati e per funzioni “radialmente illimitate” (che tendono a +inf comunque ci si allontani dall’origine). Derivata direzionale, vettore gradiente, matrice Hessiana, sviluppo in serie di Taylor in Rⁿ arrestato al I o II ordine. Derivata direzionale = Grad_f(x)^Td. Esempio numerico.

02) Ven. 09/03/07 Definizione di matrice (semi)definita positiva. Proprietà: legame fra (semi)definita positività, determinanti dei minori principali e autovalori. Convessità: insieme convesso, funzione convessa. Proprietà: in ott. convessa min loc = min glob. Proprietà di ins. conv. e funz. conv. Proprietà: quando un problema di ottimizzazione non lineare è convesso. Proprietà: f di classe C¹(S) è convessa in S sse f(y)-f(x)³ Grad_f(x)^T(y-x) per ogni x,y appartenente ad S. Proprietà: legame fra (semi)definita positività della matrice Hessiana e convessità di f(). Definizione di direzione di discesa. Proprietà: legame fra derivata direzionale e direzione di discesa.

03) Mar. 13/03/07 Condizioni necessarie di ottimalità del primo e del secondo ordine. Condizioni sufficienti di ottimalità del secondo ordine. Condizioni necessarie e sufficienti di ottimalità per funzioni convesse. I punti si minimo di funzioni convesse definiscono un insieme convesso. Quando posso dire qualcosa sull’ottimo globale: le funzioni Lipschitziane. La programmazione quadratica: variazioni sul tema “Q”.

04) Ven. 16/03/07 Schema generale degli algoritmi di discesa. Definizione di convergenza globale e locale di un algoritmo. Definizione di rapidità di convergenza sublineare, lineare, superlineare, quadratica, di ordine p. Esercizio su rapidità di convergenza sublineare, lineare, superlineare, quadratica. Criteri di convergenza empirici. Condizioni sul passo a. Condizioni di Wolfe-Powell, (CWP). Proprietà: le CWP possono venir soddisfatte da funzioni di classe C¹ non inferiormente illimitate lungo la direzione di discesa d_k. Determinazione del passo a.

05) Mar. 20/03/07 Determinazione del passo a. Ricerca esatta, metodo di Armijo, interpolazione quadratica e cubica. Metodo della sezione aurea, metodo di bisezione. Esercizi.

06) Ven. 23/03/07 Condizioni sulla direzione d_k. Condizione d’angolo (CA). Proprietà: convergenza globale di algoritmi di discesa per funzioni di classe C¹ se sono soddisfatte CWP e CA. Metodo del gradiente. Metodo del gradiente applicato ai problemi quadratici: dipendenza dal valore degli autovalori di Q. Proprietà di convergenza lineare: teorema di Kantorovich. Introduzione al metodo di Newton.

07) Mar. 27/03/07 Teorema di convergenza locale e quadratica per H(x) lipschitziana. Limiti del metodo di Newton. Metodo di Newton modificato. Approssimazione di H(x) alle differenze finite. Metodi quasi-Newton. Approssimiamo H^-1.

08) Ven. 30/03/07 Metodi quasi-Newton. Formula di aggiornamento di rango uno. Formula di aggiornamento di rango due. Metodo Davidon-Fletcher-Powell (DFP). Proprietà del metodo DFP. Metodo inverso: approssimiamo H. Metodo Broyden-Fletcher-Goldfarb-Shanno (BFGS). Famiglia di Broyden.

09) Mar. 03/04/07 Metodi alle direzioni coniugate per funzioni quadratiche. Metodi di gradiente coniugato. Metodo Fletcher-Reeves e metodo Polak-Ribiere. Introduzione alla ottimizzazione vincolata. Condizioni analitiche necessarie per problemi con vincoli di uguaglianza.

10) Ven. 13/04/07 Esempio di problema con vincoli di uguaglianza. Programmazione quadratica con vincoli di uguaglianza lineari.Vincoli di disuguaglianza come vincoli di uguaglianza. Vincoli di disuguaglianza: condizioni di Karush-Kuhn-Tucker. Qualificazione dei vincoli.

11) Mar. 17/04/07 KKT: esempio numerico. Teoria del punto di sella. Teoremi di dualità. Programmazione quadratica con vincoli di disuguaglianza lineari, cenni. Metodi iterativi. Metodi con funzione di penalità e metodi a barriera.

12) Ven. 20/04/07 Laboratorio. Introduzione al linguaggio Ampl.

13) Mar. 24/04/07 Metodi iterativi. Metodo del gradiente proiettivo nel caso di vincoli di uguaglianza lineari e cenni per il caso di vincoli di uguaglianza qualsiasi. Metodo dei lagrangiani aumentati nel caso di vincoli di uguaglianza qualsiasi. Cenni sul Sequential Quadratic Programmino (SQP).

14) Ven. 27/04/07 Laboratorio. Il linguaggio Ampl.

15) Ven. 04/05/07 Laboratorio. Il linguaggio Ampl.

16) Mar. 08/05/07 Rilassamento lagrangiano. Concavità e non differenziabilità della funzione obiettivo duale. Esempio: il problema Knapsack. Introduzione alla tecnica del sottogradiente.

17) Ven. 11/05/07 Laboratorio. Calcolo dei moltiplicatori lagrangiani ottimi mediante tecnica di sottogradiente. Utilizzo degli script in AMPL (file .run) per implementare un algoritmo di sottogradiente per la determinazione del rilassamento lagrangiano ottimo di un problema di trasporto e localizzazione.

Mar. 15/05/07 Sospesa a causa dello sciopero dei mezzi ATM.

18) Ven. 18/05/07 Laboratorio. Applicazione della tecnica di sottogradiente per il calcolo del rilassamento lagrangiano di un problema di tipo MKP01.

19) Mar. 22/05/07 Definizione e proprietà del sottogradiente. Esistenza del sottogradiente per funzioni concave. Il sottogradiente come direzione di avvicinamento a l*. Introduzione alla tecnica di column generation.

20) Ven. 25/05/07 Laboratorio. Applicazione della tecnica di column generation al problema Cutting Stock: risoluzione del problema di pricing per l’individuazione di una colonna con coefficiente di costo ridotto negativo mediante la soluzione di un problema di Knapsack Intero.

21) Mar. 29/05/07 Ancora sulla tecnica di column generation. Esercizi di modellizzazione. Un buon articolo introduttivo alla tecnica: primer.pdf.

22) Ven. 01/06/07 Laboratorio. Esercizi di modellizzazione e soluzione di problemi di PNL.

23) Mer. 06/06/07 Introduzione al metodo dei piani di taglio e alla tecnica di Branch & Cut. Esempio problema di knapsack: le Cover inequalities con l’oracolo di separazione. Esempio del TSP: risoluzione del problema di separazione per l’individuazione di vincoli di eliminazione di sottocicli violati mediante la soluzione di un problema di Max Flow-Min Cut su un grafo opportuno. Le Comb inequalities.

24) Ven. 08/06/07 Laboratorio. Esercizi di modellizzazione e soluzione di problemi di PLI. Conclusione corso. File Ampl per cover inequalities MKP01.zip . Proposte progetti ma potete integrarlo… Proposte.pdf

---

Simulazione
Ore di didattica: 48	Crediti: 6	Semestre: 1°
Modalita’ d’esame: prova orale, progetto

Obiettivi del corso:

L’insegnamento si propone lo scopo di rendere lo studente familiare con la teoria e le tecniche fondamentali che permettono di studiare un sistema complesso analizzando un sistema equivalente ma simulato attraverso un calcolatore.

Parallelamente, dopo aver brevemente accennato ai risultati più significativi della teoria delle code, verranno analizzati alcuni strumenti software per la simulazione a flusso di entità, per la simulazione nel continuo.

Programma del corso:

Modulo A [Prof. Dario Malchiodi]: Teoria e tecniche

• Introduzione alle problematiche di simulazione
• Prerequisiti di matematica, probabilità e statistica
• Simulazione di variabili aleatorie discrete e continue
• Simulazione di sistemi a eventi discreti
• Analisi di dati provenienti da sistemi simulati
• Validazione di sistemi simulati tramite tecniche statistiche

Modulo B [Prof. M. Trubian]: Cenni di teoria delle code e strumenti SW

• Cenni di teoria delle code, simulazione di reti di code
• Quando la teoria non ci aiuta: quale tool per quale tipo di simulazione
• Tool di Simulazione a flusso di entità
• Tool di Simulazione nel continuo

Metodi didattici:

La didattica sarà esercitata principalmente in forma frontale, rimandando gli studenti a una serie di approfondimenti individuali e di gruppo in laboratorio.

Materiale bibliografico di riferimento:

Il modulo A è basato principalmente sulla monografia

Ross, S. M., Simulation, Second edition, San Diego: Academic Press, Statistical Modeling and Decision Science, 1997

e prevede alcuni approfondimenti tratti da

Ripley, B. D., Stochastic Simulation, New York: John Wiley & Sons, Wiley Series in Probability and Mathematical Statistics, 1987

Il modulo B si basa sul capitolo 15 del testo

Hillier, F. S. and Lieberman, G. J., Introduction to Operations Research (6th Ed), 1995.

per quanto attiene alla teoria delle code e sui manuali online dei pacchetti SW presentati

---

Algoritmi e Strutture Dati II mod. 1
Ore di didattica: 48	Crediti: 6	Semestre: 2°
Modalita’ d’esame: progetto (per i frequentanti), Prova orale

Obiettivi del corso:

Fornire i principi di analisi e progetto di algoritmi (deterministici e randomizzati) per la soluzione di problemi su vari modelli di calcolo.

Programma del corso:

Strutture dati avanzate: Heap Binomiali, Heap di Fibonacci, Alberi randomizzati di ricerca (treap). Algoritmi paralleli su PRAM. Algoritmi per reti a grado limitato. Algoritmi concorrenti. Algoritmi distribuiti: topologie, algoritmi per la mutua esclusione e elezione di leader. Algoritmi non deterministici. Algoritmi di enumerazione implicita: B&B, Algoritmi probabilistici. Classi di complessità P, NP, co-NP, PSPACE, LOGSPACE, RP, RpP, NC.

Bibliografia di riferimento:

A. Bertossi, Algoritmi e strutture di dati, UTET, 2000.

T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduzione agli algoritmi, Jackson Libri, II edizione italiana 1999.

Bibliografia consigliata:

A. Bertoni, Algoritmi II (dispense)

Prerequisiti:

Analisi e sintesi di algoritmi sequenziali

Argomenti trattati

05 marzo Lunedì	1	Strutture dati avanzate: Heap Binomiali.	Lez01.pdf
08 marzo Giovedì	2	Strutture dati avanzate: Heap di Fibonacci e Treap.	Lez02.pdf Lez02bis.pdf
12 marzo Lunedì	3	Introduzione agli Algoritmi per Architetture Parallele (AAP). Classificazione SISD,SIMD,MISD,MIMD,Modello PRAM, simulazioni CR con ER e CW con EW, reti di interconnessione (RI): mesh, vettore, ipercubo, albero, shuffle. Algoritmi di broadcast per RI. Def. speedup, efficienza e lavoro. Algoritmi per ricerca, trasposta, prodotto matriciale su PRAM. AAP. Calcolo prodotto matrici su Mesh.	Lez03.pdf
15 marzo Giovedì	4	Circuiti combinatori. Confrontatori, reti di ordinamento, principio 0-1. Rete di ordinamento bitonico. Teoremi di Brent. Algoritmi su PRAM EREW: sommatoria. Tecnica per ottenere lavoro ottimo. Sommeprefisse.	Lez04.pdf
19 marzo Lunedì	5	Valutazione di polinomi. Tecnica del salto dei puntatori: calcolo del rango, sommeprefisse. Tecnica del ciclo euleriano: un algoritmo che numera i nodi e uno che calcola la profondità di un albero binario. Reti di interconnessione: ordinamento su vettore: due algoritmi.	Lez05.pdf
22 marzo Giovedì	6	Sommatoria e massimo su Mesh. Sommatoria e massimo su ipercubo.Sommatoria su shuffle. Introduzione agli Algoritmi Concorrenti (AC): modelli asincroni con memoria condivisa. Calcolo del massimo.AC. Calcolo dei cammini minimi (versione Pape-D'Esopo). Quicksort concorrente.	Lez06.pdf
26 marzo Lunedì	7	Introduzione agli Algoritmi Distribuiti (AD): modelli asincroni senza memoria condivisa. Architetture di rete per AD. Tecniche e algoritmi per ottenere la sincronizzazione (Clock logico globale), per garantire la mutua esclusione (non esistono primitive quali lock e unlock), per individuare un processore privilegiato (Elezione del leader).	Lez07.pdf
29 marzo Giovedì	8	Introduzione al Non Determinismo (ND). Alberi di decisione. Introduzione agli algoritmi casualizzati (AR). Es. algoritmo di Rabin per il test di primalità.	Lez08.pdf Lez08bis.pdf
02 aprile Lunedì	9	Es. commutatività di matrici. Es. Matching Perfetto, teoremi di Tutte e di Schwartz. Introduzione alla complessità computazionale. Problema, istanza, dimensione, codifica, modello di calcolo, criterio di costo. Le classi P ed NP.	Lez09.pdf Lez09bis.pdf Lez09-10-11cc.pdf
12 aprile Giovedì	10	Algoritmi probabilistici con errori ai due lati. Complessità computazionale. Le classi NP e co-NP. Riduzioni.
16 aprile Lunedì	11	Complessità computazionale. Ancora riduzioni. Complessità computazionale per algoritmi casualizzati. Complessità computazionale per algoritmi paralleli.
19 aprile Giovedì	12	Ancora sugli algoritmi casualizzati (AR). Es. Matching Perfetto di valore esatto. FFT: algoritmo per il calcolo della DFT.	Lez12.pdf

---

Algoritmi e Strutture Dati II mod 2
Ore di didattica: 48	Crediti: 6	Semestre: 2°
Modalita’ d’esame: progetto (per i frequentanti), Prova orale

Obiettivi del corso:

Fornire i principi di analisi e progetto di algoritmi (deterministici e randomizzati) per la soluzione di problemi su vari modelli di calcolo.

Programma del corso:

Algoritmi di ottimizzazione: algoritmi approssimati. Ottimizzazione locale e globale. Tecniche di ottimizzazione locale sul continuo. Ricerca locale e varianti. Meta-euristiche: Tabu Search, Algoritmi genetici, Ants System, Variable Neighbourhood Search. Ottimizzazione stocastica, algoritmo di Metropolis e Annealing simulato. Reti neurali di Hopfield, macchine di Boltzmann.

Bibliografia di riferimento:

R.Tadei, F. Della Croce, Ricerca Operativa e ottimizzazione, Progetto Leonardo, II edizione 2002.

Bibliografia consigliata

A. Bertossi, Algoritmi e strutture di dati, UTET, 2000.

T.H. Cormen, C.E. Leiserson, R.L. Rivest, Introduzione agli algoritmi, Jackson Libri, II edizione italiana 1999.

A. Bertoni, Algoritmi II, dispense

M.Mitchell, An Introduction to Genetic Algorithms, MIT, 1996.

E.Aarts, J.Korst, Simulated Annealing and Boltzmann Machines, John Whiley and Sons, 1989.

Prerequisiti:

Analisi e sintesi di algoritmi sequenziali

Argomenti trattati

23 aprile Lunedì	01	Simulazione ND con enumerazione esplicita ed implicita. Es. clique e TSP. Introduzione alla tecnica del Branch and Bound (B&B) per problemi di Ottimizzazione Combinatoria (OC). Tecniche per il calcolo della stime per difetto e per eccesso.	Lez01.pdf
26 aprile Giovedì	02	Esempio di B&B applicato al problema TSP. Introduzione agli Algoritmi approssimati. Es. Zaino intero e Macchine parallele.	Lez02.pdf Lez02-03-04.pdf
03 maggio Giovedì	03	Gli algoritmi approssimati. Es. TSP. Es. Vertex Cover. Tecnica di derandomizzazione applicata al problema MaxSat, primo esempio.
07 maggio Lunedì	04	Gli algoritmi approssimati. Tecnica di derandomizzazione applicata al problema MaxSat, secondo esempio. Introduzione alla ricerca locale. Definizione di intorno. Esempi.	Lez04.pdf
10 maggio Giovedì	05	VLNS. Esempi. Introduzione all’algoritmo di Metropolis e all’Annealing simulato.	Lez0506.pdf
14 maggio Lunedì	06	L’Annealing simulato. Esempi di problemi di ottimizzazione combinatoria da scegliere per l’elaborato finale dal sito: http://www2.informs.org/Resources/Resources/Problem_Instances/
17 maggio Giovedì	07	Le meta-euristica Grasp e Ants System. Altri esempi di problemi di ottimizzazione combinatoria da scegliere per l’elaborato finale dal sito: http://www.nada.kth.se/~viggo/problemlist/	Lez07.pdf
21 maggio Lunedì	08	Gli Algoritmi Genetici	Lez08.pdf
24 maggio Giovedì	09	Introduzione alle Reti Neurali Artificiali	Lez0910.pdf
28 maggio Lunedì	10	Reti Neurali Artificiali, Reti di Hopfield e Tank, Macchine di Boltzmann, Mean Field Annealing, Reti elastiche
31 maggio Giovedì	11	Analisi progetti studenti	Guida DJ.pdf
04 giugno Lunedì	12	Analisi progetti studenti

---