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

mercoledì 16 febbraio 2005

mercoledì 13 aprile 2005

mercoledì 15 giugno 2005     

mercoledì 27 luglio 2005 

mercoledì 14 settembre 2005

venerdì 13 gennaio 2006  

AVVISO

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

Successivamente devono cortesemente inviarmi una email per informarmi che non intendono svolgere lo scritto (ma solo verbalizzare).

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 V6 via Venezian

Mercoledì 14,30 - 16,30 Giovedì 14,30 - 16,30

Complementi di Ricerca Operativa

Aula 6 via Comelico

Martedì 17,30 - 19,30 Giovedì 17,30 - 19,30

Algoritmi e Strutture Dati II mod A

Aula a via Comelico

Martedì 11,30 - 14,30 Venerdì 16,30 - 19,30

Algoritmi e Strutture Dati II mod B

Aula a via Comelico

Martedì 11,30 - 14,30 Venerdì 16,30 - 19,30

Programma dei corsi per l'a.a. 2004/05 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.

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

(Contiene i lucidi del corso)

Bibliografia consigliata:

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: 11 novembre 2004

FRO_A, FRO_B, FRO_C, FRO_D

 

Seconda prova in itinere  mercoledì 19 gennaio 2005

 FRO

 

Primo appello: 16/02/05

FRO

 

Secondo appello: 13/04/2005

 FRO

 

Terzo appello: 15/06/2005

 FRO

 

Quarto appello: 27/07/2005

 

 

Quinto appello:14/09/2005

 

 

Testo precedenti appelli di Ricerca Operativa

10 febbraio 2004

RO

06 aprile 2004

RO

martedì 01 giugno 2004     

RO

martedì 27 luglio 2004 

RO

martedì 14 settembre 2004

RO

mercoledì 17 novembre 2004

RO

martedì 11 gennaio 2005  

 RO

Argomenti trattati

  1. Lezione mercoledì 29/09/04 Introduzione ed esempi di modelli di Programmazione matematica. Notazione. Definizioni di "insieme convesso", "funzione convessa", "ottimizzazione convessa". Proprietà fondamentali.
  2. Lezione  mercoledì 06/10/04 Esempi di modelli di Programmazione Lineare (PL) e Programmazione Lineare Intera (PLI)
  3. Lezione  giovedì 07/10/04 Esempi di modelli di Programmazione Lineare (PL) e Programmazione Lineare Intera (PLI)
  4. Lezione  mercoledì 13/10/04 PL: Trasformazione da Forma Generale a Forma Standard. Soluzione geometrica di un problema di PL in due variabili. Def. di iperpiano, semispazio, poliedro, politopo e vertice. Teorema Minkowski-Weyl (enunciato) Teorema esistenza ottimo finito => esistenza vertice ottimo (con dimostrazione).
  5. Lezione  giovedì 14/10/04 Definizione di Base. Definizione forma canonica rispetto ad una base. Relazione fra vertici dei poliedri e soluzioni di base. Schema algoritmo del simplesso. Teorema Condizioni di ottimalità nella PL (con dimostrazione).
  6. Lezione  mercoledì 20/10/04 Esercizio di soluzione per via geometrica. Esercizio sulla forma canonica rispetto ad una base: individuazione di una variabile entrante e di quella uscente. Condizioni di illimitatezza. Algoritmo del simplesso.
  7. Lezione  giovedì 21/10/04 Esercizio sulla forma canonica rispetto ad una base: il cambio di base. Forma Tableau dell'algoritmo del simplesso. Determinazione di una soluzione iniziale. Esempi.
  8. Lezione  mercoledì 27/10/04 Algoritmo del simplesso: convergenza e degenerazione. Esercizi.
  9. Lezione  giovedì 28/10/04 Dualità. Lemma di Farkas (con dimostrazione). Relazioni primali duali. Interpretazione economica della dualità: il problema del trasporto.
  10. Lezione  mercoledì 03/11/04 Teoremi di dualità debole e dualità forte (con dimostrazione). Corollario. Esercizi.
  11. Lezione  giovedì 04/11/04 Teorema sulle condizioni di scarto complementare. Esempi. Analisi di sensitività: variazione dei termini noti e dei coefficienti di costo. Analisi per via geometrica e per via algebrica. Nuova lettura dell'algoritmo del simplesso. Algoritmo del simplesso duale. Inserimento di nuovi vincoli.
  12. Lezione  mercoledì 10/11/04 Esercizi di preparazione al primo compitino.

