Lezione del 7/12/04 [2 ore, in AULA C, dalle 16:00 alle 18:00]

Lezione del 7/12/04 [2 ore, in AULA C, dalle 16:00 alle 18:00]

di: Algoritmi & Laboratorio (Modulo 1)

"Riassunto" della lezione:

Sono stati svolti i seguenti esercizi (alla lavagna).

1. Si risolvano con il metodo iterativo le seguenti relazioni di ricorrenza:

a) T(1) = 1

T(n) = 4T(n/2) + n³ n > 1

b) T(1) = 1

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

c) T(1) = 1

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

d) T(1) = 1

T(n) = 3T(n/2) + (1/3)T(n/2) + n⁴ n > 1

e) T(0) = 1

T(n) = T(⎣n/2⎦) + T(⎣n/5⎦) + 3 n > 0

Svolgimento dell’esercizio 1.a.

Nel seguito log sta a indicare logaritmo in base 2.

T(n) = 4T(n/2) + n³

= 2²T(n/2) + n³

= 2² (2²T(n/2²) + (n/2)³)+ n³

= 2⁴T(n/2²) + n³ /2 + n³

= 2⁴ (2²T(n/2³) + (n/2²)³) + n³ /2 + n³ = 2⁶T(n/2³) + n³ /2² + n³ /2 + n³

= 2⁶ (2²T(n/2⁴) + (n/2³)³) + n³ /2² + n³ /2 + n³ = 2⁸T(n/2⁴) + n³ /2³ + n³ /2² + n³ /2 + n³

= 2⁸ (2²T(n/2⁵) + (n/2⁴)³) + n³ /2³ + n³ /2² + n³ /2 + n³

= 2¹⁰T(n/2⁵) + n³ /2⁴ + n³ /2³ + n³ /2² + n³ /2 + n³ …

= 2^{2 log n} T(n/2^{log n}) + n³ /2^{(log n)-1} +...+ n³ /2² + n³ /2 + n³ = 2^{log n^2} T(1) + n³ ( 1/2^{(log n)-1} +...+ 1/2² + 1/2 + 1) = n² + n³ ( 1/2^{(log n)-1} +...+ 1/2² + 1/2 + 1)

= n² + n³ ( ((1/2)^{log n} - 1) / (1/2 - 1) ) = n² + 2 n³ ( 1 - (1/2)^{log n} )

= n² + 2 n³ ( 1 - 1/n ) = n² + 2 n² ( n-1) = 2n³ - n²

= THETA(n³)

Svolgimento dell’esercizio 1.b.

Nel seguito log sta a indicare logaritmo in base 2.

T(n) = 5T(n/2) + n

= 5 (5T(n/2²) + n/2) + n

= 5²T(n/2²) + (5/2)n + n

= 5² (5T(n/2³) + n/2²) + (5/2)n + n = 5³T(n/2³) + (5/2) ² n + (5/2)n + n

= 5³ (5T(n/2⁴) + n/2³) + (5/2) ² n + (5/2)n + n = 5⁴ T(n/2⁴) + (5/2) ³ n + (5/2) ² n + (5/2)n + n …

= 5 ^{log n} T(n/2^{log n}) + (5/2)^{(log n)-1}n +...+ (5/2) ² n + (5/2)n + n = 5 ^{log n} T(1) + (5/2)^{(log n)-1}n +...+ (5/2) ² n + (5/2)n + n

= 5 ^{log n} + (5/2)^{(log n)-1} n +...+ (5/2) ² n + (5/2)n + n

= n ^{log 5} + (5/2)^{(log n)-1} n +...+ (5/2) ² n + (5/2)n + n = n ^{log 5} + n ( (5/2)^{(log n)-1} +...+ (5/2)² + 5/2 + 1) = n ^{log 5} + n( ((5/2)^{log n} - 1) / (5/2 - 1) )

= n ^{log 5} + (2/3) n( (5/2)^{log n} - 1) = n ^{log 5} + (2/3) n( (n ^{log 5} )/n - 1) ) = n ^{log 5} + (2/3) n ^{log 5} – (2/3) n = THETA(n ^{log 5})

Svolgimento dell’esercizio 1.c.

Simile allo svolgimento dell’esercizio precedente.

Svolgimento dell’esercizio 1.d.

Si osservi che

T(n) = 3T(n/2) + (1/3)T(n/2) + n⁴

= (10/3) T(n/2) + n⁴

il resto e’ simile allo svolgimento dell’esercizio 1.a.

Svolgimento dell’esercizio 1.e.

Risolviamo l’equazione disegnando l’albero della ricorsione.

T(n)

3 / \

/ \ T(⎣n/2⎦) T(⎣n/5⎦)

3

__________/ \_________

/ \ 3 3 / \ / \ / \ / \

T(⎣n/2²⎦) T(⎣n/(2*5)⎦) T(⎣n/5*2⎦) T(⎣n/5²⎦)

...

Dall’esame dell’albero e’ evidente che

- il ramo di sinistra avra’ altezza (log2 n)+1, - il ramo di destra avra’ altezza (log5 n)+1,

- gli altri rami avranno altezza compresa tra (log5 n)+1 e (log2 n)+1.

Ogni nodo interno e’ etichettato la costante 3, e le foglie sono etichettate con la costante 1.

Per maggiorare valore della funzione e’ quindi sufficiente contate i nodi di un albero binario completo di altezza (log2 n)+1 e moltiplicarli per 3.

Siccome un albero binario completo di altezza log2 n ha n –1 nodi, allora la soluzione dell’equazione di ricorrenza e’ O(n).