Appunti del corso di Algoritmi e programmazione

SERS ALANT ESKTOP UNI SECONDOANNO APA TEORIA VIDEOACQUISITI LGORITMI E PROGRAMMAZIONE LEZ MP ETTORE MULTIMEDIALE MP

Nelle funzioni ricorsive, quindi, cosa accade? Sebbene una chiamata ricorsiva sia una funzione che chiama

sé stessa, lo Stacks di sistema viene usato allo stesso identico modo per chiamate a funzioni non ricorsive:

per ogni chiamata è generato uno Stack Frame. È più probabile, quindi, che nelle funzioni ricorsive si

verifichi il fenomeno di Stack Overflow.

Funzioni ricorsive in coda

Si chiamano funzioni ricorsive in coda quelle funzioni ricorsive del tipo:

return chiamataricorsiva(parametri);

Cioè quelle funzioni ricorsive che, come istruzione di hanno solamente la chiamata ricorsiva.

return

Esempio:

La seguente funzione:

unsigned long fact(int n){

if(n == 0)

return 1;

return n*fact(n-1);

}

Non è una funzione ricorsiva in coda, perché prima viene ritornato il valore della chiamata poi viene

eseguita la moltiplicazione.

Una funzione di questo tipo ci “costringe” ad attendere la fase di risalita dall’ultima chiamata ricorsiva.

La seguente funzione

unsigned long tr_fact(int n,

unsigned long f) {

if(n == 0)

return f;

return tr_fact(n-1, n*f);

}

È ricorsiva in coda, perché la moltiplicazione è effettuata in fase di discesa.

n*f

In questo caso si riscontrano diversi vantaggi:

• Maggiore efficienza per l’assenza della fase di risalita;

• Le chiamate non necessitano di uno Stack Frame apposito, perché la chiamata ricorsiva rimpiazza

quella corrente (si noti, nella funzione precedente, che non viene fatto alcun calcolo all’interno

della funzione una volta che i parametri sono stati identificati);

• Di conseguenza, non può verificarsi il fenomeno di Stack Overflow;

Svantaggi:

• Questo tipo di funzione è, in generale, più complesso da scrivere.

Esistono alcuni linguaggi di programmazione che consentono di ottimizzare in autonomia il codice di una

funzione quando il compilatore si accorge di avere a cha fare con funzione che possono essere sostituite in

funzioni ricorsive in coda (non il C, perché è un coglione).

Distinzione tra funzioni ricorsive iterative e funzioni ricorsive in coda ù

Gli algoritmi ricorsivi di ordinamento

Merge Sort

Si divide un dato vettore in due sotto-vettori: il destro ed il sinistro, individuati dagli opportuni indici, quindi

eseguiamo il Merge Sort su tali sotto-vettori, sino alla condizione di terminazione con vettori di un

elemento (l==r) o 0 elementi (l>r).

La ricombinazione prevede di “fondere” i due vettori di partenza per costruire quello riordinato finale.

A ’

LLEGO UN VIDEO D ESEMPIO

C:\U \ .LAPTOP-8L623GR6\D \ \ \ \ \ \A _ _ _ _23. 4 - L VLC 2020-11-24 12-22-22. 4

SERS ALANT ESKTOP UNI SECONDOANNO APA TEORIA VIDEOACQUISITI LGORITMI E PROGRAMMAZIONE LEZ MP ETTORE MULTIMEDIALE MP

In questo frangente si introduce un concetto che torna utile nell’espressione del concetto di modularità: le

funzioni wrapper. Questo tipo di funzione serve a “preparare” i dati da passare ad una funzione,

eventualmente ricorsiva. Guardiamo questo esempio: La funzione in verde funge

void MergeSort(Item A[], Item B[], int N){ da “preparatore”, cioè, dai

int l=0, r=N-1; dati inseriti o acquisiti

MergeSortR(A, B, l, r); genera altri dati che

serviranno alla funzione

} ricorsiva in blu.

