Following description of given problems (in Italian, as it was given like this).

Progetto di laboratorio (prima parte)

Scopo del progetto di laboratorio è verificare che lo studente sia in grado di progettare, implementare e analizzare la complessità di un programma usando gli strumenti illustrati durante le lezioni del corso di algoritmi e strutture dati. I programmi prodotti dovranno risolvere alcuni problemi classici di natura computazionale e dovranno essere formalmente corretti. Ogni progetto di laboratorio consiste nella produzione di uno o più programmi che risolvano un problema computazionale assegnato, nella stima empirica della complessità di tali programmi al variare della dimensione dell'input e di eventuali altri parametri, e nella redazione di una relazione in cui si discutano puntualmente alcune scelte implementative e si faccia un'analisi della stima di complessità.

Di seguito sono riportate le consegne per la prima parte del progetto di laboratorio, da consegnare necessariamente prima dell'iscrizione all'esame finale di teoria.

La prima parte del progetto richiede l'implementazione e l'analisi dei tempi medi di esecuzione di tre algoritmi di selezione (calcolo del k -esimo elemento più piccolo in un vettore non ordinato di interi). I tre algoritmi di selezione, denominati rispettivamente "quick select", "heap select" e "median-of-medians select", dovranno avere le seguenti caratteristiche:

Quick Select

Si tratta di una variante dell'algoritmo di ordinamento "quick sort", in cui ogni chiamata ricorsiva su un intervallo del vettore fornito in input termina in tempo costante ogniqualvolta il parametro non sia contenuto nell'intervallo . L'algoritmo deve avere complessità temporale asintotica nel caso pessimo e nel caso medio, dove è il numero di elementi del vettore.

Heap Select

Questo algoritmo di selezione utilizza due min-heap, denominate e . La prima heap é costruita a partire dal vettore fornito in input in tempo lineare e non viene modificata. La seconda heap contiene inizialmente un solo nodo, corrispondente alla radice di . All' -esima iterazione, per che va da a , l'algoritmo estrae la radice di , che corrisponde a un nodo in , e reinserisce in i nodi successori (figli sinistro e destro) di nella heap . Dopo iterazioni, la radice di corrisponderà al -esimo elemento più piccolo del vettore fornito in input. L'algoritmo descritto ha complessità temporale sia nel caso pessimo che in quello medio. Per sufficientemente piccolo, quindi, l'algoritmo "heap select" sarà preferibile, almeno nel caso pessimo, all'algoritmo "quick select". È possibile implementare una variante che utilizzi opportunamente min-heap o max-heap, a seconda del valore di .

Median-of-medians Select

L'algoritmo è basato sulla suddivisione del vettore fornito in input in blocchi di dimensione limitata e sul calcolo della mediana delle mediane. Più precisamente, l'algoritmo esegue le seguenti operazioni:

• divisione dell'array in blocchi di 5 elementi, escluso eventualmente l'ultimo blocco che potrà contenere meno di 5 elementi,
• ordinamento e calcolo della mediana di ciascun blocco,
• calcolo della mediana delle mediate dei blocchi, attraverso chiamata ricorsiva allo stesso algoritmo
• partizionamento dell'intero array attorno alla mediana , attraverso una variante della procedura "partition" dell'algoritmo "quick sort"
• chiamata ricorsiva nella parte di array che sta a sinistra o a destra della mediana , in funzione del valore k fornito in input. Il modo più semplice per implementare quest'algoritmo consiste nell'allocare, ad ogni chiamata ricorsiva, un nuovo vettore per memorizzare le mediane dei blocchi. Esiste tuttavia un approccio più efficiente e "in place" che riutilizza lo spazio allocato per il vettore originariamente fornito in input. La valutazione del progetto terrà conto della variante implementata (quella "in place", essendo più complicata ma anche più efficiente, sarà valutata con un punteggio più alto). Indipendentemente dalla variante implementata, nel caso pessimo l'algoritmo dovrà avere complessità, sia temporale che spaziale, pari a .

Modalità di consegna

Si richiede:

1. L'implementazione in un linguaggio a scelta (ad esempio, C, C++, Java) dei tre algoritmi descritti sopra, in modo che siano formalmente corretti (è possibile assumere che gli input siano ben formati, ovvero che i vettori non siano vuoti e che il parametro sia sempre positivo e minore o uguale alla dimensione del vettore). Per agevolare la verifica di correttezza da parte del docente sono stati predisposti tre moduli "Virtual Programming Laboratory" (VPL) da utilizzare per caricare il codice degli algoritmi. Una condizione necessaria alla valutazione dell'elaborato è il superamento di tutti i test previsti, per tutti e tre gli algoritmi. Nota: l'esecuzione di un programma lato server attraverso un modulo VPL garantisce uno spazio di memoria di almeno 64KB, giudicato ampiamente sufficiente per risolvere il problema assegnato con qualunque algoritmo fra quelli sopra descritti.

