Algoritmi e Strutture Dati con domande riassuntive

else c = 0

r = conta5 (A[], i + 1)

return(c+r) <- fa da contatore

Tempo

​ ​ ​ n

T(n) = T(n-1) + 4C con n > 1 come prima

ϴ

→ ( )

2C con n = 0

3. Contare quanti elementi sono seguiti dal proprio successore in un array

Sc(A[], i)

​ ​

if i > length(A)

return(0)

else if A[i] == A[i+1] - 1

c = 1

else c = 0

4. Sommare primo e ultimo elemento dell’array, poi il secondo e il penultimo e così

via ​ ​ ​ ​

int Somma(A[], i, f) si può usare anche solo i e length(A)​ senza creare f

→ 2 casi base:

- Indici si accavallano

- Indici sono uguali

if i > f return(0)

if i == f return(A[i])

else somma = A[i] + A[f]

r = somma(A[], i+1, f-1)

return(somma+r)

Tempo

​

T(n) = T(n-2) + 4C n > 1

3C n = 1

2C n = 0

n dispari

​

T(n) = T(n-2) + 4C = T(n-2k) + k4C n

k = n/2 T(0) + n2C = 2C + n2C = ϴ

→ ( )

5. Palindromo

boolean Palindromo(A[], i, f)

​ ​

c if f < i return TRUE

else

c if(A[i] == A[f])

t(n-2) r = Palindromo(A[], i+1, f-1)

c*tif return(r)

else

c*fif return(FALSE)

Tempo

T(n)​ = T(n-2)*tif + 2C con n>1

2C con n = 1 o n = 0

Caso peggiore: A[] palindromo

​

Tp(n) = T(n-2) + 3C con n > 1

2C

Caso migliore: Non palindromo

​

Tm (n) = 3C con n > 1

= 2C con n = 0,1

Divide et impera

● Prende il problema da risolvere

● Spezza il problema in più sottoproblemi fino a quando non si arriva ad un

elemento singolo (Divide, parte iterativa)

● Risolve ricorsivamente i sottoproblemi (parte ricorsiva)

● Combina soluzioni ottenute dai sottoproblemi per risolvere il problema

principale (Impera, parte iterativa)

Merge Sort (ordinamento) n log n

● Tempo di esecuzione = ϴ

( )

​ ​

● NON è un algoritmo in loco = con il Selection o l’Insertion si utilizza un numero

​

costante di variabili di appoggio​ (le tmp usate per spostare gli elementi dell’array)

● Stabile = a parità di valore, l’ordine con cui trovo gli elementi uguali nell’array

originale non verrà cambiato nell’array ordinato (se ho due 5, quello che è scritto prima

viene messo prima dell’altro anche nell’array ordinato)

Parti del Merge Sort

● Divide -> divide A[] in due metà (e poi continua a dividere fino a quando non avrà da

ordinare un array formato da un elemento)

● Impera -> ordina la prima metà

ordina la seconda metà

● Combina -> Merge

Esempio funzionamento

5,2,4,6,1,3,2,6,2

Array diviso a metà: 5,2​ ,4,6​ ,1|3,2​ ,6​ ,2​

a a b b c

​ ​ ​ ​

mergeSort(A[], 1, 9) 5,2​ ,4,6​ ,1,3,2​ ,6​ ,2​

a a b b c

​ ​ ​ ​

mergeSort(A[], 1, 5) 5,2​ ,4,6​ ,1

a a

​ ​

mergeSort(A[], 1, 3) 5,2​ ,4

a

​

mergeSort(A[], 1, 2) 5,2​ a mergeSort(A[], 1, 1) 5 -> array ordinato;

torna su e riordina tutto

● Il Merge Sort utilizza un array grande quanto l’array originale come variabile

d’appoggio, in cui ordina gli elementi mano a mano che “risale” nelle chiamate

ricorsive.

● L’algoritmo ordina tutta la prima metà, poi la seconda metà e alla fine si avrà:

1,2​ ,4,5,6​ |2​ ,2​ 3,,6​

a a b c b

​ ​ ​ ​

che diventa 1,2​ ,2​ ,2​ ,3,4,5,6​ ,6​

a b c a b

​ ​ ​ ​

Codice Merge Sort

void MS(A[], inizio, fine)

if inizio != fine

m = (inizio+fine) diviso 2 -> Divide

MS(A[], inizio, m) -> impera

MS(A[], m+1, fine) -> impera

Merge(A[], inizio, m, fine)

Esempio

MS(A, 1, 9) inizio = 1 fine = 9 m = 5

MS(A, 1, 5) m = 3

MS(A, 1, 3) m = 2

MS(A, 1, 2) m = 1

MS(A, 1, 1) -> ordinato -> porta elementi in B[]

*Fine parte da inizio a m = 5*

Ordina elementi in B[]

Copia elementi ordinati in A[]

Torna su e conclude le chiamate facendo la stessa roba

Codice Merge ​ ​

Merge(A[], sx, h, dx) -> sono i

nizio, m e fine

I1 = sx

I2 = h+1

​ ​ ​ ​

while I1 < h and I2 < dx

​ ​

If A[I1] < A[I2]

B[Ib] = A[I1]

I1++

else B[Ib] = A[I2]

I2++

Ib++

​ ​

while I1 < h

B[Ib] = A[I1]

I1++

Ib++

​ ​

