Appunti Fondamenti I (C)

N

multi-insieme V di N elementi in D (V D ) e un valore target D, il

⊆ ∈

problema della ricerca consiste nel decidere se esiste un elemento V V

∈

i

v==V

tale che . Considereremo solo il caso in cui i dati sono memorizzati

i

in memoria primaria, ovvero il caso in cui il costo per il riferimento alle

variabili è trascurabile rispetto a quello per il confronto e la manipolazione

dei loro valori.

Implementazione per gli algoritmi di ricerca:

#include <math.h>

#define PRECISION .000000119

#define TRUE 1

#define FALSE 0

typedef unsigned short int Boolean

struct data {

float key;

…..

};

2.4.1 – Ricerca sequenziale

Se non esistono ipotesi sui valori di V, l’unica possibilità è quella di

controllarli uno ad uno, fino ad averli esauriti o fino ad aver trovato il

target, quest’ultimo caso potrebbe portare l’algoritmo ad un risultato

sbagliato in quanto potrebbero esserci più valori uguali al target. La

complessità della ricerca sequenziale è Θ(N).

Si osservi che per via della precisione finita, il test di uguaglianza è

sostituito con la verifica che la distanza relativa sia minore della

precisione di macchina, per quanto riguarda il valore della costante

PRECISION, questo può dipendere dalla particolare applicazione, un

possibile valore fornito dal file <float.h>, dove la costante di precisone di

macchina è definita dalla costante FLT_EPSILON=0.00000011920928960

-7

(circa 10 ), che è il valore corrispondente alla differenza tra il valore 1 ed

il più piccolo numero float maggiore di 1.

Boolean sequential_search(struct data * V, int N, struct data target)

{ Boolean found;

int count;

found=FALSE;

count=0;

while(found==FALSE && count<N)

{ if(is_equal(V[count].key,target.key)==TRUE)

found=TRUE;

else count++;

}

return found;

}

2.4.2 – Ricerca binaria

Se i valori di V sono ordinati, allora l’esito di un solo test può escludere

più di un elemento di V dallo spazio della ricerca. Se oltre l’ipotesi di

ordinamento possiamo anche assumere che i valori sono memorizzati su

un vettore, diventa conveniente applicare una ricerca binaria. Qui il target

viene comparato contro l’elemento in posizione mediana (V[N/2]); se è

uguale la ricerca termina con successo, se è maggiore la ricerca prosegue

nella metà destra del vettore, se è minore prosegue nella metà sinistra.

Quando la ricerca viene applicata su un vettore di lunghezza 0 è possibile

concludere che il target non è presente nell’insieme. Il caso pessimo si

realizza quando il test di uguaglianza fallisce, in tal caso il costo di

c

esecuzione è pari a un valore costante più il costo per proseguire la

ricerca sulla metà selezionata: C = Θ(ln (N))

bin 2

L’algoritmo ha una naturale implementazione in forma ricorsiva.

Boolean b_search(int * V, int N, int target)

