Progetto 2014/15

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

Problema

Dopo l'assedio di Troia, Odisseo si accinge a ritornare ad Itaca. A causa dell'ira di Poseidone, il suo viaggio è tormentato e Odisseo si ritrova a vagare tra molti luoghi diversi. Da ogni luogo parte un certo numero di rotte verso altri luoghi (o anche verso lo stesso luogo). Ogni rotta ha una direzione precisa: per esempio, la rotta da A verso B può essere soltanto percorsa in quel verso. Inoltre, ogni rotta ha un nume tutelare che protegge chi la segue. Non ci sono vincoli su quale nume sia associato ad una rotta: per esempio è possibile che da A parta una rotta per B tutelata da X, una rotta per C tutelata da Y, e una rotta per D tutelata di nuovo da X. Odisseo però viene aiutato da Hermes, che gli rivela un'importante informazione: per potere tornare a Itaca, Odisseo deve seguire una qualunque sequenza di rotte i cui rispettivi numi tutelari formano una precisa sequenza.
Riuscirà l'eroe multiforme a ritornare ad Itaca?

Formato dei dati

I luoghi raggiungibili da Odisseo sono rappresentati da numeri naturali (che il tipo int può rappresentare). La città di Troia, dove parte Odisseo è il luogo numero 0, mentre Itaca, l'arrivo, è il luogo numero 1. I numi sono rappresentati da caratteri (tipo char), e di conseguenza la sequenza di numi rivelata da Hermes è una String.

I dati relativi alle rotte e al messaggio di Hermes sono memorizzati su un file di testo nel formato seguente: 

N
partenza1 nume1 arrivo1
partenza2 nume2 arrivo2
...
partenzaN numeN arrivoN
numeAnumeB...numeZ

dove partenza1,... e arrivo1,... sono naturali, mentre numeX sono singoli caratteri. La prima riga del file contiene il numero di rotte N. Poi, seguono esattamente N righe con le triple partenza nume arrivo che rappresentano le rotte: qui partenza e nume sono separati da un carattere spazio, così come nume e arrivo. L'ultima riga del file invece contiene il messaggio di Hermes, e può essere lunga zero o più caratteri (ed è terminata con un a-capo '\n'). Nessun nume è rappresentato col carattere spazio (' ') o a-capo ('\n').

Esempio

esempio di rotte

Le rotte mostrate sopra possono essere rappresentate in un file come segue, assieme al messaggio di Hermes: 

8
0 a 2
2 a 0
2 c 1
2 a 2
2 b 3
3 c 1
3 c 2
3 c 4
aaabcbc

in questo caso Odisseo può raggiungere Itaca con il percorso 0-a-2-a-2-a-2-b-3-c-2-b-3-c-1. Se il messaggio di Hermes fosse invece stato aaabcb, Odisseo non avrebbe potuto raggiungere Itaca rispettando la sequenza di numi. Analogamente non avrebbe potuto con aaabbcc.

Altri esempi:

Svolgimento

Si chiede di scrivere una funzione in Java che, dato un nome di file contenente i dati relativi al problema, restituisca un boolean. Il valore true indica che Odisseo può salvarsi, mentre false indica che non può. Si vedano più sotto i requisiti tecnici che tale funzione deve soddisfare.

Non è richiesto l'uso di uno specifico algoritmo (fermi restando i requisiti di cui sotto).

Come suggerimento verso una possibile soluzione si fa notare che, nell'esempio sopra:

Quindi, siccome Itaca (1) appare tra le opzioni finali, Odisseo può raggiungerla.

Precisazioni e casi degeneri

La sequenza di numi di Hermes va seguita interamente. Non importa se Itaca viene raggiunta prima della fine.

La sequenza di numi può essere vuota (ed in tal caso, Odisseo non raggiunge Itaca).

Da un luogo (incluso Troia (0)) possono partire zero rotte.

Ad un luogo (incluso Itaca (1)) possono condurre zero rotte.

Da un luogo possono partire più rotte tutelate dallo stesso nume.

Una rotta può partire ed arrivare nello stesso luogo.

È possibile che Troia e Itaca siano completamente sconnesse, ovvero che nessuna sequenza di rotte le colleghi.

Ci possono essere zero rotte nel file.

