POLITECNICO DI TORINO CORSO DI LAUREA IN INGEGNERIA INFORMATICA CORSO DI ALGORITMI E PROGRAMMAZIONE AVANZATA I & II
Esercitazione di laboratorio n. 1 La corretta implementazione di almeno due degli algoritmi di ordinamento iterativi sarà oggetto di valutazione ai fini dell’attribuzione del punteggio per i laboratori.
Esercizio n. 1: confronto tra algoritmi di ordinamento. Si realizzi un programma che: • legga due numeri positivi M ed N, di valore limitato a 10000. • generi casualmente N numeri interi, memorizzandoli in un vettore. • ordini tale vettore in maniera crescente, utilizzando uno dei seguenti algoritmi: o insertion sort o selection sort o bubble sort • ripeta la generazione casuale e l’ordinamento per M volte. Si confrontino le prestazioni dei tre algoritmi per i valori di M=10, 100, 1000 e di N=1000, 5000, 10000, misurandone i tempi di esecuzione.
GENERAZIONE DI NUMERI CASUALI Per generare valori interi (pseudo-)casuali, si può utilizzare la funzione di libreria rand(). Tale funzione può essere chiamata previa inclusione di <stdlib.h> e ritorna un intero di valore com-preso tra 0 e RAND_MAX (minimo 32767). Se occorre un valore casuale inferiore ad un valore massimo NMAX, si può ricorrere alla funzione di "modulo" (che in C viene eseguita tramite l’operatore ‘%’), come nel seguente esempio: #include <stdlib.h> #define NMAX 1000 ... int val; val = rand() % NMAX; ...
MISURA DEI TEMPI DI ESECUZIONE Per misurare i tempi di esecuzione è possibile utilizzare la funzione di libreria clock(). Tale funzione può essere chiamata previa inclusione di : dividendo il valore ritornato per la costante CLK_TCK, si ottiene il tempo (in secondi) intercorso dall'inizio del programma. Un esempio di utilizzo di questa funzione è il seguente:
#include ... float t0, t1; t0 = ((float)clock())/CLK_TCK; /* parte di programma di cui si vuole misurare la durata */ ... t1 = ((float)clock())/CLK_TCK; printf("Tempo di esecuzione in secondi: %f\n", t1-t0);
PSEUDOCODICE DEGLI ALGORITMI DI ORDINAMENTO È riportato di seguito lo pseudo-codice degli algoritmi di sorting proposti per l’esercizio. In tutti i casi, N rappresenta il numero di dati da ordinare e V[0...N-1] è il vettore in cui i dati sono memorizzati. Il vettore viene ordinato per valori crescenti. •
Insertion Sort
for i=1 to N-1 key = V[i]; /* inserisce V[i] nella sequenza ordinata V[0...i-1] */ j = i-1; while (j>=0 and V[j]>key) V[j+1] = V[j]; j = j-1; V[j+1] = key;
•
Selection Sort
for i=0 to N-2 /* cerca il minimo nella sequenza V[i...N-1] */ small = i; for j=i+1 to N-1 if V[j]
•
Bubble Sort
for i=N-1 downto 1 /* scambia tutti i valori adiacenti non ordinati nell’intervallo 0...i */ for j=0 to i-1 if V[j]>V[j+1] SWAP(V, j, j+1);
Esercizio n. 2: confronto tra algoritmi di union-find. Si realizzi un programma che: • legga due numeri positivi M ed N, di valore limitato a 15000. • generi casualmente M coppie di numeri, ciascuno dei quali di valore inferiore a N. Ogni coppia rappresenta una nuova connessione tra gli elementi della coppia stessa. Le connessioni sono commutative e transitive. • per ogni coppia generata, stampi a video gli elementi della coppia solo se la coppia stabilisce una nuova connessione (ovvero, se i suoi elementi non erano già connessi). Per la gestione delle connessioni, si utilizzino i seguenti algoritmi (cfr. Sedgewick, §1.3): o quick find o quick union Si confrontino le prestazioni dei due algoritmi per i valori di M=3000, 6000, 12000 e di N=2000, 4000, 8000, misurandone i tempi di esecuzione. PSEUDOCODICE DEGLI ALGORITMI DI UNION-FIND È riportato di seguito il codice delle due funzioni richieste dall’esercizio. In entrambi i casi, p e q sono i valori della coppia di numeri ricevuti in ingresso e V[0...N-1] è il vettore usato per rappresentare le informazioni necessarie a stabilire la loro connessione. La funzione stampa la coppia (p q) se p e q non erano precedentemente connessi (in questo caso, il vettore V viene anche aggiornato), mentre non fa nulla in caso contrario. Si osservi che, in entrambi i casi, il vettore V deve essere inizializzato con V[i] = i, per ogni valore di i nell’intervallo [0...N-1]. •
Quick Find
quick_find(V, p, q) if (V[p] == V[q]) return; j = V[p]; for (i=0; i
•
Quick Union
quick_union(V, p, q) for (i=p; i!=V[i]; i=V[i]) ; for (j=q; j!=V[j]; j=V[j]) ; if (i == j) return; V[i] = j; /* visualizza il nuovo collegamento */ printf("%d %d", p, q); return;