Progetto 2024/25

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

Esercizio: un sistema elettorale con voto singolo trasferibile

Descrizione generale

L'esercizio consiste nel determinare l'esito di un'elezione in cui viene usato un sistema elettorale basato su "voto singolo trasferibile", così come descritto in questa pagina.

In questo sistema elettorale, ogni elettore vota non indicando un singolo candidato, ma elencando tutti i candidati in ordine di preferenza.

Indichiamo con N il numero dei candidati, e di conseguenza identifichiamo ogni candidato con un numero naturale da 0 a N-1.

Un voto di un elettore viene quindi rappresentato da un vettore v = [C_0, C_1, ... C_N-1] dove [C_0, C_1, ... C_N-1] è una permutazione dei numeri da 0 a N-1. Inizialmente, il voto v viene contato a favore di C_0.

Durante il conteggio dei voti, l'algoritmo può decidere di eleggere o escludere un candidato C_0. In entrambi questi casi il candidato viene considerato deciso. Quando C_0 diventa deciso, la preferenza espressa da v viene trasferita a favore del primo candidato in v ancora indeciso.

Più in generale, man mano che i voti vengono conteggiati, ogni volta che un candidato diventa deciso, tutte le preferenze a suo favore vengono trasferite a favore dei candidati ancora indecisi, secondo l'ordine indicato nei voti.

Dati in input

Per poter determinare il risultato dell'elezione, si ricevono in input i seguenti dati:

Ogni riga della matrice listaVoti rappresenta un singolo voto, che elenca tutti i candidati in ordine di preferenza.

Per esempio, considerando un'elezione tra 3 candidati, la seguente matrice listaVoti indica le preferenze di 4 elettori: 

                  1, 0, 2
                  0, 2, 1
                  0, 1, 2
                  0, 2, 1

In particolare, il vettore listaVoti[0] = [1,0,2] rappresenta il voto di un singolo elettore: questo elettore ha il candidato 1 come prima preferenza, seguita dal candidato 0, e infine dal candidato 2.

Peso dei voti

A ogni voto è associato un peso, che rappresentiamo con un double. Inizialmente ogni voto ha peso pari a 1.0, e viene contato a favore del candidato indicato come prima preferenza.

Quando il voto viene trasferito a causa di un candidato che diventa deciso in quanto eletto, il peso dei voti che hanno contribuito ad eleggerlo viene diminuito, decurtandone una parte. Il metodo in cui questo avviene è dettagliato sotto.

Quando invece il voto viene trasferito a causa di un candidato che diventa deciso in quanto escluso, il peso dei voti che erano a suo favore rimane invariato.

Algoritmo per il conteggio dei voti

Inizialmente viene stabilita una quota, ovvero un valore double pari al numero di voti pesati necessari a un candidato per essere eletto. La quota viene fissata a 

  S / (listaVoti.length + 1)

Si inizializza un vettore int[] eletti nel quale verranno memorizzati i candidati eletti.

L'algoritmo continua ripetendo i passi seguenti fino a quando S candidati non sono stati eletti.

  1. Si trova il candidato cMax con più voti, opportunamente pesati. Più precisamente, per ogni candidato si sommano i pesi dei voti a suo favore, ottenendo così il suo peso totale. Il candidato con peso totale massimo viene quindi scelto. In caso di parità, viene scelto il candidato che è rappresentato dall'intero minore.
  2. In modo analogo, si trova il candidato cMin con meno voti, opportunamente pesati. (Nota che qui in caso di parità viene preso il candidato che è rappresentato dall'intero maggiore.)
  3. Se il peso totale di cMax supera la quota, allora il candidato cMax diventa eletto (e quindi anche deciso). I voti a favore di cMax hanno il loro peso decurtato secondo il metodo dettagliato sotto. Infine, le preferenze a favore di cMax nei voti sono trasferite al prossimo candidato ancora indeciso seguendo l'ordine di ogni voto. Il candidato cMax viene aggiunto in coda al vettore eletti.
  4. Se invece il peso totale di cMax non supera la quota, allora cMin (nota bene: non cMax) diventa escluso (e quindi anche deciso). Infine, le preferenze a favore di cMin nei voti sono trasferite al prossimo candidato ancora indeciso seguendo l'ordine di ogni voto.

Il risultato di questo algoritmo è il vettore eletti, che elenca tutti i candidati eletti nell'ordine in cui sono stati dichiarati tali.

Decurtazione dei pesi

Dopo che un candidato è stato eletto, occorre ridurre il peso dei voti che hanno contribuito alla sua elezione. Complessivamente, il peso totale viene ridotto di un valore pari alla quota. Questa decurtazione viene divisa sui singoli voti in base alla "regola dell'istogramma".

Consideriamo un istogramma che mostri i pesi dei singoli voti, come quello in figura sotto. Tracciamo una riga orizzontale ad altezza h in modo tale che, prendendo la parte delle barre sotto la linea, e sommando la loro lunghezza, si ottiene il valore quota.

Ogni peso maggiore di h viene quindi diminuito del valore h, mentre gli altri vengono azzerati.

Per esempio, qui sotto mostriamo i pesi prima della decurtazione, e la linea orizzontale derivante da quota=6.0, che ha conseguente altezza h=0.74.

istogramma prima della decurtazione

Dopo la decurtazione, i nuovi pesi diventano come segue. In pratica, il nuovo istogramma diventa la parte superiore alla linea orizzontale.

istogramma dopo la decurtazione

Formalmente, l'altezza h viene fissata in modo tale da rendere vera la formula 

  quota = ∑i min(h, peso[i])

Consigli

Si consiglia di usare un vettore boolean[] deciso per segnare quali candidati hanno avuto il loro esito deciso.

Si consiglia di usare un vettore double[] peso per segnare il peso di ogni voto.

Si consiglia di usare un vettore int[] preferenza per segnare, per ogni voto, la posizione della preferenza corrente (che aumenterà quando il candidato riferito diventa deciso).

Implementazione in Java

Il programma Java che dovete sviluppare dovrà contenere una funzione 

public static int[] calcolaEletti(int candidati, int seggi, int[][] listaVoti)

che calcola il vettore degli eletti in base ai dati forniti.

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 la funzione calcolaEletti(), e non dentro il main, in quanto quest'ultimo non verrà eseguito.

Noi testeremo la funzione calcolaEletti() su vari input, chiamandola ripetutamente anche in modo automatizzato, e senza eseguire il main() della vostra classe Progetto.

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à una 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 progetto2024.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. 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. Siccome il progetto di questo anno fa uso di variabili double, e quindi è potenzialmente soggetto a errori di arrotondamento numerico, verrà tollerata una percentuale molto piccola di risultati errati.

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 calcolaEletti() 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 dati in 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. Ci riserviamo la possibilità di convocarvi per un colloquio sul codice che avete consegnato, anche dopo l'esame scritto, sia nel caso ci siano dubbi sull'autenticità del progetto o per effettuare verifiche a campione.

In caso di plagio, manifesto o accertato, verranno presi provvedimenti, che potranno anche andare oltre il semplice annullamento della prova d'esame.

Si sottolinea che non è solo vietato copiare il codice da altri, ma anche condividere il proprio progetto con altri, anche dopo che l'esame è stato superato e verbalizzato. Anche dopo la verbalizzazione potranno essere presi provvedimenti.

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, 2024