Progetto 2023/24

Questa pagina descrive il progetto per il corso di Informatica della Laurea in Matematica per gli appelli dell'anno accademico 2023/2024.

Il progetto richiede di svolgere due esercizi.

Esercizio 1: moltiplicare polinomi

Descrizione generale

L'esercizio consiste nel leggere due file contenenti due polinomi a coefficienti interi in due variabili, calcolarne il prodotto, e scriverlo in un file di output.

I file di input

Ogni polinomio a due variabili ... + A_ij x^i y^j + ... è rappresentato all'interno di un file come segue: 

N M
A_ij x^i y^j + ... + A_kl x^k y^l

La prima riga contiene due numeri naturali N,M > 0. La seconda riga contiene il polinomio, dove A_ij è il coefficiente intero di x^i y^j. Qui si ha sempre 0 <= i < N e 0 <= j < M. I vari monomi non sono in nessuno specifico ordine, ed è possibile che ci siano più monomi con gli stessi esponenti ripetuti. I monomi con coefficienti zero possono apparire nel file oppure essere omessi. I coefficienti uno sono sempre esplicitati. Gli esponenti zero e uno sono sempre esplicitati. Il segno + separa i monomi anche in caso di coefficiente negativo. Le varie componenti sintattiche sono sempre separate da uno spazio.

Per esempio, questo è un file possibile: 

6 20
7 x^3 y^17 + -2 x^0 y^0 + -4 x^5 y^1

Si noti che tutti gli esponenti di x nel polinomio sono < N, mentre tutti gli esponenti di y sono < M.

Il file di output

Il formato del file di output è perfettamente analogo a quelli di input.

Se i due file di input iniziano rispettivamente con i naturali N1 M1 e N2 M2, il file di output deve avere come prima riga (N1+N2-1) (M1+M2-1). La seconda riga deve contenere il polinomio, scritto con lo stesso formato visto per l'input.

Non è ammesso rappresentare il polinomio diversamente, per esempio questi formati sono errati: 7 x^3 + 4 y^2 (mancano gli esponenti zero), 5 x y (mancano gli esponenti uno), 4 x^1 y^1 + x^2 y^2 (manca il coefficiente uno) o 3 x^1 y^2 - 4 x^2 y^1 (manca il +).

Implementazione in Java

In Java, i polinomi vanno rappresentati usando una matrice long[][] di dimensioni opportune. Tutti i calcoli sui coefficienti devono essere svolti usando long.

Per calcolare il prodotto tra i due polinomi non è richiesto nessun algoritmo specifico. Si richiede solo che non sia eccessivamente inefficiente (vedi sotto). Per esempio, è sufficiente usare l'algoritmo banale che calcola ogni singolo coefficiente del polinomio risultato sommando i prodotti tra i coefficienti dei monomi opportuni.

Il programma Java che dovete sviluppare dovrà contenere una funzione 

public static void polyMultiply(String polyFileName1, String polyFileName2, String polyFileNameResult)

che legge i due polinomi dai file i cui nomi sono passati nei primi due parametri, calcola il prodotto, e lo scrive nel file che ha il nome specificato nel terzo parametro.

Esercizio 2: valutazione parziale di un polinomio

Descrizione generale

L'esercizio consiste nel leggere un polinomio a coefficienti interi in due variabili x e y, fissare il valore di x a un intero dato v, e generare il polinomio in y con i coefficienti così ottenuti.

Il valore v è compreso tra 0 e 1000.

Il file di input

Il file di input ha lo stesso formato del precedente esercizio.

Il file di output

Il file di output contiene un polinomio in una sola variabile y, in un formato analogo a quello per i polinomi in due variabili 

M
A_j y^j + ... + A_l y^l

Valgono le stesse regole su coefficienti, esponenti, segni, spazi già descritte per il file di input. Il valore M è lo stesso presente nel file in input (la costante che maggiora tutti gli esponenti di y).

Implementazione in Java

In Java, il polinomio in due variabili va rappresentato usando una matrice long[][] di dimensioni opportune. Analogamente, il polinomio in una variabile può essere rappresentato usando un vettore long[] di dimensioni opportune. Tutti i calcoli sui coefficienti devono essere svolti usando long.

