Algoritmi e Strutture Dati con domande riassuntive
Anteprima
ESTRATTO DOCUMENTO
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 ← { }
⋃
DESCRIZIONE APPUNTO
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.
I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher RickyBolt 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à Milano Bicocca - Unimib o del prof Zandron Claudio.
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