Algoritmi e strutture dati

FONDAMENTI algoritmo,

Informalmente, un è una procedura di calcolo bene definita che prende un certo valore, o un

input output;

insieme di valori, come e genera un valore, o un insieme di valori, come un algoritmo è quindi

una sequenza di passi computazionali che trasforma l'input in output. problema computazionale

Possiamo anche considerare un algoritmo come uno strumento per svolgere un

ben definito; la definizione del problema specifica in termini generali la relazione di input/output desiderata.

L'istanza di un problema è formata dall'input (che soddisfa tutti i vincoli importi nella definizione del

problema) richiesto per calcolare una soluzione del problema.

corretto

Un algoritmo si dice se, per ogni istanza di input, termina con l'output corretto; diciamo che un

risolve

algoritmo corretto il problema computazionale dato. Un algoritmo errato potrebbe non terminare con

qualche istanza di input o potrebbe terminare fornendo un risultato errato.

1. NOTAZIONE ASINTOTICA

Notazione o-grande

• f O(g) c n n > n f(n) < c g(n).

La funzione è in se e solo se esistono due numeri positivi e tali che per ogni ,

0 0

O(g) = f c, n > 0 tali che per ogni n > n si ha f(n) < c g(n)

{ | esistono }

0 0

La notazione o-grande rappresenta un limite superiore per la funzione data.

Notazione omega-grande

• f (g) c n n > n f(n) > c g(n).

La funzione è in se e solo se esistono due numeri positivi e tali che per ogni ,

r 0 0

(g) = f c, n > 0 tali che per ogni n > n si ha f(n) > c g(n)

{ | esistono }

0 0

La notazione omega-grande rappresenta un limite inferiore per la funzione data.

Notazione theta-grande

• f O(g) c , c n n > n

La funzione è in se e solo se esistono tre numeri positivi e tali che per ogni

1 2 0 0

c g(n) < f < c g(n)

1 2

O(g) = f | esistono c , c e n tali che per ogni n > n si ha c g(n) < f < c g(n)

{ }

1 2 0 0 1 2

f f O(g) f (g)

Si può dedurre che è in O(g) se e solo se è in e è in r n

2. DIVIDE ET IMPERA

divide et impera

Nel metodo un problema viene risolto in modo ricorsivo, applicando tre passi ad ogni livello

di ricorsione:

Divide: questo passo divide il problema in un certo numero di sottoproblemi, che sono istante più

◦ piccole dello stesso problema.

Impera: i sottoproblemi vengono risolti in modo ricorsivo; quando i sottoproblemi hanno una

◦ dimensione sufficientemente piccola, essi vengono risolti direttamente.

Combina: le soluzioni dei sottoproblemi vengono combinate per generare la soluzione del problema

◦ originale.

ricorrenza

Una è un'equazione che descrive una funzione in termini del suo valore con input più piccoli.

METODO DI SOSTITUZIONE

metodo di sostituzione

Il per risolvere le ricorrenze richiede due passi:

Ipotizzare la forma della soluzione

◦ Usare l'induzione matematica per trovare le costanti e dimostrare che là soluzione funziona.

◦

Il nome del metodo deriva dalla sostituzione della soluzione ipotizzata al posto della funzione quando

l'ipotesi induttiva viene applicata a valori più piccoli.

Questo metodo è potente, ma ovviamente può essere applicato soltanto nei casi in cui sia facile immaginare

la forma della soluzione.

METODO DELL'ALBERO DI RICORSIONE

Sebbene il metodo di sostituzione possa fornire una prova della correttezza di una soluzione di una

ricorrenza, a volte è difficile formulare una buona ipotesi per la soluzione; disegnare un albero di ricorsione è

una tecnica semplice per ideare una buona ipotesi.

albero di ricorsione

In un ogni nodo rappresenta il costo di un singolo sottoproblema nell'insieme delle

chiamate ricorsive di funzione. Sommiamo i costi all'interno di ogni livello per ottenere un insieme di costi per

livello; poi sommiamo tutti i costi per livello per determinare il costo totale di tutti i livelli della ricorsione.

METODO DELL'ESPERTO

Il metodo dell'esperto rappresenta un ricettario per risolvere equazioni alle ricorrenze della forma

a b f(n)

dove e sono costanti >1 e è una funzione asintoticamente positiva. n a

La ricorrenza descrive il tempo di esecuzione di un algoritmo che divide un problema di dimensione in

n/b, a b

