|
|
Università
|
Diploma in Ingegneria Informatica
|
A.A. 2001/2002
Si realizzi una nuova versione della classe FI2.Examples.Point che fornisca gli stessi metodi pubblici di quella originaria ma che memorizzi le componenti x e y del punto in un vettore di 2 elementi double.
Si realizzi la classe Misure che memorizza in un campo floating point val il valore di una grandezza e nel campo unit la relativa unità di misura come stringa. Prevedere per la classe:
Si definisca la classe SpLine che rappresenta una spezzata sul piano costituita da un numero arbitrario di N lati. La spezzata è definita dagli N+1 punti che sono i successivi estremi dei lati. Memorizzare tali punti in un array di FI2.Examples.Point, fissando l'estensione N+1 al momento della costruzione di un'istanza. Definire, oltre ai costruttori, i seguenti metodi: NEdge restituisce il numero di lati, Edge restituisce le coordinate dei due punti estremi dell'i-esimo lato (1<=i<=N), Length restituisce la lunghezza come somma delle lunghezze dei lati, IsClosed restituisce true se la spezzata è chiusa (l'ultimo punto coincide con il primo), toString restituisce la sequenza delle coordinate degli N+1 punti.
Si definisca la classe NumeroNaturale atta a rappresentare un numero naturale n con 0<=n<=10 miliardi. La classe dispone dei seguenti metodi:
Con riferimento all'esercizio 1.4 e volendo definire una analoga classe ma per i numeri interi i con -10 miliardi<=n<=10 miliardi, si risponda, giustificando la risposta, alle seguenti domande:
Si definisca la classe Lampadina che include:
Con riferimento alla classe Lampadina dell'esercizio 1.6, si effettuino modifiche successive, e per ciascuna il relativo collaudo, per ottenere rispettivamente quanto segue:
| passo | lampadine accese |
|---|---|
| 1 | 0 - 3- 6 - 9 ... |
| 2 | 1 - 4 - 7 - 10 ... |
| 3 | 2 - 5 - 8 - 11 ... |
Realizzare la seguente successione di classi collegate, a seconda dei casi, da una relazione isA o hasA:
Con riferimento alla classe Misure dell'esercizio 1.2, si derivi da essa una classe NLMisure che è in grado di gestire misure di lunghezza normalizzate. Precisamente, sono ammesse come unità le misure mm, cm, dm, m, dam, hm, km; se possibile (valore non troppo piccolo o troppo grande), la misura viene normalizzata in modo che il suo valore sia nel range 1<=val<10, adattandone l'unità di misura, oppure 0 e unità metri. A questi scopi, la classe include, oltre ai costruttori:
Si realizzi nel metodo statico main di una classe Replace una funzione di sostituzione di stringhe. Il metodo contiene un ciclo indefinito che chiede, ricevendoli da stdin nell'ordine, il nome di un file di ingresso, che tenterà di aprire (salvo visualizzare un messaggio d'errore in caso di fallimento e riciclare), una stringa da cercare e una da sostituire alla prima. Il metodo entra in un ciclo interno ove cerca più volte la stringa nel file di ingresso aperto, assunto come file di testo, e produce un file di output temporaneo che è una copia del primo salvo le occorrenze della stringa cercata che vengono sostituite con quella di rimpiazzo. La sostituzione ha luogo, su ciascuna occorrenza, solo dopo aver visualizzato su stdout la riga che la contiene e una evidenziazione della sua posizione nella riga e dopo aver chiesto e ottenuto il relativo consenso all'utente da stdin. Terminato il file di ingresso, si esce dal ciclo interno, il file di ingresso viene cancellato e quello temporaneo di uscita rinominato con il nome di quello d'ingresso. Quando il programma attende il nome del file, si può uscire dal ciclo esterno impostando la stringa $exit; quando attende un consenso di sostituzione, si può uscire dal ciclo interno con la stringa $nomore (il resto del file d'ingresso viene copiato su quello di uscita prima di uscire dal ciclo), oppure con $abort (il file di ingresso rimane immodificato), sia da quello interno che da quello esterno con la stringa $exit.
Utilizzando il costrutto switch di Java, realizzare un metodo di generazione automatica di stringhe gens che riceve come parametri un carattere-selettore sel e un intero val. Se il selettore è pari a 'a', il metodo deve restituire una stringa di lunghezza 6 i cui caratteri sono generati casualmente; se pari a 'b', deve restituire una stringa di caratteri generati casualmente ma di lunghezza pari al parametro val; se pari a 'c', deve restituire la stringa che esprime la rappresentazione esadecimale del valore del parametro val; in tutti gli altri casi, deve generare una stringa di 6 caratteri eguali pari a sel.
Calcolare con il metodo statico tabRow della classe Pitagora una riga della tabella pitagorica: a tale scopo il metodo riceve nel parametro row il fattore (1..n) che identifica la riga e nel parametro lastCol il fattore (1..m) dell'ultima colonna, e restituisce come valore di ritorno la riga indicata sottoforma di array di valori interi. Sovraccaricare il metodo con una versione analoga ma che restituisce un array di oggetti wrapper Integer. Gestire opportunamente le impostazioni errate dei parametri.
Si realizzi la classe CacheArray che ha un metodo cache che riceve come parametro un array generico di Object di lunghezza arbitraria e restituisce egualmente un array generico di Object. Il metodo copia l'array ricevuto come parametro in una copia interna, restituendo come ritorno un riferimento all'array precedentemente conservato. La classe include un costruttore base che, salvo il ritorno, ha un effetto analogo a cache, e i metodi get e set che ricevono un parametro intero idx e che consentono, rispettivamente, di restituire, come valore di ritorno, e di modificare, con il valore di un secondo parametro val di tipo Object, l'elemento di indice idx dell'array correntemente memorizzato.
Si definisca l'interfaccia Wrapper che preveda un metodo wrap per ciascun tipo base che ritorna un oggetto di tipo Wrapper incapsulando il valore passato come parametro, e un metodo get che restituisce, sottoforma di Object, il valore incapsulato. Successivamente si realizzi una implementazione dell'interfaccia Wrapper con la classe StrWrap che preveda di memorizzare il valore incapsulato sottoforma di un qualificatore di tipo (la cui codifica è fissata dalla classe StrWrap stessa) e da una stringa che rappresenta il valore in un formato opportuno a seconda del tipo. In StrWrap i metodi wrap creano un nuovo oggetto inizializzato secondo specifiche e ne restituiscono il riferimento, il metodo get restituisce un oggetto di una classe wrapper di Java adeguata al tipo incapsulato. Aggiungere alla classe StrWrap il metodo toSTring e un metodo main di collaudo
Dovendo implementare l'interfaccia java.util.Enumeration (analoga a FI2.Util.ObjectIterator) per una gerarchia di classi-contenitori che implementano l'interfaccia Sizeable utilizzando un array indicizzabile di dimensione non fissa, si realizzi una classe astratta IndexedEnum che implementa il metodo hasMoreElements mantenendo un indice corrente e sfruttando l'unico metodo size dell'interfaccia Sizeable. Definire una classe ArrayCollection che memorizza in un array di int un set di interi (di numero massimo fissato alla costruzione) che implementa Sizeable e che include una classe anonima locale al metodo elements che estende IndexedEnum per restituire un enumeratore per un oggetto di classe ArrayCollection. Il metodo nextElement della classe anonima restituisce uno dopo l'altro i valori memorizzati nell'array, incapsulati in oggetti wrapper di classe Integer.
Definire la classe CircQueue che realizza gli stessi metodi della classe FI2.Linear.LinkedQueue, utilizzando, diversamente da quest'ultima, una lista concatenata circolare con un nodo che fa da sentinella. La coda è rappresentata in astratto da un riferimento alla sentinella che segue il suo ultimo nodo e precede, circolarmente, il primo.
Utilizzare una implementazione dello stack per rappresentare i movimenti dei dischi dei tre pioli di una Torre di Hanoi con N dischi iniziali.
Estendere l'interfaccia Queue con l'interfaccia MQueue che prevede una versione overloaded di enqueue che riceve come parametro aggiuntivo un fattore di permanenza mult. L'elemento inserito ha associato un 'contatore di servizi' che viene decrementato ad ogni sua 'estrazione'. Un'estrazione normale lo rimuove definitivamente (indipendentemente dal valore corrente del contatore); un'estrazione multipla restituisce l'oggetto ma non lo estrae, decrementando il contatore; un'estrazione con riaccodamento lo estrae dalla testa, decrementa il contatore e lo riaccoda (in coda). I tre tipi di estrazione sono rappresentati da altrettanti metodi dequeue overloaded. Implementare l'interfaccia MQueue con la classe ArrayMQueue (eventualmente come estensione di ArrayQueue) e con la classe LinkedMQueue (eventualmente come estensione di LinkedQueue).
Definire la classe EArrayQueue ottenuta mediante modifica della classe ArrayQueue tale da poter estendere la prima con la classe ArrayBiQueue che implementa sia l'interfaccia Stack che quella Queue (nella realizzaione si riduca al minimo il codice della classe ArrayBiQueue rispetto a quello ereditato da EArrayQueue).
Realizzare una forma non grafica del 'gioco del 15' in cui le 16 posizioni del quadrato sono rappresentate dagli indici 1..16 in un ArrayList e i tasselli da 16 elementi di cui uno speciale come 'elemnto vuoto'. Implementare la primitiva di movimento che fa uso del metodo 'posizionale' swap secondo le regole del gioco. Un metodo toString provvede a restituire una forma visualizzabile dello stato del quadrato di gioco.
Modificare l'esempio FI2.Tree.Calculator in modo che la costruzione dell'albero astratto adotti la rappresentazione figlio a sinistra - fratello anziché quella con i due figli. Allo scopo si definisca una classe per questo tipo di rappresentazione degli alberi.
Si utilizzi un dizionario basato su tabella hash per memorizzare circa 1000 codici fiscali. Studiare una funzione hash ragionevole e una opportuna rappresentazione del codice fiscale.
Si utilizzi un dizionario basato su lista concatenata ordinata ove la chiave è costituita da un istante temporale (data e istante con precisione del minuto) ove è previsto il verificarsi di un evento descritto da una stringa associata all'istante temporale. Il dizionario consente l'inserimento di nuovi eventi e l'aggiornamento delle descrizioni degli eventi non ancora scaduti. Prevedere il metodo clock() che fornisce la base temporale (viene chiamato dall'esterno ogni minuto) e che provvede anche a rimuovere gli eventi scaduti.
Si scelga uno degli ordinamenti su vettore illustrati nell'esempio FI2.Sorting.ArraySort e si costruisca la classe Rubrica che memorizza una rubrica di tipo telefonico, ove ogni elemento è rappresentato da una stringa cognome, una stringa nome e un numero telefonico. Si mantenga alfabeticamente ordinata la rubrica utilizzando il metodo scelto nel senso che ogni inserimento avviene dopo l'ultimo elemento già presente e si procede poi ad un riordinamento. Si tenga presente che in caso di cognome eguale, l'ordine è basato sul nome e in caso di omonimia completa, è basato sul numero telefonico. Progettare e realizzare tutti i metodi che si ritengono utili, evitando un uso scorretto delle informazioni (attraverso l'usuale controllo della visibilità dei membri della classe).
Definito stabile un algoritmo che mantiene eguali, dopo l'ordinamento, le posizioni relative che due elementi con la stessa chiave hanno prima dell'ordinamento, stabilire per ogni algoritmo realizzato nella classe FI2.Sorting.ArraySort la condizione di stabilità. Si verifichi quanto affermato effettuando l'ordinamento con i vari metodi di un array di oggetti che contengono, come chiave un carattere compreso tra 'A' e 'F' che identifica una classe di appartenenza, come dato-satellite una stringa. Più dati possono appartenere alla stessa classe.
Similmente all'esercizio 6.1, si estenda la classe FI2.Linear.ArraySequence nella classe Rubrica con un opportuno metodo di sorting al fine di gestire, mantenendola ordinata, una rubrica telefonica. Definire nella classe Rubrica un metodo di collaudo che realizzi una semplice interfaccia utente (usando STDIN/STDOUT): tale interfaccia consente il caricamento di dati iniziali da un file, l'aggiornamento manuale dei dati (ricerca, modifica, cancellazione, aggiunta), il salvataggio sul file della rubrica.
1^ prova
Realizzare la classe RisultatoPartita che memorizza il risultato di una partita di calcio. Le specifiche di dettaglio sono le seguenti:
· Un vettore di 2 stringhe (squadre) è utilizzato per memorizzare i nomi delle 2 squadre.
· Un vettore di 2 interi (reti) è utilizzato per memorizzare le rispettive reti.
· È definito un costruttore che riceve i due parametri stringa squadra1 e squadra2 e i 2 interi reti1 e reti2, di ovvio significato.
· È definito un altro costruttore che riceve solo i due parametri stringa: per default il risultato è 0-0.
· È definito un metodo di lettura della squadra (squadra(...)) che riceve il parametro stringa quale, che può valere "prima" o "seconda"; il metodo restituisce il corrispondente nome della squadra. Si gestisca in modo ragionevole un parametro illegale.
· È definito un metodo di lettura delle reti (reti(...)) che riceve il parametro stringa quale, similmente al metodo squadra();il metodo restituisce il corrispondente valore delle reti segnate dalla squadra.
· È definito il metodo toString() che fornisce la stringa con il risultato completo.
Estendere la classe RisultatoPartita con la classe RisultatoSchedina che include:
· due costruttori analoghi a quelli della classe RisultatoPartita;
· il metodo valore() che restituisce il valore 1 oppure X oppure 2 (adottare allo scopo una ragionevole convenzione per rappresentare i 3 valori) calcolato sulla base del risultato della partita;
· il metodo toString(), analogo a quello di RisultatoPartita, a cui viene aggiunto il valore 1-X-2.
Realizzare infine un segmento di codice che alloca un vettore schedina di 10 elementi di tipo RisultatoSchedina e lo inizializza mediante un ciclo for che a questo scopo utilizza un metodo (accessibile) Acquisisci(), privo di parametri. Ad ogni chiamata di Acquisisci() viene restituita una stringa; le chiamate successive forniscono, una dopo l'altra, il nome della prima squadra del primo risultato, poi quello della seconda squadra, poi le reti della prima squadra, poi le reti della seconda, e poi si passa alla analoga sequenza per il secondo risultato, per il terzo, ecc.. Si supponga il metodo Acquisisci() già realizzato.
Per la realizzazione, si ricordi quanto segue: int Integer.parseInt(Stringa stringaValoreDecimale); consente di convertire una stringa nel corrispondente valore intero String String.valueOf(int valoreIntero); effettua la conversione opposta.
Si realizzi la classe GeoPoint che rappresenta una posizione geografica in coordinate longitudine/latitudine (ad esempio [35D 45’ W, 12D 0’ S] ove D sta per gradi e ’ per primi). Ogni GeoPoint memorizza i 4 valori numerici delle coordinate (gradi e primi) in altrettanti attributi per valori naturali, e le sigle di verso (W o E, N o S) in due attributi di tipo char. La classe GeoPoint prevede un costruttore di default, un costruttore di base (con opportuni parametri), un metodo toString() per la conversione a stringa e un metodo dist il cui prototipo è:
public int[] dist(GeoPoint snd);
e che restituisce nelle due componenti del valore di ritorno, nella prima, la distanza (assoluta, funzione
Math.abs(x)) misurata in primi sulla longitudine (differenza nel senso W-E) tra i due punti rappresentati da this e dal parametro snd, nella seconda, la distanza sempre tra i due punti misurata in primi sulla latitudine (differenza nel senso N-S). Ad esempio:7D 41’ W ÷ 12D 24’ W = |461’ - 744’| = 283’
12D 13’ S ÷ 26D 7’ N = 733’ + 1567’= 2300’
(cioè il calcolo diventa una somma se i versi non sono concordi).
Si implementi quindi l’interfaccia
EnumerableContainer:public interface EnumerableContainer
{
int size();
boolean isEmpty();
Enumeration elems(Object select);
}
con la classe Route che memorizza in un array, di dimensione fissata alla costruzione, un insieme di n GeoPoint che ordinatamente rappresentano i vertici di un percorso di (n-1) tratte rettilinee. La classe Route, oltre al costruttore base, prevede un metodo insert per aggiungere, uno dopo l’altro, gli n punti; il metodo deve sollevare l’eccezione FullArrayException (la cui definizione non è richiesta) se si tenta un inserimento ad array già pieno. Il metodo elems prevede un parametro di classe Boolean e l’enumeratore restituito effettua una visita dei punti in ordine di inserimento se tale parametro ha valore true, in ordine inverso se false.
Il concetto matematico di norma (||x|| norma di x) estende quello di lunghezza. In questo senso si realizzi quanto sotto richiesto.
1) L’interfaccia Normato che include i seguenti 5 metodi:
distanza(this, altro) º ||this - altro||
(l’operatore – corrisponde al metodo diff)2) La classe astratta NormaBase che implementa parzialmente l’interfaccia Normato realizzando i soli metodi norma 2^ variante, seNormaZero e distanza sulla base delle specifiche dei metodi norma 1^ variante e diff;
3) La classe FuncNormato che estende NormaBase e che implementa Normato con la realizzazione dei due rimanenti metodi dell’interfaccia, norma 1^ variante e diff. Data l’interfaccia:
interface FuncDesc { int f(int x); }
la classe
FuncNormato memorizza, in un attributo fdesc di tipo FuncDesc, un oggetto di una classe (non importa quale) che implementa l’interfaccia FuncDesc stessa. La classe FuncNormato memorizza inoltre in un attributo valNorma il valore della norma di this calcolato una-tantum nella fase di costruzione. Definire nella classe FuncNormato:public class DiffFunc implements FuncDesc
{
private FuncDesc fd1, fd2;
public DiffFunc(FuncDesc f1, FuncDesc f2)
{
fd1 = f1; // memorizza i descrittori
fd2 = f2;
}
public int f(int x)
{
return fd1.f(x) – fd2.f(x);
// calcola la differenza delle funzioni
}
}
(l’oggetto tornato consente di definire una funzione che calcola la differenza tra le funzioni associate a this ed ad
altro).Promemoria:
Integer.MIN_VALUE, Integer.MAX_VALUE
valori minimo e massimo per una variabile di tipo int.2^ prova
public interface Ordered
{
boolean isGT(Ordered obj2); // maggiore
boolean isGE(Ordered obj2); // maggiore o eguale
}
Qual è la complessità dell'algoritmo? Perché conviene utilizzare
la ricerca binaria?
3^ prova
Domanda 1 Su uno stack realizzato mediante vettore
Risp.A si puo` sempre eseguire un pop ma non sempre un push.
Risp.B e` sempre possibile verificare se un successivo push fallira` o meno.
Risp.C si puo` sempre eseguire un push ma non sempre un pop.
Risp.D si puo` eseguire un push a patto che subito prima si possa eseguire un pop.
Domanda 2 Usando una notazione a parentesi (^ nodo assente, i nodi all'interno dello stesso livello di parentesi sono fratelli), un valido albero di ricerca binario con chiavi intere puo` avere il contenuto
Risp.A 12 (6 (^ 8 (7 11)) 14)
Risp.B 12 (8 (6 13) 14(^ 17))
Risp.C 12 (6 (4 8 (^ 7)) 14)
Risp.D 12 (6 (8 (7 11) ^) ^)
4^ prova
Si voglia realizzare in Java la classe VList che implementa, utilizzando un unico vettore pool, un insieme di code. Ogni coda è realizzata in forma concatenata nel modo sotto descritto, e i suoi nodi sono rappresentati da elementi di classe VListNode. Tutti i nodi che formano le varie code sono contenuti nel vettore pool, che è di dimensione n. La classe VListNode include:
· un intero key che rappresenta una chiave di ordinamento;
· un oggetto el di classe Dati che rappresenta i dati-satellite;
· un intero next che rappresenta l'indice dell'elemento del vettore che costituisce il nodo successore nella lista, oppure -1 se non ha successore.
Una coda è quindi costituita da un nodo di testa che, attraverso il campo next, riferisce il successivo nodo mediante il suo indice all'interno del vettore; questo a sua volta riferisce, mediante indice, il suo successore, e così via. L'ultimo nodo della coda ha il campo next pari a -1. Una coda viene rappresentata in astratto da un intero (da qui in avanti denotato come handle), che è l'indice nel vettore del nodo in testa, oppure dal valore -1 se la coda è vuota.
La classe VList include:
· un costruttore che alloca il vettore pool di n VListNode e lo organizza come un serbatoio (pool) di nodi liberi (cioè non inclusi in alcuna coda): per far questo, imposta opportunamente il campo next degli elementi in modo che la sequenza di nodi liberi costituisca una unica lista di n elementi concatenati;
· un metodo privato newEl che alloca un elemento estraendolo dalla testa della lista serbatoio (se si interpreta la lista-serbatoio come uno stack, questa operazione equivale ad un pop) restituendone l'indice;
· un metodo privato freeEl che dealloca un elemento reinserendolo in testa alla lista serbatoio (se si interpreta la lista-serbatoio come uno stack, questa operazione equivale ad un push);
· un metodo newQue che ritorna l'handle di una coda vuota;
· un metodo insert che riceve l'handle di una coda (assunta naturalmente con nodi interni all'oggetto this di classe VList oppure vuota), una chiave e un dato e li copia in un nodo che viene allocato dal pool e successivamente inserito nella coda; adottare per l'inserimento, se possibile, una metodologia che faciliti la ricerca; il metodo restituisce il nuovo handle della coda;
· un metodo extract che estrae un elemento dalla coda, lo dealloca e restituisce al chiamante chiave e dati dell'elemento estratto e il nuovo handle della coda;
· un metodo search che effettua una ricerca per chiave nella coda e, se trovata, restituisce un riferimento ai dati-satellite associati, null altrimenti.
Realizzare inoltre una classe di prova con un metodo test che riceve in ingresso una successione di terne rappresentate da due stringhe e un valore intero: ciascuna stringa rappresenta l'etichetta del nodo di un grafo, mentre il valore intero è il peso dell'arco che collega i due nodi della terna. Definire opportunamente la classe Dati per memorizzare, con una coda in un oggetto VList, la successione di terne, inserendo queste ultime nella coda nell'ordine fornito. Produrre infine su standard output il numero di archi che hanno per peso il minimo dei pesi della successione di terne, assieme al valore di tale peso.
Data la seguente interfaccia, definita nel package
Temi:public interface InspectableTable extends FI2.Set.InspectableKeyBasedContainer
{
public static Object NOT_FOUND = new String ("Not found!");
public Object find(Object key);
// cerca l’elemento di chiave key e, se trovato,
// ne restituisce l’oggetto-dati associato; l’oggetto NOT_FOUND altrimenti
public Object firstKey();
// restituisce la chiave dell’elemento che verrebbe estratto per primo, o
// l’oggetto NOT_FOUND se la struttura dati e’ vuota
} //{i} InspectableTable
Si implementi tale interfaccia con la classe
StackTab, definita nel package Temi e che estende la classe ArrayStack. Quest’ultima è una versione modificata della classe FI2.Linear.ArrayStack ove la definizione di tutti i campi originariamente private è stata trasformata in protected in modo da essere estensibile (non realizzare la classe ArrayStack , la si assuma già disponibile e definita nel package Temi).Per la realizzazione della classe
StackTab si tengano presenti i seguenti dettagli:void push(Object key, Object data);
(
inserisce la coppia chiave/dato come nuovo elemento sul top dello stack);FI2.Set.Item pop(int dummy);
(
restituisce, in un oggetto Item , chiave e dato dell’elemento estratto; il parametro serve per evitare l’overriding con la stessa firma)i due metodi devono essere realizzati fruendo degli omonimi metodi della classe
ArrayStack;La classe
StackTab includa anche un metodo main di collaudo che, dopo aver aperto il file il cui pathname viene fornito come primo parametro di chiamata del metodo, legga dal file (ad esempio mediante il metodo readLine della classe BufferedReader), una per riga, coppie di stringhe: di ciascuna coppia, la prima stringa rappresenta la chiave dell’elemento corrispondente, data da un numero floating point in singola precisione, rappresentato come stringa con la usuale notazione decimale con eventuale parte frazionaria, mentre la seconda stringa rappresenta il dato associato. Ad esempio:6 dato1
3.2 dato2
0.01 dato3
Il metodo
main inserisca in un’istanza della classe StackTab, una dopo l’altra, le coppie chiave floating point-dato ottenute dal file d’ingresso; esaurito tale file, il metodo, utilizzando l’apposito iteratore per le chiavi, visualizzi su stdout tutte le chiavi presenti nella struttura dati DOPO aver eseguito una singola estrazione, ed effettui infine una ricerca dell’elemento di chiave 3.5, fornendo su stdout la risposta "non presente" se l’elemento cercato non è nella struttura dati, altrimenti fornendo la stringa-dato associata all’elemento trovato.Nel caso di situazioni di errore, i metodi si limitino ad una segnalazione su stdout e a terminare (fanno eccezione i casi in cui si deve implementare un metodo di interfaccia che prevede di generare una possibile eccezione).
Prova scritta
Si voglia realizzare in Java una struttura di dati che rappresenti l'albero astratto di una espressione booleana. L'espressione può includere gli usuali operatori (| or inclusivo, & and, ! not), definiti con l'usuale priorità, le parentesi [ e ] per modificare la priorità degli operatori, e come operandi le parole chiave T e F, corrispondenti rispettivamente a true e false. Ad esempio, una espressione valida è:
T & ! [ ! F | T & F ] | T & T
L'albero dovrà essere realizzato con la tecnica 'figlio-fratello di destra'. I metodi da realizzare debbono consentire:·
la costruzione di un albero vuoto;·
l'aggiunta, come figlio (sinistro o destro), di un nodo cui è associato un operando dell'espressione (foglia dell'albero);·
l'aggiunta, come figlio (sinistro o destro), di un sottoalbero la cui radice è associata ad un operatore dell'espressione;·
il conteggio sull'albero, con tecnica ricorsiva, del numero di operatori di ciascun tipo e quello degli operandi, presenti nell'espressione;·
il calcolo dell'espressione, tenendo conto del fatto che valgono le seguenti relazioni:F & xxx = xxx & F = F
T | xxx = xxx | T = T
per cui il sottoalbero che rappresenta la sottoespressione
xxx non deve essere 'calcolato';·
la visualizzazione su standard output di una versione con parentesi complete dell'espressione attraverso una opportuna visita dell'albero. Se il tempo lo consente, si realizzi un segmento di codice di prova che costruisce l'albero a partire da una stringa contenente un'espressione booleana (assunta sintatticamente corretta). Nella valutazione dell'elaborato si terrà conto dell'impostazione adottata, della leggibilità del codice e della presenza di commenti esplicativi.Si voglia rappresentare una mappa associativa tra stringhe e coppie di numeri floating point. Più precisamente, si realizzi in linguaggioo Java la classe Assoc che include una lista di dimensione variabile, memorizzata in un vettore. Ciascuno degli elementi della lista è costituito da una stringa (di lunghezza arbitraria) e da una coppia di numeri floating point in singola precisione. La classe, oltre ai metodi di inizializzazione, deve includere (almeno):
·
un metodo findKey che ricerca un elemento usando come chiave una stringa;·
un metodo findSubKey che ricerca uno o più elementi usando come chiave una sottostringa della stringa da cercare: il metodo fornisce, in successive chiamate, ogni elemento, presente nella tabella, la cui stringa contiene (come sottostringa) la chiave fornita;·
un metodo insert per l'inserimento nella lista di un nuovo elemento;·
un metodo extract per la rimozione dalla lista di un elemento.Adottare tutti gli accorgimenti che consentono una realizzazione efficiente di questi metodi.
Si realizzi inoltre una classe Temp che, fruendo della classe Assoc, memorizza una tabella di temperature minime e massime per un insieme di città. Si realizzi nella classe Temp un programma di prova che, assumendo già inizializzato un oggetto di classe Assoc denominato tempCitta, fornisca su STDOUT tutta la tabella, con il nome di ciascuna città e con le 2 corrispondenti temperature, una città per riga. Il programma deve anche produrre su STDOUT i valori minimo e massimo sia delle temperature minime che di quelle massime, indicando per ciascuna la corrispondente città.
Si definisca una interfaccia Java denominata Dictionary che rappresenti il tipo di dati astratto dizionario: l'interfaccia dovrà includere metodi di uso generale per l'inserzione, la rimozione, la ricerca di elementi sulla base di una chiave. Si ipotizzi quindi una realizzazione mediante la classe BSTDict mediante albero binario di ricerca, rappresentato dalla classe SBinTree assunta già realizzata, e con chiavi costrituite da stringhe di 4 caratteri: per questa classe si definiscano i membri campo (con i necessari modificatori di visibilità) e si realizzi almeno un metodo tra inserimento, rimozione o ricerca previsti dall'interfaccia Dictionary.
Utilizzando la classe BSTDict, supposta a questo punto interamente realizzata, si definisca la classe Prenotazioni in grado di rappresentare un archivio di prenotazioni alberghiere. Gli elementi da inserire nell'archivio sono schede personali ove è memorizzato il cognome, il nome, la data di nascita, altre due date che rappresentano giorno di arrivo e di partenza e un numero naturale che rappresenta la stanza assegnata. Ricavare dalla scheda in modo opportuno la chiave alfanumerica di 4 caratteri. Realizzare per questa classe, oltre ai costruttori da prevedersi, un metodo per l'inserimento di una scheda, uno per la ricerca su cognome, uno per la ricerca su stanza, uno per la ricerca su data, uno per la rimozione.
Si voglia implementare in Java una versione modificata dell'algoritmo di merge sort come di seguito spiegato.
La classe MMS include il metodo STATICO di supporto fmerge che riceve 5 parametri: tre sono code (q1, q2, q3) di tipo Queue (interfaccia di libreria FI2.Linear.Queue), uno (factor) è di tipo int, e uno (comp) è di tipo Comparator (interfaccia di libreria FI2.Util.Comparator) e definisce i confronti tra gli elementi nelle code. Il metodo assume che in q1 siano contenuti elementi ordinati per gruppi di 2factor elementi successivi. Ad esempio, per n=7 elementi con chiavi intere e per factor=1 (2factor = 2), un possibile contenuto per q1 in ingresso potrebbe essere nell'ordine:
q1 (testa) 12 23 5 81 20 62 15 (coda)
Come si vede ciascun gruppo di 2 chiavi successive è ordinato (l'ultimo gruppo può essere formato da meno di 2factor chiavi). Il metodo, utilizzando come supporto le due code q2 e q3 , assunte inizialmente vuote, produce in q1 una sequenza riordinata degli elementi in modo che le loro rispettive chiavi risultino ordinate a gruppi di 2factor+1 chiavi successive. Ciò viene realizzato in due fasi. Nella prima fase viene inserito alternativamente nelle due code q2 e q3 ciascun gruppo ordinato di 2factor chiavi estratto (nell'ordine) da q1. Per l'esempio sopra, ciò produrrebbe:
q2 (testa) 12 23 20 62 (coda)
q3 (testa) 5 81 15 (coda)
e svuoterebbe q1. Nella seconda fase si effettua l'operazione di merge fra le due code, con destinazione la coda q1, a gruppi di 2factor+1 chiavi, cioè considerando, per ogni gruppo, 2factor chiavi da q2 e 2factor chiavi da q3, e ripetendo l'operazione fino a svuotare le due code. Ciò darebbe, per l'esempio, come risultato (2factor+1 = 4):
q1 (testa) 5 12 23 81 15 20 62 (coda)
Ora, come detto, q1 contiene gruppi di 2factor+1 chiavi successive ordinati, salvo eventualmente l'ultimo gruppo che, come in questo caso, può essere formato da meno di 4 chiavi.
La classe MMS include anche il metodo STATICO fmsort che riceve come parametro una coda q di tipo Queue e un comparatore comp di tipo Comparator, e che provvede ad ordinare gli n elementi nella coda q chiamando iterativamente il metodo fmerge con parametro factor che varia da 0 a k con k valore tale che 2k < n e 2k+1 >= n .
Successivamente, si estenda la classe ArrayQueue (classe di libreria FI2.Linear.ArrayQueue) mediante la classe MMSArrQue che, oltre ai necessari costruttori, aggiunge il metodo D'ISTANZA sort, senza parametri, che ordina la coda, oggetto della chiamata del metodo, utilizzando il metodo fmsort della classe MMS. Si risolva opportunamente l'associazione tra un'istanza di MMSArrQue e il comparatore da usare nell'ordinamento.
Si effettui infine il collaudo 'sulla carta', facendo vedere lo stato delle due code di supporto, prima del merge, e della coda fusa, dopo il merge, per ciascuno dei cicli di chiamata di fmerge, supponendo che inizialmente la coda contenga le seguenti chiavi intere:
q (testa) 23 12 62 -3 5 81 100 20 15 (coda)
Solo se il tempo lo consente, si includa nella classe MMSArrQue un metodo main di collaudo.
Si definisca in Java un’interfaccia NatAssocMem per una memoria associativa, ovvero un dizionario in cui ciascun elemento è costituito da un oggetto a cui è associato un valore naturale. L’interfaccia deve includere i metodi:
·
lookupcerca un oggetto e, se trovato, restituisce il valore
·
insertinserisce nel dizionario una coppia oggetto-valore associato, sollevando l’eccezione
AlreadyPresentException se l’oggetto è già presente con un valore associato diverso; se già presente con valore associato eguale a quello fornito come parametro, il metodo non modifica la struttura di dati·
deleterimuove l’oggetto che coincide con il parametro di chiamata, restituendo il valore associato come valore di ritorno del metodo; solleva l’eccezione
NotPresentException se l’oggetto non è presenteSi prevede che l’eguaglianza tra due oggetti venga verificata da una classe comparatore che implementa l’interfaccia
Equality.
Si implementi l’interfaccia
NatAssocMem con la classe StringVal che adotta il metodo dell’adattatore, utilizza come dizionario di supporto un’istanza della classe di libreria FI2.Dictionary.UnOrderedSLList, assume come oggetti da inserire nel dizionario stringhe (cioè di classe String) e come valore associato ad una stringa il valore naturale m con 0£ m£ 500. Il valore m deve essere controllato all’atto dell’inserimento e, se non valido, deve essere sollevata l’eccezione InvalidValueException. La classe StringVal include inoltre un metodo di collaudo main che:1. acquisisce da standard input il valore 0<N£ 200
2. acquisisce da standard input N coppie stringa-valore naturale
3. inserisce le N coppie in un dizionario istanza della classe
4. acquisisce da standard input 5 stringhe da ricercare nel dizionario di cui sopra, restituendo il risultato della ricerca
5. acquisisce da standard input 1 stringa da rimuovere, gestendo l’eventuale condizione d’errore
Sarà oggetto di valutazione anche l’ordine e la chiarezza, commenti compresi, con cui il programma risulta sviluppato.
a) Si definisca in Java un’interfaccia PQueue che estende l'interfaccia
FI2.Linear.Queue con due metodi pubblici:Nel definire l'interfaccia di questi metodi si prevedano, quando giustificato, adeguate eccezioni.
b) Si implementi quindi l'interfaccia PQueue con la classe ArrayPQueue , definita come estensione della classe ArrayQueue, quest'ultima ottenuta dalla classe FI2.Linear.ArrayQueue apportando la sola trasformazione di attributo da private a protected dei campi della classe.
c) Si realizzi infine un programma di prova (metodo main della classe ArrayPQueue ) che, in forma ciclica, consenta di ricevere da STDIN un valore booleano o intero, seguito da un valore intero che rappresenta una posizione, oppure un comando. Allo scopo si preveda che ogni riga-comando inizi con una lettera identificativa (b per booleano, i per intero, v per visualizzazione intera coda, c visualizzazione elemento di coda, r per rimozione della testa, s per svuotamento); nel caso di un valore (identificativi b e i), questo segue la lettera identificativa, è espresso nel formato standard in relazione al tipo (booleano o intero), deve essere assegnato ad un corrispondente oggetto wrapper (Boolean o Integer ), provvedendo poi ad inserire questo oggetto in una coda di classe ArrayPQueue nella posizione fornita da STDIN subito dopo il valore; nel caso di un comando, la riga contiene solo la lettera identificativa. I comandi ammessi sono: visualizzazione ordinata dei valori nell'intera coda, visualizzazione del valore in fondo alla coda, rimozione del valore in testa alla coda, svuotamento della coda.
Esempi:
i -3 0 inserisce il valore intero -3 in fondo alla coda
b false -2 inserisce il booleano false che diventerà il terzultimo elemento della coda
i 8 2 inserisce il valore intero 8 che diventerà il secondo elemento della coda
c visualizza l'ultimo elemento della coda
Sarà oggetto di valutazione anche l’ordine e la chiarezza, commenti compresi, con cui il programma risulta sviluppato.
Si definisca in Java una classe RBuf che realizza una 'bufferizzazione' di oggetti in modo che ogni BUFNUM oggetti inviati al buffer, questi vengono inseriti, in ordine inverso a quello di invio, in una coda FIFO. Più precisamente la classe RBuf include la definizione della costante locale BUFNUM, uno stack e una coda (FIFO). Sullo stack vengono inseriti, uno dopo l'altro e in ordine di invio, BUFNUM oggetti, dopodiché tutti i BUFNUM oggetti vengono singolarmente rimossi dallo stack e inseriti nella coda, così da occupare in questa un ordine inverso a quello originale di invio. Dalla coda possono essere successivamente e singolarmente prelevati.
Allo scopo la classe RBuf deve implementare 2 metodi pubblici, di cui è richiesta una adeguata definizione del prototipo di interfaccia:
·
insert·
removerimuove e restituisce il primo oggetto dalla coda interna
Nel definire questi metodi, si aggiungano le eventuali, motivate eccezioni e si gestiscano quelle delle strutture dati di supporto.
Si includano nella classe
RBuf anche 2 costruttori overloaded, uno di default che alloca lo stack interno come istanza della classe FI2.Linear.ArrayStack e la coda come istanza di FI2.Linear.ArrayQueue, e uno che alloca lo stack come istanza di FI2.Linear.LinkedStack e la coda come istanza di FI2.Linear.LinkedQueue.Supponendo infine che una classe
GInf implementi un'interfaccia grafica che include 2 textarea, rappresentate dai campi text1 e text2, e 2 bottoni, rappresentati dei campi butt1 e butt2, definire la classe SetText, interna a GInf, che implementa un ascoltatore dell'evento di pressione di ciascuno dei due bottoni. Il metodo che viene attivato alla pressione di un bottone deve riconoscere il bottone coinvolto e, se si tratta del primo, deve estrarre la stringa contenuta nella textarea text1 e passarla come parametro al metodo insert di un oggetto di classe RBuf, provvedendo poi ad azzerare la textarea; se è il secondo bottone, deve estrarre una stringa chiamando il metodo remove dell'oggetto RBuf e deve visualizzarla nella textarea text2. Il metodo in questione deve gestire le eventuali eccezioni previste per i metodi di RBuf. Si ribadisce che della classe GInf si deve realizzare SOLO la classe interna SetText, assumendo già realizzato tutto il resto.Sarà oggetto di valutazione anche l’ordine e la chiarezza, commenti compresi, con cui il programma risulta sviluppato.
Si voglia implementare un dizionario di stringhe mediante la classe TrieDict con il supporto un albero trie. Un albero trie è un albero ove ad ogni arco è associato un carattere e i nodi possono essere ‘finali’ o ‘non finali’; considerando un percorso dalla radice verso le foglie, e la stringa s ottenuta giustapponendo nell’ordine i caratteri associati agli archi del percorso, allora s appartiene al dizionario se il nodo terminale del percorso è etichettato come ‘finale’. Due stringhe s1 e s2, rappresentate rispettivamente dai percorsi p1 e p2, che hanno r come prefisso comune di lunghezza maggiore (s1, s2 e r non necessariamente devono essere stringhe del dizionario, nel senso detto) sono tali che p1 e p2 hanno come parte iniziale comune più lunga, il percorso associato ad r.
Ad esempio in fig. 1, ove i nodi anneriti sono finali e quelli bianchi non finali, le stringhe del dizionario sono:
da a al i il ina pi pio ras raso rasa raspa
Come si vede
il e in (questa seconda non stringa del dizionario) hanno come più lungo prefisso comune i e le due stringhe hanno percorsi la cui parte iniziale comune è associata a quel prefisso ed è costituita dal solo arco con etichetta i. Per implementare l’albero trie si pensi di utilizzare, col metodo dell'adattatore, un albero binario (classe FI2.Tree.ExpandBinaryTree) e la tecnica figlio-fratello, secondo la quale l’albero di fig. 1 verrebbe effettivamente rappresentato da quello di fig. 2 (ove nel disegno sono state omesse, per semplicità, le foglie-sentinella).
Fig. 1 Fig. 2
[Solo se il tempo rimasto lo consente:]
Si estenda l’interfaccia
FI2.Dictionary.Dictionary con l’interfaccia SetDictionary che aggiunge i metodi union, intersect e subtract: questi metodi operano sull'oggetto this (da qui in poi denominato d0) e su un parametro d'ingresso di tipo SetDictionary (da qui in poi denominato d1) che deve avere lo stesso tipo di comparatore, previsto per i dizionari non ordinati (tipo FI2.Dictionary.Equality), di d0. Questi metodi effettuano le omonime operazioni secondo quanto sotto precisato:Si assuma che oggetti di tipo
SetDictionary non contengano mai due chiavi eguali.Si implementi quindi l’interfaccia
SetDictionary con la classe SUS che estende la classe FI2.Dictionary.UnOrderedSLList, che realizza un dizionario (non ordinato) mediante una lista concatenata semplice. Si cerchi nella realizzazione di SUS di forzare il vincolo di chiave singola sopra imposto per gli oggetti di tipo SetDictionary.Se il tempo lo consente, si aggiunga alla classe
SUS un metodo di collaudo main che, similmente al metodo main della classe UnOrderedSLList, riceva da stdin due sequenze di lunghezza fornita dall'utente di coppie "chiave di 6 caratteri-stringa dati" e visualizzi su stdout il contenuto degli oggetti restituiti dalle chiamate dei metodi union, intersect e subtract.
Si voglia implementare in Java l'algoritmo di ordinamento topologico per un generico DAG (grafo orientato aciclico).
a) A tale scopo si realizzi nel package
FI2.Temi la classe DAGManag che include il seguente metodo:public static int[] topSort(boolean[][] graph) throws NotAcyclicException;
Il metodo riceve nel parametro
graph la matrice di adiacenza del DAG: l'elemento graph[i,j] è true se il grafo ha un arco (orientato) che va dal vertice i al vertice j. Il metodo restituisca in un vettore, come valore di ritorno, la sequenza di indici dei vertici ordinati secondo l'ordinamento calcolato, a meno che l'ordinamento non sia calcolabile, in quanto il grafo passato come parametro presenta uno o più cicli, nel qual caso il metodo sollevi l'eccezione NotAcyclicException.b.1) La classe
DAGManag includa il metodo statico di collaudo main che legge i dati del grafo da un file, se un nome di file viene fornito sulla linea di comando, oppure da stdin in caso contrario. I dati sono forniti sottoforma di un numero che rappresenta il numero totale dei vertici, seguito da una serie (di lunghezza non prefissata) di coppie di indici, ciascuna delle quali rappresenta un arco del grafo (nel senso detto sopra per la matrice di adiacenza). Il metodo main inizializzi una matrice di adiacenza con i dati forniti, chiami il metodo topSort con quella matrice, e, nel caso di ordinamento effettivamente calcolato, fornisca su stdout una rappresentazione semi-grafica del grafo con i vertici riordinati e collocati nell'ordine da sinistra a destra, secondo quanto qui sotto esemplificato.Grafo con 8 nodi (0..7) e 12 archi:
Input:
8
(0 3) (0 5) (1 2) (1 3) (2 3) (3 5) (2 4) (2 7) (4 6) (5 6) (5 7) (6 7)
(se lo si preferisce, si assuma che nell'input effettivo le parentesi siano omesse e che le coppie di indici vengano inserite una per riga)
Ordinamento topologico: 1 2 4 0 3 5 6 7
Rappresentazione semigrafica del grafo riordinato:
01 02 04 00 03 05 06 07
*-->+ | | | | | |
*---|---|---|-->+ | | |
*-->+ | | | | |
*---|---|-->+ | | |
*---|---|---|---|---|-->+
*---|---|---|-->+ |
*-->+ | | |
*---|-->+ | |
*-->+ | |
*-->+ |
*---|-->+
*-->+
Suggerimento
Nella realizzazione si possono utilizzare i seguenti metodi:
static NumberFormat NumberFormat.getInstance();
restituisce un oggetto di supporto per la formattazione di stringhe numeriche
void NumberFormat.setMinimumIntegerDigits(int min);
imposta il minimo numero di cifre per la formattazione di numeri (interi)
void NumberFormat.setMaximumIntegerDigits(int min);
imposta il massimo numero di cifre per la formattazione di numeri (interi)
String NumberFormat.format(int value);
produce in una stringa una rappresentazione formattata del numero passato come parametro, secondo le specifiche di formattazione precedentemente impostate; la stringa è restituita come valore di ritorno
b.2) In subordine, al posto della rappresentazione semigrafica del punto precedente, il
main fornisca la tabella di rinumerazione dei vertici secondo l’ordinamento prodotto, e la nuova sequenza degli archi (coppie di indici), ottenuta da quella originaria applicando la citata rinumerazione dei vertici (cioè i vertici hanno ora una numerazione diversa, ordinata secondo l'algoritmo, e conseguentemente gli archi) . Spiegare perché quest’ultimo output fa vedere che gli archi soddisfano l’ordinamento topologico.
Si debba realizzare, nel package FI2.Temi, la classe TFifo che rappresenta un contenitore che archivia oggetti generici in una coda FIFO (di tipo FI2.Linear.Queue) e, contemporaneamente, in una coda a priorità (di tipo FI2.Linear.PriorityQueue) avendo come chiave di ordinamento un tempo assoluto di scadenza espresso mediante un valore naturale nel range 0..225-1 (valori di questa natura vengono rappresentati in variabili intere da 32 bit).
Della classe TFifo è richiesta la realizzazione dei seguenti metodi:
Nel realizzare i metodi richiesti si tenga presente che si devono usare le 2 code di supporto esclusivamente con i metodi previsti dalla classe che implementa ciascuna di loro, senza apportare o supporre modifiche e/o estensioni a quelle classi. È comunque consentito utilizzare altre code temporanee se serve per l'implementazione dei metodi richiesti.
Sarà oggetto di valutazione anche l’ordine e la chiarezza, commenti compresi, con cui il programma risulta sviluppato.
Si supponga di disporre (quindi non la si deve realizzare), nel package FI2.Temi, della classe SBSTree che è una variante della classe FI2.Dictionary.SimpleBinarySearchTree ottenuta modificando da private a protected l'attributo dei campi dichiarati nella classe al fine di rendere quest'ultima estensibile (e naturalmente tutte le occorrenze del simbolo SimpleBinarySearchTree vengono sostituite con SBSTree).
Si estenda la classe SBSTree con la classe SBSPQ, da realizzare in modo che sia anch'essa contenuta nel package FI2.Temi, e che implementi anche l'interfaccia PriorityQueue: i metodi che devono essere definiti in SBSPQ, che includono quelli delle interfacce Container, InspectablePriorityQueue, e PriorityQueue (vedi sotto), devono essere realizzati il più possibile sfruttando l'ereditarietà da SBSTree. Si noti, in particolare, che nell'albero incluso in un'istanza di SBSPQ i nodi continuano ad avere chiavi distribuite secondo i vincoli dell'albero binario di ricerca (NON quindi trasformato in heap).
La classe SBSPQ includa inoltre il metodo statico:
public static List insSort(List uns, Comparator comp);
Il metodo riceve nel parametro
uns una lista non ordinata, utilizza un'istanza di SBSPQ come coda a priorità di supporto, e alloca, restituendola come valore di ritorno del metodo insSort, una lista dello stesso tipo di quella del parametro d'ingresso uns. La lista ritornata dal metodo conterrà gli stessi oggetti contenuti nella lista di ingresso ma in ordine crescente; l'ordinamento viene ottenuto applicando in insSort un algoritmo di tipo insertion sort con l'uso della coda a priorità. L'ordine è fissato dal comparatore passato come parametro comp al metodo.Infine la classe
SBSPQ includa il metodo statico di collaudo main che predispone una lista su array (di tipo ArrayList) di N numeri interi, generati casualmente nell'intervallo -100..100 (si faccia uso del metodo double Math.random() che genera numeri casuali tra 0.0 e 1.0), chiami il metodo insSort passando tale lista e un adeguato comparatore, e visualizzi su stdout i valori della lista originaria e di quella restituita dal metodo. Il valore N sia fornito come parametro sulla linea di comando (cioè attraverso il parametro args del metodo main).Sarà oggetto di valutazione anche l’ordine e la chiarezza, commenti compresi, con cui il programma risulta sviluppato.
public interface Container extends InspectableContainer
{
Container newContainer();
}
public interface InspectablePriorityQueue
extends InspectableKeyBasedContainer
{
Object minElement()
throws EmptyContainerException;
Object minKey()
throws EmptyContainerException;
}
public interface PriorityQueue
extends InspectablePriorityQueue, KeyBasedContainer
{
void insertItem
(Object key, Object element)
throws InvalidKeyException;
Object removeMin()
throws EmptyContainerException;
}
Torna
alla pagina principale