Ricerca Operativa: Reti di comunicazione

(Corso di Laurea Specialistica in Informatica (classe 23/s))

Codice:

AA246

Crediti:

Semestre:

Sigla:

ROC

Docente

Stefano Pallottino

Prerequisiti

Ricerca Operativa

Obiettivi di apprendimento

Il corso di Ricerca Operativa: Reti di Comunicazione e di Trasporto è rivolto a presentare agli studenti le principali problematiche algoritmiche che nascono nella gestione e nel progetto di reti di comunicazione, con particolare enfasi alle reti di trasmissione di dati e alle reti di traffico.

Descrizione

Nella prima parte del corso vengono presentati algoritmi "ad hoc" per alcuni rilevanti problemi di flusso su reti (flusso di costo minimo, cammino minimo, flusso massimo, accoppiamento, flussi multicommodity, albero ottimo). Vengono quindi presentate problematiche algoritmiche che nascono nell'ambito di problemi di Routing in reti di trasmissione di dati, nel Progetto di reti, ed in Reti di traffico.

English Description

In the first part the classical Network Flow problems -- that is, Min Cost Flow, Shortest Path, Max Flow, Bipartite Matching, Multicommodity Flows, Spanning Tree -- are presented and the classical solution algorithms are introduced. Then, several typical optimization problems, arising from Routing Problems, Network Design Problems and Urban Transportation Network Problems, are analyzed and studied, and solution algorithms are introduced.

Programma

Algoritmi "ad hoc" per problemi di flusso su rete (22 ore)
Il problema di flusso di costo minimo: teoria e algoritmi di Simplesso su reti.
Il problema dei cammini minimi: Algoritmi, strutture di dati e complessità.
Il problema di flusso massimo: algoritmo Preflow-Push.
Il problema dell'albero di copertura di costo minimo: algoritmo di Kruskal, operazioni di Find-Union.
Problemi di accoppiamento: problemi, proprietà, algoritmi e complessità.
Il problema di flusso di costo minimo "multicommodity".
Routing in reti di comunicazione (8 ore)
Reti di comunicazione: aspetti tecnologici ed economici.
Il grafo della rete e i dati caratteristici.
Problemi di routing.
Progetto di reti di comunicazione (5 ore)
Il problema dell'albero di copertura di costo minimo con capacità.
Il progetto di reti "multicommodity".
Tecniche di "lower bound" ed algoritmi di ricerca locale.
Reti di trasporto (5 ore)
Il problema del trasporto individuale urbano.
Modelli di equilibrio.
Tecniche di ottimizzazione non lineare.
Un algoritmo risolutivo.

(Le ore indicate includono le esercitazioni)

Bibliografia

Appunti forniti dal docente. "Network flows", Ahuja, Magnanti, Orlin (1993). "Scienza delle Decisioni per i Trasporti", Pallottino, Sciomachen (eds.) (1999).

Modalità di esame

Scritto e orale