void MergeSortR(Item A[], Item B[], int l, int r){ Il termine “wrapper” deriva

int q = (l + r)/2; dell’inglese to wrap che

if (r <= l) vuol dire “incartare”, cioè

indica, in questo caso, un

return; funzione in cui è incartata

MergeSortR(A, B, l, q); quella a cui servono i dati

MergeSortR(A, B, q+1, r); creati.

Merge(A, B, l, q, r);

}

Guardando all’ordinamento, invece, notiamo che all’interno della funzione verde è presente un secondo

vettore (Item che servirà in un secondo momento per “fondere” i due sotto-vettori ordinati. Tale

B[]),

vettore può essere dichiarano ed inizializzato all’interno del come in questo caso, oppure dichiarato

main,

all’interno della funzione wrapper come sotto.

MergeSort,

Si noti che, in questo, caso alla funzione ricorsiva sono passati due puntatori.

MergeSortR

for (k = l; k <= r; k++)

if (i > q)

void MergeSort(Item *A, int N){

B[k] = A[j++];

int l=0, r=N-1;

else if (j > r)

Item *B = (Item *)malloc(N*sizeof(Item)); //allocazione dinamica

B[k] = A[i++];

MergeSortR(A, B, l, r);

else if (ITEMlt(A[i], A[j]) || ITEMeq(A[i], A[j]))

} B[k] = A[i++];

void MergeSortR(Item *A, Item *B, int l, int r){

else

int q = (l + r)/2;

B[k] = A[j++];

if (r <= l)

for ( k = l; k <= r; k++ )

return;

A[k] = B[k];

MergeSortR(A, B, l, q);

return;

MergeSortR(A, B, q+1, r);

} Merge(A, B, l, q, r);

}