while I2 < dx

B[Ib] = A[I2]

I2++

Ib++

for Ib = sx to dx

A[Ib] = B[Ib]

Tempo

Tms(n)​ = c con n = 1

​

Tms(n) = 2T(n/2) + 2C + Tmerge con n > 1 n

Tmerge = 3C + 4Cn + 2Cn = 6Cn + 3C = ϴ

( )

​ n

Quindi Tms(n)​ = 2T(n/2) + ϴ

( )

2

O n si può dimostrare

( )

O n log n si può dimostrare

( )

O n non si può dimostrare

( )

n log n si può dimostrare

Ω

( ) n log n O n log n

quindi o meglio

ϴ

~ ( ) ( )

​ ​

Dimostrazione n log n tramite induzione

k

n = 2 1 1

log log

caso base: k = 1 2 2 = 2 2 = 2 · 1 = 2

k k k

t log

Suppongo k vera (2 ) = 2 2

k+1

k+1 (2 ) k+1

t t

Passo induttivo (2 ) = 2 + 2

2

t n t n n

( ) = 2 ( /2) +

k+1 k+1

t

2 (2 /2) + 2

k k+1 k k k

t t log

->

2 (2 ) + 2 (2 ) = 2 2

k k k+1

log

2

(2 2 ) + 2

k+1 k

log

2 ( 2 + 1

)

k+1 k

log l

og

2 ( 2 + 2)

2

k+1 k

log l

og

2 ( 2 + 2)

k+1 k+1

log log n n n log n

2 ( 2 ) = Θ · Θ = Θ

Altro metodo

t n t n n

( ) = 2 ( /2) +

t n t n n n

( ) = 2

[2 ( /4) + /2] +

k k k+1 k

t n t n n k

n n k l

og n

con

= ( ) = 2 ( /2 ) + ( /2 ) + = 2 = 2

Equazioni di ricorrenza

t n k

t n h r f n t z c c = equazione del caso base;

( ) = (( − )/ ) + ( ) ( ) = z = dimensione input nel caso base

3 metodi di risoluzione

1. Iterativo o albero di ricorrenza

n -> n

n -> t(n/2) t(n/2)

n -> t(n/4) t(n/4) t(n/4) t(n/4)

.

.

.

n

Profondità dell’albero : log n -> quindi n log n

2. Sostituzione

Parto da equazione che già so e poi faccio induzione

3. Teorema dell’esperto (SOLO Divide et impera)

a = n° iterazioni

b = n° sottoproblemi 2t(n/2) + n il 2 di 2t = a; il 2 di n/2 = b

log a

n f n

← ( )

b

n n -> se è stessa grandezza uno dei due è moltiplicato per log n

t n n log n

( ) = Θ( )

Esercizio:

t n t n n Divisione intera

( ) = 2 ( /2) + →

n=7

n Base (due L specchiate)

( /4) → 7

/4 = 1

n Tetto (due L a rovescio specchiate)

( /4) → 7

/4 = 2

Esercizio: caso iterativo

t n t base n n

( ) = 3 ( ( /4)) +

t c

(1) =

t n t n n

( ) = 3 ( /4) +

t n t n n n

( ) = 3

[3 ( /(4 4

)) + ( /4)] +

*

3 2

t n t n n n n

( ) = 3

{3[3 ( /4 ) + ( /4 )] + ( /4)} +

3 3 2

t n t n n n n

( ) = 3 ( /4 ) + (

(3 )/4) + (

(3 )/4) +

k k k−1 k−2 0

t n n n n

3 ( /4 ) + (

3/4) + (

3/4) + .

.....(3/4)

k−1

k k i

t n t n n

( ) = 3 ( /4 ) + ∑ (3/4)

i=0

Assegno a k il valore più strategico

k n k log n

4 = = 4

log n−1

4

log n i

t n

3 · (1) + ∑ (3/4)

4 i=0

log a log a

log n log a

a (b ) = n

g b

b b

∞ i 1

∑ (k) = 1−k

i=0

Quick Sort

● Sempre divide et impera

● In loco,​ non ha bisogno di un array di appoggio

n log n

● Caso medio: Θ

( )

2

O n

● Caso peggiore: ( )

​

● NON è stabile Esecuzione

●Divide l’array in parti non uguali (​

partition​ )

​

●La prima parte è m inore​ della seconda

●Ordina ricorsivamente le due parti

●La combina non c’è perchè è inutile ​

●Per dividere l’array usa un elemento “perno”, chiamato pivot che

è di solito il primo elemento

○Nella prima parte andranno gli elementi < del pivot, nella

​ ​

seconda quelli > del pivot

Partition (originale)

13,19,9,5,12,8,7,4,11,2,6,21

SX: indice all’inizio

DX: indice alla fine

Pivot = 13 ​ ​

● Se DX trova un numero > del pivot scorre indietro

● Se DX trova un numero < del pivot si blocca

● Se SX trova un numero < del pivot scorre avanti

​ ​

● Se SX trova un numero > del pivot si blocca

● Se si bloccano entrambi, scambiano i numeri che li hanno fatti bloccare

Codice Quick Sort

QS(A[], i,f)

If i < f Q=partition(A[],i,f)

QS=(A[], i,Q)

QS=(A[], Q+1,f)

Codice partition

int Partition(A[], B, E)

Pivot=A[B], sx = B-1, dx = E+1;

