Laboratorio di Informatica: Algoritmi e Strutture Dati

a.a. 2001/2002

Progetto n. 2

Data: 03.04.2002 

Data consegna relazioni: 28.05.2002 (corso A); 29.05.2002 (corso B).

Il problema dello String Matching consiste nella ricerca di tutte le occorrenze di un pattern P all’interno di un testo T, costituiti entrambi da stringhe su un comune alfabeto. Il problema e’ trattato nel testo di riferimento (Cormen et al., I edizione) al capitolo 34, al quale si rimanda per gli algoritmi e la notazione.

Si vogliono confrontare i seguenti algoritmi per lo string matching:

Algoritmo Naïve;

Algoritmo di Rabin-Karp;

Algoritmo di Knuth-Morris-Pratt.

L’esperimento si compone di due parti:

Prima parte: Per ciascun algoritmo assegnato, stimare il tempo di esecuzione in media con un intervallo di confidenza del 95%, su testi di varia lunghezza (comunque superiore ad 1.000.000) e pattern di lunghezza 3 e 4. Testi e pattern si dovranno generare in modo pseudo-casuale su un alfabeto opportuno.

Seconda parte: Si progetti una batteria di test per analizzare il comportamento degli algoritmi assegnati su testi e pattern italiani (o inglesi) significativi. Si giustifichino le scelte effettuate e si confrontino le performance degli algoritmi tra loro e coi risultati ottenuti nella prima parte.

In entrambe le parti, si confrontino i risultati ottenuti con i risultati teorici, cercando di motivare eventuali discrepanze.

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 devono coincidere con quelli che hanno consegnato la prima relazione.

I gruppi che hanno ottenuto una valutazione insufficiente (D) nel primo progetto possono, se lo credono opportuno, estendere l’esperimento all’algoritmo di Boyer-Moore.