void Merge(Item *A, Item *B, int l, int q, int r) {

int i, j, k;

i = l;

j = q+1;

L’algoritmo prevede due cicli che scorrono il sotto-vettore destro e sinistro in contemporanea; così

for

facendo, si confrontano gli elementi correntemente considerati di ciascun sotto-vettore: a seconda della

condizione, viene scelto uno dei due elementi ed apposto all’interno del vettore finale. Nel caso in cui uno

dei due sotto-vettori termini i suoi elementi, essendo, l’altro sotto-vettore, ordinato, vengono apposti in

coda gli elementi restanti del sotto-vettore da fondere nel vettore finale.

Si noti che questo algoritmo è stabile e non in loco, perché richiede l’ausilio di un vettore secondario in cui

parcheggiare l’ordinamento.

Analisi di complessità

= 2

L’approccio è divide et impera. Per ipotesi, consideriamo elementi.

• () = Θ(1), perché la divisione consiste nel passaggio dei parametri di riferimento, il cui centrale

è calcolato tramite una sola divisione;

• () = Θ(), perché effettuata dall’algoritmo nella funzione Merge.

• = 2; = 2, perché da ogni vettori non elementare si generano 2 sotto-vettori di dimensione

dimezzata.

() + () = Θ().

Quindi

Equazione alle ricorrenze

() = ( ) + = 2 ( ) + > 1

{ 2

(1) = 1 = 1

Per unfolding:

( ) = 2 ( ) +

2 4 2

( ) = 2 ( ) +

4 8 4

= 1 → = log .

Termina quando il vettore è elementare, cioè: 2

2

() = + 2 ∙ ∙ ∙ ( ) + + = + 2 ∙ ( ) + 2 ∙ + = + 8 ( ) + 4 ∙ + 2 ∙ =

{2 [2 ] } [4 ]

8 4 2 8 4 2 8 4 2

log log

2 2

(1

= + + + 8 ( ) = 3 + 8 ( ) = ∑ 2 ∙ = ∙ ∑ 1 = ∙ + log ) = ( ∙ log )

2

8 8 2

=0 =0

Bottom-up Merge Sort

È la versione non ricorsiva dell’omonimo algoritmo. Funziona così: partendo da sotto-vettori di lunghezza

unitaria (ordinati per costruzione), si applica il per ottenere a ogni passo vettori ordinati di

Merge

lunghezza doppia; il programma termina quando il vettore ha dimensione pari a quella del vettore iniziale.

A LLEGO UN ESEMPIO

C:\U \ .LAPTOP-8L623GR6\D \ \ \ \ \ \A _ _ _ _23. 4 - L VLC 2020-11-24 16-00-17. 4

SERS ALANT ESKTOP UNI SECONDOANNO APA TEORIA VIDEOACQUISITI LGORITMI E PROGRAMMAZIONE LEZ MP ETTORE MULTIMEDIALE MP

Codice

void BottomUpMergeSort(Item *A, int N) {

int i, m, l=0, r=N-1;

Item *B = (Item *)malloc(N*sizeof(Item));

for (m = 1; m <= r – l; m = m + m)

for (i = l; i <= r – m; i += m + m)

Merge(A, B, i, i+m-1, min(i+m+m-1,r));

}

Quick-sort ricorsivo

L’algoritmo appena rappresentato, seppur di complessità ottima, presenta alcune limitazioni, tra le quali

l’imposizione che il vettore abbia un numero di elementi pari ad una potenza di 2 e la necessità di

ricombinare gli elementi, oltre al fatto che non è in-loco.

Per questo, il signor Hoare nel 1961, propose questo algoritmo ricorsivo che non ha tali limitazioni e

interpella una divisione intelligente del vettore da ordinare. Tale divisione risiede nella determinazione dei

due sotto-vettori (definiti in loco), che viene effettuata in questo modo:

1. Si sceglie un elemento pivot (arbitrario); ad esempio x=A[q];

2. A sinistra di tale elemento staranno tutti gli elementi più piccoli di x;

3. A destra staranno tutti gli elementi più grandi di x;

4. Al termine, in automatico il pivot si ritroverà nella posizione corretta.

Ne consegue che l’indice del pivot non è necessariamente quello che divide il vettore a metà.

int partition (Item *A, int l, int r ){

int i = l-1, j = r;

Item x = A[r];

for ( ; ; ) { //ciclo for non inizializzato (non termina)

while(ITEMlt(A[++i], x));

while(ITEMgt(A[--j], x))

if (j == l)

break;

if (i >= j)

break;

Swap(A, i, j);

}

Swap(A, i, r);

return i;

}

Nel codice, viene scelto l’elemento più a destra fa da pivot, che verrà confrontato sia da destra che da

sinistra con i restanti elementi del vettore: i due cicli si occupano di questo. In particolare, il primo

while

ricerca il primo elemento più grande del pivot dall’inizio del vettore verso destra, il secondo ricerca il primo

elemento più piccolo dal primo elemento a sinistra del pivot, verso sinistra. Quando i corrispondenti indici

sono stati trovati, gli elementi corrispondenti sono scambiati di posizione. Gli indici e non vengono

i j

riportati ad un valore iniziale, perciò riprendono dal corrispondente punto del vettore dove si erano

fermati. Il secondo si ferma, eventualmente, quando non ci sono elementi più piccoli del pivot da

while

spostare. Nel momento in cui l’indice che scandiva il vettore da sinistra, è uguale od oltrepassa l’indice

i,

il ciclo termina e l’elemento all’indice viene scambiato con l’elemento pivot, che si viene, quindi, a

j, for i

trovare in posizione corretta.

A LLEGO UN ESEMPIO

C:\U \ .LAPTOP-8L623GR6\D \ \ \ \ \ \A _ _ _ _23. 4 - L VLC 2020-11-24 17-36-59. 4

SERS ALANT ESKTOP UNI SECONDOANNO APA TEORIA VIDEOACQUISITI LGORITMI E PROGRAMMAZIONE LEZ MP ETTORE MULTIMEDIALE MP

Nello schema a sinistra,

si osservino i pivot

considerati

ricorsivamente: da

sinistra verso destra, essi

compongono il vettore

ordinato.

Il codice generale

dell’algoritmo è il

seguente.

Codice