while sx < dx

begin

do

sx++

whileA[sx] < pivot

do

dx--

while A[dx] > pivot

if sx < dx

scambia(A, sx, dx)

end

return(dx) n

Tempo partition = Θ

( )

Tempo Quick Sort:

● c se n=1 n

t(n)=T(Q)+T(n-Q)+ Θ

( )

Caso taglio a metà n

t(n)=t(n/2) + t(n/2) + Θ

( )

n n log n

= 2t(n/2)+ =

Θ

( ) Θ

( )

Caso 1 vs n-1 n

t(n)=t(1)+t(n-1)+ Θ

( )

n n

= c + t(n-1)+ ( è n)

Θ

( ) Θ

( )

=c+(c+t(n-2)+n-1)+n

n i

=c*kt(n-k)+ k=n

∑

i=n−k

n n(n+1) 2

i c

n O n

=c*nt(0)+ =

∑ · = ( )

2

i=n−k

Caso peggiore:

2 2

c

Q c n Q n

tp(n) = + ( − ) +

2 2

2

c

Q c n Q nQ n

+ ( + − 2 ) +

2 2

2

c

Q c

n cQ cnQ n (dtp(n))/dQ

+ + − 2 ) +

=2cQ+2cQ-2nc

=4cQ-2nc

Q=n/2 ​ ​

Se il taglio dell’array è molto sbilanciato, il tempo dell’array rimane sempre nell’ordine di

n logn .

Θ

( )

n logn è più veloce di quello del merge sort e risparmia spazio,perchè non ha array di

( )

appoggio. 2 ​

n

Si arriva a se il pivot è il primo o l’ultimo elemento

​

Si può scegliere ogni elemento dell’array come pivot tranne l’ultimo (a meno che l’ultimo

venga spostato di posto).

Quick Sort Random

● Pivot scelto a caso n logn

● Tempo al 99% in Θ

( )

Counting Sort

● Tempo di calcolo minore se il range dei numeri da ordinare è minore del numero di

elementi da ordinare

○ Ordinare 100k numeri tra 1 e 100 -> - tempo

○ Ordinare 100 numeri tra 1 e 100k -> + tempo

● Esempio: si hanno 3 array A[], B[] e C[] con elementi da 1 a n

○ A 7 1 8 1 2 7 5 4 2 4 4

○ Azzero C (array di tutti 0)

○ Scansiono A contando le occorrenze dei valori

■ A[1] = 7 C[7] = 1

■ A[2] = 1 C[1] = 2

■ C = 22031021

○ Sommo ad ogni elemento di C il contenuto del precedente

■ C=2 4 4 7 8 8 10 11

○ Parto dall’ultimo elemento in A(4 -> indice 11), prendo in C il numero in

posizione 4 -> C[4] = 7, poi in B[7] scrivo 4 e in C[4] decremento di 1

Codice

Counting_Sort(A[])

k = length(C)

h = length(A)

For i = 1 to n

C[1]=0

For i = 1 to n

pos = A[i]

C[pos]++

For i = 2 to k

posC = A[i]

posB = C[posC]

c[posC]--

B[posB] = A[i] h k

Tcs(n) = 2c + fch + Ack = Θ

( + )

Se k = O(n) n

Tch(n) = Θ

( )

Algoritmo non in loco

Stabile se l’ultima parte fa da n a 1. Al contrario non è stabile

Bucket Sort

Codice

Bucket_Sort(A[])

h = length(A)

For i = 0 to n-1

do B[hA[i]]

For i = 0 to n-1

do insertion_sort(B[i])

h−1 2

n O n

T(n) = Θ

( ) + ∑ ( )

i=0 Strutture dati

Stack e code

● Sono insiemi dinamici

● Stack​ : l’elemento cancellato dall’insieme è quello inserito per ultimo (schema

LIFO​ )

● Coda: l’elemento cancellato dall’insieme è quello che è rimasto nell’insieme

​

per più tempo (schema FIFO​ )

● Stack

○ L’operazione INSERT è detta PUSH

○ L’operazione DELETE è detta POP

○ Lo stack si implementa con un array S[1...n].

○ top|S|: indice elemento inserito più di recente

○ Lo stack è formato dagli elementi S[1...top|S|] con S[1] primo elemento

inserito nello stack ​

○ top|S| = 0 lo stack è vuoto

○ L’operazione STACK-EMPTY verifica se lo stack è vuoto

○ Se si tenta di estrarre un elemento (POP) da un array vuoto si ha un

underflow ​ ​

○ Se top|S| supera n si ha un o

verflow

Codici

STACK_EMPTY(S[])

if top|S| = 0

then return TRUE

else return FALSE

PUSH(S[], x)

top|S| = top|S| + 1

S[top|S|] = x

POP(S[])

if STACK_EMPTY(S[])

then error “underflow”

else top|S| = top|S| - 1

return S[top|S|]+1

● Code

○ ENQUEUE: operazione INSERT

○ DEQUEUE: operazione DELETE

○ Come POP, anche DEQUEUE non richiede un elemento in input ma

solo l’array

○ La coda ha un inizio (​

head​

) e una fine (​

tail​ )

○ Quando viene inserito un nuovo elemento, esso viene inserito dopo

​ ​

l’elemento tail​ e diventa il nuovo t ail

Codice

ENQUEUE(Q[], x)

Q[tail[Q]] = x

