|
E' indetta una gara di programmazione sul problema del mantenimento dinamico delle distanze da una sorgente prefissata in un grafo diretto non pesato soggetto a cancellazioni di archi.
 Obiettivo. Dato un grafo diretto non pesato iniziale G=(V,E) con n nodi e m archi e un nodo sorgente s prefissato, l'obiettivo è quello di implementare in un linguaggio a scelta una struttura dati in grado di supportare efficientemente una qualunque sequenza di cancellazioni di archi inframmezzata da query che restituiscono la distanza (in termini di minimo numero di archi orientati da attraversare) da s a un nodo v, o -1 se v non à raggiungibile da s.
File di input. Ogni istanza di input sarà formata da due file con stesso nome, ma estensione diversa, forniti dal docente (un sottoinsieme dei file è disponibile qui):
- File nel formato DIMACS .gr contenente il grafo di partenza (è possibile scaricare grafi di test nel formato DIMACS dal sito del 9th DIMACS Implementation Challenge). Si ignori il campo che specifica il peso dell'arco, che va considerato unitario. Esempio nome file: USA-road-d.COL.gr.
- File nel formato DIMACS .dss contenente la sequenza di operazioni (cancellazioni di archi e query di distanze) da applicare al grafo di partenza. Esempio nome file: USA-road-d.COL.dss.
File di output. I file di output dovranno essere generati da ciascuna implementazione e saranno di due tipi:
- File nel formato DIMACS .dss.res contenente il report delle prestazioni dell'implementazione per ogni istanza di input. Oltre agli attributi obbligatori, si richiede che il file contenga l'attributo i (improvements) che specifica il numero totale di incrementi di distanze dei nodi dalla sorgente durante l'intera sequenza di cancellazioni. Il nome del file deve essere: nome-istanza.cognome-studente.dss.res. Esempio nome file: USA-road-d.COL.rossi.dss.res.
- File nel formato DIMACS .dss.chk contenente il risultato delle distance query nello stesso ordine in cui appaiono nell'istanza di input. Questo file verrà usato per verificare la correttezza dell'implementazione. Per denotare una distanza infinita, si usi il valore -1. Il nome del file deve essere: nome-istanza.cognome-studente.dss.chk. Esempio nome file: USA-road-d.COL.rossi.dss.chk.
Robustezza delle implementazioni. Assumere che il grafo di partenza specificato dal file .gr possa contenere archi multipli (es. due volte lo stesso arco) e self-loop (archi con gli estremi uguali). La sequenza di cancellazioni potrebbe richiedere episodicamente la cancellazione anche di un arco non presente nel grafo, nel qual caso l'operazione non deve dare errore. Si assuma tuttavia che tutte le etichette dei nodi che appaiono nelle operazioni delete o query specificate nel file .dss siano comprese nell'intervallo {1,...,n}, dove n è il numero di nodi nel grafo iniziale.
Piattaforma di test. I test prestazionali verranno effettuati su un PC con processore Pentium IV dual core a 3 GHz, 2 GB RAM, 2MB cache L2, 3 hard disk SATA da 250 GB (XFS/EXT-3), equipaggiato con sistema operativo Linux Mandriva 2007.0, kernel 2.6.17 e gcc 4.1.1.
Criteri di valutazione. Le implementazioni candidate verranno giudicate in base a tre criteri di valutazione:
- tempo medio per operazione in millisecondi richiesto dall'algoritmo durante l'intera sequenza di operazioni, calcolato come il tempo totale per eseguire l'intera sequenza di operazioni diviso per il numero di operazioni (sia update che query);
- numero totale di incrementi di distanze dei nodi dalla sorgente calcolato sull'intera sequenza di cancellazioni;
- memoria utilizzata, o alternativamente il grafo più grande trattabile dall'implementazione fra quelli proposti dal docente.
Sessioni di gara. La gara sarà pubblica e i risultati dei test insieme alle implementazioni stesse verranno pubblicati su questo sito alla fine dell'anno accademico. Si prevede una sessione di gara per ogni appello per consentire la realizzazione delle implementazioni in tempi diversi.
Premi. Ogni studente che parteciperà alla gara con una propria implementazione avrà un aumento di punteggio sul voto finale a discrezione del docente. La partecipazione alla gara è individuale e facoltativa ai fini del superamento dell'esame. Ogni studente che parteciperà alla gara riceverà inoltre una maglietta di marca in cotone con il logo di FOCS 2004, il prestigioso congresso IEEE sbarcato in Europa (a Roma!) per la prima volta dopo 45 anni (tutte le edizioni precedenti si sono tenute in Nord America).
|
