Presentazione

Organizzazione della Didattica

DM270
INFORMATICA ORD. 2011


6

Corsi comuni

 

Frontali Esercizi Laboratorio Studio Individuale
ORE: 28 12 12 85

Periodo

AnnoPeriodo
III anno1 semestre

Frequenza

Facoltativa

Erogazione

Convenzionale

Lingua

Italiano

Calendario Attività Didattiche

InizioFine
01/10/201523/01/2016

Tipologia

TipologiaAmbitoSSDCFU
affine/integrativo Nessun ambitoMAT/096


Responsabile Insegnamento

ResponsabileSSDStruttura
Dott. DE GIOVANNI LUIGIMAT/09Dipartimento di Matematica

Altri Docenti

DocenteCoperturaSSDStruttura
Prof. RINALDI FRANCESCOAffidamentoMAT/09Dipartimento di Matematica

Attività di Supporto alla Didattica

Non previste.

Bollettino

Conoscenze di base di analisi matematica e algebra. E' propedeutico l'insegnamento di Algebra e Matematica Discreta.

Costruzione di modelli matematici per il supporto alle decisioni e relativi algoritmi, con particolare riferimento alla programmazione lineare nel continuo e nel discreto e all'ottimizzazione su grafi. Uso di pacchetti software per la soluzione di problemi di ottimizzazione.

L'insegnamento prevede lezioni frontali ed esercitazioni in laboratorio. Le esercitazioni in laboratorio consistono nell'implementazione in un linguaggio di modellazione algebrica di semplici modelli di programmazione lineare (mista intera).

1. Problemi di ottimizzazione e modelli: modellazione e utilizzo di risolutori software in laboratorio. 2. Programmazione lineare: teoria e metodo del simplesso, teoria della dualità e applicazioni. 3. Ottimizzazione su grafi: modelli e algoritmi per il problema dell'albero di copertura di costo minimo, il problema del cammino minimo (algortimi di Dijkstra e Bellman-Ford), il problema del flusso massimo (algoritmo di Ford-Fulkerson) e del flusso di costo minimo. 4. Elementi di Programmazione Lineare Intera e Ottimizzazione Combinatoria: metodi esatti (Branch-and-Bound), cenni su metodi euristici e metaeuristici (ricerca locale e varianti).

Scritto, con eventuali orale e/o discussione di un mini-progetto.

L'esame scritto richiede lo svolgimento di esercizi per la valutazione del livello di apprendimento degli argomenti svolti (ad esempio, modellazione di un problema di ottimizzazione in programmazione lineare intera, applicazione dell'algoritmo del simplesso, applicazione di algoritmi di ottimizzazioni su rete, applicazione della teoria della dualità, applicazione dell'algoritmo del Branch-and-Bound, domande sui diversi argomenti svolti etc.)

CONTENUTO NON PRESENTE

Vengono rese disponibili delle dispense degli argomenti trattati a lezione e dei lucidi degli argomenti trattati in laboratorio, che contengono tutte le nozioni richieste all'esame. Gli studenti interessati possono approfondire gli argomenti sui seguenti testi: - M. Fischetti, Lezioni di Ricerca Operativa, 1999, Libreria Progetto Padova. - D. Bertsimas, J. Tsitsiklis, Introduction to linear optimization, 1996, Athena Scientific. - R. K.Ahuja, T. L. Magnanti, J. B. Orlin "Network flows. Theory, algorithms, and applications", 1993, Prentice Hall. - L. A. Wolsey: "Integer programming", 1998, Wiley.