if tail[Q] == lunghezza Q

then tail[Q] = 1

else tai[Q]++

DEQUEUE(Q[])

x = Q[head[Q]]

if head[Q] == lunghezza Q

then tail[Q] = 1

else tail[Q] = head[Q]++

return x

Liste concatenate

● Struttura dati in cui gli elementi sono disposti in ordine lineare

​ ​

● L’ordine degli elementi è determinato da un p

untatore in ogni oggetto

​

● La lista doppiamente concatenata L contiene elementi i quali contengono, a loro

​ ​ ​ ​ ​

volta, un campo chiave k

ey e altri due campi puntatori: next e prev

​ ​

● Dato un elemento x

, next[x] punta al suo successore nella lista concatenata, e prev[x]

al suo predecessore ​

● Se prev[x] = NIL, l’elemento x non ha predecessore ed è quindi l’elemento testa o

head. ​ ​ ​

● Se next[x] = NIL, l’elemento x non ha successore ed è quindi l’elemento c

oda o tail

​

● Se head[L] = NIL la lista è vuota

​

● Lista singolarmente concatenata:​ non ha il puntatore prev

​ ​

● Lista ordinata: l’ordine della lista è l’ordine delle chiavi memorizzate negli elementi

della lista: l’elemento minimo è la testa, l’elemento massimo la coda

​

● Lista non ordinata​ : gli elementi si trovano in ordine casuale

​

● Lista circolare: il puntatore prev della testa della coda punta alla fine della coda, il

next della fine della coda punta alla testa della coda

Ricerca in una lista concatenata

● LIST_SEARCH trova il primo elemento con chiave k nella lista L mediante ricerca

lineare, restituendo il puntatore a questo elemento. Se non esiste restituisce NIL

Codice

LIST-SEARCH

x = head|L|

while x != NIL and key[x] != k

do x = next[x]

return x

Inserire un elemento in una lista concatenata

● Dato un elemento x il cui campo key è già stato impostato, la procedura

LIST-INSERT inserisce x davanti alla lista concatenata

Codice

LIST-INSERT(L[],x)

next[x] = head[L]

if head[L] != NIL

then prev[head[L]] = x

head[L] = x

prev[x] = NIL

Tempo​ = O(1)

Cancellare elemento da una lista concatenata

​ ​

● Riceve in input un puntatore a x e poi elimina x dalla lista aggiornando i puntatori

● Per cancellare un elemento con una data chiave, dobbiamo prima invocare

LIST-SEARCH

Codice

LIST-DELETE(L[], x)

if prev[x] != NIL

next[prev[x]] = next[x]

else head[L] = next[x]

if next[x] != NIL

prev[next[x]] = prev[x]

Sentinella ​

● E’ l’oggetto nil[L], un elemento che rappresenta NIL ma ha tutti i campi degli altri

elementi della lista

● Ogni volta che si trova un riferimento a NIL nel codice della lista, si sostituisce e si

​

usa nil[L]. Questo trasforma la lista in una lista circolare doppiamente concatenata

con sentinella ​

● La sentinella nil[L] è posta tra tra la testa e la coda: il campo next[nil[L]] punta a

​ ​

head[L], mente prev[nil[L]] punta a tail[L]. Il next della coda e il prev della testa

puntano a nil[L]

​

● Poichè next[nil[L]] punta alla testa della lista, si possono sostituire tutti i riferimenti a

​

head[L] con next[nil[L]]

​ ​ ​ ​

● Una lista è vuota se è formata solo dalla sentinella​

, in quanto next[nil[L]] e

​

prev[nil[L]] possono essere impostati entrambi a nil[L]

LIST-SEARCH con sentinella

LIST-SEARCH’(L[], x)

x = next[nil[L]]

while x != nil[L] and key[x] != k

x = next[x]

return x

LIST-INSERT con sentinella

LIST-INSERT’(L[], x)

next[x] = next[nil[L]]

prev[next[nil[L]]] = x

next[nil[L]] = x

prev[x] = nil[L]

Uso delle sentinelle

● Non si usano per velocizzare l’esecuzione dell’algoritmo, in quanto raramente

portano un beneficio in termini di velocità

● Si usano per ridurre i fattori costanti

● Rendono il codice, soprattutto all’interno dei cicli, più chiaro

​ ​

● Le sentinelle non vengono usate in liste piccole, in quanto porterebbero ad

uno spreco di memoria

Implementare puntatori e oggetti

Tecniche per implementare strutture dati concatenate senza utilizzare un esplicito tipo di

dato puntatore. Si sintetizzano oggetti e puntatori tramite array e indici di array.

Rappresentazione di oggetti tramite array

E’ possibile rappresentare una collezione di oggetti che hanno gli stessi campi utilizzando un

array per ogni campo.

Si può implementare una lista concatenata con 3 array: key, prev e next.

● Key contiene i valori delle chiavi che si trovano correttamente nell’insieme dinamico.

​ ​

● I puntatori sono memorizzati negli array n

ext e prev.

​ ​ ​

Per un dato indice x dell’array, key[x], next[x] e prev[x] rappresentano un oggetto della lista

​ ​ ​ ​ ​

concatenata. Significa che x è un semplice i

ndice comune t

ra key, next e prev.

Se, nella nostra lista concatenata, l’oggetto con chiave 4 segue l’oggetto con chiave 16 e nel

