Roberto Zunino, 2018
Questa pagina descrive il progetto per il corso di Informatica della Laurea in Matematica per le sessioni dell'anno accademico 2018/2019.
Il progetto è costituito da due mini-esercizi.
Un automa cellulare (unidimensionale) è un modello rudimentale per descrivere l'evoluzione di un insieme di celle, disposte su una riga. Per esempio,
###--#---#-----#---#---##-##-#-#--#-##-###-#--##---###-##-#-##-#-#--#####-##-##-
rappresenta uno stato dell'automa, in cui alcune celle sono
"vive" (#) e altre sono "morte" (-).
Da uno stato come quello sopra può essere generato uno stato
successivo, seguendo una regola che varia da automa a automa.
Una regola è una funzione che definisce se la cella numero i
nel nuovo stato è viva in funzione delle celle numero
i-1,i,i+1 nel vecchio stato.
Quindi, una regola è una funzione definita su 8 casi (i possibili valori
di tre celle) a valori booleani (vivo/morto).
Possiamo rappresentare una regola come segue:
--- ==> r_0 --# ==> r_1 -#- ==> r_2 -## ==> r_3 #-- ==> r_4 #-# ==> r_5 ##- ==> r_6 ### ==> r_7
dove r_0,...,r_7 sono booleani
(true/#/1/vivo oppure false/-/0/morto).
Sotto queste ipotesi, ci sono esattamente 256 regole possibili.
Per convenzione, le regole si numerano da 0 a 255 come se
i booleani r_i fossero le cifre binarie di un numero
(somma per i che va da 0 a 7 di 2^i * r_i).
Per esempio, la regola 110 (in binario 01101110) è la funzione
--- ==> - --# ==> # -#- ==> # -## ==> # #-- ==> - #-# ==> # ##- ==> # ### ==> -
Applicando la regola ripetutamente allo stato iniziale di sopra, si ottiene la seguente evoluzione. Ogni stato/riga viene ricavato applicando la regola allo stato/riga sovrastante.
###--#---#-----#---#---##-##-#-#--#-##-###-#--##---###-##-#-##-#-#--#####-##-##- #-#-##--##----##--##--##########-#######-###-###--##-#############-##---#######- ######-###---###-###-##--------###-----###-###-#-#####-----------####--##-----#- #----###-#--##-###-####-------##-#----##-###-#####---#----------##--#-###----##- #---##-###-#####-###--#------#####---#####-###---#--##---------###-####-#---###- #--#####-###---###-#-##-----##---#--##---###-#--##-###--------##-###--###--##-#- #-##---###-#--##-######----###--##-###--##-###-#####-#-------#####-#-##-#-#####- ####--##-###-#####----#---##-#-#####-#-#####-###---###------##---##########---#- #--#-#####-###---#---##--#######---#####---###-#--##-#-----###--##--------#--##- #-####---###-#--##--###-##-----#--##---#--##-###-#####----##-#-###-------##-###- ###--#--##-###-###-##-####----##-###--##-#####-###---#---#######-#------#####-#- #-#-##-#####-###-######--#---#####-#-#####---###-#--##--##-----###-----##---###- ########---###-###----#-##--##---#####---#--##-###-###-###----##-#----###--##-#- #------#--##-###-#---#####-###--##---#--##-#####-###-###-#---#####---##-#-#####- #-----##-#####-###--##---###-#-###--##-#####---###-###-###--##---#--#######---#- #----#####---###-#-###--##-#####-#-#####---#--##-###-###-#-###--##-##-----#--##- #---##---#--##-#####-#-#####---#####---#--##-#####-###-#####-#-######----##-###- #--###--##-#####---#####---#--##---#--##-#####---###-###---#####----#---#####-#-
Si chiede di scrivere una funzione Java che,
dato il numero corrispondente alla regola,
uno stato iniziale (vettore di booleani), e un numero di passi
N, calcoli lo stato finale (vettore di booleani)
che si raggiunge dopo avere applicato la regola N
volte (quindi corrispondente allla riga numero N
nell'esempio sopra, iniziando a contare da 0).
Alcune precisazioni:
N è un naturale.
(Se N=0, lo stato finale è uguale a quello iniziale.)
>=0.
Lo stato finale ha la stessa dimensione. (Si noti che i due vettori
possono avere dimensione zero.)
false).
Si chiede di scrivere una funzione Java avente (esattamente) nome e tipo come segue:
public static boolean[] cellularAutomaton(int ruleNum, boolean[] initialState, int steps)
I parametri indicano, in ordine: il numero della regola, lo stato iniziale delle celle, il numero di passi da eseguire.
Come risultato, deve essere restituito un vettore di booleani contenente il nuovo stato ottenuto applicando la regola tante volte quanto il numero di passi fornito.
Il vettore di input initialState non deve essere modificato
dalla funzione.
In caso di input malformato (per esempio, numero della regola 364, o numero di passi -43), non si richiede nessun comportamento particolare. Il programma può dare un risultato qualunque, o anche generare un errore a tempo di esecuzione.
Dati due numeri naturali positivi, di grandezza arbitraria, si chiede di calcolare il loro prodotto.
Si chiede di scrivere una procedura Java che legga da un file i due fattori, e che scriva in un altro file il prodotto. Tutti i naturali, sia quelli in input che quello in output, sono espressi come sequenza di cifre decimali.
Si chiede di scrivere una procedura Java avente (esattamente) nome e tipo come segue:
public static void multiplication(String inFileName, String outFileName)
Alla funzione viene passato un nome di file inFileName
che è garantito esistere, e contenere due righe di testo con i due
fattori naturali positivi. Per esempio:
1234567890123456789012345678901234567890 987654321098765
I naturali possono avere un numero arbitrario di cifre.
Pertanto, non si può assumere che possano essere memorizzati
in una variabile int o long di Java.
La procedura multiplication deve leggere i due
fattori sopra, e scrivere un'unica riga nel file il cui nome
corrsiponde al parametro outFileName. Per esempio:
1219326311370217418792871741879287174187806784787655850
I numeri nei file di input sono espressi in notazione decimale, con prima cifra diversa da zero. Nel file di output devono essere scritti nello stesso modo.
Nota bene: i nomi dei file non sono prefissati, ma passati
come parametri. All'interno della procedura multiplication
non si può quindi aprire file di nome, per esempio,
"input.txt" o "output.txt".
È tassativamente vietato l'uso di librerie di Java che implementino la moltiplicazione o l'addizione su un numero di cifre arbitrario, in quanto renderebbero banale l'esercizio.
In caso di errore di IO (per esempio, il nome di file passato come argomento non corrisponde a nessun file) o di input malformato (per esempio, meno di due righe nel file), non si richiede nessun comportamento particolare. Il programma può dare un risultato qualunque, o anche generare un errore a tempo di esecuzione.
Potete tenere memorizzati i numeri come String
e fare eseguire la moltiplicazione come si farebbe a mano "in colonna",
cifra per cifra. Alternativamente, è possibile convertire le stringhe
in vettori di cifre int, usare tali vettori per la
moltiplicazione "in colonna", e poi scrivere su file le cifre del
risultato. Fate attenzione a non inserire numeri a due o più cifre
dentro il vettore, se questo creasse problemi al vostro algoritmo!
Si chiede di scrivere una singola classe Java
Progetto, che contenga entrambe le procedure/funzioni
cellularAutomaton, multiplication
descritte sopra. In particolare, è
obbligatorio
usare come base per il progetto un progetto Eclipse
contenente il il seguente scheletro di di classe Java.
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 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 (a parte, come detto
sopra, quelle per la moltiplicazione/addizione).
È 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
relative ai due esercizi, e non dentro
il main, in quanto quest'ultimo non verrà eseguito.
Durante la correzione, le funzioni relative agli esercizi verranno chiamate ripetutamente eseguendo (anche) test automatizzati.
Per potere testare più facilmente il vostro progetto, vi viene fornita la seguente libreria Java.
Dopo avere scaricato il file di sopra in una qualunque cartella,
potete inserire la libreria tester 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 tester 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 progetto2018.Tester;
all'inizio del file.
boolean Tester.testCellularAutomaton( int ruleNum
, boolean[] initialState
, int steps
, boolean[] finalState )
boolean Tester.testMultiplication( String inFileName
, String outFileName )
La funzione Tester.testCellularAutomaton
prende come parametri il numero della regola
di un automa cellulare, lo stato iniziale, il numero di passi,
e uno stato finale. Restituisce true
se gli input sono validi e se lo stato finale è quello corretto.
Altrimenti restituisce false e stampa un messaggio
di errore con alcune informazioni.
Analogamente, Tester.testMultiplication
prende come parametri due nomi di file, li legge entrambi,
aspettandosi due fattori nel file di input (uno per riga),
e un prodotto del file di output. Se il prodotto è corretto,
restituisce true, altrimenti restituisce false
e stampa un messaggio di errore.
Usare il tester non è obbligatorio (anche se raccomandato).
Se non lo volete usare, per potere compilare lo scheletro
dovete rimuovere dal file sia la riga
import progetto2018.Tester;
che tutti i riferimenti alle funzioni Tester.
Nota bene: se usate il tester su un po' di casi, e su quelli non rileva problemi, questo non vuol dire che il vostro programma sia corretto. È possibile che, in fase di valutazione del progetto, vengano controllati altri casi, e che su questi si scopra che il programma non funziona. In altre parole: con i test possiamo solo dimostrare che un programma è scorretto, ma mai che è corretto.
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.
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.
Progetto come descritto
sopra nel vostro progetto eclipse.
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
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.
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.
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);
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.
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 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.
Informatica - Teaching - Home
Roberto Zunino, 2018