2. La stima dei tempi medi di esecuzione per tre algoritmi, al variare della dimensione n del vettore ed eventualmente del parametro k (nei casi, ovviamente, in cui si ritenga esista una correlazione fra tempo di esecuzione e parametro k). Il vettore in input deve essere generato in modo pseudo-casuale con interi, eventualmente anche negativi, e il tempo di inizializzazione dell'input dev'essere opportunamente scomputato dalla stima del tempo di esecuzione. Gli algoritmi valutati in questa parte dovranno essere gli stessi di quelli presentati al punto 1) (ad esclusione, ovviamente, delle parti di codice che gestiscono l'input e l'output). I tempi di esecuzione devono essere misurati con un errore relativo massimo pari a 0.01 (1%), utilizzando un orologio di sistema monotono di tipo "stopwatch" e calcolandone preliminarmente la risoluzione. Dal momento che i tempi di esecuzione dipenderanno dall'input generato in modo pseudo-casuale, si richiede la stima del tempo medio di esecuzione e della sua deviazione standard. Anche per questa parte è stato predisposto un modulo VPL da utilizzare per caricare il programma che raccoglie i tempi medi di esecuzione e le deviazioni standard per ciascuno dei tre algoritmi (in questo caso non sarà predisposto alcun test automatico, e per ovvie ragioni si sconsiglia l'esecuzione del programma lato server...). Tale programma dovrà produrre in output una sequenza di record nel formato "N K T1 D1 T2 D2 T3 D3", dove N è la dimensione del vettore generato, K è un'istanza del parametro k, Ti (per i=1,2,3) è una stima del tempo medio del i-esimo algoritmo e Di una stima della relativa deviazione standard. Si consiglia di generare un centinaio di campioni della dimensione N che variano indicativamente fra 100 e 5000000, con una distribuzione esponenziale o geometrica (ovvero, i campioni di N tenderanno a essere più "densi" negli intervalli di valori bassi).

3. I dati raccolti al punto 2) devono essere presentati e discussi in una relazione, da caricare sul server in formato PDF. La valutazione della relazione contribuirà in modo significativo al voto finale del progetto di laboratorio. Non è necessario inviare una relazione con molte pagine: qualche decina di pagine è largamente sufficiente a discutere gli aspetti importanti dell'implementazione e dell'analisi dei tempi di esecuzione. Si consiglia l'uso di grafici comparativi, sia in scale lineari - vs - che doppiamente logaritmiche - vs .

Progetto di laboratorio (seconda parte)

Di seguito sono riportate le consegne per la seconda parte del progetto di laboratorio, da consegnare necessariamente prima dell'iscrizione all'esame finale di teoria.

La seconda parte del progetto richiede l'implementazione e l'analisi dei tempi di l'esecuzione di operazioni di inserimento e di ricerca in alberi binari di ricerca. Nello specifico, si richiede di implementare le operazioni di ricerca e inserimento per tre tipi diversi di alberi binari di ricerca: alberi binari di ricerca semplici, di tipo AVL e di tipo Red-Black. Si assuma che ogni nodo di un albero binario di ricerca contenga una chiave numerica (di tipo intero) e un valore alfanumerico (di tipo stringa). Non è richiesta l'implementazione dell'operazione di rimozione di un nodo (i test automatici di auto-valutazione sono preparati in modo da non eseguire mai l'istruzione di rimozione).

Alberi binari di ricerca semplici

Si ricorda che un albero binario di ricerca semplice deve soddisfare la seguente proprietà: per ogni nodo che non sia una foglia e per ogni nodo nel sotto-albero sinistro (rispettivamente, destro) di , la chiave associata a è strettamente maggiore (rispettivamente, minore) della chiave associata a . Si faccia riferimento all'Esercizio 16 per la descrizione delle operazioni di inserimento e ricerca di un nodo.

Alberi binari di ricerca di tipo AVL

Si ricorda che un albero binario di ricerca di tipo AVL, oltre a soddisfare la proprietà di un albero di ricerca semplice, deve soddisfare anche la seguente proprietà: per ogni nodo , le altezze dei sotto-alberi di sinistra e di destra nel nodo differiscono al più di 1. Si faccia riferimento all'Esercizio 18 per la descrizione delle operazioni di ribilanciamento in seguito a inserimento di un nodo.

Alberi binari di ricerca di tipo Red-Black