​ ​ ​ ​

nostro array 4 appare in key[2] e 16 appare in k ey[5], avremo che next[5] = 2 e prev[2] = 5.

​ ​

Anche se la costante NIL appare nel campo next della coda e nel campo prev della testa, di

solito si utilizza un intero (0 o -1) che non può essere affatto indice dell’array (0 no perchè gli

array partono per convenienza da 1, -1 è negativo).

Rappresentazione di oggetti con un solo array

Le parole, nella memoria di un calcolatore, sono indirizzate da numeri interi compresi tra 0 e

M-1 con M intero opportunamente grande. In molti linguaggi di programmazione un oggetto

​ ​

occupa un insieme contiguo di locazioni nella memoria del calcolatore. Il puntatore è

l’indirizzo della prima locazione di memoria dell’oggetto; le altre locazioni si indicizzano

aggiungendo un offset al puntatore.

Per implementare gli oggetti possiamo adottare la stessa stategia degli ambienti di

programmazione senza puntatore: ​

● Un oggetto occupa un sottoarray contiguo A [j...k].

● Ogni campo dell’oggetto corrisponde a un offset nell’intervalo tra 0 e k-j. L’indice j è il

puntatore dell’oggetto ​ ​

● Se gli offset che corrispondono a key, next e prev sono 0,1 e 2, per leggere il valore

​ ​ ​

di prev[i], dato un puntatore i

, aggiungiamo il valore i del puntatore all’offset 2,

​

ottenendo A[i+2].

La rappresentazione con un solo array è flessibile perchè consente agli oggetti i lunghezza

differente di essere memorizzati nello stesso array. Il problema di gestire tale collezione

eterogenea di oggetti è più difficile del problema di gestione di una collezione omogenea,

dove tutti gli oggetti hanno gli stessi campi. Useremo però strutture dati omogeneee.

Allocare e liberare oggetti

Per inserire una chiave in un insieme dinamico rappresentato da una lista doppiamente

concatenata, bisogna allocare un puntatore a un oggetto correttamente inutilizzato nella lista

concatenata. Bisogna, quindi, gestire bene gli oggetti correttamente inutilizzati. Per farlo si

​ ​

utilizzano i garbage collector (spazzini della memoria), che determinano quali oggetti sono

inutilizzati. Molte applicazioni, però, sono semplici al punto da poter svolgere il compito di

restituire gli oggetti non utilizzati a un gestore della memoria.

Esaminiamo il problema di allocare/deallocare oggetti omogenei in una lista doppiamente

concatenata, rappresentata da più array. ​ ​

● Supponiamo array con grandezzza m e in qualche istante l’insieme dinamico ha n

<

m elementi. ​

● m - n oggetti sono liberi​ e possono essere utilizzati per allocare nuovi oggetti.

● Gli oggetti liberi sono mantenuti in una lista singolarmente concatenata chiamata free

list che ha solo l’array next. La testa della free list è mantenuta nella variabile globale

free.

● Quando l’insieme dinamico rappresentato dalla lista concatenata L non è vuoto, la

free list può essere interlacciata con la lista L. Ogni oggetto può trovarsi in L o in free

list, non in entrambre.

● La free list è uno stack: il prossimo oggetto allocato è l’ultimo che è stato liberato

(LIFO) ​

● Supponiamo che la variabile f

ree punti al primo elemento della free list

Allocate_Object()

if free == NIL

error “spazio esaurito!”

else x = free

free = next|x|

return x

Free_Object(x)

next|x| = free

free = x

Tempo O(1).

● La free list contiene gli n oggetti non allocati. Quando lo spazio è esaurito da’ errore.

Rappresentazione di alberi con radice

Rappresentiamo i singoli nodi di un albero come un oggetto. Supponiamo che ogni nodo

contenga un campo key. I restanti campi sono puntatori ad altri nodi.

Alberi binari ​ ​

Si utilizzano i campi p, left e right per indicare padre, figlio sinistro e figlio destro di ogni nodo

​

dell’albero T.

​

● Se p[x] == NIL allora x è la radice.

​

● Se left[x] == NIL allora il nodo non ha figlio sinistro

​

● Se right[x] == NIL allora il nodo non ha figlio destro

​

● L’attributo root[T] punta alla radice dell’albero

​

● Se root[T] == NIL l’albero è vuoto.

Alberi con ramificazione senza limite

Lo schema per rappresentare gli alberi binari può essere esteso a qualsiasi classe di alberi il

​ ​

cui numero di figli per nodo sia al massimo una qualche costante k

: sostituiamo i campi left e

​

right con child1, child2, child3..childk.

Questo schema non funziona più se il numero di figli è illimitato, perchè non sappiamo in

anticipo quanti campi allocare (gli array nella rappresentazione con più array).

​

Inoltre, nel caso in cui il numero massimo di figli k sia limitato da una grande costante ma la

maggior parte dei nodi ha un piccolo numero di figli, andremmo a sprecare memoria.

Per rappresentare gli alberi con un numero arbitrario di figli, esiste uno schema derivato da

quello degli alberi binari: ​ ​

● Come con gli alberi binari, ogni nodo contiene un puntatore p al padre e root[T] alla

​

radice. Anzichè avere un puntatore per ogni figlio, ogni nodo x ha soltanto due

puntatori: ​

○ left-child[x], che punta al figlio di x più a sinistra

​

