Progetto finale

Si vuole implementare in modo efficiente il tipo di dato astratto insieme disgiunto di numeri interi, con le operazioni Make(x), Union(x,y) e Find(x). Lo studente ha visto nel corso di Algoritmi e Strutture Dati una possibile implementazione che sfrutta foreste disgiunte la quale, usando le euristiche dell'unione per rango e della compressione dei cammini, permette l'esecuzione di una successione di m operazioni, di cui n Make, in tempo O(m alpha(m,n)).

Sono note in letteratura altre euristiche che garantiscono lo stesso tempo asintotico e che, in alcuni casi, esibiscono costanti moltiplicative più piccole. Tra queste ricordiamo in particolare il dimezzamento dei cammini (path-splitting): durante una Find(x), il genitore di ogni nodo sul cammino da x alla radice (eccettuata la radice ed i suoi figli) è cambiato in modo da puntare al nonno di x. Si osservi che il dimezzamento dei cammini è un'euristica ad unica passata sull'albero.

Si vogliono studiare sperimentalmente queste euristiche. Pertanto:

1. Si implementi il tipo di dato astratto insieme disgiunto, sia usando le euristiche unione per rango e compressione dei cammini che le euristiche unione per rango e dimezzamento dei cammini.

2. Si progetti un esperimento per valutare le prestazioni delle due implementazioni fornite, in termini di numero di accessi ai nodi delle strutture dati, in funzione dei parametri m (numero totale operazioni) ed n (numero di Make). I gruppi sono liberi di progettare l’esperimento nel modo che riterranno più opportuno. Tuttavia, sembra ragionevole che:

a. si costruiscano in primo luogo foreste generate in modo casuale, ma in modo da garantire che (i) i singoli alberi che le compongono abbiano profondità significativa; (ii) vi sia un numero consistente di alberi;

b. si generino su tali foreste ulteriori successioni casuali di operazioni, nelle quali la frequenza delle tre operazioni è opportunamente scelta;

c. si valuti il numero di accessi medi, nei vari casi ed in funzione di m, n, e della frequenza relativa delle tre operazioni, con un intervallo di confidenza del 95%.

Si consegni una relazione finale sull'esperimento condotto, contenente la presentazione e la discussione dell’esperimento, i suoi risultati, la loro interpretazione, tutti i listati.

Se si intende sostenere l’esame negli appelli di giugno e luglio, la relazione deve essere consegnata entro giovedì 31 maggio in laboratorio o nella casella postale del Prof. Martini, presso il Dipartimento di Matematica e Informatica.