Page begin -
Logo DISCO
|
Go to the Highly accessible area
|
Go to the Content page
|
Go to the End of content
|
Go to the Main menu
|
Go to the Navigation Bar (location)
|
Go to the Navigation menu (tree)
|
Go to the Commands list
|
Go to the Further readings
|
Go to the Bottom Menu
|
Logo Ateneo
   
Education
Algoritmi e ricerca operativa

Docente: P. Bonizzoni, A. Leporati, G. Lulli, G. Mauri, E. Messina, A. Dennunzio

Crediti: 4 + 4 + 4

Obiettivi dell'insegnamento:

L'insegnamento intende introdurre le principali tecniche algoritmiche (programmazione dinamica, greedy) e gli strumenti di base della ricerca operativa; gli studenti acquisiranno la capacità di formulare modelli di programmazione matematica per la pianificazione e la gestione delle risorse, e di applicare le più idonee tecniche algoritmiche per la loro analisi e soluzione. 

Algoritmi e strutture dati 2 (4CFU)

  • Programmazione dinamica

Esempi introduttivi
Caratteristiche principali
Implementazione con matrici 

  • Algoritmi su grafi


Rappresentazione in memoria di un grafo.
Visita in ampiezza e in profondità di un grafo.
Ricerca delle componenti connesse di un grafo non orientato.
Ricerca delle componenti (fortemente) connesse in un grafo orientato

Ricerca operativa 1 (4 CFU)

Formulazione di modelli di programmazione matematicaProgrammazione Lineare (PL): interpretazione geometrica

  • Metodi Risolutivi della Programmazione Lineare: Algoritmo del Simplesso, e Metodo delle due fasi
  • Dualità e Analisi di Sensitività nella Programmazione Lineare
  • Programmazione Lineare Intera e Metodo Branch & Bound
  • Teoria delle decisioni e alberi decisionali
  • PNL non vincolata: metodo del gradiente, metodo di newton
  • PNL vincolata: condizioni di ottimalità di KKT

Laboratorio di Algoritmi e Ricerca Operativa (4 CFU):

  • Soluzione con greedy, PD e PL di problemi di ottimizzazione su grafi:

    - cammini minimi
    - problemi di flusso
    - albero di copertura
    - formulazione e soluzione problemi in PL, PLI e PNL 

Testi consigliati:

  • Introduzione agli algoritmi e strutture dati (II ediz. McGraw-Hill) autori: T. H. Cormen, C. E. Leinserson, R. L. Rivest, C. Stein
  • Ricerca Operativa (VIII ediz. McGraw-Hill) autori: Frederick S. Hillier, Gerald J. Lieberman

 

 

Further readings
(C) Copyright 2016 - Dipartimento Informatica Sistemistica e Comunicazione - Viale Sarca, 336
20126 Milano - Edificio U14
redazioneweb@disco.unimib.it - last update of this page 11/11/2013