○ right-sibiling[x], che punta al fratello di x immediatamente a destra

​ ​

● Se il nodo x non ha figli, left-child[x] = NIL. ​

● Se il nodo è il figlio più a destra di suo padre, r ight-sibiling[x] = NIL.

Il tempo è O(n)

Viste alberi binari ​ ​

● Vista in ordine: viene stampato prima il sottoalbero sinistro, poi la radice e poi il

sottoalbero destro ​

● Vista in postordine: viene stampato prima il sottoalbero sinistro, poi il

sottoalbero destro, poi la radice ​

● Vista in preordine: viene stampata prima la radice, poi il sottoalbero sinistro, poi

il sottoalbero destro.

Alberi binari di ricerca

● Strutture dati che supportano molte operazioni su insiemi dinamici, tra cui SEARCH,

MINIMUM, MAXIMUM PREDECESSOR, SUCCESSOR, INSERT e DELETE. Quindi

un un albero binario di ricerca può essere utilizzato sia come dizionario che come

coda di priorità.

● Le operazioni richiedono un tempo proporzionale all’altezza dell’albero.

​ ​

○ Per un albero binario completo (cioè ogni nodo ha 2 figli) con n nodi servirà

un tempo nell’ordine di Θ(log n) nel caso peggiore.

​ ​ ​

○ Per un albero a catena lineare con n nodi, le stesse operazioni richiedono un

tempo Θ(n) nel caso peggiore.

​

○ L’altezza attesa di un albero binario di ricerca costruito in modo casuale è

O(log n), quindi le operazioni elementari svolte su questo tipo di albero

richiedono un tempo nell’ordine di Θ(log n)

Cosa sono gli alberi binari di ricerca?

Un albero binario di ricerca è organizzato in un albero binario (ogni nodo ha al massimo 2

figli, ma può averne anche solo 1 o 0) che può essere rappresentato da una struttura dati

concatenata in cui ogni nodo è un oggetto.

​ ​ ​

Oltre al campo chiave key, ogni nodo ha i campi left, right e p che puntano ai nodi che

corrispondono al figlio sinistro, figlio destro e padre. Se manca uno di essi, il campo

​ ​

corrispondente avrà valore NIL. Il nodo radice root è l’unico nodo che ha p = NIL.

Le chiavi in un albero binario di ricerca sono sempre memorizzate in modo da soddisfare la

proprietà degli alberi binari di ricerca​ .

​ ​ ​

● Sia x un nodo in un albero binario di ricerca. Se y è un nodo nel sottoalbero sinistro

​ ​ ​ ​ ​

di x

, allora key[y] < key[x]. Se y è un nodo nel sottoalbero destro di x, allora key[x]

< key[y]. (Il figlio sinistro deve essere minore del padre, il figlio destro deve essere

maggiore del padre).

Questa proprietà consente di visualizzare ordinatamente tutte le chiavi di un albero binario di

​

ricerca con un semplice algoritmo ricorsivo di attraversamento simmetrico di un albero

(inorder), chiamato così perchè la chiave della radice di un sottoalbero viene visualizzata fra

i valori del suo sotto albero sinistro e quelli del suo sottoalbero destro.

​ ​

L’algoritmo di attraversamento anticipato di un albero (preorder) visualizza la radice prima

​ ​

dei suoi sottoalberi e un algoritmo di attraversamento posticipato di un albero (postorder)

visualizza la radice dopo i valori dei suoi sottoalberi.

Per visualizzare tutti gli elementi di un albero binario di ricerca T, la chiamata da fare è

INORDER_TREE_WALK(root[T]).

INORDER_TREE_WALK(x)

if x != NIL

INORDER_TREE_WALK(left[x])

visualizza key[x]

INORDER_TREE_WALK(right[x])

Tempo di Θ(n) perchè, dopo la chiamata iniziale, la procedura viene chiamata

ricorsivamente per due volte per ogni nodo dell’albero (una per il figlio sinistro e una per il

destro). ​ ​

Teorema: Se x è la radice di un sottoalbero di n nodi, la chiamata

INORDER_TREE_WALK(x) richiede il tempo Θ(n)

​

Dimostrazione: T(n) tempo richiesto dalla procedure INORDER_TREE_WALK quando

​

viene chiamata per la radice di un sottoalbero di n nodi. ​

Se il sottoalbero è vuoto, l’algoritmo ci mette un tempo costante c, quindi T(0) = c.

​

Per n > 0, supponiamo che l’algoritmo sia chiamato per un nodo x il cui sottoalbero sinistro

​ ​ ​

ha n nodi e il destro ha n-k-1 nodi. Il tempo di esecuzione è T(n) = T(k) + T(n-k-1)+d con d

costante positiva che tiene conto del tempo per eseguire l’algoritmo, escluse le chiamate

ricorsive.

Con il metodo di sostituzione si prova che T(n) = Θ(n) dimostrando che T(n) = (c+d)n + c.

Per n = 0, abbiamo (c + d) * 0 + c = c = T(0).

Per n > 0, abbiamo:

T(n) = T(k) + T(n-k-1)+d

T(n) = (c+d)k + c) + ((c+d)(n-k-1)+ c)+ d

T(n) = (c+d)n + c - (c+d)+ c+ d

T(n) = (c+d)n + c

T(n) = Θ(n)

Heap

Un heap (binario) è una struttura dati composta da un array che possiamo considerare come