Lezione  giovedì 11/11/04 Sospensione per protesta contro DDL Moratti sul riordino dello stato giuridico del personale docente universitario.

  1. Lezione  martedì 16/11/04 Recupero lezione sospesa. Esercizi di preparazione al primo compitino.
  2. Lezione  mercoledì 17/11/04 Primo compitino.
  3. Lezione  giovedì 18/11/04 Programmazione Lineare Intera. Considerazioni introduttive. Rilassamento continuo. Definizioni di matrice Unimodulare e Matrice Totalmente Unimodulare. Un esempio: il problema di Assegnamento. Metodo dei Piani di Taglio. I tagli di Gomory. Un esempio numerico.
  4. Lezione  mercoledì 24/11/04 Metodo del Branch & Bound. Tecniche di "bounding": rilassamento per eliminazione di vincoli, rilassamento continuo, rilassamento lagrangiano.
  5. Lezione  giovedì 25/11/04 Tecniche di "bounding": rilassamento surrogato e lagrangiano surrogato. Strategie di esplorazione dell'albero di branching. Esempio di B&B per la PLI.

Lezione  mercoledì 01/12/04 Sospensione per concomitante sciopero dei mezzi di trasporto pubblico.

  1. Lezione  giovedì 02/12/04 Esempio di B&B per il problema dello zaino. Esercizi.
  2. Lezione  giovedì 09/12/04 Esercizi.
  3. Lezione  mercoledì 15/12/04 Introduzione ai grafi: definizioni e notazione. Rappresentazione di grafi con matrici e liste. Il problema dell'albero di costo minimo in un grafo non orientato. Formulazione matematica.
  4. Lezione  giovedì 16/12/04 Teorema 2. (che caratterizza i lati appartenenti ad alberi di costo minimo). Algoritmo di Prim-Dijkstra: versione O(nm) e versione O(n2). Algoritmo di Kruskal: versione O(m log m + n). Il problema dei cammini minimi su grafo orientato. Formulazione matematica.
  5. Lezione  mercoledì 22/12/04 Algoritmo di Dijkstra. Algoritmo di Floyd-Warshall. Algoritmo (non polinomiale) per grafi con archi negativi ma privo di circuiti di lunghezza negativa. Il problema del flusso massimo in una rete. Formulazione matematica.
  6. Lezione  mercoledì 12/01/05 Algoritmo di Ford-Fulkerson per il problema del flusso massimo in una rete. Formulazione matematica del problema di instradare a costo minimo in una rete un flusso dato. Esercizi.
  7. Lezione  giovedì 13/01/05 Esercizi di preparazione al secondo compitino.
  8. Lezione  mercoledì 19/01/05 Secondo compitino. Ore 14,30. Aula G.2.1 in via Golgi 19.
  9. Lezione  giovedì 21/01/05 Cenni di Complessità Computazionale. EXIT.

Complementi di Ricerca Operativa

Ore di didattica: 48

Crediti: 6

Semestre: 2°

Modalita’ d’esame: progetto (per i frequentanti), prova orale

Obiettivi del corso:

In primo luogo il corso si propone di ampliare i fondamenti della programmazione matematica introdotti nel corso di Fondamenti di Ricerca Operativa, con particolare attenzione ai modelli di programmazione non lineare. In secondo luogo vengono illustrati tre importanti ambiti di applicazione della Ricerca Operativa: i problemi di localizzazione, i problemi di schedulazione ed i 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. Problemi di localizzazione

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

3. Problemi di schedulazione

Introduzione. Notazione e classificazione. Misure di prestazione. Problemi su macchina singola. Macchine parallele. Flow shop e Job shop.

4. 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' consigliabile aver seguito il corso di Fondamenti di Ricerca Operativa.

