Progetto software di Algoritmi per le Reti, A.A. 2007-2008

Supponete di avere un grafo G con pesi non negativi, una sorgente s, e un albero T dei cammini minimi in G a partire dal nodo s.

Considerate i seguenti problemi:

1) Il peso di uno degli archi del grafo appartenente anche all'albero T aumenta di una certa quantità d: verificare se T è ancora un albero dei cammini minimi nel grafo con la nuova pesatura ed eventualmente calcolare un nuovo albero T' dei cammini minimi in G a partire dal nodo s.

2) Il peso di uno degli archi del grafo non appartenente all'albero T diminuisce di una certa quantità d (il nuovo peso rimane comunque positivo): verificare se T è ancora un albero dei cammini minimi nel grafo con la nuova pesatura ed eventualmente calcolare un nuovo albero T' dei cammini minimi in G a partire dal nodo s.

Progettare due algoritmi di verifica e due algoritmi per il calcolo di T'. Gli algoritmi devono essere il più possibile efficienti ed evitare di applicare banalmente l'algoritmo di Dijkstra: dovrebbero invece cercare di sfruttare il più possibile le informazioni già presenti in T (che può essere considerato parte dell'input, insieme a G e s).

Dimostrare innanzitutto formalmente la correttezza degli algoritmi proposti.

Implementare poi l'algoritmo di Dijkstra e i nuovi algoritmi in un linguaggio di programmazione a scelta tra C, C++ e Java, ed eseguire un confronto sperimentale delle prestazioni volto a verificare se e quanto i nuovi algoritmi siano più efficienti in pratica rispetto all'applicazione dell'algoritmo di Dijkstra (qual è il rapporto tra il tempo di esecuzione dei nuovi algoritmi e il tempo di esecuzione dell'algoritmo di Dijkstra?).

Nell'analisi sperimentale potete considerare sia grafi random che grafi sintetici o ottenuti da applicazioni reali:

- Un grafo random può essere facilmente generato (ad esempio) a partire dal numero dei nodi n e dalla probabilità p, con 0<=p<=1, di esistenza di un arco: basta enumerare tutte le possibili coppie di nodi u e v, ed inserire l'arco (u,v) nel grafo con probabilità p.

- Una buona fonte di istanze sintetiche e reali (e, più in generale, fonte di ispirazione per il progetto) è il sito del recentissimo 9th DIMACS Implementation Challenge, relativo al problema dei cammini minimi. Questo articolo contiene varie informazioni utili relative al challenge ed alle istanze in esso utilizzate.

I risultati dell'analisi sperimentale possono essere presentati tramite grafici o tabelle (opportunamente commentati e motivati) che mostrino i tempi di esecuzione dei vari algoritmi (o il loro rapporto, come suggerito sopra).

Per formarsi un'idea più chiara su una corretta metodologia sperimentale è utile leggere il seguente articolo:

Bernard M. E. Moret: Towards a discipline of experimental algorithmics. In Proceedings of the 5th DIMACS Implementation Challenge, DIMACS Monograph Series, 2000.

La descrizione degli algoritmi, l'analisi di correttezza, la descrizione delle istanze usate e degli esperimenti effettuati, e la discussione dei risultati sperimentali ottenuti devono essere contenuti in una relazione a corredo del progetto.

Consegna: i voti conseguiti agli scritti sono validi fino all'appello di recupero, che sarà in settembre 2008. Potete pertanto consegnare e discutere i progetti fino a quella data, indipendentemente da quando avete sostenuto lo scritto. Potete inoltre svolgere il progetto in gruppi di massimo tre persone, a patto che il contributo di ciascun componente nelle varie fasi di progettazione, analisi ed implementazione risulti chiaramente evidente in fase di discussione del progetto stesso. Inviatemi il progetto per e-mail (relazione e sorgenti, in un unico file compresso) entro il 30 settembre 2008.