un albero binario quasi completo. Ogni nodo dell’albero è un elemento dell’array.

Tutti i livelli dell’albero sono riempiti ad eccezione dell’ultimo che può essere riempito solo a

sinistra fino a un certo punto.

Un array A che rappresenta uno heap è un oggetto con due attirbuti:

● lunghezza[A], numero degli array

● heapsize[A], numero degli elementi dell’heap che sono registrati nell’array A.

La differenza tra heapsize e lunghezza dell’array è che se A[1...lunghezza[A]] contiene

​

numeri validi, nessun elemento dopo A[heapsize[A]], dove heapsize < lunghezza, è un

elemento dell’heap. ​

La radice è A[1]. Se i è l’indice di un nodo, gli indici di suo padre PARENT(i), del figlio

sinistro LEFT(i) e del figlio destro RIGHT(i) sono:

● PARENT(i): return └i/2┘

● LEFT(i): return 2i

● RIGHT(i): reutrn 2i + 1

Nella maggior parte dei calcolatori, LEFT(i) può calcolare 2i con una sola istruzione facendo

scorrere di una posizione a sinistra la rappresentazione binaria di i.

RIGHT(i) può essere calcolato allo stesso modo e in più viene aggiunto un 1 come bit meno

significativo.

PARENT(i) si può calcolare con uno scorrimento di una posizione a destra della

rappresentazione di i.

Ci sono due tipi di heap binari: ​ ​

● max-heap, in cui A[PARENT(i)] > A[i]. Ossia che il padre è sempre più grande dei

figli. ​ ​

● min-heap​ , in cui A[PARENT(i)] < A[i], il contrario di max-heap.

​ ​

Per l’algoritmo Heapsort​ si utilizza m

ax-heap​

.

● Altezza di un nodo: numero di archi nel cammino semplice da un nodo fino a una

sua foglia.

● Altezza di un heap:​ altezza dalla sua radice.

​

Poichè un heap di n elementi è basato su un albero binario completo, la sua altezza è Θ(log

n).

Le operazioni fondamentali sugli heap vengono eseguite in un tempo che, nel caso

peggiore​ , è O(log n).

Algoritmi Heap: Heapify

HEAPIFY è un algoritmo che ordina lo heap secondo la proprietà del max-heap.

Input:​ Array A e un indice i dell’array.

Quando viene invocato HEAPIFY, si suppone che gli alberi binari con radici in LEFT(i) e

RIGHT(i) siano max-heap, ma che A[i] possa essere più piccolo dei suoi figli, violando la

proprietà max-heap. La funzione di HEAPIFY è quella di scambiare i valori in modo che il

sottoalbero con radice i sia anch’essa un max-heap.

Azione ​

● A ogni passaggio viene determinato il più grande gli elementi fra A[i], A[LEFT(i)] e

​

A[RIGHT(i)]. L’indice viene memorizzato in m assimo.

​

● Se A[i] è il più grande, il sottoalbero è un max-heap e l’algoritmo termina.

​ ​ ​

● Se A[i] non è il più grande, A[i] viene scambiato con A[massimo]; in questo modo, il

​

nodo i e i suoi figli soddisfano la proprietà del max-heap.

​ ​

● Il nodo con indice massimo, però ha adesso il valore originale di A[i] e, quindi, il

​

sottoalbero con radice in massimo potrebbe violare la proprietà del max-heap. Di

conseguenza, deve essere chiamata ricorsivamente la procedura HEAPIFY per

questo sottoalbero.

Codice

HEAPIFY(A,i)

l = LEFT(i)

r = RIGHT(i)

​ ​

if l < heapsize[A] and A[l] > A[i]

massimo = l

else massimo = i

​ ​

if r < heapsize[A] and A[r] > A[massimo]

massimo = r

if massimo != r

Scambia (A, i, massimo)

HEAPIFY(A, massimo)

Tempo ​

In un sottoalbero di dimensione n con radice in un nodo i è pari al tempo Θ(1) per sistemare

​

le relazioni tra gli elementi A[i], A[LEFT(i)] e A[RIGHT(i)], più il tempo per eseguire HEAPIFY

​

in un sottoalbero con radice in uno dei figli del nodo i

. ​

I sottoalberi dei figli hanno ciascuno una dimensione che non supera 2n/3 (il caso peggiore è

quando l’ultima riga dell’albero è piena esattamente a metà) e il tempo di esecuzione è

quindi:

​ ​

T(n) < T(2n/3)+Θ(1) .

La soluzione è, per il caso 2 del teorema dell’esperto, O(log n). Si può indicare con O(h) il

​

tempo di esecuzione in un nodo di altezza h

.

Buildheap ​

Si può utilizzare HEAPIFY dal basso verso l’alto per convertire un array A[1..n] con n =

lunghezza[A] in un max-heap.

Supponiamo che tutti gli elementi del sottoarray A[(Ln/2 +1)..n] sono foglie dell’albero e

」

quindi ciascuno è un heap di un elemento da cui iniziare.

BUILDHEAP attraversa i restanti nodi dell’albero ed esegue HEAPIFY in ciascuno di essi.

Codice

BUILDHEAP(A)

heapsize[A] = lunghezza[A]

for i = Llunghezza[A]/2 down to 1

」

HEAPIFY(A, i)

Per verificare il corretto funzionamento, si utilizza la seguente invariante di ciclo:

