Progetto 2015/16

Questa pagina descrive il progetto per il corso di Informatica alla Laurea in Matematica per le sessioni dell'anno accademico 2015/2016.

Problema: le vacanze del sig. Rossi

Il sig. Rossi si trova a casa, pronto a partire per le meritate vacanze, che vuole trascorrere in una città turistica. Avendo molte alternative a disposizione, è fortemente indeciso sulla città da visitare. Tra i vari fattori che vuole tenere in considerazione, c'è quello della distanza da percorrere per raggiungere le varie mete. Il sig. Rossi ha però un atlante stradale che indica la lunghezza di ogni strada, e vuole sfruttarlo per calcolare la distanza verso tutte le mete possibili. Per "distanza", si intende la lunghezza del tragitto più breve che collega la partenza ad ogni altra città.

Per semplicità, si suppone che ogni strada colleghi due città, e che sia a "senso unico", ovvero percorribile solo in una direzione. Si può supporre che tutte le città sull'atlante siano raggiungibili dalla casa del sig. Rossi. Inoltre, la distanza tra due città non supera mai 10 volte la distanza massima tra due punti sulla Terra.

Formato dei dati

Le città sono rappresentate da naturali 0, ..., N-1, dove 0 è la città di partenza del sig. Rossi. Le città sono connesse tra loro da M strade. Tali strade, con le relative lunghezze, sono elencate in un file di testo nel formato seguente: 

N
M
partenza1 arrivo1 lunghezza1
partenza2 arrivo2 lunghezza2
...
partenzaM arrivoM lunghezzaM

dove partenza1,... e arrivo1,... sono i naturali corrispondenti alle strade (che sono "a senso unico"), mentre lunghezza1,... sono le relative lunghezze, espresse in metri (naturali positivi). La prima riga del file contiene il numero di città N, mentre la seconda il numero di strade M. Poi, seguono esattamente M righe con le triple partenza arrivo lunghezza che rappresentano le strade. Ogni tripla di naturali è separata da un carattere spazio, e terminata da un carattere a-capo ('\n' in Java).

Esempio

Ecco sei città collegate da strade.

esempio di mappa

L'atlante mostrato sopra può essere rappresentato in un file come segue: 

6
13
0 3 4
0 4 2
0 5 9
1 5 3
2 4 3
2 1 2
3 0 7
3 2 2
3 4 6
4 1 8
4 5 5
5 0 3
5 1 2

In questo caso, le distanze dalla città 0 sono date dai numeri in arancio qui sotto. Sempre in arancio sono evidenziati i tragitti che realizzano tali distanze.

distanze

ed in particolare sono rappresentate dal vettore a = {0, 8, 6, 4, 2, 7} dove a[i] contiene la distanza dalla città 0 alla città i.

Svolgimento

Si chiede di scrivere una funzione in Java che, dato un nome di file contenente i dati relativi al problema, restituisca un vettore di int contenente tutte le distanze. Il vettore deve essere lungo quanto il numero di città, e in posizione i deve contenere la distanza tra la città 0 e la città i. Si vedano più sotto i requisiti tecnici che tale funzione deve soddisfare.

Per calcolare le distanze, si richiede l'uso del seguente algoritmo.

Algoritmo

