Roberto Zunino, 2022
Questa pagina descrive il progetto per il corso di Informatica della Laurea in Matematica per gli appelli dell'anno accademico 2022/2023.
Il progetto consiste nel leggere da file una matrice di numeri razionali e di calcolarne il determinante.
Il file con la matrice ha la seguente forma
N m11 ... m1N ... mN1 ... mNN
La prima riga contiene un numero naturale N > 0, che
indica il numero di righe e colonne della seguente matrice quadrata.
Ogni elemento della matrice mij è un razionale espresso
come frazione n/d dove:
n è
un intero qualunque,d è un intero
positivo,n,d sono coprimi (primi tra loro, non hanno fattori non
banali in comune).
Di conseguenza, il razionale zero può solo essere scritto
come 0/1, e più in generale tutti gli interi solo come
n/1. Per esempio, 4/2, 2/-1, 0/7 non sono
rappresentazioni valide.
In Java, i razionali vanno rappresentati come un
vettore long[] di lunghezza 2, i cui elementi devono
sempre rappresentare una frazione che soddisfa i vincoli elencati
sopra. Fate attenzione, perché se non semplificate
tutte
le frazioni man mano che fate i calcoli rischiate di ottenere numeri
troppo grandi per stare in un long e quindi di ottenere
un risultato finale errato.
Di conseguenza, la matrice sarà un long[][][], con
m[i][j][0] che rappresenta un numeratore e
m[i][j][1] che rappresenta un denominatore.
Il programma Java che dovete sviluppare dovrà contenere una funzione
public static long[] determinante(String fileName)
che legge la matrice dal file il cui nome è passato come parametro, calcola il suo determinante, e lo restituisce come risultato (un razionale come frazione, con i soliti vincoli).
Per sviluppare il codice, è obbligatorio creare un progetto Eclipse
senza module-info.java e senza package, che
contiene una classe Progetto, seguendo lo scheletro di
codice che vi forniamo:
La classe scheletro va posizionata in un progetto Eclipse come segue.
Create un progetto Eclipse chiamato cognome_matricola
(usate i vostri dati, per esempio
tramaglino_000001 o
de_paperoni_000002),
e create la classe Progetto al suo interno nella cartella
src. Dovete ottenere un file come segue:
zunino_555555/src/Progetto.javaÈ obbligatorio rispettare la posizione del file della classe come descritto sopra. Dentro quel file potete quindi inserire il codice dello scheletro fornito.
È tassativamente proibito
modificare lo scheletro
nelle parti segnate al suo interno come da non modificare.
In particolare, non si può modificare il tipo o il nome delle
procedure / funzioni già presenti all'interno.
In nessun caso il file consegnato dovrà contenere una dichiarazione
package.
È invece consentito (e consigliabile) definire delle
procedure/funzioni addizionali all'interno della
classe Progetto. È consentito aggiungere
import per usare librerie di Java. È in ogni caso
vietato usare funzioni di libreria (incluse in Java o esterne) che
rendano banale lo svolgimento del compito.
È consentito modificare il metodo main della classe
nello scheletro. Si noti, tuttavia, che tale metodo
potrà essere cancellato e sovrascritto, o comunque
non eseguito, da chi corregge.
Di conseguenza, se si decidono di usare variabili globali,
queste devono essere inizializzate dentro la funzione
determinante(), e non dentro
il main, in quanto quest'ultimo non verrà eseguito.
Noi testeremo la funzione determinante() su vari file,
chiamandola ripetutamente anche in modo automatizzato, e senza
eseguire il main() della vostra
classe Progetto. Di conseguenza, se usate variabili
globali, non potete fare affidamento sul fatto che esse siano state
inizializzate nel main() o sul fatto che la
funzione determinante() non sia mai stata eseguita
prima.
Per calcolare il determinante della matrice, dovete usare l'algoritmo di Gauss che riduce la matrice "a gradini". Ad ogni passo, man mano che la matrice viene modificata, tenete traccia di come il determinante cambia. Le due operazioni fondamentali usate da Gauss sono:
(Convincetevi che è proprio così, siccome il determinante è multilineare e alternante)
Dopo avere ridotto a scalini la matrice, il determinante è banalmente il prodotto degli elementi della diagonale principale. Ricordatevi di correggere il segno opportunamente.
Quando il "pivot" è zero, e quindi è necessario scambiare una riga con un'altra, scegliete come altra riga quella di indice minore.
Anche se non esplicitamente richiesto, potrebbe esservi utile scrivere qualche funzione per le operazioni di base. Qui sotto elenchiamo qualche esempio, in modo non esaustivo.
a,b interi non
negativi (se sono negativi, basta cambiare segno all'inizio).
mcd(a,0) = amcd(a,b) = mcd(b,a % b) se
b > 0, dove a % b è il resto
della divisione.
Ricordatevi che se avete due razionali long[] a,b in
Java non potete scrivere
semplicemente a+b, a-b, ... ma dovete
implementare opportunamente queste operazioni.
Allo stesso
modo, a == b non è il modo corretto di controllare se
due razionali sono uguali.
Per dividere le righe del file e costruire la matrice di partenza,
potrebbe essere utile usare
s.split(" ") (dividi sugli spazi) e
s.split("/") (dividi sulla barra) su una String
s. Questo genera un vettore di
stringhe String[] ottenuto spezzando la
stringa s sui delimitatori forniti.
Per convertire una String in un long, usate
Long.parseLong(s).
Quando la funzione viene chiamata, vi viene garantito che il file di
input fileName è un file di testo nel formato
richiesto. Se così non fosse, il vostro programma non è tenuto a
dare il risultato giusto, e potrebbe anche terminare con un'eccezione.
Vi viene garantito che, se eseguite Gauss come indicato sopra e
semplificate sempre le frazioni a ogni passo, i numeri in gioco non
diventano così grandi (o piccoli) da non potere essere rappresentati
in un long. Se non semplificate le frazioni questo non
è garantito.
Per aiutarvi nel testare il vostro codice, vi mettiamo a disposizione
100 test. I file matrice-NNN.txt sono possibili file di input
per la funzione determinante(), mentre i corrispondenti file
det_matrice-NNN.txt contengono il determinante atteso
come output.
Durante la correzione del vostro progetto non useremo necessariamente gli stessi test. Le matrici che useremo per i test non saranno necessariamente di dimensioni simili a quelle dei test sopra.
Se lo desiderate, potete organizzarvi tra di voi e scambiarvi ulteriori test e relativi risultati. Potete usare il forum Moodle del corso per coordinarvi, o qualunque altro mezzo a vostra disposizione.
Il progetto verrà valutato secondo i seguenti criteri, che descrivono un insieme di requisiti sul codice consegnato. Ogni requisito primario deve essere rispettato rigidamente: in caso di violazione, anche minima, di uno di questi requisiti la prova d'esame non è superata. I requisiti secondari devono essere generalmente rispettati. Violazioni minori saranno tollerate, ma violazioni gravi possono comunque causare il non superamento della prova.
Requisiti tecnici (primario). La soluzione consegnata deve seguire lo scheletro di progetto fornito sopra, modificato nel modo descritto sopra.
Devono inoltre essere rispettati questi requisiti:
Progetto, i nomi o i tipi delle procedure/funzioni
segnate come da non modificare.
Non ci deve essere nessuna dichiarazione di
package della classe.
Non ci deve essere nessun
module-info.java.
Progetto come descritto
sopra nel vostro progetto Eclipse.
new File(fileName) usa il parametro, mentre
new File("fileName") usa un nome prefissato.
main invece può interagire con l'utente, se desiderato
(ma comunque come detto sopra il codice del main
può essere ignorato da noi durante i test.)
Il non rispettare questi requisiti tecnici può causare il fallimento dei nostri test automatizzati, ed in tal caso la prova non sarà superata.
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
ben formato. 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.
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 variabile e di funzione appropriati, strutturare il codice adeguatamente (dove ha senso, meglio dividere una funzione lunga in più funzioni ausiliarie), e di inserire dei commenti dove sia utile.
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.atan2(y, x);
Efficienza (secondario).
Il vostro programma deve svolgere il suo compito in tempi ragionevoli.
Noi dobbiamo essere in grado di svolgere agevolmente i nostri test
chiamando la funzione determinante() molte volte su input
diversi.
Se il vostro programma è così lento da impedirci di eseguire tutti i test nel tempo di pochi minuti, riterremo tutti i test falliti.
Per potere partecipare allo scritto di un appello di esame, il progetto deve essere consegnato entro le date indicate nell'elenco degli appelli d'esame. La consegna si svolge su Moodle, in modo simile a quanto fatto per il tutorato.
zunino_555555/src/Progetto.javazunino_555555/README.txtSe avete dubbi sul testo del progetto, ovvero su che cosa vi sta venendo chiesto, chiedete pure delucidazioni, preferibilmente usando il forum su Moodle, ma alternativamente anche 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, e che non siano soluzioni degli esercizi proposti o di una loro parte significativa. Nei casi consentiti 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.
Se preferite, potete usare anche caratteristiche di Java non viste a lezione (costrutti diversi come gli oggetti, librerie non viste a lezione purché incluse tra quelle standard di Java), anche se il progetto si può svolgere benissimo senza. Dovete però comprendere il codice che state usando: se venite chiamati ad un colloquio (vedi sopra) vi può essere chiesto di spiegarlo.
Se ci sono parti del testo del progetto che ritenete non chiare, vi invitiamo a fare domande usando il forum che trovate su Moodle, in modo che tutti gli studenti possano leggere le nostre risposte.
Informatica - Teaching - Home
Roberto Zunino, 2022