Algoritmi e Strutture Dati II mod A

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

  1. Lezione martedì 01/03/05 Introduzione al corso. Gli Heap Binomiali (Lucidi01)
  2. Lezione  venerdì 04/03/05 Gli Heap di Fibonacci e gli Alberi randomizzati di ricerca (treap) (Lucidi02, Lucidi02bis)
  3. Lezione  martedì 08/03/05 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. (Lucidi03)
  4. Lezione  venerdì 11/03/05 AAP. Circuiti combinatori. Confrontatori, reti di ordinamento, principio 0-1. Rete di ordinamento bitonico. Teoremi di Brent. Algoritmi su PRAM EREW: sommatoria, sommeprefisse, ordinamento (Lucidi04)
  5. Lezione  martedì 15/03/05 AAP. Algoritmi su PRAM EREW: valutazione di polinomi. Salto dei puntatori: calcolo del rango, sommeprefisse. Ciclo euleriano: un algoritmo che numera i nodi e uno che calcola profondità. Ordinamento su vettore. Sommatoria e massimo su Mesh. Sommatoria e massimo su ipercubo. (Lucidi05)
  6. Lezione  venerdì 18/03/05 AAP. Sommatoria su shuffle. Introduzione agli Algoritmi Concorrenti (AC). Quicksort concorrente, calcolo dei cammini minimi (versione Pape-D'Esopo) con algoritmo concorrente. Introduzione agli Algoritmi Distribuiti (AD). Architetture di rete per AD. (Lucidi06)
  7. Lezione  martedì 22/03/05 AD. Clock logico globale, mutua esclusione, elezione del leader. Non Determinismo (ND). Alberi di decisione. (Lucidi07)
  8. Lezione  martedì 05/04/05 Simulazione ND con enumerazione esplicita ed implicita. Introduzione alla tecnica del Branch and Bound. (Lucidi08)
  9. Lezione  venerdì 08/04/05 Rilassamenti. Esempio di B&B applicato al problema TSP. Introduzione agli algoritmi casualizzati (AP). Es. algoritmo di Rabin per il test di primalità (Lucidi09)
  10. Lezione  martedì 12/04/05 Gli algoritmi casualizzati. Es. commutatività di matrici (Lucidi10). Introduzione alla complessità computazionale.
  11. Lezione  venerdì 15/04/05 Introduzione alla complessità computazionale (Lucidi10e11).

Algoritmi e Strutture Dati II mod B

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

  1. Lezione martedì 26/04/05 Gli algoritmi casualizzati (AP). Es. Matching Perfetto. Algoritmi approssimati (AA). Es. Zaino intero
  2. Lezione venerdì 29/04/05 AP. Es. Matching Perfetto di valore esatto. AA. Es. Scheduling
  3. Lezione martedì 03/05/05 Valutare e interpolare polinomi: la trasformata discreta di fourier (DFT) e la Fast Fourier Transform (FFT) AP. Matching Perfetto di valore esatto con FFT. AA. Es. TSP e Vertex Cover. (Lucidi12e13).
  4. Lezione venerdì 06/05/05 AA. Es. Vertex Cover. Da algoritmi casualizzati ad algoritmi approssimati mediante derandomizzazione. Tecnica delle probabilità condizionate. Arrotondamento LP. Es. MAX-SAT. Classi NPO, APX, PTAS. (Lucidi14e15)
  5. Lezione martedì 10/05/05 Algoritmi di Ricerca Locale. (Lucidi16)
  6. Lezione venerdì 13/05/05 Meta euristica Simulated Annealing (SA). (Lucidi17)
  7. Lezione martedì 17/05/05 Meta euristiche Grasp e Ants System. (Lucidi18)
  8. Lezione martedì 24/05/05 Meta euristica Algoritmi genetici. (Lucidi19)
  9. Lezione venerdì 27/05/05 Algoritmi genetici e introduzione alle Reti Neurali
  10. Lezione martedì 07/06/05 Reti Neurali, reti di Hopfield, Macchine di Boltzman, Tabu Search. (Lucidi2021)