Studieremo alcune tecniche per il progetto di algoritmi e di strutture dati:

Programmazione dinamica

Algoritmi golosi

Analisi ammortizzata

Vedremo poi alcuni tipi di strutture dati importanti per le applicazioni:

B-alberi

Strutture dati per insiemi disgiunti

Esempio: taglio delle aste

Problema del taglio delle asteE’ data un’asta metallica di lunghezza n che deve essere tagliata in pezzi di lunghezza intera (con un costo di taglio trascurabile). Per ogni lunghezza l = 1,…,n è dato il prezzo pl a cui si possono vendere i pezzi di quella lunghezza.Si vuole decidere come tagliare l’asta in modo da rendere massimo il ricavo della vendita dei pezzi ottenuti.

Programmazione Dinamica

Esempio l 1 2 3 4 5 6 7 8 9 10

pl 1 5 8 9 10 17 17 20 24 30

Lunghezza asta n Ricavo massimo rn Suddivisione ottima

1 1 1

2 5 2

3 8 3

4 10 2+2

5 13 2+3

6 17 6

7 18 1+6 o 2+2+3

8 22 2+6

9 25 3+6

10 30 10

Un’asta di lunghezza n può essere tagliata in 2n-1 modi distinti in quanto abbiamo una opzione tra tagliare o non tagliare in ogni posizione intera 1,…,n-1.Ad esempio per n = 4 abbiamo i seguenti 8 modi

Suddivisioni4 1+1+21+3 1+2+12+2 2+1+13+1 1+1+1+1

In generale il ricavo massimo rn o è il costo pn dell’asta intera oppure si ottiene effettuando un primo taglio in posizione i e quindi sommando i ricavi massimi del primo e del secondo pezzo, ossia rn= ri + rn-i

Quindi

1 se),...,,,max(

1 se

112211

1

nrrrrrrp

npr

nnnnn

Osserviamo che la soluzione ottima del problema di ottiene da soluzioni ottime di sottoproblemi. Diciamo che il problema ha sottostruttura ottima.

Otteniamo una struttura ricorsiva più semplice se invece di scegliere la posizione i di un primo taglio intermedio scegliamo la lunghezza i del primo pezzo per cui rn= pi + rn-i

0 se)(max

0 se0

1nrp

nr

inini

n

Cut-Road(p, n) if n == 0 return 0 q = -1 for i =1 to n q = max(q, p[i]+Cut-Road(p, n-i)) return q

nn

j

jTnT 2)(1)(1

0

Albero di ricorsione per n = 4

0

001

0

012

3

4

001

2 01

Lo stesso problema di dimensione 2 viene risolto due volte, quello di dimensione 1 quattro volte e quello di dimensione 0 otto volte.

Questo spiega la complessità 2n.

Ripetizione dei sottoproblemi!!

Possiamo ridurre la complessità evitando di risolvere più volte gli stessi problemi.

Un primo modo per farlo è dotare l’algoritmo di un blocco note in cui ricordare le soluzioni dei problemi già risolti: metodo top-down con annotazione.

Un secondo modo per farlo è calcolare prima i problemi più piccoli memorizzandone le soluzioni e poi usare tali soluzioni per risolvere i problemi più grandi: metodo bottom-up.

Versione top-down con annotazione:Memoized-Cut-Road(p, n) for i = 0 to n // inizializza il blocco note r[i] = -1 return Cut-Road-Aux(p, n, r)

Cut-Road-Aux(p, j, r) if r[j] ≥ 0 // il problema è già stato risolto return r[j] if j == 0 q = 0 else q = -1 for i = 1 to j q = max(q, p[i] + Cut-Road-Aux(p, j-i, r)) r[j] = q return q

)()( 2nnT

Versione bottom-up:

Bottom-Up-Cut-Road(p, n) r[0] = 0 // il problema più semplice for j = 1 to n q = -1 for i = 1 to j q = max(q, p[i] + r[j-i]) r[ j] = q return r[n] )()( 2nnT

Versione bottom-up estesa per calcolare la soluzione ottima e non solo il suo valoreExtended-Bottom-Up-Cut-Road( p, n) r[0] = 0 for j = 1 to n q = -1 for i = 1 to j if q < p[i]+r[ j - i] q = p[i]+r[ j - i] s[ j] = i // memorizzo il taglio ottimo r[ j] = q return r ed s

La seguente procedura calcola e stampa la soluzione ottima:

Print-Cut-Road-Solution( p, n) (r, s) = Extended-Bottom-Up-Cut-Road( p, n) j = n while j > 0 print s[j] j = j - s[j]

Moltiplicazione di matrici

Esso richiede pqr prodotti scalari

L’algoritmo per moltiplicare due matrici A e B di dimensioni pq e qr è:

Matrix-Multiply(A, B) for i = 1 to A.rows for j = 1 to B.columns C[i, j] = 0 for k = 1 to A.columns C[i, j] = C[i, j] + A[i, k] B[k, j] return C

Problema della moltiplicazione di matrici

Si deve calcolare il prodotto

A1 A2 ... An

di n matrici di dimensioni

p0p1 , p1p2 , ... , pn-1pn

Poiché il prodotto di matrici è associativo possiamo calcolarlo in molti modi.

Esempio:

Per calcolare il prodotto A1 A2 A3 di 3 matrici di dimensioni 2005, 5100, 1005 possiamo:

a) moltiplicare A1 per A2 (100000 prodotti scalari) e poi moltiplicare per A3 la matrice 200100 ottenuta (100000 prodotti scalari).