Anche qui non specifichiamo nessun algoritmo specifico, basta che non sia eccessivamente inefficiente (vedi sotto).

Il programma Java che dovete sviluppare dovrà contenere una funzione 

public static void polyApply(String polyFileName, long v, String polyFileNameResult)

che legge il polinomio in due variabili dal file il cui nome è passato come primo parametro, fissa il valore x=v, e scrive il polinomio a una variabile ricavato nel file che ha il nome specificato nel terzo parametro.

Come scrivere il progetto

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:

È 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 le funzioni polyMultiply() e polyApply(), e non dentro il main, in quanto quest'ultimo non verrà eseguito.

Noi testeremo le funzioni polyMultiply() e polyApply() su vari file, chiamandola ripetutamente anche in modo automatizzato, e senza eseguire il main() della vostra classe Progetto.

Consigli

Per dividere le righe del file e costruire la matrice di partenza, potrebbe essere utile usare s.split(" ") (dividi sugli spazi) su una String s. Questo genera un vettore di stringhe String[] ottenuto spezzando la stringa s sui delimitatori forniti.

Vi potrebbe essere utile usare s.substring(int a) il cui valore è la sottostringa di s che inizia dalla posizione a fino alla fine della stringa. Invece, s.substring(int a, int b) è la sottostringa di s che inizia dalla posizione a e finisce nella posizione b (esclusa).

Per convertire una String in un long, usate Long.parseLong(s).

Precondizioni

Quando la funzione viene chiamata, vi viene garantito che i file di input esistono e sono 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 usate i long per fare i calcoli i numeri in gioco non diventano così grandi (o piccoli) da non potere essere rappresentati in un long.

Un aiuto per testare il vostro codice

Per aiutarvi nel testare il vostro codice, vi mettiamo a disposizione una piccola libreria helper.

Dopo avere scaricato il file helper di sopra in una qualunque cartella, potete inserire la libreria helper nel vostro progetto Eclipse, selezionando il vostro progetto, facendo clic destro, e selezionando dal menù la voce Build Path -> Add External Archives.... Comparirà un finestra dove potete selezionare il file jar fornito sopra.

Dopo avere aggiunto la libreria helper al vostro progetto, all'interno del file Java Progetto.java potete usare le funzioni della libreria, che mostriamo sotto. Nello scheletro di progetto che vi forniamo, trovate già degli esempi su come usarle nel main(), dopo avere usato import progetto2023.Helper; (come fa già lo scheletro di codice fornito).

La libreria helper fornisce le seguenti funzioni:

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.

Requisiti e criteri di valutazione

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:

  1. Non modificate il nome della classe 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.
  2. Posizionate la classe Progetto come descritto sopra nel vostro progetto Eclipse.
  3. I file di input e output devono essere quelli passati come parametri, e non altri con un nome prefissato. Per esempio, new File(fileName) usa il parametro, mentre new File("fileName") usa un nome prefissato.
  4. Le procedure/funzioni richieste non devono interagire con l'utente in nessun modo (ad es., chiedere di inserire dati da tastiera). I nostri test devono potere chiamare ripetutamente quelle funzioni in modo automatico, senza il nostro intervento manuale. Il 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 se ritenuto 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 in tempo (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 polyMultiply() e la funzione polyApply() 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.

Efficienza in spazio (secondario). Il vostro programma deve usare una quantità ragionevole di memoria. Noi dobbiamo essere in grado di svolgere i test senza avere problemi di memoria. In caso contrario riterremo i test falliti.

Si richiede più precisamente di non allocare memoria non davvero richiesta. Non allocate vettori o matrici di dimensioni prefissate a un valore "grande", ma regolate la loro dimensione secondo i valori N e M che ci sono nei file di input.

Consegna del progetto

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.

Procedure anti plagio

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.

Verranno usati dei software anti plagio per confrontare le diverse consegne anche in appelli distinti. 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" 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.

Note Finali

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.

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.

Informatica - Teaching - Home

Valid CSS Valid XHTML 1.1 Roberto Zunino, 2023