Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

O

5.3. ALCUNE REGOLE PER IL CALCOLO DI 51

ordina il vettore A

O(1)

costa se la dimensione del vettore è costante – ciò non è vero se la

dimensione di A dipende dall’input.

inserisci l’elemento E nella lista L

può richiedere tempo costante o meno, dipendentemente dall’implementazione

della lista.

Mini esempio.

1. x := 0

2. For i:=1 to n do

3. x := x+i O(1). O(1). O(1)

Il passo 1 costa Il passo 3 costa I passi 2 e 3 costano: +

O(1)] O(1) O(1) O(1) O(n) O(n).

n [O(1) + = + n = + = Lintero algoritmo

O(1) O(n) O(n),

ha costo: + = ovvero lineare nella dimensione dell’input.

Esercizio

1. x := 0

2. i :=1

3. While i<=n do

4. For j:=1 to i do

5. Begin

6. x := x+i *j

7. y := i+1

8. End

9. i:=i+1 2

O(n

Dimostrare che il tempo richiesto è ). O

5.3 Alcune regole per il calcolo di

Regola della somma O(f

Se una sezione di codice A di complessità (n)) è seguita da una sezione

O(g(n))

di codice B di complessità allora la complessita di A + B (ovvero,

O(max[f

la complessità del tutto) è data da (n), g(n)]).

52CAPITOLO 5. LINGUAGGI PER LA DESCRIZIONE DI ALGORITMI

Regola del prodotto O(f O(g(n))

Se una sezione di codice A di complessità (n)) è eseguita volte,

O(f

allora la complessità globale è (n) g(n)).

Caso particolare: Se g(n) = k, costante indipendente da n, allora la

O(k O(f

complessità globale è f (n)) = (n)).

5.3.1 Applicazione: funzioni polinomiali

k k−1

T (n) = c n + c n + . . . + c

k k−1 0

k

O(n

Si ha T (n) = ). Si deduce dalla regola della somma:

T (n) = T (n) + . . . + T (n)

k 0

dove i

T (n) = c n

i i

e dalla regola del prodotto, poichè i i

O(c O(n

T (n) = n ) = )

i i

Capitolo 6

Algoritmi ricorsivi

Si presuppone che lo studente abbia gia incontrato la nozione di algoritmo

ricorsivo all’interno del corso di ”Programmazione”.

Sicuramente lo studente avrà incontrato alcuni esempi canonici, quali

l’algoritmo per il calcolo del fattoriale di un numero e l’algoritmo per risolvere

il problema della Torre di Hanoi, ed avrà studiato la loro implementazione

in Pascal.

Probabilmente lo studente avrà studiato anche il quicksort o il mergesort,

dipendentemente dal contenuto del corso di ”Programmazione”.

Si presuppone che lo studente abbia già incontrato la tecnica di dimostrazione

per induzione nel corso di ”Programmazione” e/o in uno dei corsi di Matem-

atica del primo anno.

Agli algoritmi ricorsivi saranno dedicate due lezioni di due ore ciascuna.

Verrà innanzitutto presentata la definizione di algoritmo ricorsivo e ver-

ranno ripresi alcuni esempi canonici già incontrati nel corso di ”Program-

mazione”.

Si mostrerà poi come la ricorsione permette una migliore comprensione

di un algoritmo e semplifica l’analisi di correttezza dello stesso, mostrando

come esempio i due approcci ricorsivo ed iterativo alla visita di un albero.

Infine si accennerà brevemente al problema di calcolare la complesità di

un algoritmo ricorsivo, problema che sarà affrontato in dettaglio in un ciclo

di lezioni successivo. 53

54 CAPITOLO 6. ALGORITMI RICORSIVI

6.1 Introduzione

Si definisce ricorsiva una prodedura P che invoca, direttamente o

indirettamente, se stessa.

L’uso della ricorsione permette di ottenere spesso una descrizione più chiara

e concisa di algoritmi, di quanto sia possibile senza la ricorsione.

Gli algoritmi ricorsivi:

1 Spesso costituiscono il metodo più naturale di risoluzione di un prob-

lema;

2 Sono facili da comprendere;

3 Sono facili da analizzare:

• La correttezza di un programma ricorsivo si dimostra facilmente

per induzione;

• Il calcolo della complessità temporale di un algoritmo ricorsivo si

riduce alla soluzione di relazioni di ricorrenza.

6.2 Qualche mini esempio

Calcolo del fattoriale di un numero

Mostriamo qui di seguito una procedura iterativa ed una ricorsiva per calco-

lare il fattoriale di un numero n.

1. Fattoriale(n)

2. int fatt;

3. fatt=1;

4. for i=2 to n

5. fatt := fatt * i

6. return( fatt )

1. Fattoriale(n)

2. if n=1

3. then return(1)

4. else return(n * Fattoriale(n-1))

6.3. LINGUAGGI DI PROGRAMMAZIONE CHE CONSENTONO LA RICORSIONE55

Come si evince dal precedente esempio, la versione ricorsiva è più concisa,

più facile da comprendere e da analizzare. Occorre comunque notare che

l’implementazione ricorsiva non offre alcun vantaggio in termini di velocità

di esecuzione (cioè di complessità).

La dimostrazione di correttezza della prima versione è alquanto laboriosa.

Per quanto riguarda la seconda versione, la correttezza si dimostra facilmente

per induzione matematica. Infatti:

1 (correttezza dal passo base)

L’algoritmo è certamente corretto per n = 1, in quanto 1! = 1;

2 (correttezza del passo induttivo)

Se l’algoritmo calcola correttamente n!, allora esso calcola corretta-

·

mente (n + 1)!, che è dato da (n + 1) n!.

6.3 Linguaggi di programmazione che consentono

la ricorsione

Non tutti i linguaggi di programmazione permettono la ricorsione: ad esem-

pio, il FORTRAN oppure il COBOL non la permettono.

Fortunatamente, il linguaggio PASCAL, che è stato studiato nel cor-

so di ”Programmazione”, oppure il linguaggio C, che viene trattato nel

”Laboratorio di Algoritmi e Strutture Dati”, lo permettono.

Procedura attiva

Con il termine procedura attiva indichiamo la procedura in esecuzione ad

istante assegnato. Tale procedura sarà caratterizzata da un contesto, che

è costituito da tutte le variabili globali e locali note alla procedura in tale

istante.

Stack e record di attivazione

I linguaggi che permettono la ricorsione utilizzano in fase di esecuzione una

pila per tenere traccia della sequenza di attivazione delle varie procedure

ricorsive.

In cima a tale pila sarà presente il record di attivazione della procedura

correntemente attiva. Tale record contiene le variabili locali alla procedura, i

56 CAPITOLO 6. ALGORITMI RICORSIVI

parametri ad essa passati, e l’indirizzo di ritorno, vale a dire il contenuto del

PROGRAM COUNTER nel momento in cui la procedura è stata invocata.

Quando una procedura P è invocata viene posto sulla pila un nuovo record

di attivazione. Ciò indipendentemente dal fatto che siano già presenti nella

pila altri record di attivazione relativi alla stessa procedura.

Quando la procedura attiva P termina viene rimosso dalla pila il record

di attivazione che si trova in cima ad essa, e l’indirizzo di ritorno in essa

contenuto viene utilizzato per cedere il controllo nuovamente alla procedura

chiamante (vale a dire, alla penultima procedura attiva).

6.3.1 Visita di un albero binario

Nel classico libro [4] a pp. 56–57 sono riportati un algoritmo ricorsivo ed uno

non-ricorsivo per visitare un albero binario.

Si noti che la versione non-ricorsiva fa uso esplicito di una pila per tenere

traccia dei nodi visitati.

La versione ricorsiva è molto più chiara da comprendere; la pila c’è ma

non si vede, ed è semplicemente lo stack che contiene i record di attivazione

delle procedure.

Capitolo 7

L’approccio Divide et Impera

Nel corso degli anni, i ricercatori nel campo dell’informatica hanno identi-

ficato diverse tecniche generali di progetto di algoritmi che consentono di

risolvere efficientemente molti problemi.

Lo studente avrà gia avuto modo di incontrare una di tali tecniche, il

backtracking, nel corso di ”Programmazione”, in relazione al classico proble-

ma delle ”Otto Regine”. Tale tecnica sarà ripresa e trattata in dettaglio nei

corsi di ”Intelligenza artificiale”

In un corso introduttivo di ”Algoritmi e strutture dati” ritengo essenziale

includere almeno:

• Il metodo Divide et Impera;

• La programmazione dinamica;

• Le tecniche greedy.

Le tecniche di ricerca locale sono anch’esse molto importanti e meritano

una trattazione approfondita. Ritengo possibile omettere tali tecniche dal

momento che saranno affrontate in dettaglio nei corsi di ”Intelligenza artifi-

ciale”.

Si noti comunque che, prima di passare alla progettazione di un algoritmo,

è necessario individuare se il problema da risolvere è irrisolubile o intrattabile.

In tali casi nessuna tecnica di progetto ci permetterà di ottenere, ovviamente,

algoritmi efficienti.

Il metodo Divide et Impera è una tra le tecniche più importanti, e dal

più vasto spettro di applicazioni. 57

58 CAPITOLO 7. L’APPROCCIO DIVIDE ET IMPERA

A tale tecnica saranno dedicate due lezioni da due ore ciascuna.

Nella prima lezione, dopo una definizione formale della tecnica, sarà pre-

sentato un esempio notevole, il mergesort. Si mostrerà quindi come effettuare

l’analisi di complessità di tale algoritmo, espandendo la relazione di ricorrenza

che ne definisce il tempo di esecuzione. Il risultato di tale analisi, O(n log n)

consentirà allo studente di apprezzare meglio tale algoritmo, confrontandone

la complessità con quella di un algoritmo di ordinamento già noto, il Bubble-

sort. Si accennerà quindi al fatto che il problema ordinamento ha complessità

Ω(n log n), e quindi lo studente avrà incontrato un algoritmo ottimale di or-

dinamento. La dimostrazione della complessità del problema ordinamento,

attraverso alberi decisionali, sarà comunque relegata ad un ciclo di lezioni

successivo dedicato al problema ordinamento.

Si passerà quindi a discutere il problema del bilanciamento, e per mostrare

le implicazioni si farà vedere che modificando opportunamente il Mergesort in

modo da avere sottoproblemi di dimensione differente, l’algoritmo risultante

sarà decisamente meno efficiente, ed avrà una complessità pari a quella del

Bubblesort.

Nella seconda lezione si mostrerà come, tale metodo, sebbene si utilizzino

sottoproblemi di dimensione simile, non porta in genere ad algoritmi più

efficienti. In altre parole, occorre comunque effettuare sempre l’analisi della

complessità dell’algoritmo per poter dire se sia efficiente o meno.

A tal fine, si mostrerà un algoritmo ricorsivo di moltiplicazione di matrici,

che richiede ad ogni passo ricorsivo 8 moltiplicazioni di matrici di dimensione

dimezzata. Dall’analisi del tempo di esecuzione di tale algoritmo lo stu-

dente potrà evincere il fatto che la sua complessità, in termini di operazioni

aritmetiche elementari, è pari a quella dell’algoritmo classico.

Si mostrerà quindi l’algoritmo di Strassen, che è una evoluzione della tec-

nica (intuitiva) ricorsiva appena vista, ma richiede ad ogni passo il calcolo di

7 prodotti di matrici di dimensione pari alla metà della dimensione originale.

Si mostrerà quindi come analizzare il tempo di esecuzione di tale algoritmo.

Per concludere la lezione, si accennerà brevemente alla complessità del

problema Moltiplicazione di Matrici, ed al fatto che nessun algoritmo otti-

male è noto sinora per risolvere tale problema.

7.1. INTRODUZIONE 59

7.1 Introduzione

Il metodo Divide et Impera è una tra le tecniche di progetto più importanti,

e dal più vasto spettro di applicazioni. Esso consiste nello spezzare un prob-

lema in sottoproblemi di dimensione più piccola, risolvere ricorsivamente tali

sottoproblemi, e quindi ottenere dalle soluzioni dei sottoproblemi la soluzione

del problema globale.

Distinguiamo quindi in un algoritmo ottenuto attraverso tale tecnica 3

fasi:

1 suddivisione del problema originale in sottoproblemi

Il problema originale di dimensione n è decomposto in a sottoproblemi

di dimensione minore f (n), . . . , f (n);

1 a

2 soluzione ricorsiva dei sottoproblemi

Gli a sottoproblemi sono risolti ricorsivamente;

3 fusione delle soluzioni, per ottenere la soluzione del problema originale

Le soluzioni degli a sottoproblemi sono combinate per ottenere la soluzione

del problema originale.

A ciascuna fase sono associati dei costi. Indichiamo con Sudd(n) il tempo

richiesto dal punto 1, e con F us(n) il tempo richiesto dal punto 3, per un

input di dimensione n. Il costo associato al punto 2 sarà ovviamente

T (f (n)) + . . . + T (f (n))

1 a

Si noti che problemi di dimensione sufficiente piccola possono essere risolti

trivialmente in tempo costante c, consultando una tabella costruita in prece-

denza.

Otteniamo pertanto la seguente equazione che esprime il tempo di ese-

cuzione dell’algoritmo:

T (n) = c n < n ;

0 ≥

T (n) = T (f (n))+. . .+T (f (n))+Sudd(n)+F us(n) n n

1 a 0

Si noti che, molto spesso, il tempo di suddivisione in sottoproblemi è

irrilevante, oppure è assorbito dagli altri termini.

In ogni caso indichiamo con d(n) la somma dei termini Sudd(n) e F us(n),

e chiamiamo tale termine la funzione guida della equazione di ricorrenza.

60 CAPITOLO 7. L’APPROCCIO DIVIDE ET IMPERA

7.1.1 Esempio: il Mergesort

Sia S una lista di n elementi da ordinare. Assumiamo che n sia una potenza

k

di 2, ovvero n = 2 , in modo da poter applicare un procedimento dicotomico.

Nell’algoritmo che segue L, L e L indicano variabili locali di tipo lista.

1 2

1. Mergesort( S ):

2. Se S ha 2 elementi

3. ordina S con un solo confronto e ritorna la lista ordinata

4. altrimenti

5. Spezza S in due sottoliste S e S aventi la stessa cardinalità

1 2

6. Poni L = Mergesort( S )

1 1

7. Poni L = Mergesort( S )

2 2

8. Fondi le due liste ordinate L ed L in una unica lista L

1 2

9. Ritorna( L )

La fusione di due liste ordinate in una unica lista si effettua molto semplice-

mente in n passi, vale a dire in tempo Θ(n) Ad ogni passo occorre semplice-

mente confrontare i due elementi più piccoli delle liste L ed L , estrarre il

1 2

minore tra i due dalla lista a cui appartiene, ed inserirlo in coda alla nuova

lista L.

Si nota facilmente che:

• il tempo richiesto per ordinare una lista di cardinalità 2 è costante;

Quindi possiamo scrivere T (2) = O(1).

• per ordinare una lista di dimensione maggiore di 2 occorre:

– spezzare la lista in due sottoliste

questo richiede tempo costante

– ordinare ricorsivamente le 2 sottoliste di dimensione n/2

questo richiede tempo T (n/2) + T (n/2)

– fondere il risultato

questo richiede tempo Θ(n)

Quindi T (n) = O(1) + T (n/2) + T (n/2) + Θ(n) = 2 T (n/2) + Θ(n).

Le due formule per T (n) appena viste, che esprimono tale funzione quando

n = 2 e quando n è una potenza di 2, insieme costituiscono ciò che si chiama

7.2. BILANCIAMENTO 61

una equazione di ricorrenza. In altre parole, possiamo calcolare T (n) se

conosciamo T (n/2), e cosi’ via . . . Poichè T (2) è noto, ci è possibile calcolare

T (n) per qualunque valore di n che sia una potenza di due.

Nelle lezioni successive mostreremo come risolvere tale relazione, ovvero

come ottenere una stima per T (n) che non dipenda da T (h) per qualche

h < n. Per ora basti sapere che asintoticamente T (n) = O(n log n),

quindi il Mergesort è sicuramente (asintoticamente) migliore dello stranoto

Bubblesort.

7.2 Bilanciamento

Abbiamo visto che nel Mergesort il problema originale viene suddiviso in

sottoproblemi di pari dimensione. Questo non è un caso. Infatti, un principio

generale dettato dall’esperienza per ottenere algoritmi efficienti utilizzando

l’approccio Divide et Impera, è quello di partizionare il problema assegnato

in sottoproblemi aventi all’incirca la stessa dimensione.

Se indichiamo con a il numero dei sottoproblemi e con n/b la dimensione di

ciascun sottoproblema, allora il tempo di esecuzione di un siffatto algoritmo

sarà descritto dalla seguente equazione di ricorrenza:

T (n) = c n < n 0

T (n) = a T (n/b) + d(n) n n 0

Tali equazioni di ricorrenza possono essere risolte utilizzando delle tecniche

standard che vedremo nelle seguenti lezioni.

Si noti che nel Mergesort a e b sono uguali tra loro (pari a 2); questo è

semplicemente un caso, e non costituisce una regola generale. Nell’algoritmo

di moltiplicazione di matrici di Strassen vedremo ad esempio che a = 7 e

b = 2.

Controesempio: l’Insertion Sort

L’Insertion Sort può essere visto come un caso particolare del Mergesort,

dove le sottoliste da ordinare hanno dimensione rispettivamente 1 ed n 1,

essendo n la dimensione della lista originale. È noto che la complessità di

2

tale algoritmo è O(n ). Ciò è stato dimostrato in una lezione introduttiva

dedicata al calcolo della comnplessità di algoritmi espressi utilizando uno

62 CAPITOLO 7. L’APPROCCIO DIVIDE ET IMPERA

pseudo-linguaggio. In tale lezione, l’insertion sort è stato codificato in forma

iterativa. La corrispondente versione ricorsiva è la seguente:

1. InsertionSort( S ):

2. Se S ha 1 elemento

3. Ritorna S

4. altrimenti −

5. Spezza S in due sottoliste S e S di cardinalità 1 ed n 1

1 2

6. Poni L = InsertionSort( S )

1 1

7. Poni L = InsertionSort( S )

2 2

8. Fondi le due liste ordinate L ed L in una unica lista L

1 2

9. Ritorna( L )

La complessità di tale algoritmo è espressa dalla relazione di ricorrenza:

( T (1) = 1 −

T (n) = T (1) + T (n 1) + n (n > 1)

2

la cui soluzione è T (n) = O(n ).

7.3 L’algoritmo di Strassen

Siano assegnate due matrici quadrate A = [a ] e B = [b ] di dimensione n.

ij ij nk=1

P

Si voglia calcolare la matrice prodotto A·B = [c ], dove c = a b .

ij ij ik kj

Lo studente può verficare facilmente che l’algoritmo tradizionale che cal-

3

cola il prodotto delle due matrici richiede 0(n ) operazioni aritmetiche (somme

e prodotti).

E possibile fare di meglio?

Supponiamo per semplicità che n sia una potenza di 2. Allora possi-

amo decomporre le matrici A, B e C ciascuna in 4 sottomatrici quadrate di

dimensione n/2 (ovvero possiamo considerarle come una matrice a blocchi):

! ! !

A A B B C C

11 12 11 12 11 12

A = B = C = (7.1)

A A B B C B

21 22 21 22 21 22

Si noti ora che la generica sottomatrice C è data da

ij

A B + A B (7.2)

i1 1j i2 2j

7.3. L’ALGORITMO DI STRASSEN 63

Possiamo quindi pensare ad un primo algoritmo ricorsivo, come segue:

1. Se A e B hanno dimensione n = 1

2. Allora moltiplica (banalmente) le due matrici

3. Altrimenti

4. Spezza A e B come in (7.1)

5. Calcola le sottomatrici C di C utilizzando la relazione (7.2)

ij

Qual è la complessità di tale algoritmo? È possibile calcolare ogni matrice

C con 2 moltiplicazioni di matrici quadrate di dimensione n/2 ed 1 somma

ij

di matrici quadrate di dimensione n/2.

Il prodotto di due matrici quadrate di dimensione n può essere allora

ricondotto ricorsivamente ad 8 prodotti di matrici quadrate di dimensione

n/2, e 4 addizioni di matrici quadrate di dimensione n/2. 2

Poichè due matrici quadrate di dimensione n/2 si sommano con (n/2)

operazioni elementari (somme di scalari), è possibile esprimere il tempo di

esecuzione dell’algoritmo attraverso la seguente equazione:

( T (1) = 1 2

T (n) = 8 T (n/2) + 4 (n/2) (n > 1) 3

La soluzione di questa equazione di ricorrenza è data da T (n) = 0(n ). Per-

tanto tale algoritmo non presenta alcun vantaggio sull’algoritmo tradizionale.

L’idea di Strassen

Si calcolino le seguenti matrici quadrate P , di dimensione n/2:

i

P = (A + A ) (B + B )

1 11 22 11 22

P = (A + A ) B

2 21 22 11

P = A (B B )

3 11 12 22

P = A (B B )

4 22 21 11

P = (A + A ) B

5 11 12 22

P = (A A ) (B + B )

6 21 11 11 12

P = (A A ) (B + B )

7 12 22 21 22

Lo studente, se lo desidera, può verificare che:

C = P + P P + P

11 1 4 5 7

64 CAPITOLO 7. L’APPROCCIO DIVIDE ET IMPERA

C = P + P

12 3 5

C = P + P

21 2 4 −

C = P + P P + P

22 1 3 2 6

È possibile calcolare le matrici P con 7 moltiplicazioni di matrici quadrate

i

di dimensione n/2 e 10 fra addizioni e sottrazioni di matrici quadrate di

dimensione n/2.

Analogamente, le C si possono calcolare con 8 addizioni e sottrazioni a

ij

partire dalle matrici P .

i

Il prodotto di due matrici quadrate di dimensione n può essere allora

ricondotto ricorsivamente al prodotto di 7 matrici quadrate di dimensione

n/2, e 18 tra addizioni e sottrazioni di matrici quadrate di dimensione n/2.

Poichè due matrici quadrate di dimensione n/2 si sommano (o sottrag-

2

gono) con (n/2) operazioni, è possibile esprimere il tempo di esecuzione

dell’algoritmo di Strassen attraverso la seguente equazione di ricorrenza:

( T (1) = 1 2

T (n) = 7 T (n/2) + 18 (n/2) (n > 1) log 7

O(n

La soluzione di questa equazione di ricorrenza è data da T (n) = ).

2

Poichè log 7 < log 8 = 3, l’algoritmo di Strassen risulta più efficiente

2 2

dell’algoritmo classico di moltiplicazione di matrici.

Capitolo 8

Tecniche di analisi di algoritmi

ricorsivi

Nel corso delle lezioni sul calcolo della complessità di un algoritmo sono state

date delle semplici regole per calcolare la complessità di un algoritmo iterativo

espresso utilizzando uno pseudo-linguaggio per la descrizione di algoritmi.

In particolare sono state presentate:

• La regola della somma,

per calcolare la complessità di una sequenza costituita da un numero

costante di blocchi di codice;

• La regola del prodotto,

per calcolare la complessità di una sezione di programma costituita da

un blocco di codice che viene eseguito iterativamente.

Per mostrare come applicare tali regole, sono stati utilizzati come esempi gli

algoritmi di bubble sort, inserion sort e moltiplicazione di matrici.

Le tecniche per analizzare la complessità di algoritmi ricorsivi sono molto

differenti dalle tecniche viste finora, ed utilizzano a tal fine delle relazioni di

ricorrenza. Le tecniche per risolvere tali relazioni di ricorrenza sono molto

spesso ad hoc, e ricordano piuttosto vagamente le tecniche per risolvere le

equazioni differenziali. Non è richiesto allo studente alcuna conoscenza di

equazioni differenziali o di matematiche superiori per poter comprendere le

tecniche base che saranno trattate nelle seguenti due lezioni. L’unico pre-

requisito matematico è la conoscenza della formula che esprime la somma di

una serie geometrica finita, formula che verrà richiamata durante la lezione.

65

66CAPITOLO 8. TECNICHE DI ANALISI DI ALGORITMI RICORSIVI

8.1 Introduzione

Molti classici algoritmi possono essere descritti mediante procedure ricorsive.

Di conseguenza l’analisi dei relativi tempi di calcolo è ridotta alla soluzione

di una o più equazioni di ricorrenza nelle quali si esprime il termine n-esimo

di una sequenza in funzione dei termini precedenti. Presentiamo le principali

tecniche utilizzate per risolvere equazioni di questo tipo o almeno per ottenere

una soluzione approssimata.

Supponiamo di dover analizzare un algoritmo definito mediante un in-

sieme di procedure P , P , . . . , P che si richiamano ricorsivamente fra loro.

1 2 m

Vogliamo quindi stimare, per ogni i = 1, 2, . . . , m la funzione T (n) che

i

rappresenta il tempo di calcolo impiegato dalla i-ma procedura su dati di

dimensione n. Se ogni procedura richiama le altre su dati di dimensione

minore, sarà possibile esprimere T (n) come funzione dei valori T (k) tali che

i j

∀j ∈ {1, 2, . . . , m} : k < n.

Per semplicificare il discorso, supponiamo di avere una sola procedura

P che chiama ricorsivamente se stessa su dati di dimensione minore. Sia

T (n) il tempo di calcolo richiesto da P su un input di dimensione n, nelcaso

peggiore.

Sarà in generale possibile esprimere T (n) come funzione dei precedenti

termini T (m) con 1 m < n. In molti degli algoritmi presentati in questo

corso T (n) dipende funzionalmente da un solo termine T (m), com m < n.

Una equazione che lega funzionalmente T (n) a T (m) con m < n è detta

equazione di ricorrenza.

Equazioni di ricorrenza

Diciamo che una sequenza a , a , . . . di elementi appartenenti ad un insieme

1 2

S è definita attraverso una equazione di ricorrenza di ordine k se il generico

termine a dipende funzionalmente dai precedenti k, ovvero se

n a = f (a , . . . , a )

n n−1 n−k

k →

per qualche funzione f : S S.

Si noti che per poter definire univocamente la sequenza occorre assegnare

le condizioni iniziali, ovvero specificare i valori dei primi k termini della

sequenza: a , . . . , a .

1 k

Le equazioni di ricorrenza che incontreremo in seguito sono tutte di ordine

1 (del primo ordine).

8.1. INTRODUZIONE 67

Fattoriali. La sequenza dei fattoriali dei numeri naturali:

1, 2, 6, 24, . . .

si può esprimere attraverso la seguente equazione di ricorrenza del primo

ordine: 1! = 1 · −

n! = n (n 1)! (n > 1)

Numeri di Fibonacci. Un’altra sequenza notevole è costitituita dai numeri

di Fibonacci F , ed è definita dalla seguente equazione di ricorrenza del

n

secondo ordine: F = 0

0

F = 1

1

F = F + F (n > 1)

n n−1 n−2

Problema: Data una sequenza definita attraverso una equazione di ricor-

renza di ordine k vogliamo trovare una formula chiusa per il termine n-mo

di tale sequenza, ovvero una formula per esprimere l’n-mo termine senza fare

riferimento ai termini precedenti.

Mini esempio: Consideriamo la seguente equazione di ricorrenza:

a = 1

0

a = c a (n > 0)

n n−1

dove c è una costante assegnata. Evidentemente, l’unica soluzione con la

n

condizione al contorno a = 1 è data da a = c .

0 n

Le equazioni di ricorrenza serviranno ad analizzare la complessità

degli algoritmi ricorsivi.

Si osservi che data la condizione al contorno (ovvero, se sono noti tutti i

valori di T (n) per 0 < n n ) allora esiste ununica funzione T (n) che

0

soddisfa l’equazione di ricorrenza assegnata.

Per collegare quanto appena detto all’analisi di algoritmi, consideriamo

il Mergesort. Ricordiamo che il tempo di esecuzione di tale algoritmo su un

input di dimensione n dipende funzionalmente (in qualche modo) dal tempo

68CAPITOLO 8. TECNICHE DI ANALISI DI ALGORITMI RICORSIVI

di esecuzione dello stesso algoritmo su un input di dimensione n/2. Possiamo

inoltre assumere che il tempo si esecuzione dell’algoritmo su un problema di

dimensione 2 sia dato da una costante c. Pertanto otteniamo la seguente

sequenza: T (2), T (4), T (8), T (16), . . .

ovvero, se utilizziamo la notazione precedentemente introdotta, otteniamo

n

una sequenza a , a , . . . dove a = c e a = T (2 ).

1 2 1 n

L’analisi di un algoritmo ricorsivo prevede quindi sempre due fasi:

• Deduzione delle relazioni di ricorrenza contenenti come incognita la

funzione T (n) da stimare;

• Soluzione delle relazioni di tali relazioni di ricorrenza.

8.1.1 Esempio: Visita di un albero binario

Si consideri la seguente procedura ricorsivoa di attraversamento di un albero

binario:

1. preorder( v ):

2. inserisci v in una lista

3. se v ha un figlio sinistro w

4. allora preorder(w)

5. se v ha un figlio destro w

6. allora preorder(w)

Tale procedura viene invocata passando come parametro la radice dell’al-

bero da attraversare. Qual è la complessità di tale procedura? Si supponga

che il passo (2) richieda tempo costante. Denotiamo con T (n) il tempo

richiesto per attraversare un albero costituito da n nodi. Supponiamo che

il sottoalbero sinistro di v abbia i nodi (0 i < n). Allora, il sottoalbero

− −

destro di v avrà n i 1 nodi. Pertanto, l’attraversamento di un albero

binario avente radice v richiederà:

1 Tempo costante c per il passo (2);

2 Tempo T (i) per i passi (3,4);

− −

3 Tempo T (n i 1) per i passi (5,6)

8.2. SOLUZIONE DELLE EQUAZIONI DI RICORRENZA 69

da cui si ricavs la seguente equazione di ricorrenza:

T (0) = 0 − − ≤

T (n) = c + T (i) + T (n i 1) (0 i < n)

Lo studente può verificare facilmente per induzione che la soluzione di tale

equazione di ricorrenza è data da T (n) = cn, e pertanto T (n) = Θ(n).

8.2 Soluzione delle equazioni di ricorrenza

La risoluzione delle ”equazioni di ricorrenza” è essenziale per l’analisi degli

algoritmi ricorsivi. Sfortunatamente non c’è un metodo generale per risolvere

equazioni di ricorrenza arbitrarie. Ci sono, comunque, diverse strade per

”attaccare” le equazioni di ricorrenza.

1 La forma generale della soluzione potrebbe essere nota.

In questo caso, occorre semplicemente determinare i parametri incog-

niti.

Esempio 19 Sia data l’equazione:

( T (n) = 7 n

T (n) = 2T ( ) + 8

2

Si ipotizzi che la soluzione abbia la seguente forma:

T (n) = an + b

Occorre ora determinare i parametri a e b. Questo si riduce alla

risoluzione di un sistema lineare di due equazioni in due incognite,

come segue: T (1) = a + b = 7 n

T (n) = an + b = 2T ( ) + 8

2

n

= 2(a + b) + 8

2

= an + 2b + 8

da cui −8

b = a = 15

quindi la nostra ipotesi era corretta, e si ha:

T (n) = 15n 8

70CAPITOLO 8. TECNICHE DI ANALISI DI ALGORITMI RICORSIVI

2 Espansione della formula di ricorrenza

in altre parole, occorre sostituire T (·) sul lato destro della ricorrenza

finchè non vediamo un pattern.

Esempio 20 Sia data l’equazione:

( 1 per n = 2

T (n) = n

2T ( ) + 2 per n > 2

2

Si ha allora n

T (n) = 2T ( ) + 2

2 n

= 2[2T ( ) + 2] + 2

4

n

= 4T ( ) + 4 + 2

4 n

= 4[2T ( ) + 2] + 4 + 2

8

n

= 8T ( ) + 8 + 4 + 2

8

..

. n k−1 k−2 k−3

k−1

= 2 T ( ) 2 + 2 + 2 + . . . + 4 + 2

k−1

2

| {z } | {z }

n k−1

P

| {z } p

2

2 T (2)=1 p=1

n 32

− −

= + n 2 = n 2

2

Ricordiamo per la comodità del lettore che la somma dei primi k + 1 termini

di una serie geometrica: k

0 1 2 k−1 k p

X

q + q + q + ... + q + q = q

p=0

è data da k+1 −

q 1

q 1

da cui k−1 k −

2 1

p k

X − − −

1 = 2 2 = n 2

2 = −

2 1

p=1

8.3 Il caso Divide et Impera

Una importante classe di equazioni di ricorrenza è legata all’analisi di algo-

ritmi del tipo divide et impera trattati in precedenza.

8.3. IL CASO DIVIDE ET IMPERA 71

Ricordiamo che un algoritmo di questo tipo suddivide il generico prob-

lema originale di dimensione n in un certo numero a di sottoproblemi (che

sono istanze del medesimo problema, di dimensione inferiore) ciascuna di di-

mensione n/b per qualche b > 1; quindi richiama ricorsivamente se stesso su

tali istanze ridotte e poi fonde i risultati parziali ottenuti per determinare la

soluzione cercata.

Senza perdita di generalità, il tempo di calcolo di un algoritmo di questo

tipo può essere descritto da una equazione di ricorrenza del tipo:

k

T (n) = a T (n/b) + d(n) (n = b k > 0) (8.1)

T (1) = c (8.2)

dove il termine d(n), noto come funzione guida, rappresenta il tempo neces-

sario per spezzare il problema in sottoproblemi e fondere i risultati parziali

in un’unica soluzione.

Si faccia ancora una volta attenzione al fatto che T (n) è definito solo per

potenze positive di b. Si assuma inoltre che la funzione d(·) sia moltiplicativa,

ovvero ∈

d(xy) = d(x) d(y) x, y N

Il comportamento asintotico della funzione T (·) è determinato confrontando

innanzitutto a con d(b).

Teorema Principale Si dimostra che: log a

se a > d(b) : T (n) = O(n )

b

log d(b)

se a < d(b) : T (n) = O(n )

b

log d(b)

se a = d(b) : T (n) = O(n log n)

b b

p

Inoltre, se d(n) = n , si ha log a

se a > d(b) : T (n) = O(n )

b

p

se a < d(b) : T (n) = O(n )

p

se a = d(b) : T (n) = O(n log n)

b

p

Si noti che il caso d(n) = n è piuttosto comune nella pratica (ad esempio,

nel MERGESORT si ha d(n) = n).

72CAPITOLO 8. TECNICHE DI ANALISI DI ALGORITMI RICORSIVI

Caso particolare: d(·) non è moltiplicativa

Supponiamo che la funzione guida non sia moltiplicativa, ad esempio:

T (1) = c

T (n) = 2 T (n/2) + f n n> 1

Si noti che la funzione d(n) = f (n) non è moltiplicativa. Consideriamo allora

la funzione U (n) definita come U (n) = T (n)/f , da cui deriva T (n) = U (n) f .

Possiamo scrivere quindi

f U (1) = c

f U (n) = 2 f U (n/2) + f n n> 1

da cui U (1) = c/f

U (n) = 2 U (n/2) + n n> 1

Si noti che in tale equazione la funzione guida è d(n) = n che è moltiplicati-

va. Risolviamo per U (n) ottenendo U (n) = O(n log n). Sostituiamo, infine,

ottenendo T (n) = f U (n) = f O(n log n) = O(n log n).

8.3.1 Dimostrazione del Teorema Principale

Sia assegnata la seguente equazione di ricorrenza:

( T (1) = c nb

T (n) = aT ( ) + d(n)

Si noti che n n n

) = aT ( ) + d( )

T ( i i+1 i

b b b

da cui discende che !

n

T (n) = aT + d(n)

b

" ! !#

n n

= a aT + d d(n)

2

b b

8.3. IL CASO DIVIDE ET IMPERA 73

n n

2

= a T + ad + d(n)

2

b b !

" ! !#

n n

n

2

= a aT + d + ad + d(n)

3 2

b b b

n n n

3 2

= a T + a d + ad + d(n)

3 2

b b b

= ... i−1 n

n

i i

X

= a T + a d

i i

b b

j=0

Si assuma ora che k

n = b

da cui k = log n

b

Si avrà pertanto k log n log a

a = a = n

b b

In generale, quindi si ha: k−1 j k−j

X

log a

T (n) = cn + a d(b )

b j=0

Soluz.Omogenea: Soluz.Particolare:

tempo per risolvere tempo per combinare

i sottoproblemi i sottoproblemi

Effettuiamo ora delle assunzioni sulla funzione guida d(·) per semplificare

l’ultima sommatoria. Assumiamo che d(·) sia moltiplicativa, cioè d(xy) =

p

· ∈

d(x) d(y) per ogni x, y N . Ad esempio d(n) = n è moltiplicativa, poichè

p p p

d(xy) = (xy) = x y = d(x)d(y).

Se d(·) è moltiplicativa, allora ovviamente:

i i

d(x ) = d(x)

74CAPITOLO 8. TECNICHE DI ANALISI DI ALGORITMI RICORSIVI

8.3.2 Soluzione Particolare

Definiamo la soluzione particolare P (n) della nostra equazione di ricorrenza

come segue: k−1 j k−j

X a d(b )

P (n) = j=0

Allora, si avrà k−1 −j

k j

X

P (n) = d(b ) a d(b )

j=0

k−1 i

a

k X

= d(b ) d(b)

j=0 k

a − 1

d(b)

k

= d(b ) a − 1

d(b)

k k

a d(b)

= a − 1

d(b)

Pertanto: k k

−d(b)

a

P (n) = a −1

d(b)

Abbiamo ora tre possibili casi:

CASO 1 : a > d(b) k log n log a

O(a O(a O(n

P (n) = ) = ) = )

b b

da cui log a log a log a

O(n O(n

T (n) = c n + ) = )

b b b

| {z } | {z }

sol.omogenea sol.particolare

ovvero log a

O(n

T (n) = )

b

Si noti che le soluzioni particolare e omogenea sono equivalenti (nella no-

O().

tazione

Per migliorare l’algoritmo occorre diminuire log a (ovvero, aumentare b

b

oppure diminuire a). Si noti che diminuire d(n) non aiuta.

8.3. IL CASO DIVIDE ET IMPERA 75

CASO 2 : a < d(b)

k k

d(b) a k log n log d(b)

O(d(b) O(d(b) O(n

P (n) = = ) = ) = )

b b

a

1 d(b)

da cui log a log d(b) log d(b)

O(n O(n

T (n) = c n + ) = )

b b b

| {z } | {z }

sol.omogenea sol.particolare

ovvero log d(b)

O(n

T (n) = )

b

p

Caso speciale: d(n) = n

Si ha p p

d(b) = b e log d(b) = log b = p

b b

da cui p

O(n

T (n) = )

La soluzione particolare eccede la soluzione omogenea. Per migliorare l’algo-

ritmo occorre diminuire log d(b), ovvero cercare un metodo più veloce per

b

fondere le soluzioni dei sottoproblemi.

CASO 3 : a = d(b) a − 1=0

La formula per le serie geometriche è inappropriata poichè d(b)

k−1 k−1

a

k i k k log n log d(b)

X

X

P (n) = d(b) ( ) = d(b) 1 = d(b) k = d(b) log n = n log n

b b

b b

d(b)

j=0 j=0

da cui log d(b) log d(b)

T (n) = c n + n log n

b b b

ovvero log d(b)

O(n

T (n) = log n)

b b

p

Caso speciale : d(n) = n

Si ha p

d(b) = n

76CAPITOLO 8. TECNICHE DI ANALISI DI ALGORITMI RICORSIVI

da cui p

O(n

T (n) = log n)

b

La soluzione particolare supera la soluzione omogenea. Per migliorare l’al-

goritmo occorre diminuire log d(b). Occorre a cercare un metodo più veloce

b

per fondere le soluzioni dei sottoproblemi.

8.3.3 Esempi a b d(b)

T (1) = c n

T (n) = 2T ( ) + n 2 2 2

1 2

n ) + n 4 2 2

T (n) = 4T (

2 2

n 2

) + n 4 2 4

T (n) = 4T (

3 2

n 3

T (n) = 4T ( ) + n 4 2 8

4 2

Si ha, in base alle precedenti considerazioni:

O(n

T (n) = log n)

1 .

2

O(n

T (n) = )

2 2

O(n

T (n) = log n)

3 .

3

O(n

T (n) = )

4

Si noti che T (n) rappresenta il tempo di esecuzione del Merge Sort.

1

Capitolo 9

Liste, Pile e Code

Si consiglia fortemente allo studente di studiare dal testo [4] le sezioni 1, 2,

3 e 4 del capitolo 2.

In alternativa é possibile studiare le sezioni 1, 2 e 3 del capitolo 11 del

testo [2]. 77

78 CAPITOLO 9. LISTE, PILE E CODE

Capitolo 10

Grafi e loro rappresentazione in

memoria

Si consiglia fortemente allo studente di studiare dal testo [4]

• le sezioni 1 e 2 del capitolo 6;

• la sezione 1 del capitolo 7.

Si richiede inoltre di implementare in C o C++ gli algoritmi base descritti

in tali sezioni. 79

80CAPITOLO 10. GRAFI E LORO RAPPRESENTAZIONE IN MEMORIA

Capitolo 11

Programmazione Dinamica

11.1 Introduzione

Spesso, la soluzione di un problema assegnato può essere ricondotta alla

soluzione di problemi simili, aventi dimensione minore della dimensione del

problema originale. E’ su tale concetto che si basa la tecnica di progetto nota

come Divide et Impera, che abbiamo incontrato nel capitolo 7.

Da un punto di vista della efficienza computazionale, tale tecnica ha gen-

eralmente successo se il numero dei sottoproblemi in cui il problema viene

suddiviso è costante, ovvero indipendente dalla dimensione dell’input.

Se invece accade che il numero dei sottoproblemi sia funzione della dimen-

sione dell’input, allora non esiste più alcuna garanzia di ottenere un algoritmo

efficiente.

La programmazione dinamica è una tecnica tabulare molto ingegnosa

per affrontare tali situazioni. La risoluzione procede in maniera bottom-

up, ovvero dai sottoproblemi più piccoli a quelli di dimensione maggiore,

memorizzando i risultati intermedi ottenuti in una tabella.

Il vantaggio di questo metodo é che le soluzioni dei vari sottoproblemi, una

volta calcolate, sono memorizzate, e quindi non devono essere più ricalcolate.

11.1.1 Un caso notevole

Si consideri la moltiplicazione di n matrici

· · ·

M = M M . . . M

1 2 n

81

82 CAPITOLO 11. PROGRAMMAZIONE DINAMICA

dove M é una matrice con r righe e r colonne. L’ordine con cui le

i i−1 i

matrici sono moltiplicate ha un effetto significativo sul numero totale di

moltiplicazioni richieste per calcolare M , indipendentemente dall’algoritmo

di moltiplicazione utilizzato. Si noti che il calcolo di

·

M M

i i+1

· ·

[r r ] [r r ]

i−1 i i i+1

· ·

richiede r r r moltiplicazioni, e la matrice ottenuta ha r righe e r

i−1 i i+1 i−1 i

colonne. Disposizioni differenti delle parentesi danno luogo ad un numero di

moltiplicazioni spesso molto differenti tra loro.

Esempio 21 Consideriamo il prodotto

· · ·

M = M M M M

1 2 3 4

· · · ·

[10 20] [20 50] [50 1] [1 100]

Per calcolare

• · · ·

M (M (M M )) sono necessari 125000 prodotti;

1 2 3 4

• · · ·

(M (M M ) M ) sono necessari 2200 prodotti;

1 2 3 4

Si desidera minimizzare il numero totale di moltiplicazioni. Ciò equivale a

n

O(2

tentare tutte le disposizioni valide di parentesi, che sono ), ovvero in

numero esponenziale nella dimensione del problema.

La programmazione dinamica ci permette di ottenere la soluzione cercata

3

O(n

in tempo ). riassumiamo qui di seguito l’idea alla base di tale metodo.

11.1.2 Descrizione del metodo

Sia ≤ ≤ ≤

m (1 i j n)

ij

il costo minimo del calcolo di · · ·

M M . . . M

i i+1 j

Si ha la seguente equazione di ricorrenza:

( 0 se i = j

m =

ij · ·

min (m + m + r r r ) se i < j

i≤k<j ik k+1,j i−1 k j

11.1. INTRODUZIONE 83

· ·

Questo perchè, se calcoliamo M . . . M come

i j

· · · · ·

(M . . . M ) (M . . . M )

i k k+1 j

sono necessarie: 0

• · ·

m moltiplicazioni per calcolare M = M . . . M

ik i k

00

• · ·

m moltiplicazioni per calcolare M = M . . . M

k+1,j k+1 j

0 00

• · · ·

r r r moltiplicazioni per calcolare M M :

i−1 k j 0 00

·

M M

· ·

[r r ] [r r ]

i−1 k j k

11.1.3 Schema base dell’algoritmo

1. Per l che va da 0 a n 1 |j −

2. Calcola tutti gli m tali che i| = l e memorizzali

ij

3. Restituisci m 1n

11.1.4 Versione definitiva dell’algoritmo

1. Per i che va da 0 a n

2. Poni m := 0

ii −

3. Per l che va da 1 a n 1

4. Per i che va da 1 a n l

5. Poni j := i + l · ·

6. Poni m := min (m + m + r r r )

ij i≤k≤j ik k+1,j i−1 k j

7. Restituisci m 1n

Nota bene 7 Si noti che, l’utilizzo di una tabella per memorizzare i valori

m via via calcolati, e l’ordine in cui vengono effettuati i calcoli ci garan-

ij

tiscono che al punto (6) tutte le quantità di cui abbiamo bisogno siano già

disponibili

84 CAPITOLO 11. PROGRAMMAZIONE DINAMICA

11.1.5 Un esempio svolto

Nell’esempio 21 da noi considerato, otteniamo

l =0 m =0 m = 0 m = 0 m = 0

11 22 33 44

l =1 m = 10000 m = 1000 m = 5000

12 23 34

l =2 m = 1200 m = 3000

13 24

l =3 m = 2200

14

Si noti che i calcoli sono eseguiti nel seguente ordine:

1 2 3 4

5 6 7

8 9

10

Capitolo 12

Dizionari

Si consiglia fortemente allo studente di studiare dal testo [4] le sezioni 1, 3,

4, 5 e 6 del capitolo 4. 85

86 CAPITOLO 12. DIZIONARI

Capitolo 13

Alberi

Si consiglia fortemente allo studente di studiare dal testo [4] le sezioni 1, 2,

3 e 4 del capitolo 3 (omettere il paragrafo ”An Example: Huffman Codes”).

In alternativa é possibile studiare dal testo [2] le sezioni 4 e 5 del capitolo

5. 87

88 CAPITOLO 13. ALBERI

Capitolo 14

Alberi di Ricerca Binari

Si consiglia fortemente allo studente di studiare dal testo [4] le sezioni 1 e

2 del capitolo 5.

In alternativa, é possibile studiare le sezioni 1, 2, 3 e 4 del capitolo 13 del

testo [2].

Nota bene 8 La trattazione dell’analisi di complessitá nel testo [4] (sezione

2, p. 160) e’ molto piú accessibile. 89

90 CAPITOLO 14. ALBERI DI RICERCA BINARI

Capitolo 15

Alberi AVL

Si consiglia fortemente allo studente di studiare dal testo [1] la sezione 6

del capitolo 13. 91

92 CAPITOLO 15. ALBERI AVL

Capitolo 16

2-3 Alberi e B-Alberi

Si consiglia fortemente allo studente di studiare dal testo [4]

• la sezione 4 del capitolo 5;

• dalla sezione 4 del capitolo 11 i paragrafi ”Multiway Search Trees”,

”B-trees” e ”Time Analysis of B-tree Operations”.

In alternativa é possibile studiare il capitolo 19 del testo [3].

93

94 CAPITOLO 16. 2-3 ALBERI E B-ALBERI

Capitolo 17

Le heaps

17.1 Le code con priorità

Una coda con priorità è un tipo di dato astratto simile alla coda, vista in

precedenza.

Ricordiamo che la coda è una struttura FIFO (First In First Out), vale a

dire, il primo elemento ad entrare è anche il primo ad uscire. Il tipo di dato

astratto coda può essere utilizzato per modellizzare molti processi del mondo

reale (basti pensare alla coda al semaforo, alla cassa di un supermercato,

ecc.). Vi sono molte applicazioni in cui la politica FIFO non è adeguata.

Esempio 22 Si pensi alla coda dei processi in un sistema operativo in attesa

della risorsa CPU. La politica FIFO in tale caso non terrebbe conto delle

priorità dei singoli processi. In altre parole, nel momento in cui il processo

correntemente attivo termina l’esecuzione, il sistema operativo deve cedere il

controllo della CPU non al prossimo processo che ne ha fatto richiesta bensì

al processo avente priorità più alta tra quelli che ne hanno fatto richiesta.

Assegnamo pertanto a ciascun processo un numero intero P , tale che ad un

valore minore di P corrisponda una priorità maggiore. Il sistema operativo

dovrà di volta in volta estrarre dal pool dei processi in attesa quello avente

priorità maggiore, e cedere ad esso il controllo della CPU.

Per modellizzare tali situazioni introduciamo le code con priorità. Sia U un

insieme totalmente ordinato, come al solito. Una coda con priorità A è un

sottinsieme di U su cui sono ammesse le seguenti operazioni:

95

96 CAPITOLO 17. LE HEAPS

• Inizializza(A) ∅;

crea una cosa con priorità vuota A, ovvero poni A =

• Inserisci(x, A)

inserisci l’elemento x nell’insieme A;

• CancellaMin(A)

cancella il più piccolo elemento di A;

• Minimo(A)

restituisce il più piccolo elemento di A.

Come implementare efficientemente una coda con priorità? La soluzione è

fornita dalle heaps.

17.2 Le heaps

Una heap è un albero binario che gode delle seguenti due proprietà:

1 Forma:

Una heap è ottenuta da un albero binario completo eliminando 0 o più

foglie. Le eventuali foglie eliminate sono contigue e si trovano sulla

estrema destra.

2 Ordinamento relativo:

La chiave associata a ciascun nodo è minore o uguale delle chiavi

associate ai propri figli; a

Nota bene 9 Come conseguenza della 2 proprietà si ha che la radice con-

tiene la chiave più piccola.

Le altre conseguenze sono dovute alla forma particolare che ha una heap.

O(log

1 L’altezza h di una heap avente n nodi è n).

2 Una heap può essere memorizzata molto efficientemente in un vettore,

senza utilizzare puntatori.

La prima asserzione è semplice da dimostrare: poichè un albero binario

h+1 h

− ≥ −

completo di altezza h ha 2 1 nodi, si ha che n 2 1, da cui

≤ O(log

h log(n + 1) = n).

17.3. RICERCA DEL MINIMO 97

Per quanto riguarda la rappresentazione di una heap, utilizziamo un vet-

tore Nodi contenente in ciascuna posizione la chiave associata al nodo. La

radice della heap verrà memorizzata nella prima posizione del vettore (ovvero,

in posizione 1). Se un nodo si trova in posizione i, allora l’eventuale figlio sin-

istro sarà memorizzato in posizione 2i e l’eventuale figlio destro in posizione

2i + 1. La seguente tabella riassume quanto detto:

N ODI P OSIZION E

Radice 1

nodo p i

i

b c

padre di p 2

figlio sinistro di p 2i

figlio destro di p 2i + 1

bxc

Come al solito, se x è un numero reale, con si intende la parte intera

inferiore di x.

Si noti che in virtù di tale rappresentazione la foglia che si trova più a

destra al livello h, dove h è l’altezza dell’albero, è memorizzata nel vettore

Nodi in posizione n.

17.3 Ricerca del minimo

In virtù delle proprietà viste precedentemente, sappiamo che il più piccolo

elemento di una heap si trova in corrispondenza della radice, che è memoriz-

zata nella prima posizione del vettore. Quindi, la procedura che implementa

la ricerca del minimo è banalmente:

Procedura Minimo()

1. Ritorna ( Nodi[1] ) O(1).

Ovviamente, il tempo richiesto è

17.4 Inserimento

L’inserimento di un nuovo elemento in una heap procede in due fasi:

1 Viene creata innanzitutto una nuova foglia contenente la chiave da

inserire. Tale foglia è inserita in posizione tale da rispettare la forma

che deve avere una heap.

98 CAPITOLO 17. LE HEAPS

2 Quindi, la chiave contenuta nella foglia viene fatta salire lungo l’albero

(scambiando di volta in volta il nodo che contiene correntemente la

chiave con il padre) fino a che la proprietà di ordinamento relativo sia

garantita.

Per quanto riguarda l’implementazione effettiva, lo pseudo-codice della pro-

cedura che implementa l’inserimento è il seguente:

Procedura Inserisci( Chiave ):

1. n := n + 1

2. Nodi[ n ] := Chiave

3. SpostaSu( n )

Procedura SpostaSu( i ):

i

b c 6

1. Se = 0

2

2. /* Nodi[ i ] ha un padre */

i

b c

3. Se Nodi[ i ] < Nodi[ ]

2 i

b c

4. Scambia Nodi[ i ] e Nodi[ ]

2

i c)

5. SpostaSu(b 2

Il tempo richiesto sarà nel caso peggiore dell’ordine dell’altezza della heap,

O(h) O(log

ovvero = n).

17.5 Cancellazione del minimo

La cancellazione del più piccolo elemento di una heap, che sappiamo trovasi

in corrispondenza della radice, procede in due fasi:

1 Viene innanzitutto copiata nella radice la foglia che si trova più a destra

al livello h.

2 Tale foglia è quindi rimossa dalla heap. Si noti che in seguito alla

rimozione di tale foglia l’albero ottenuto ha ancora la forma di heap.

3 Quindi, la chiave contenuta nella radice viene fatta scendere lungo l’al-

bero (scambiando di volta in volta il nodo che contiene correntemente

la chiave con uno dei propri figli) fino a che la proprietà di ordinamento

relativo sia garantita.

17.6. COSTRUZIONE DI UNA HEAP 99

Per quanto riguarda l’implementazione effettiva, lo pseudo-codice della pro-

cedura che implementa l’inserimento è il seguente:

Procedura CancellaMin():

1. Nodi[ 1 ] := Nodi[ n ]

2. n := n - 1

3. SpostaGiu( 1 )

Procedura SpostaGiu( i ):

0. Se 2i n

1. /* Nodi[ i ] ha almeno un figlio */

2. Sia m l’indice del figlio contenente la chiave più piccola

3. Se Nodi[ m ] < Nodi[ i ]

4. Scambia Nodi[ m ] e Nodi[ i ]

5. SpostaGiu( m )

Poichè il numero totale di confronti e scambi è al più volta proporzionale

all’altezza della heap, il tempo richiesto sarà ancora una volta O(log n).

17.6 Costruzione di una heap

Sia S un insieme du n chiavi, tratte da un insieme universo U totalmente

ordinato. Si voglia costruire una heap contenente le n chiavi.

9 Attenzione

Si noti che date n chiavi, possono esistere più heaps contenenti tali chiavi.

{7,

Ad esempio, se S = 8, 9} allora esistono esattamente due heaps costruite

a partire da S: entrambe saranno due alberi binari completi di altezza 1, con

la chiave 7 in corrispondenza della radice.

Esistono più strategie per costruire una heap a partire da un insieme S

assegnato. La strategia da noi utilizzata si basa sulla seguente proprietà:

Teorema 1 Sia H una heap avente n nodi, memorizzata in un vettore Nodi.

≤ ≤

Allora, i nodi corrispondenti alle ultime i posizioni del vettore (con 1 i n)

formeranno un insieme di alberi, ciascuno dei quali è a sua volta una heap.

La dimostrazione di tale fatto è banale ed è lasciata allo studente. L’algoritmo

da noi utilizzato procede come segue:

100 CAPITOLO 17. LE HEAPS

• Inizialmente gli elementi di S sono disposti in maniera arbitraria nel

vettore Nodi.

• Quindi, per i che va da 1 ad n gli ultimi i elementi del vettore ven-

gono opportunamente permutati per garantire che la proprietà appena

enunciata sia valida.

Per quanto riguarda l’implementazione effettiva, lo pseudo-codice della pro-

cedura che implementa la costruzione di una heap è il seguente:

Procedura CostruisciHeap ( S ):

1. Inserisci arbitrariamente gli elementi di S nel vettore Nodi

2. Per i che va da n fino a 1

3. SpostaGiu( i )

Correttezza

La correttezza dell’algoritmo si dimostra per induzione sul numero i di nodi

della foresta costituita dagli ultimi i elementi del vettore Nodi.

• La foresta costituita dall’ultimo nodo del vettore è banalmente una

heap.

• −

Supponiamo ora che la foresta costituita dagli ultimi i 1 elementi del

vettore sia costituita da un certo numero di heaps. Allora, quando la

procedura SpostaGiu( i ) è invocata, sono possibili 3 casi:

1 Il nodo in posizione i non ha figli. In tal caso la procedura ritorna

senza fare niente.

2 Il nodo in posizione i ha un solo figlio, il sinistro. Si noti che

in tal caso il sottoalbero avente radice in i ha due soli nodi! Al

termine della procedura il nodo in posizione i conterrà certamente

una chiave più piccola della chiave contenuta nel figlio.

3 Il nodo in posizione i ha entrambi i figli. In tal caso, al termine

della procedura il sottoalbero avente radice nel nodo i godrà della

proprietà di ordinamento relativo di una heap.

17.7. ESERCIZI 101

Complessità

La costruzione di una heap di n elementi richiede tempo O(n).

Dimostrazione: Indichiamo con l(v) la massima distanza di un nodo v da

una foglia discendente di v. Indichiamo poi con n il numero di nodi v della

l

heap tali che l(v) = l. Si noti che h

2 n

h−l

≤ ≤

n 2 =

l l l

2 2

Se il nodo v contenuto nella posizione i-esima di Nodi ha l(v) = l, allora la

procedura SpostaGiu( i ) richiede al più un numero di operazioni elementari

(confronti più scambi) proporzionale ad l. Quindi, il tempo totale richiesto

sarà dato da: h

X ·

T (n) = l n l

l=1

h n

X

≤ ·

l l

2

l=1 h l

X

= n l

2

l−1

Poichè ∞

h l l 1/2

X X

< = =2

l l 2

2 2 (1 1/2)

l=1 l=0 O(n).

si ha che T (n) < 2n ovvero T (n) =

17.7 Esercizi

1 Modificare le procedure viste in questo capitolo in modo tale che ciascun

elemento del vettore contenga altre informazioni oltre alla chiave, ed

implementare tali procedure in C.

102 CAPITOLO 17. LE HEAPS

Capitolo 18

Heapsort

L’Heapsort è un algoritmo di ordinamento ottimale nel caso peggiore, che

sfrutta le proprietà delle heaps viste in precedenza. Questo algoritmo ordina

in loco, cioè utilizza una quantita’ di spazio pari esattamente alla dimensione

dell’input. Sia S un insieme di elementi da ordinare di dimensione n. L’al-

goritmo heapsort costruisce dapprima una heap contenente tutti gli elementi

di S, quindi estrae ripetutamente dalla heap il piu’ piccolo elemento finche’

la heap risulti vuota.

Heapsort( S ):

1. CostruisciHeap( S )

2. Per i che va da 1 a n

3. A[i] = Minimo()

4. CancellaMin()

Qual è la complessità di tale algoritmo? Ricordiamo che il passo 1 richiede

tempo O(n), il passo 2 tempo costante ed il passo 4 tempo O(log n) nel caso

pessimo. Dalla regola della somma e dalla regola del prodotto si deduce che

la complessita’ nel caso pessimo e’ O(n log n).

103

104 CAPITOLO 18. HEAPSORT

Capitolo 19

Tecniche Hash

Alle tecniche hash saranno dedicate 2 lezioni da (circa) 2 ore ciascuna all’in-

terno di un corso introduttivo di ”Algoritmi e Strutture Dati” della durata

di 120 ore.

1 Nella prima lezione saranno presentati i concetti fondamentali, e la clas-

sificazione delle diverse tecniche. In tale lezione verrà omesso comple-

tamente il problema della cancellazione negli schemi ad indirizzamento

aperto.

2 Nella seconda lezione sarà mostrata l’implementazione effettiva delle

procedure di inserimento, cancellazione e ricerca nel caso degli schemi

ad indirizzamento aperto, ricorrendo all’uso di pseudo-codice laddove

necessario. In particolare verrà posto l’accento sui problemi legati alla

cancellazione di un elemento.

Quindi verrà mostrata la complessità nel caso peggiore e nel caso medio

delle operazioni elementari di inserimento, ricerca e cancellazione. Per

semplicità l’analisi di complessità verrà effettuata per i soli schemi a

concatenamento.

Lo studente dovrà avere appreso dalle lezioni precedenti:

• Il concetto di lista concatenata,

come (possibile) struttura dati per implementare il tipo di dato astratto

lista;

• Il concetto di insieme,

come tipo di dato astratto; 105

106 CAPITOLO 19. TECNICHE HASH

• Il concetto di dizionario,

come tipo di dato astratto, ottenuto specializzando il tipo di dato

astratto insieme;

• Come implementare un dizionario utilizzando un vettore di bit.

19.1 Introduzione

Abbiamo visto nelle lezioni precedenti che il tipo di dato astratto dizionario

è uno tra i più utilizzati nella pratica.

Gli elementi che costituiscono un dizionario sono detti chiavi , e sono

tratti da un insieme universo U . Ad ogni chiave è associato un blocco di

informazioni.

Scopo del dizionario è la memorizzazione di informazioni; le chiavi per-

mettono il reperimento delle informazioni ad esse associate.

Su un dizionario vogliamo poter effettuare fondamentalmente le oper-

azioni di inserimento, ricerca e cancellazione di elementi.

Le tabelle hash consentono di effettuare efficientemente queste tre op-

erazioni, nel caso medio. In particolare dimostreremo che tali operazioni

richiedono tempo medio costante, e pertanto gli algoritmi che implementano

tali operazioni su una tabella hash sono ottimali nel caso medio.

Sfortunatamente, la complessità delle tre operazioni viste sopra è lineare

nel numero degli elementi del dizionario, nel caso peggiore.

Le tecniche hash di organizzazione delle informazioni sono caratterizzate

dall’impiego di alcune funzioni, dette hashing (o equivalentemente scattering),

che hanno lo scopo di ”disperdere” le chiavi appartenenti al nostro universo

U all’interno di una tabella T di dimensione finita m, generalmente molto

più piccola della cardinalità di U .

Una funzione hash è una funzione definita nello spazio delle chiavi U ed

a valori nell’insieme N dei numeri naturali. Tale funzione accetta in input

una chiave e ritorna un intero in un intervallo predefinito [0, m 1].

La funzione hash deve essere progettata in modo tale da distribuire uni-

formamente le chiavi nell’intervallo [0, m 1]. Il valore intero associato ad

una chiave è utilizzato come indice per accedere ad un vettore di dimensione

m, detto Tabella hash, contenente i records del nostro dizionario. I records

sono inseriti nella tabella (e quindi possono essere successivamente trovati)

19.1. INTRODUZIONE 107

utilizzando la funzione hash per calcolare l’indice nella tabella a partire dalla

chiave del record.

Quando la funzione hash ritorna lo stesso indice per due chiavi differenti

abbiamo una collisione. Le chiavi che collidono sono dette sinonimi. Un

algoritmo completo di hashing consiste di

1 un metodo per generare indirizzi a partire dalle chiave, ovvero una

funzione hash;

2 un metodo per trattare il problema delle collisioni, detto schema di

risoluzione delle collisioni.

Esistono due classi distinte di schemi di risoluzione delle collisioni:

1 La prima classe è costituita dagli schemi ad indirizzamento aperto.

Gli schemi in tale classe risolvono le collisioni calcolando un nuovo

indice basato sul valore della chiave - in altre parole effettuano un

rehash nella tabella;

2 La seconda classe è costituita dagli schemi a concatenamento.

In tali schemi tutti i record che dovrebbbero occupare la stessa po-

sizione nella tabella hash formano una lista concatenata.

Per inserire una chiave utilizzando l’indirizzamento aperto occorre scandire la

tabella secondo una politica predefinita, alla ricerca di una posizione libera.

La sequenza di posizioni scandite è chiamata percorso.

Negli schemi ad indirizzamento aperto la chiave sarà inserita nella prima

posizione libera lungo tale percorso, avente origine nella posizione calcola-

ta attraverso la funzione hash. Ci sono esattamente m! possibili percorsi,

{0, −

corrispondenti alle m! permutazioni dell’insieme . . . , m 1}, e la maggior

parte degli schemi ad indirizzamento aperto usa un numero di percorsi di gran

lunga inferiore a m! Si noti che a diverse chiavi potrebbe essere associato lo

stesso percorso.

La porzione di un percorso interamente occupato da chiavi prende il nome

di catena. L’effetto indesiderato di avere catene più lunghe di quanto sia

atteso è detto clustering. Esistono delle tecniche di scansione (scansione

uniforme e scansione casuale) che non soffrono del problema del clustering.

Sia m la cardinalità della nostra tabella, ed n il numero dei records in essa

memorizzati. La quantità α = n/m è detta fattore di carico della tabella.

Ovviamente nelle tecniche ad indirizzamento aperto α deve essere minore

108 CAPITOLO 19. TECNICHE HASH

uguale di uno, mentre non esiste nessuna restrizione sul fattore di carico α

se vengono utilizzate delle liste concatenate per gestire le collisioni.

Verrà dimostrato al termine della lezione che l’efficienza di queste tecniche

dipende fondamentalmente dal fattore di carico della tabella: in altre parole,

quanto più è piena la tabella, tante più operazioni di scansione occorre ef-

fettuare per cercare la nostra chiave o per cercare una posizione libera in cui

inserire una nuova chiave.

19.2 Caratteristiche delle funzioni hash

Ricordiamo che una funzione hash h dovrà consentire di mappare l’insieme

universo U sull’insieme [0, . . . , m 1] degli indici della tabella, che ha gen-

eralmente cardinalità molto più piccola.

Una buona funzione hash h deve essere innanzitutto semplice da calcolare.

In altre parole, l’algoritmo che la calcola deve essere un algoritmo efficiente.

Inoltre, per ridurre il numero di collisioni, una buona funzione hash h deve

distribuire uniformemente le chiavi all’interno della tabella T . In termini

probabilistici, ciò equivale a richiedere che ≤

P (h(k ) = h(k )) 1/m

1 2

se k e k sono due chiavi estratte a caso dall’universo U .

1 2

In altri termini, per una tale funzione hash, la preimmagine di ciascun

|U |/|T |

indice della tabella T dovrà avere all’incirca cardinalità (i sinonimi

partizionano l’insieme delle chiavi in sottinsiemi di cardinalità approssiva-

mente uguale).

Chiavi intere

Se l’universo U è costituito da numeri interi, allora una buona funzione hash

è la funzione riduzione modulo m: ∈

h(k) = k mod m k U

Chiavi alfanumeriche

Se l’universo U è costituito da stringhe alfanumeriche, possiamo ad esempio

considerare tali stringhe come numeri in base b, dove b è la cardinalità del

19.3. TECNICHE DI SCANSIONE DELLA TABELLA 109

codice utilizzato (ad esempio ASCII). In tal caso, supponendo che la stringa

sia composta dai caratteri s , s , . . . , s possiamo porre:

1 2 k

k−1 i

X

h(k) = b s (mod m)

k−i

i=0

Per evitare l’insorgere di problemi di overflow, si consiglia di far seguire la

riduzione modulo m a ciascuna operazione aritmetica (somma o prodotto).

19.3 Tecniche di scansione della tabella

Qui di seguito elenchiamo alcune delle tecniche maggiormente usate di scan-

sione della tabella, negli schemi ad indirizzamento aperto. Ricordiamo che la

scansione avviene sempre a partire dalla posizione h(x) calcolata applicando

la funzione hash h(·) alla chiave x. L’obiettivo della scansione è quello di

trovare la chiave cercata (nel caso della ricerca) oppure una posizione libera

in cui inserire una nuova chiave (nel caso dell’inserimento).

19.3.1 Scansione uniforme

La scansione uniforme è uno schema di indirizzamento aperto che risolve le

collisioni scandendo la tabella secondo una permutazione degli interi [0, . . . , m−

1] che dipende unicamente dalla chiave in questione. Quindi, per ogni chiave,

l’ordine di scansione della tabella è una permutazione pseudo-casuale delle

locazioni della tabella. Questo metodo utilizza con uguale probabilità tutti

gli (m 1)! possibili percorsi.

Tale schema va inteso maggiormante come un modello teorico, essendo

relativamente semplice da analizzare.

19.3.2 Scansione lineare

In tale schema la scansione avviene considerando di volta in volta la prossima

locazione della tabella (mod m). In altre parole, la scansione della tabel-

la avviene sequenzialmente, a partire dall’indice ottenuto attraverso l’appli-

cazione della funzione hash alla chiave, finchè non si raggiunga la fine della

tabella, riprendendo in tal caso la scansione a partire dall’inizio della tabella.

Questo metodo utilizza un solo percorso circolare, di lunghezza m.

110 CAPITOLO 19. TECNICHE HASH

|T |

Esempio 23 Sia m = = 10 ed h(x) = 3. Il percorso sarà

3, 4, 5, 6, 7, 8, 9, 0, 1, 2

La scansione lineare è una delle tecniche più semplici di risoluzione delle col-

lisioni. Purtroppo soffre di un problema, detto clustering primario. Quanto

più cresce una sequenza di chiavi contigue, tanto più aumenta la probabilità

che l’inserimento di una nuova chiave causi una collisione con tale sequenza.

Pertanto le sequenze lunghe tendono a crescere più velocemente delle corte.

Tale schema è indesiderabile quando il fattore di carico è alto, ovvero in

quelle applicazioni in cui la tabella potrebbe riempirsi quasi completamente.

19.3.3 Hashing doppio

L’hashing doppio è una tecnica ad indirizzamento aperto che risolve il prob-

lema delle collisioni attraverso l’utilizzo di una seconda funzione hash h (·).

1

La seconda funzione hash è usata per calcolare un valore compreso tra 1

ed m 1 che verrà utilizzato come incremento per effettuare la scansione

della tabella a partire dalla posizione calcolata attraverso la prima funzione

hash h(·). Ogni differente valore dell’incremento da origine ad un percorso

distinto, pertanto si hanno esattamente m 1 percorsi circolari.

L’hashing doppio è pratico ed efficiente. Inoltre, dal momento che l’in-

cremento utilizzato non è costante ma dipende dalla chiave specifica, tale

schema non soffre del problema del clustering primario.

|T |

Esempio 24 Sia m = = 10, h(x) = 3 ed h (x) = 2. Il percorso sarà

1

3, 5, 7, 9, 1

Se si desidera garantire che ciascun percorso abbia lunghezza massima, ovvero

lunghezza pari ad m, basta prendere m primo.

|T |

Esempio 25 Sia m = = 11, h(x) = 3 ed h (x) = 2. Il percorso sarà

1

3, 5, 7, 9, 0, 2, 4, 6, 8, 10, 1

19.3.4 Hashing quadratico

L’hashing quadratico è una tecnica di scansione della tabella che utilizza un

passo variabile. All’i-esimo tentativo, la posizione scandita sarà data dalla

19.4. HASHING TRAMITE CONCATENAMENTO DIRETTO 111

posizione iniziale h(x) più il quadrato di i (chiaramente, il tutto modulo la

dimensione della tabella). In altre parole, le posizioni scandite saranno:

h(k) (mod m),

h(k) +1 (mod m),

h(k) +4 (mod m),

h(k) +9 (mod m),

h(x) + . . . (mod m)

Affinchè il metodo sia efficace occorre che la dimensione m della tabella sia un

numero primo. In tal caso ciascun percorso avrà lunghezza pari esattamente

a metà della dimensione della tabella.

|T |

Esempio 26 Sia m = = 11 ed h(x) = 3. Il percorso sarà

3, 4, 7, 1, 8, 6

19.4 Hashing tramite concatenamento diret-

to

Tale metodo fa uso di funzioni hash e liste concatenate come segue. La

funzione hash viene utilizzata per calcolare un indice nella tabella. Tale

tabella non contiene records bensi’ puntatori a liste concatenate di record che

collidono nella stessa posizione. Pertanto tale metodo può essere considerato

come una combinazione della tecnica hash con le liste concatenate.

Questa tecnica ha tanti vantaggi sull’indirizzamento aperto:

• Il numero medio di accessi per una singola operazione di ricerca, in caso

di successo o insuccesso, è molto basso;

• La cancellazione di un record avviene molto efficientemente, semplice-

mente eliminando tale record da una delle liste concatenate;

• Il fattore di carico della tabella può essere maggiore di uno. In altre

parole non è necessario conoscere a priori la cardinalità massima del

dizionario per poter dimensionare la tabella.

Questo metodo si presta molto bene ad una implementazione utilizzando

memoria secondaria. In questio caso il vettore dei puntatori è conservato in

memoria centrale, e le liste concatenate nella memoria secondaria.


ACQUISTATO

2 volte

PAGINE

137

PESO

372.38 KB

AUTORE

flaviael

PUBBLICATO

+1 anno fa


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria informatica
SSD:
A.A.: 2013-2014

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher flaviael di informazioni apprese con la frequenza delle lezioni di Algoritmi e strutture dati e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Napoli Federico II - Unina o del prof Vincenzo Acciaro.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Algoritmi e strutture dati

Algoritmi e strutture dati
Dispensa
Algoritmi e strutture dati - Analisi Lessicale-Sintattica
Dispensa
Algoritmi e strutture dati – Alberi rosso neri
Dispensa
Algoritmi e strutture dati - Esercitazione
Esercitazione