Si inizializzi un vettore d con delle distanze provvisorie: 0 per la città 0 e un numero sicuramente più grande della vera distanza per tutte le altre inf (sfruttate l'ipotesi nel testo sopra).

Inoltre, si tenga traccia di un insieme di città da visitare C (inizialmente {0,...,N-1}).

Finché rimangono città da visitare, eseguiamo quanto segue. Si tolga da C la città n con distanza provvisoria minima p. Si esaminino quindi tutte le città m raggiungibili da n usando una singola strada (lunga q). Se la distanza provvisoria di m è maggiore della distanza p di n più la lunghezza q della strada, il risultato di questa somma diventa la nuova distanza per m.

Quando tutte le città sono state visitate, le distanze provvisorie sono quelle definitive.

Correttezza dell'algoritmo

Diamo ora una bozza della dimostrazione di correttezza dell'algoritmo. L'algoritmo preserva la seguente invariante:

Chiaramente, quando alla prima iterazione si visita 0, le invarianti sono banalmente vere. Nelle iterazioni successive, se visito n che ha la minima distanza provvisoria, sicuramente il suo tragitto minimo non passa dalle altre città che hanno distanza provvisoria maggiore. Inoltre, dopo avere visitato n, riconsideriamo la distanza provvisoria di ogni città immediatamente collegata m: se passando da n si raggiunge m con un tragitto più breve rispetto a quelli che passano solo dalle altre città visitate (senza c, quindi), aggiorniamo d[m] con la lunghezza del nuovo tragitto.

Precisazioni e casi degeneri

Ogni strada è elencata una volta sola nel file.
Ogni città è raggiungibile dalla città 0.
Ogni strada è a "senso unico": è percorribile in un verso solo.
Ogni strada è lunga un numero naturale positivo di metri.
Le strade sono elencate nel file in ordine crescente secondo il seguente ordinamento. Se le partenze differiscono, viene prima la strada con partenza minore; altrimenti, viene prima la strada con arrivo minore.
Due città sono collegate al massimo da una strada per ogni direzione.

Test

Potete provare qui alcuni esempi.


Risultato: esegui il test

Requisiti e criteri di valutazione

Il progetto verrà valutato secondo i seguenti criteri, che formano un insieme di requisiti sul codice consegnato. Ogni requisito primario è condizione necessaria per il superamento della prova: anche se uno di questi non viene rispettato, la prova non è superata. I requisiti secondari devono essere generalmente rispettati. Nel caso ci siano solo minori violazioni di tali requisiti, la prova è comunque superata. Violazioni gravi possono comunque causare il non superamento della prova.

Correttezza (primario). Non ci devono essere errori a tempo di compilazione: il programma deve compilare. Non ci devono essere errori a tempo di esecuzione: il programma non deve generare eccezioni (per esempio, DivisionByZero oppure ArrayIndexOutOfBounds) quando eseguito su un input valido. Il programma deve dare l'output desiderato su qualunque input compatibile con la specifica.
Nota bene: Nel caso il programma sia scorretto, non è compito di chi corregge fare il debugging, ovvero identificare la causa dell'errore e suggerire una modifica per rimuoverla. Anche quando tale causa fosse nota a chi corregge, non verrà comunicata allo studente, in quanto sarebbe come suggerire una parte non banale della soluzione della prova. Infatti, capita frequentemente che correggere l'errore dopo averlo individuato diventi banale ("devo usare x, e non x+1"), e che la prova di conseguenza consista prevalentemente nella ricerca dell'errore.
Corollario: se provando il programma su un insieme di input campione si riscontrano già errori di correttezza, chi corregge non è tenuto ad esaminare il codice del programma.

Usabilità (secondario). Su input errati (file inesistente o con formato errato) è consentito generare errori. Si chiede in tal caso di stampare a video un messaggio di errore che spieghi la causa dell'errore.

Requisiti tecnici (primario). L'algoritmo deve essere implementato seguendo lo scheletro di progetto eclipse seguente.

Scheletro di progetto

Lo scheletro non va modificato, tranne dove espressamente consentito in esso. Lì vi si richiede di scrivere due funzioni:

Potete definire anche altre funzioni ausiliarie .java, Potete usare anche altre classi in altri file .java, oltre a quello di sopra (anche queste classi vanno nel package di default).
La funzione distanze non deve interagire con l'utente (chiedere all'utente dati, aprire finestre, ecc). È permesso l'output di messaggi su console (che verranno ignorati da chi corregge). La funzione main, se usata, può interagire con l'utente (ma non sarà considerata da chi corregge).

