Ricerca Operativa: Reti di Comunicazione

(Corso di Laurea in Informatica (quinquennale))

Codice:

4I091

Crediti:

Semestre:

Sigla:

ROC

Docente

Maria Grazia Scutellà

Tel. 0502212771

Prerequisiti

Programmazione Matematica

Obiettivi di apprendimento

Il corso di Ricerca Operativa: Reti di comunicazione è 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, 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

"Ad hoc" algorithms are presented for most relevant network flow problems (min cost flow, shortest paths, max flow, multicommodity flows, minimum cost spanning tree).
Then, three relevant fields of application -- namely Routing in data networks, Network desing, Transport networks -- are presented by showing both methodologies and solution algorithms.

Programma

Algoritmi "ad hoc" per problemi di flusso su rete (14 ore)
- Il problema dei cammini minimi: algoritmo di Dial ed algoritmo Radix-Heap.
- Il problema di flusso massimo: algoritmo Preflow-Push.
- Il problema di flusso di costo minimo: algoritmo "Successive-shortest paths".
- Il problema di flusso "multicommodity": l'approccio "column generation".
- Il problema dell'albero di copertura di costo minimo: algoritmo di Kruskal.
Progetto di reti di comunicazione (10 ore)
- Il problema dell'albero di copertura di costo minimo con capacità.
- Problemi di localizzazione di nodi della rete.
- Tecniche di "lower bound" ed algoritmi di ricerca locale.
Routing in reti di trasmissione di dati (6 ore)
- Aspetti tecnologici ed economici.
- Alcuni problemi di routing.
Reti di trasporto (10 ore)
- Il problema del trasporto individuale urbano.
- Modelli di equilibrio.
- Un algoritmo risolutivo.

Ore lezione:

Ore esercitazione:

Bibliografia

"Network flows", Ahuja, Magnanti, Orlin (1993).

Appunti forniti dal docente.