Progetto 2013/14

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

Testo del progetto

Si scriva un programma in Java che risolva il seguente problema. Sia dato un file input.csv contenente un elenco di punti distinti su un piano, rappresentati tramite le loro coordinate (x,y). Le coordinate non sono necessariamente intere. Per nessuna tripla di tali punti passa una retta. Si chiede di generare un file output.csv con il sottoinsieme di tali punti che giacciono sulla frontiera dell'inviluppo convesso, usando l'algoritmo descritto sotto. Tali punti devono essere elencati nel file di output seguendo lo stesso ordine usato nel file di input.

Chiarimento: il programma non deve interagire con l'utente, ma semplicemente leggere il file chiamato input.csv, calcolare l'inviluppo convesso, e generare il file chiamato output.csv. Non si devono quindi aprire finestre per chiedere all'utente di selezionare i file di input o output. I file in questione sono da trovarsi nella "cartella corrente" e non nella cartella home dell'utente. Basta quindi non usare nomi del tipo C:\Users\zunino\input.csv ma usare direttamente input.csv.

La classe Java col metodo main che svolge le operazioni richieste sopra deve chiamarsi Progetto e quindi trovarsi in un file Progetto.java. Potete usare tutte le funzioni della libreria standard di Java. Si consiglia di evitare di reimplementarsi funzionalità già offerte dall'ambiente Java, in quanto facendolo si rischia di produrre codice meno efficiente e con possibili errori all'interno.

Algoritmo

L'inviluppo convesso di un insieme di punti è il più piccolo insieme convesso che contiene tali punti.

esempio di inviluppo convesso

Si sceglie come punto "pivot" il punto con coordinata y minore (e in caso di parità, con coordinata x minore). Si ordinano gli altri punti in funzione dell'angolo tra la retta punto-pivot e l'asse x, come nella figura sotto.

passo 1

Si "cammina" quindi sui punti ordinati in tal modo, partendo dal pivot e poi proseguendo dal punto 1. Ad ogni punto sul cammino si controlla se si sta "svoltando a sinistra" o "a destra". Una svolta "a destra" in un punto rivela che il punto non fa parte della frontiera dell'inviluppo convesso. Si scartano quindi questi punti in modo che il cammino costruito includa solo svolte "a sinistra". Si veda l'esempio sotto.

passo 2

Una volta raggiunto l'ultimo punto sul cammino, abbiamo trovato tutta la frontiera richiesta. (Ricordatevi che i punti vanno salvati in output.csv seguendo l'ordine usato per l'input, quindi la frontiera va riordinata in tal modo).

Un consiglio: per capire se una svolta è a destra o a sinistra, non è necessario fare conti trigonometrici complicati. Basta considerare i due vettori che partono dal nodo in cui c'è la svolta, vederli come vettori tridimensionali (con z=0) e calcolarne il prodotto vettoriale. Il prodotto vettoriale è un vettore della forma (0,0,z) e il segno di z rivela il tipo di svolta. Per il prodotto vettoriale ci sono formule aritmetiche molto semplici, che non includo qui appositamente (documentatevi! Le trovate facilmente anche in rete).

Esempio

Se il file input.csv contiene le righe seguenti 

0.5;0.5
0.5;2.5
1.1;2.1
2.5;2.5
2.5;0.5

allora il file output.csv dovrà contenere le righe seguenti 

0.5;0.5
0.5;2.5
2.5;2.5
2.5;0.5

esattamente nell'ordine in cui appaiono sopra.

Criteri di valutazione

Il progetto verrà valutato secondo i seguenti criteri generali.

Correttezza. 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.

Efficienza. 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à. 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. 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);

Invarianti. Annotate i cicli più complessi con un'invariante informale. Non è necessario che tale invariante sia tale per cui uno possa usarla per una dimostrazione formale di correttezza del codice. L'invariante viene aggiunta come documentazione al codice, quindi per aiutare il lettore a capire cosa sta succedendo. Per esempio: 

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

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. 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.

Informatica - Teaching - Home

Valid CSS Valid XHTML 1.1 Roberto Zunino, 2014