Efficienza (primario). Tentate di essere efficienti nel codice che scrivete. Il vostro programma sarà provato su file di grandi dimensioni, e il tempo di calcolo richiesto T sarà confrontato col tempo massimo usato da un altro programma di riferimento R che esegue la stessa operazione su un insieme di input.
Se, per qualche input si osserva che T >= 10*R + 100 secondi la prova non viene superata.
Lo scopo di questo criterio non è quello di scartare le soluzioni debolmente inefficienti, ma quelle che usano algoritmi molto più inefficienti di quelli che si possono usare.

Leggibilità (secondario). Il codice deve essere scritto in modo tale da permettere ad un altro programmatore di comprenderne la logica. Non è sufficiente che il codice "funzioni", o che sia chiaro a chi lo ha scritto. Per aiutare la lettura del codice da parte di altri, si consiglia di usare dei nomi di variabili appropriati, strutturare il codice adeguatamente (dove ha senso, meglio dividere una funzione lunga in più funzioni ausiliarie), e di inserire dei commenti.

Non commentate come state calcolando qualcosa, commentate piuttosto cosa state calcolando. Per esempio, il seguente commento è altamente inutile: 

	// incremento i
	i++;

Al contrario, il seguente aiuta a comprendere il codice: 

	// passo a coordinate polari
	rho = Math.sqrt(x*x + y*y);
	theta = Math.atan(y/x);

Consegna del progetto

Per potere partecipare allo scritto di una sessione di esame, il progetto deve essere consegnato entro le date indicate nell'elenco delle sessioni di esame. La consegna si svolge mandando una email avente esattamente le seguenti caratteristiche.

Note Finali

Se avete dubbi sul testo del progetto, ovvero su che cosa vi sta venendo chiesto, chiedete pure delucidazioni per email o a ricevimento. Se invece avete dubbi sulla soluzione dell'esercizio, ovviamente non possiamo suggerirvi nulla.

Il progetto non viene svolto in un ambiente "controllato" come per esempio avviene per un esame scritto, ma vi viene lasciata libertà di svolgerlo dove e quando preferite (compatibilmente con le scadenze). Per esempio, potete usare i laboratori quando liberi, o farlo su un vostro computer personale.

Il progetto è individuale, non di gruppo. Tuttavia, vi è consentito discutere del progetto con altre persone per scambiarsi opinioni a riguardo. Non è consentita, ovviamente, la copia di pezzi di codice inerenti al progetto da uno studente all'altro. Allo stesso modo, farsi fare il progetto da un'altra persona è considerato equivalente a copiare. In caso di dubbi sull'autenticità del progetto, ci riserviamo la possibilità di convocarvi per un colloquio sul codice che avete consegnato, anche dopo l'esame scritto.

Vi è consentito di "copiare" invece pezzi di codice che vi abbiamo fornito noi, o di "tradurre in Java" dei pezzi di codice che potreste trovare su qualche libro o tutorial online. In questo caso, però, dovete obbligatoriamente citare la fonte in un commento nel codice.

Il discutere del progetto su forum di discussione su Internet o simili non è vietato a prescindere, ma è soggetto alle stesse regole della comunicazione tra altri studenti. Inoltre, se iniziate una discussione su un forum riguardo al progetto, dovete obbligatoriamente dichiarare 1) che l'esercizio in questione è un progetto di esame, e 2) che non desiderate che qualcuno vi scriva una soluzione al posto vostro. Se anche chiarendo ciò qualcuno vi risponde includendo del codice, voi non potete includerlo nel progetto.

Risposte a domande degli studenti

Se preferite, potete usare anche caratteristiche di Java non viste a lezione (costrutti, librerie, ...), anche se il progetto si può svolgere benissimo anche senza. Dovete però comprendere il codice che state usando: se venite chiamati ad un colloquio (vedi sopra) vi può essere chiesto di spiegarlo.

Non vi è permesso di cambiare il tipo della funzione distanze, per esempio aggiungendo nuove eccezioni.

Dove sopra scrivo '\n' per indicare l'a-capo non indico la sequenza di due caratteri barrarovesciata-n, ma il char che rappresenta l'a-capo (che in Java viene scritto appunto in tal modo).

Informatica - Teaching - Home

Valid CSS Valid XHTML 1.1 Roberto Zunino, 2015