In totale 200000 prodotti scalari.

b) moltiplicare A2 per A3 (2500 prodotti scalari) e poi moltiplicare A1 per la matrice 55 ottenuta (5000 prodotti scalari).

In totale 7500 prodotti scalari.

Vogliamo trovare il modo per minimizzare il numero totale di prodotti scalari.

In quanti modi possiamo calcolare il prodotto?

Tanti quante sono le parentesizzazioni possibili del prodotto A1 A2 ... An .

Ad esempio per n = 4:(A1 (A2 (A3 A4)))

(A1 ((A2 A3) A4))

((A1 A2) (A3 A4))

((A1 (A2 A3)) A4)

(((A1 A2) A3) A4)

Il numero P(n) di parentesizzazioni possibili del prodotto A1 A2 ... An di n matrici si esprime ricorsivamente come segue:

1 se)()(

1 se1)(

1

1

nknPkP

nnP

n

k

Si può dimostrare che P(n) cresce in modo esponenziale.

Quindi, tranne per valori di n molto piccoli, non è possibile enumerare tutte le parentesizzazioni.

Passo 1: struttura di una parentesizzazione ottima

Supponiamo che una parentesizzazione ottima di A1 A2 ... An preveda come ultima operazione il prodotto tra la matrice A1..k (prodotto delle prime k matrici A1 ... Ak) e la matrice Ak+1..n (prodotto delle ultime n-k matrici Ak+1 ... An).Le parentesizzazioni di A1 ... Ak e di Ak+1 ... An sono parentesizzazioni ottime per il calcolo di A1..k e di Ak+1..n .

Perché?

Passo 2: soluzione ricorsiva

Di conseguenza la matrice prodotto parziale Ai..j è una matrice pi-1pj con lo stesso numero pi-1 di righe della prima matrice Ai e lo stesso numero pj di colonne dell’ultima matrice Aj .

Prendiamo come sottoproblemi il calcolo dei prodotti parziali Ai..j delle matrici Ai ... Aj .

Ricordiamo che la generica matrice Ai ha dimensioni pi-1pi .

Se i = j allora Ai..j = Ai ed m[i,i] = 0.

jipppjkmkim

jijim

jkijki

se)],1[],[(min

se0],[

1

Se i < j allora Ai..j = Ai ... Aj si può calcolare come prodotto delle due matrici Ai..k e Ak+1..j con k compreso tra i e j-1.

Il costo di questo prodotto è pi-1 pk pj .

Quindi

Passo 3Esempio

A1 3035A2 3515A3 155A4 510A5 1020A6 2025

i

1 65432

1

2

3

4

5

6

A1..1

0

A2..2

0

A3..3

0

A4..4

0

A5..5

0

A6..6

0

j

30

35

15

5

10

20

p

35 252010515 p

mk

mk

mk

mk

mk

mk

A1..2

157501

A2..3

26252

A3..4

7503

A4..5

10004

A5..6

50005

A1..3

79001

A2..4

43753

A3..5

15004

A4..6

35005

A1..4

94003

A2..5

71253

A3..6

53753

A1..5

119003

A2..6

105003

A1..6

151253

A1..1A2..2: 303515 = 15750A2..2A3..3: 35155 = 2625A1..1A2..3: 0+2650+30355 = 7900A1..2A3..3: 15750+0+30155 = 18000A3..3A4..4: 15510 = 750A2..2A3..4: 0+750+351510 = 6000A2..3A4..4: 2625+0+35510 = 4375A1..1A2..4: 0+4375+303510 = 14875A1..2A3..4: 15750+750+301510 = 21000A1..3A4..4: 7900+0+30510 = 9400

A4..4A5..5: 0+0+51020 = 1000A3..3A4..5: 0+1000+15520 = 2500A3..4A5..5: 750+0+15105 = 1500A2..2A3..5: 0+1500+351520 = 12000A2..3A4..5: 2625+1000+35520 = 7125A2..4A5..5: 4375+0+351020 = 11375

A1..1A2..5: 0+7125+303520 = 28125A1..2A3..5: 15750+1500+301520 = 26250A1..3A4..5: 7900+1000+30520 = 11900A1..4A5..5: 9400+0+301020 = 15400

A5..5A6..6: 0+0+102025 = 5000A4..4A5..6: 0+5000+51025 = 6250A4..5A6..6: 1000+0+52025 = 3500A3..3A4..6: 0+3500+15525 = 5375A3..4A5..6: 750+5000+151025 = 9500A3..5A6..6: 1500+0+152025 = 9000

A2..2A3..6: 0+5375+351525 = 18500A2..3A4..6: 2625+3500+35525 = 10500A2..4A5..6: 750+5000+351025 = 14500A2..5A6..6: 1500+0+352025 = 19000

A1..1A2..6: 0+10500+303525 = 36750A1..2A3..6: 15750+5375+301525 = 32375A1..3A4..6: 7900+3500+30525 = 15150A1..4A5..6: 9400+5000+301025 = 21900A1..5A6..6: 11900+0+302025 = 26900