sottoproblemi, ciascuno di dimensione dove e sono costanti positive.

T(n/b)

• i sottoproblemi vengono risolti in modo ricorsivo, ciascuno nel tempo

f(n)

• la funzione comprende il costo di dividere il problema e combinare i risultati dei sottoproblemi.

E nafta

m'Yb

Se allora

0

Fln

◦ Tin 8D

m'Yb

Fln

Se allora Tin

◦ n log

n

E

nlofts

Se e se

◦ treno

Fln

f

fin f

r 1

c c

a e

per

allora fini

Tin e

ALGORITMI DI ORDINAMENTO

INSERTION SORT INSERTION-SORT (A)

for to

1 j=2 A.length

2 key = A[ j ]

3 // inserisce A[ j ] nella sequenza ordinata A[1...j-1]

4 i=j-1

while

5 i>0 and A[ i ] > key

6 A[i+1] = A[ i ]

7 i--

8 A[i+1] = key

j for

L'indice identifica l'elemento corrente da inserire negli altri. All'inizio di ogni iterazione del ciclo con

j, A[1...j-1] A[ j+1...n]

indice il sottoarray formato dagli elementi è ordinato, mentre il sottoarray sono gli

elementi non ancora ordinati.

• Complessità temporale O(n)

Caso ottimo, elementi già ordinati:

◦ 2

O(n )

Caso pessimo, elementi in ordine decrescente:

◦ 2

O(n )

Caso generale:

◦ O(1)

• Complessità spaziale:

MERGE SORT p, r)

MERGE-SORT(A,

if

1 p<r then

2 q = (p+r) / 2

3 MERGE-SORT (A, p, q)

4 MERGE-SORT (A, q+1, r)

5 MERGE (A, p, q, r) for,

All'inizio di ogni iterazione del ciclo

A[p...k-1]

righe 11-16, il sottoarray

k-p

contiene ordinati i elementi più ti

L[1...n1+1] R[1...n2+1].

piccoli di e

L[ i ] R[ j ]

e sono i più piccoli elementi dei

A.

loro array non copiati in

Divide: n n/2

• divide la sequenza degli elementi da ordinare in due sottosequenze di elementi ciascuna

Impera: merge_sort

• ordina le due sequenze in modo ricorsivo utilizzando l'algoritmo

Combina: merge.

• fonde le due sottosequenze ordinate per generare la sequenza ordinata, usando

• Complessità temporale D(n) = O(1)

Divide, calcola il centro del sottoarray: tempo costante

◦ n/2: T(n/2)

Impera, risolve in modo ricorsivo i 2 sottoproblemi 2

◦ •

merge C(n) = O(n)

Combina, la procedura richiede un tempo lineare:

◦ T(n) = 2T(n/2) + O(n) = O(n logn)

‣

QUICK SORT p, r)

