Laboratorio di Informatica: Algoritmi e Strutture Dati

a.a. 1999/2000

Progetto n. 3

Data: 13.04.2000

Data consegna relazioni:

Le relazioni devono essere consegnate al docente (in orario di Lab o Ricevimento) o lasciate nella sua casella postale presso il Dipartimento di Matematica e Informatica (accanto alle Segreterie davanti all'Aula multimediale).

Si vogliono confrontare le tecniche per la risoluzione delle collisioni in tabelle hash con indirizzamento aperto.

Si assuma che la funzione hash h' sia data direttamente mediante il generatore di numeri casuali visto in laboratorio, con le ovvie modifiche per generare un numero naturale casuale compreso tra 0 e m-1. Nel seguito con n indicheremo il numero di elementi effettivamente presenti nella tabella.

Si vogliono confrontare i seguenti metodi:

(i) scansione lineare: h(k,i) = (h'(k)+i) mod m;

(ii) scansione quadratica: h(k,i) = (h'(k)+c1i+c2i2) mod m;

(iii) scansione lineare ad incremento pesato: h(k,i) = (h'(k)+[(2h'(k)+1)mod m]i) mod m.

Per il metodo (ii) si discuta anche la scelta delle due costanti c1 e c2 (si veda Cormen at al., Problem 12-4 della versione inglese).

Al variare di m in [100,1000,5000] (o valori vicini per (ii)) e del fattore di riempimento ALFA=n/m in [50%,80%,90%,95%,99%], si stimi la media dei seguenti due parametri, con intervalli di confidenza del 95%:

An = numero di volte che l'algoritmo deve accedere alla tabella per trovare uno degli n elementi ivi memorizzati;

In = numero di volte che l'algoritmo deve accedere alla tabella per inserire un (n+1)-esimo elemento ad una tabella che gia' contiene n elementi.

E’ ammesso l’uso dei seguenti linguaggi di programmazione: Pascal, C, C++, Java.

Si deve consegnare una relazione analitica che comprenda:

  1. obiettivi dell’esperimento;
  2. metodologia dell’esperimento;
  3. strumenti usati;
  4. tabelle e grafici riepilogativi e comparativi;
  5. conclusioni;
  6. listati completi.

I gruppi possono contenere al piu’ tre componenti.