Si ricorda che in un albero binario di ricerca di tipo Red-Black, ogni nodo ha associato un colore associato, che può essere rosso o nero. L'altezza nera del sottoalbero radicato in un nodo è definita come il massimo numero di nodi neri lungo un possibile cammino da a una foglia. Un albero binario di ricerca Rosso-Nero deve soddisfare anche la seguente proprietà: per ogni nodo , le altezze nere dei sotto-alberi di sinistra e di destra nel nodo coincidono.

Complessità media ammortizzata

Si richiede una stima dei tempi medi e ammortizzati per l'esecuzione di operazioni di inserimento e ricerca nei tre tipi di alberi binari di ricerca sopra descritti. Per tale stima si potrà procedere nel modo seguente. Al variare del parametro , ad esempio, fra 1000 e 1000000, si eseguono volte le seguenti operazioni su un albero di ricerca inizialmente vuoto: si genera in modo pseudo-casuale un valore intero , si ricerca un nodo con chiave nell'albero e, qualora il nodo non esistesse, si inserisce un nuovo nodo con chiave nell'albero. Si noti che al termine di tale procedura saranno state eseguite esattamente operazioni di ricerca e operazioni di inserimento, per un opportuno (l'albero binario di ricerca conterrà quindi al più nodi). Nell'ipotesi che i numeri generati in modo pseudo-casuale varino in un dominio sufficientemente grande, il valore di sarà probabilmente simile a quello di e potrà quindi essere sostituito con .

Il tempo ammortizzato per l'esecuzione di tali operazioni è dato dal tempo totale diviso il numero di operazioni di ricerca ed eventuale inserimento, ovvero:

Si richiede di stimare il tempo ammortizzato al variare di con un errore relativo limitato superiormente da (1%).

Modalità di consegna

Si richiede:

1. L'implementazione in un linguaggio a scelta (ad esempio, C, C++, Java) dei tre tipi di alberi binari di ricerca, in modo che le operazioni di inserimento e ricerca siano formalmente corrette. Per semplificare la valutazione di correttezza sono stati predisposti tre moduli "Virtual Programming Laboratory" (VPL) da utilizzare per caricare l'implementazione delle varie strutture dati. Una condizione necessaria alla valutazione dell'elaborato è il superamento di tutti i test previsti, per tutti e tre i tipi di alberi binari di ricerca.

2. La stima dei tempi medi e ammortizzati di esecuzione per le tre strutture dati, al variare del parametro (numero di iterazioni di ricerca ed eventuale inserimento di un nodo in un albero). Non essendovi particolari operazioni computazionalmente onerose per l'inizializzazione di un albero vuoto, non sarà necessario scomputare i tempi di inizializzazione. Gli algoritmi valutati in questa parte dovranno essere gli stessi di quelli presentati al punto 1) (ad esclusione, ovviamente, delle parti di codice che gestiscono l'input e l'output). I tempi ammortizzati di esecuzione devono essere misurati con un errore relativo massimo pari a (1%), utilizzando un orologio di sistema monotono di tipo "stopwatch" e calcolandone preliminarmente la risoluzione. Dal momento che i tempi di esecuzione dipenderanno dalla particolare sequenza di chiavi generate, si richiede la stima del tempo medio ammortizzato e della sua deviazione standard. Anche per questa parte è stato predisposto un modulo VPL da utilizzare per caricare il programma che raccoglie i tempi medi e ammortizzati di esecuzione e le deviazioni standard per ciascuna delle tre strutture dati (in questo caso non sarà predisposto alcun test automatico, e per ovvie ragioni si sconsiglia l'esecuzione del programma lato server...). Tale programma dovrà produrre in output una sequenza di record nel formato "N T1 D1 T2 D2 T3 D3", dove N rappresenta il numero iterazioni di ricerca ed eventuale inserimento, (per ) è una stima del tempo medio e ammortizzato di ciascuna operazione e una stima della relativa deviazione standard. Si consiglia di generare un centinaio di campioni della dimensione N che variano indicativamente fra 1000 e 100000, con una distribuzione esponenziale o geometrica (ovvero, i campioni di N tenderanno a essere più "densi" negli intervalli di valori bassi).

3. I dati raccolti al punto 2) devono essere presentati e discussi in una relazione, da caricare sul server in formato PDF. La valutazione della relazione contribuirà in modo significativo al voto finale del progetto di laboratorio. Non è necessario inviare una relazione con molte pagine: qualche decina di pagine è largamente sufficiente a discutere gli aspetti importanti dell'implementazione e dell'analisi dei tempi di esecuzione. Si consiglia l'uso di grafici comparativi, sia in scale lineari - vs - che doppiamente logaritmiche - vs .