| | | |  corso | | | |
Ricerca Operativa: Reti di Comunicazione
(Corso di Laurea in Informatica (quinquennale))
| Codice: | 4I091 | Crediti: | 6 | Semestre: | 2 | Sigla: | ROC | |
Docente
Stefano Pallottino
Prerequisiti
Programmazione Matematica
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,
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 (18 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.
- Routing in reti di trasmissione di dati (8 ore)
- Aspetti tecnologici ed economici.
- Alcuni problemi di routing.
- Problemi di cammino minimo a più criteri.
- Progetto di reti di comunicazione (8 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.
- Reti di trasporto (6 ore)
- Il problema del trasporto individuale urbano.
- Modelli di equilibrio.
- Un algoritmo risolutivo.
| Ore lezione: | 25 | Ore esercitazione: | 15 | | | |
Bibliografia
Appunti forniti dal docente.
"Network flows", Ahuja, Magnanti, Orlin (1993).
"Scienza delle Decisioni per i Trasporti", Pallottino, Sciomachen
(eds.) (1999).Modalità di esame
Prova scritta e prova orale (solo orale per studenti del corso di laurea in SI)