{ if(N>0)

{ if(V[N/2]==target

return TRUE

else if(V[N/2]>target)

return b_search(V,N/2,target);

else return b_search(&V[(N/2)+1], N-(N/2)-1,target);

}

else return FALSE;

}

Si osservi che N/2 è il numero di elementi che precedono l’elemento

V[N/2], che N-(N/2)-1 è il numero di elementi che lo seguono, e che

&V[(N/2)+1] è l’indirizzo del primo elemento successivo a V[N/2]. (Vale

anche per N dispari)

Esistono inoltre forme iterative e sequenziali per la ricerca binaria (vedere

codici sul libro)

2.4.3 – Ricerca a salti (NO)

-2.5Algoritmi di ordinamento

Come già per il problema della ricerca, ci interessa considerare il caso in

cui i dati sono in memoria primaria, ovvero il caso in cui il costo per il

riferimento alle variabili è trascurabile rispetto a quello per il confronto e

la manipolazione dei loro valori.

2.5.1 – Sequential-sort

L’algoritmo sequential sort riduce il problema dell’ordinamento alla

sezione del massimo e allo swap: sull’insieme V viene selezionato il

massimo, e l’elemento che lo realizza viene swappato con l’elemento in

ultima posizione; dopodiché il problema prosegue allo stesso modo sui

primi N-1 elementi, di conseguenza dopo N-1 passaggi, il vettore è

C(SeqS)= 2

ordinato. Il costo del sequential sort è Θ(N )

Nel caso in cui l’insieme V sia rappresentato su un vettore, piuttosto che

modificare la posizione degli elementi nel vettore, si costruisce un vettore

di permutazione che fornisce la sequenza con cui il vettore può essere

visitato in ordine. Questo ha il vantaggio di non perdere l’eventuale

informazione codificata nel disordine iniziale e permette una sostanziale

ottimizzazione nel caso in cui i dati siano complessi.

void sequential_sort(int * V, int N, int * Perm)

{ int count;

int count_of_max;

int iter;

for(count=0; count<N; count++)

Perm[count]=count;

for(iter=0; iter<N; iter++)

{ for(count=1, count_of_max=0; count<N-iter; count++)

if(V[Perm[count]]>V[Perm[count_of_max]])

count_of_max=count;

swap(Perm, count_of_max, N-iter-1);

}

}

Si osservi che l’espressione V[Perm[count]]>V[Perm[count_of_max]] non

è legale se V è un tipo strutturato, in tal caso, verrebbe sostituita con

l’espressione V[Perm[count]].key>V[Perm[count_of_max]].key

Un modo per ridurre il numero di confronti dell’algoritmo è quello di

sostituire la ricerca e lo swap del massimo con la ricerca e lo swap

contemporaneo di massimo e minimo. Cosi facendo il numero di

interazione si dimezza mentre il costo di ciascuna interazione aumenta. Il

guadagno deriva dal fatto che la ricerca contemporanea di massimo e

minimo può essere effettuata con un numero di confronti minore del

doppio dei confronti richiesti per la ricerca del solo massimo: dovendo

x y max min, x y

comparare e contro e si compara inizialmente contro e

successivene il maggiore tra i due può diventare il massimo e il minore il

minimo, così facendo il numero di confronti si riduce da 4 a 3.

if(x>y)

{ if(x>max)

max=x;

if(y<min)

min=y;

}

else

{ if(y>max)

max=y;

if(x<min)

min=x;

}

2.5.2 – Bubble-sort

L’algoritmo di BubbleSort opera in iterazioni successive: nella k-esima

iterazione un indice count scandisce le posizioni da 0 a N-k-1,

confrontando ad ogni passo il valore di V[count] contro quello di

V[count+1] e permutando le posizioni dei due elementi se essi non sono

in ordine. L’algoritmo termina quando nel corso di una iterazione non

sono stati identificati due elementi fuori ordine. L’algoritmo non è

particolarmente efficiente, ma ci interessa per esemplificare il problema

della correttezza. Quest’ultimo è scomposto in due parti:

La correttezza parziale, è quella per cui se l’algoritmo termina, allora il

 risultato prodotto è corretto

La correttezza totale, si raggiunge quando alla correttezza parziale

 viene aggiunta la garanzia di terminazione

Nel caso del bubble sort, la correttezza parziale è garantita in modo

immediato: l’algoritmo termina quando nel corso di una iterazione non

sono identificati due elementi contigui fuori ordine, il che garantisce che il

vettore sia in ordine. Per quando riguarda la correttezza totale si pone il

problema di capire come aggiungere la garanzia di terminazione; questa

può essere dimostrata sulla base di due proprietà:

1. Un elemento che all’inizio dell’iterazione non è preceduto da alcun

maggiorante avanza fino ad incontrare il primo maggiorante, nel caso

particolare in cui non ha nessun maggiorante avanza fino all’ultima

posizione del vettore.

2. Un elemento che all’inizio dell’iterazione è preceduto da almeno un

maggiorante, al termine dell’iterazione è arretrato di una posizione

Al termine della k-esima iterazione, le ultime k posizioni del vettore

contengono i k maggiori elementi nel loro corretto ordine, questo implica

che entro N-1 iterazioni, gli ultimi N-1 elementi sono nella loro corretta

posizione e quindi l’intero vettore è ordinato. Inoltre, la

k-esima iterazione può essere limitata alle sole N-k posizioni. Grazie a

questo il costo di esecuzione su N elementi può essere espresso come:

C(BubS)= 2

Θ(N )

Pur realizzando la stessa complessità, tra il sequential sort e il bubble sort

esistono sostanziali differenze. Mentre il sequential sort ha costo

invariante rispetto ai dati, il bubble sort può terminare senza aver

compiuto tutte le N-2 iterazioni, come svantaggio però, mentre il

sequential sort richiede sempre N-1 swaps, il bubble sort ne può

richiedere

(N-1)(N-2)

void BubbleSort(int * V, int N, int * Perm)

{ int iter;

Boolean swap_found;

int count;

for(count=0; count<N; count++)

Perm[count]=count;

iter=0;

do

{ for(count=0, swap_found=FALSE; count<N-iter-1; count++)

{ if(V[Perm[count]]>V[Perm[count+1]])

{ swap(Perm, count, count+1)

swap_found=TRUE;

}

}

iter++;

}

while(swap_found==TRUE);

}

2.5.3 – Merge-sort

L’algoritmo di merge sort riduce il problema dell’ordinamento al problema

della fusione: due metà del vettore sono ordinate separatamente e poi

fuse in modo da ottenere un vettore ordinato globalmente.

Fusione

Il problema della fusione consiste nell’ordinare un vettore partizionato in

due semi-vettori ciascuno dei quali è inizialmente ordinato al suo interno.

Il semi-vettore sinistro viene inizialmente copiato su un semi-vettore di

appoggio, viene poi ripetutamente selezionato e trasferito sul vettore

complessivo il minimo del semi-vettore di appoggio e quello del

semi-vettore destro. L’algoritmo termina quando tutti gli elementi del

vettore di appoggio sono stati copiati sul vettore complessivo. L'algoritmo

esegue in tempo lineare rispetto alla lunghezza N del vettore

complessivo: ad ogni selezione e confronto tra due minimi, il vettore

complessivo cresce di un elemento, per cui l'algoritmo termina dopo un

numero massimo di N selezioni; d'altra parte, essendo i due semi-vettori

ordinati, la selezione e il confronto dei loro minimi avviene in tempo

costante. Al costo di selezione e copia dai due semi-vettori si aggiunge il

costo iniziale per copiare il semi-vettore sinistro nell'area di appoggio, che

l r

comunque avviene in tempo lineare. Gli indici ed indicano il numero di

elementi inizialmente contenuti nel semi-vettore di appoggio e in quello

destro che sono già stati selezionati e riportati nel