​ ​

All’inizio di ogni iterazione del ciclo for, ogni nodo i

+1, i+2, ..n è la radice di un max-heap.

Bisogna dimostrare che è vera per la prima iterazione, che ogni iterazione conserva

l’invariante e che l’invariante fornisce un’utile proprietà per dimostrare la correttezza quando

termina il ciclo ​ ​ ​ ​

Inizializzazione: prima dell’iterazione del ciclo, i = L​ n/2 . Ogni nodo L​ n/2 + 1, L​ n/2 +

」 」 」

2...n è una foglia e, quindi, è la radice di un banale max-heap.

Conservazione: Per verificare che ogni iterazione conserva l’invariante di ciclo, notiamo che

​

i figli del nodo i hanno una numerazione più alta di i

. Per l’invariante di ciclo sono entrambi

radici di max-heap ed è la condizione richiesta affinchè la chiamata HEAPIFY(A,i) renda il

​

nodo i radice di un max-heap. Inoltre, la chiamata HEAPIFY preserva la proprietà che tutti i

​

nodi i+1, i+2...n siano radici di max-heap.

​

La diminuzione di i ad ogni ciclo for ristabilisce l’invariante di ciclo per la successiva

iterazione. ​ ​

Conclusione: alla fine del ciclo i=0. Per l’invariante di ciclo ogni nodo 1,2,...n è la radice di

un max-heap, in particolare lo è il nodo 1.

Si può calcolare un limite superiore del tempo di esecuzione:

● Ogni chiamata di HEAPIFY è O(log n) e ci sono O(n) chiamate. Quindi il tempo di

esecuzione è O(n log n), ma non è asintoticamente stretto.

● Si può ottenere un limite stretto se si osserva il tempo per eseguire HEAPIFY in un

nodo che varia con l’altezza del nodo dell’albero, e le altezze della maggior parte dei

​

nodi sono piccole. L’analisi più rigorosa stabilisce che un heap di n elementi ha

h+1

​ ​

un’altezza L​ log n e al massimo Γn/2​ nodi di qualsiasi altezza h

.

」 ↰ ​

● Il tempo richiesto da HEAPIFY per un nodo di altezza h è O(h), quindi si può

esprimere BUILDHEAP come se fosse limitato dall’alto da:

( )

Ŀlog n」 Ŀlog n」

n h

O h O

∑ Γ ( ) = ∑

↰

h+1 h

2 2

h=0 h=0

L’ultima sommatoria può essere calcolata ponendo x=½

∞ h 1/2

∑ =

h 2

2 (1−1/2)

h=0

Quindi il tempo di esecuzione di BUILDHEAP sarà

( ) ( )

Ŀlog n」 ∞

h h

O n O n

∑ = ∑

h h

2 2

h=0 h=0

O(n)

Quindi si può costruire un max-heap da un array non ordinato in un tempo lineare.

Heapsort

L’heapsort inizia utilizzando BUILDHEAP per costruire un max-heap dell’array di input

​

A[1...n] con n=lunghezza[A]. Poichè l’elemento più grande dell’array è memorizzato nella

​

radice A[1], esso può essere inserito nella sua posizione finale corretta scambiandolo con

A[n]. I figli della radice restano max-heap, ma la nuova radice potrebbe violarne la proprietà,

quindi bisogna chiamare HEAPIFY. ​

HEAPSORT ripete questo processo da 1 fino a n.

Codice

HEAPSORT(H)

BUILDHEAP(H)

for i=1 to n

Scambia(H,1, heapsize(H))

heapsize(H)--

HEAPIFY(H,1)

Tempo:

HEAPSORT ha un tempo di esecuzione di O(n log n), in quanto BUILDHEAP impiega O(n) e

​

ciascuna delle n chiamate impiega O(log n).

Code di priorità

Heapsort è un eccellente algoritmo, ma Quicksort è ancora più veloce. Nonostante ciò, la

struttura dati Heap è molto utile con le code di priorità.

Esistono due tipi di code di priorità:

● code di max-priorità​ , basate sul max-heap

​

● code di min-priorità, basate sul min-heap

​ ​

Definizione: una coda di priorità è una struttura dati che serve a mantenere un insieme S

​

di elementi, ciascuno con valore associato detto c

hiave​

.

​ ​

Operazioni max-priorità: Una coda di m

ax​ priorità supporta le seguenti operazioni:

​ ​ S x

● INSERT(S,x), inserisce elemento x nell’insieme S

. Può essere scritta ← { }

⋃

Argomenti dell'esame con spiegazione dei diversi algoritmi ed esercizi di esempio. Domande riassuntive finali utili anche in caso di esame orale.

Algoritmi:
- Ricerca sequenziale.
- Ricerca dicotomica.
- Selection Sort.
- Insertion sort.
- Limiti asintotici.
- Principio di induzione e ricorsione.
- Algoritmi con cicli for innestati, sommatorie.
- Algoritmi Divide et impera.
- Merge Sort.
- Quick Sort.
- Equazioni di ricorrenza.
- Counting Sort.

Srutture dati:
- Stack e code.
- Liste concatenate, operazioni, sentinella.
- Implementazione puntatori e oggetti.
- Alberi binari.
- Alberi binari di ricerca.
- Heap, heapify, buildheap, heapsort.
- Code di priorità.
- Hashing, operazioni.