Ci possono essere cicli nelle rotte (come nell'esempio sopra), e quindi è possibile passare più volte sullo stesso luogo.

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.

Invarianti (primario). Nel "cuore" del programma, dove viene effettivamente usato l'algoritmo che risolve il problema, si richiede di aggiungere qualche invariante informale (e non banale). Non è necessario che tali invarianti siano così precise da essere direttamente usabili in una dimostrazione formale di correttezza del codice. Le invarianti vanno invece aggiunte come documentazione al codice, per aiutare il lettore a capire come funziona il programma.
Le invarianti vanno aggiunte prima dei cicli while/for. Se usate funzioni ricorsive, aggiungete invece una pre- e una post-condizione.
Per esempio: 

	int num = 10;
	Punto[] p = ... ;
	...
	// INV: nessuna coppia di punti tra p[0] .. p[num-1] dista più di 4
	while (num > 0) { 
           ...
        }

Requisiti tecnici (primario). L'algoritmo deve essere implementato in una classe fatta esattamente come segue 

   // File "Progetto.java"

   // Non usate "package" qui, usate quello di default.

   // Potete usare import per accedere alle librerie di java.

   public class Progetto {  // con la P maiuscola
      public static boolean raggiungibile(String nomeFile) {
        // Scrivete qui la vostra soluzione al problema
      }

      // Qui potete aggiungere altri metodi, se volete, incluso
      // un metodo main.
      // Il metodo raggiungibile di sopra deve comunque funzionare
      // anche se viene invocato da un main diverso da quello che scrivete
      // voi.
      // Per esempio, il vostro main NON deve inizializzare variabili
      // che poi vengono usate dentro raggiungibile (inizializzatele
      // direttamente là).
      //
      // Ad esempio, questo main va bene:
      public static void main(String[] args) {
         String f = "/home/zunino/java/progetto/test1.txt"; // o altro nome di file nella vostra home
         System.out.println(raggiungibile(f));
      }
   }

Potete usare anche altre classi in altri file .java, oltre a quello di sopra (anche queste classi vanno nel package di default).
La funzione raggiungibile 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).

Complessità (secondario). Annotate in un commento vicino alla funzione raggiungibile la complessità dell'algoritmo che state usando, in funzione del numero dei luoghi, delle rotte e della lunghezza del messaggio di Hermes (la sequenza di numi).

Efficienza (secondario). Si faccia attenzione a quali algoritmi si usano e alla loro complessità. Non è richiesto l'uso dell'algoritmo più efficiente possibile per un sottoproblema, ma la soluzione proposta non deve essere enormemente più inefficiente di quanto non si possa fare.

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, potete inserire dei commenti.

Commenti (secondario). 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 sotto) vi può essere chiesto di spiegarlo.

Potete assumere che l'input da file abbia esattamente il formato di cui sopra. Non vi si chiede di gestire gli errori nell'input in modo controllato: il vostro programma può dare errore o restituire un risultato arbitrario in tal caso. Se fate comunque qualche tipo di validazione sull'input, è cosa bene accetta.

Se volete usare un TreeSet di char, dovete usare TreeSet<Character>. Il motivo è che TreeSet richiede un tipo classe, mentre char è un tipo primitivo. Il tipo Character è un tipo classe che contiene un singolo char e viene automaticamente convertito da e in char da Java. Allo stesso modo, usate TreeSet<Integer> per gli int.

Siccome dovete leggere il file, Java vi obbliga a gestire un'eccezione FileNotFoundException. Fatelo per esempio come segue: 

try {
   ... // codice che legge il file
} catch (FileNotFoundException e) {
   System.out.println("Errore in lettura: " + e);
   return true; // o false
}

Non vi è permesso di cambiare il tipo della funzione raggiungibile con throws FileNotFoundException e fare in modo che ci pensi il chiamante a gestirla. (In un programma più serio, questa seconda opzione sarebbe quella "giusta", ma per questo progetto non vi si chiede una gestione precisa degli errori.)

Quando il messaggio di Hermes è vuoto, dopo la riga dell'ultima rotta c'è un a-capo (che finisce la rotta) seguito direttamente da un altro a-capo (che finisce immediatamente il messaggio di Hermes), e dopo il file di testo finisce. Il file di testo non finisce subito dopo il primo a-capo.

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

Informatica - Teaching - Home

Valid CSS Valid XHTML 1.1 Roberto Zunino, 2015