QUICK-SORT(A,

if

1 p<r then

2 q = PARTITION (A, p, r)

3 QUICK-SORT (A, p, q)

4 QUICK-SORT (A, q+1, r)

All'inizio di ogni iterazione del ciclo, righe 3-6, per qualsiasi (A, p, r)

PARTITION

k

indice dell'array 1 x = A[r]

p < k < i A[k] < x

se allora

◦ 2 i = p-1

i+1 < k < j-1 A[k] > x

se allora

◦ for to

3 j=p r-1

k = r A[k] = x

se allora

◦ if

4 A[ j ] < x

5 i++

Le ultime due righe inseriscono il pivot al suo posto nel 6 scambia A[ i ] con A[ j ]

mezzo dell'array, scambiandolo con l'elemento più a 7 scambia A[i+1] con A[r]

x,

sinistra che è maggiore di e poi restituiscono il nuovo return

8 i+1

indice del pivot. t

i

P r

22h22am x

il Xx

EX sx (A, p, r)

PARTITION-HOARE

1 x = A[p]

2 i = p-1

3 j = r+1

loop

4 repeat

5

6 j--

until

7 A[ j ] < x

repeat

8

9 i++

until

10 A[ i ] > x

if

11 i < j

12 scambia A[ i ] con A[ j ]

else return

13 j

O(n)

Il partizionamento costa in termini di tempo.

Il tempo di esecuzione del quick-sort dipende dal fatto che il partizionamento sia bilanciato o sbilanciato e

questo, a sua volta, dipende da quali elementi vengono utilizzati per il partizionamento.

• Partizionamento nel caso peggiore n-1

Si verifica quando la routine "partition" produce un sottoproblema con elementi e uno con 0 elementi.

T(n)

Supponendo che questo partizionamento si verifichi in ogni chiamata ricorsiva, la ricorrenza per è

a

T(n) = T(n-1) + T(0) + O(n) = T(n-1) + O(n) = O(n )

• Partizionamento nel caso migliore (molto vicino al caso medio) n/2

Si verifica quando la routine "partition" produce due sottoproblemi con elementi ciascuno. T(n)

Supponendo che questo partizionamento si verifichi per ogni chiamata ricorsiva, la ricorrenza per è

T(n) = 2 T(n/2) + O(n) = O( n logn )

•

HEAP SORT

heap

Un è una struttura dati composta da un array che possiamo considerare come un albero binario quasi

completo; ogni nodo dell'albero corrisponde ad un elemento dell'array, e tutti i livelli dell'albero sono

completamente riempiti, tranne eventualmente l'ultimo che può essere riempito solo parzialmente.

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

A.lenght, che indica il numero di elementi nell'array

◦ A.heap-size, che indica il numero degli elementi dell'heap che sono registrati nell'array.

◦ A[1...A.lenght],

Cioè, anche se ci possono essere dei numeri memorizzati in tutto l'array soltanto i numeri in

A[1...A.heap-size] sono elementi validi dell'heap.

i di

Se è l'indice un nodo, gli indici di suo padre, del figlio sinistro e del figlio destro possono essere calcolati

LEFT ( i ) RIGHT ( i )

PARENT ( i ) return return

return 2i 2i+1

i/2

max-heap, i, A[ PARENT(i) ] > A[ i ],

In un la proprietà è che per ogni nodo si ha ovvero il valore di un nodo è

al massimo il valore di suo padre. Quindi l'elemento più grande di un max-heap è memorizzato nella radice e

il sottoalbero di un nodo contiene valori minori o uguali di quello contenuto nel nodo stesso.

min-heap, i, A[ PARENT(i) ] < A[ i ],

In un la proprietà è che per ogni nodo si ha ovvero il valore di un nodo è

al minimo il valore di suo padre. Quindi l'elemento più piccolo di un max-heap è memorizzato nella radice e il

sottoalbero di un nodo contiene valori maggiori o uguali di quello contenuto nel nodo stesso.

Conservare la proprietà dell'heap

• MAX-HEAPIFY, quando viene chiamata, assume che gli

MAX-HEAPIFY (A, i) LEFT(i) RIGHT(i)

alberi con radici e siano max-heap, ma

l = LEFT(i) A[ i ]

che possa essere più piccolo dei suoi figli.

r = RIGHT(i) A[ i ]

La procedura fa "scendere" il valore nel max-heap in

if l < A.heap-size and A[ l ] > A[ i ] i

modo che il sottoalbero con radice diventi un max-heap.

max = l

else max = i

if r < A.heap-size and A[ r ] > A[max] Ad ogni passo, viene determinato il più grande tra gli

max = r A[ i ], A[left(i)] A[right(i)];

elementi e il suo indice viene

if max != i max.

memorizzato in

scambia A[i] con A[max]

MAX-HEAPIFY (A, max)

A[ i ] i

Se è più grande, allora il sottoalbero con radice nel nodo è un max-heap e la procedura termina.

A[ i ] A[max];

Altrimenti, uno dei due figli ha l'elemento più grande e viene scambiato con in questo modo, il

i

nodo ed i suoi figli soddisfano la proprietà del max-heap. A[ i ] max

Il nodo con indice massimo, però, adesso ha il valore originale e quindi il sottoalbero con radice in

potrebbe violare la proprietà del max-heap; di conseguenza, deve essere chiamata ricorsivamente la routine

MAX_HEAPIFY per questo sottoalbero.

O( logn )

• Complessità temporale:

Costruire uno heap

• MAX-HEAPIFY

Possiamo utilizzare la procedura dal basso verso l'alto (bottom-up) per convertire un array

A[1...n], n = A.lenght,

con in un max-heap. A[n/2...n]

Essendo un albero binario, tutti gli elementi nel sottoarray sono foglie dell'albero; la procedura

BUILD-MAX-HEAP MAX-HEAPIFY

attraversa i restanti nodi dell'albero ed esegue in ciascuno di essi.

BUILD-MAX-HEAP (A)

A.heap-size = A.lenght

for down to

i = A.lenght/2 1

MAX-HEAPIFY (A,i)

O(n)

• Complessit&agrav