Corso di Perfezionamento · 2020-02-05 · Divide et Impera Ricorrenze Tecniche di Programmazione...

Divide et ImperaRicorrenze

Corso di PerfezionamentoDivide et Impera, Algoritmi Ricorsivi e Ricorrenze

Maria Rita Di Berardini1

1Dipartimento di Matematica e InformaticaUniversita di Camerino

17 febbraio 2009

Maria Rita Di Berardini Corso di Perfezionamento


Outline

1 Divide et Impera

2 RicorrenzeMetodo iterativoMetodo degli alberi di ricorsioneMetodo della sostituzioneMetodo dell’esperto



Tecniche di Programmazione

Tecniche di progettazione di algoritmi:

1 Divide et Impera2 Programmazione Dinamica (PD for short)3 Algoritmi golosi

Le ultime due tecniche sono piu sofisticate rispetto al Divide etImpera, ma consento di risolve in maniera efficiente moltiproblemi computazionali

Vedremo come queste tecniche di programmazione vengonousate per risolvere problemi di ottimizzazione



Approccio Divide et Impera

L’approccio seguito da questa tecnica di progettazione consistenel suddividere il problema in input in un certo numero disottoproblemi di dimensione inferiore

Una volta risolti ricorsivamente i sottoproblemi cosı generati, sicombinano le loro soluzioni per creare la soluzione al problemadato

Distinguiamo tre fasi principali: Divide, Impera e Combina



Determinazione del massimo

Definizione del problema: determinazione del massimo in unasequenza di n elementi

Approccio Divide et Impera:

Divide: gli n elementi della sequenza vengono divisi in duesottosequenze di ≈ n/2 elementi ciascuna

Impera: si determina il massimo m1 della prima sequenza edil massimo m2 della seconda

Combina: ottiene il massimo della sequenza in input comemaxm1,m2



Algoritmo per la determinazione del massimo

Max(A, i , j)if i < j

then m← b(i + j)/2creturn maxMax(A, i , m), Max(A, m + 1, j)

Complessita di Max(A, 1, n) e descritta dalla ricorrenza

T (n) =

2T (n/2) + 1 se n > 1

1 se n > 1



Algoritmo di ordinamento MergeSort

Le tre fasi possono essere cosı descritte

Divide: gli n elementi della sequenza da ordinare vengono indue sottosequenze di ≈ n/2 elementi ciascuna

Impera: ordina, usando ricorsivamente il merge sort, le duesottosequenze

Combina: fonde le due sottosequenze per produrre comerisposta la sequenza ordinata




Il processo di suddivisione si ferma quando la sequenza da ordinareha lunghezza 1

Il passo combina fonde le due sequenze utilizzando una proceduraausiliaria di fusione merge(A, p, q, r), dove: A e un array e p, q, rsono indici di elementi dell’array tali che p < q < r

merge(A, p, q, r) assume che A[p, ..., q] e A[q + 1, ..., r ] sianoordinati e genera A[p, ..., r ] ordinato




MergeSort(A, left, right)if left < right

then mid = b(left + right)/2cMergeSort(A, left, mid)MergeSort(A, mid + 1, right)Merge(A, left, mid , right)



A = 8, 5, 4, 6, 1, 3, 7

8 5 4 6 1 3 7

fusione

8 5 4 6 1 3 7

8 5 4 6 1 3 7

5 4 6 1 3 4

4 5

4 5 8

1 6 3 7

1 3 6 7

1 3 4 5 6 7 8

divisione



Fusione di due sottosequenze ordinate

Merge(A, left,mid , right)m1 ← mid − left + 1 . dim di A[left, ...,mid ]m2 ← right −mid . dim di A[mid + 1, ..., right]B[1, . . . ,m1]← A[left, ...,mid ]C [1, . . . ,m2]← A[mid + 1, ..., right]i , j ← 1, k ← leftwhile i ≤ m1 and j ≤ m2

do if B[i ] ≤ C [j ]then A[k]← B[i ]

i ← i + 1else A[k]← C [j ]

j ← j + 1k ← k + 1

if i ≤ m1

then A[k, . . . , right]← B[i , ...,m1]else A[k, . . . , right]← C [j , ...,m2]



Analisi della complessita del MergeSort

Il costo dell’algoritmo mergeSort e descritto dalla ricorrenza:

T (n) =

2T (n/2) + f (n) se n > 1

1 se n = 1

dove con f (n) = n e il costo della procedura di fusione



Metodo iterativoMetodo degli alberi di ricorsioneMetodo della sostituzioneMetodo dell’esperto

Cosa e una relazione di ricorrenza

Una relazione di ricorrenza – o piu semplicemente ricorrenza – euna equazione che descrive una funzione in termini del suo valorecon input piu piccoli

Esistono tre grandi metodi per risolvere le ricorrenze, ossia perottenere dei limiti asintotici Θ o O

Il metodo iterativo, o metodo della albero di ricorsione

Il metodo della sostituzione

Il metodo dell’esperto che consente di risolvere ricorrenze dellaforma T (n) = aT (n/b) + f (n) dove a ≥ 1, b > 0 ed f (n) euna funzione data




Metodo iterativo

“Srotoliamo” la ricorsione fino ad ottenere una sommatoriadipendente da n — Esempio:

T (n) =

1 + T (n/2) se n > 1

1 se n = 1

T (n) = 1 + T (n/2)= 1 + 1 + T (n/4)= 1 + 1 + 1 + T (n/8)= 1 + 1 + 1 + 1 + T (n/16)= · · ·= k + T (n/2k)




Metodo iterativo

T (n) = 1 + T (n/2)= 1 + 1 + T (n/4)= 1 + 1 + 1 + T (n/8)= 1 + 1 + 1 + 1 + T (n/16)= · · ·= k + T (n/2k)

Continuiamo a srotolare la ricorsione fin quando n/2k = 1, i.e.quando k = log2 n. Allora:

T (n) = log2 n + 1 = O(log2 n)




Metodo iterativo: un altro esempio (meno semplice)

T (n) =

n + T (n/2) se n > 1

1 se n = 1

T (n) = n + T (n/2)= n + n/2 + T (n/4)= n + n/2 + n/4 + T (n/8)= n + n/2 + n/4 + n/8 + T (n/16)

= n/20 + n/21 + n/22 + n/23 + T (n/24)= · · ·

=k−1∑i=0

n/2i + T (n/2k)




Metodo iterativo: un altro esempio (meno semplice)

T (n) =k−1∑i=0

n/2i + T (n/2k) = nk−1∑i=0

(1/2)i + T (n/2k)

Di nuovo, ci fermiamo quando k = log n — quindi:

T (n) = nlog n−1∑

i=0

(1/2)i + 1

= n 1−(1/2)log n

1−(1/2)+ 1

= 2n(1− 12log n ) + 1

= 2n(1− 1n) + 1 = 2n − 1 = Θ(n)




Metodo degli alberi di ricorsione

E una variante del metodo iterativo in cui usiamo degli alberiper rappresentare i costi delle varie chiamate ricorsive

Esempio

T (n) =

n + 2T (n/2) se n > 1

1 se n = 1




Alberi di ricorsione: un esempio

n

T(n/2) T(n/2)

n

n/2 n/2

T(n/4) T(n/4) T(n/4) T(n/4)

T(n)

(b)(a)

(c)




Alberi di ricorsione

n

n/2 n/2

n/4 n/4 n/4 n/4

(d)

T(n/8) T(n/8) T(n/8) T(n/8) T(n/8) T(n/8) T(n/8) T(n/8)





n

n/4

n/2

n/4

n/8 n/8 n/8 n/8

n/4

n/2

n/4

n/8 n/8 n/8 n/8

0

1

2

3

T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1) T(1)T(1)T(1) T(1) T(1)k





Sia i un generico livello dell’albero di ricorsione — i = 0, . . . , k

Il livello i-esimo ha 2i nodi(al livello 0 abbiamo 1 = 20 nodi, ed ogni livello il doppio deinodi del precedente)

Ciascun nodo al livello i ha un costo pari a n/2i

(il nodo al livello 0 ha un costo pari a n = n/1 = n/20, e ognivolta che scendiamo di livello il costo dei nodi si dimezza)

il costo complessivo dei nodi al livello i e

2i × n/2i = n





Quale e il costo complessivo della chiamata T (n)?

T (n) =k∑

i=0

costo livello(i) =k∑

i=0

n = n · (k + 1)

Ci rimane da determinare il valore di k

L’ultimo livello corrisponde ad una serie di chiamate di T (1) (cifermiamo quando la dimensione del problema e 1)

k e tale che n/2k = 1, e quindi k = log n

Ricapitolando

T (n) = n · (k + 1) = n(log n + 1) = Θ(n log n)




Metodo della sostituzione

Metodo della sostituzione: “indovinare” una possibile soluzioneed usare l’induzione matematica per dimostrare che la soluzione ecorretta

Consideriamo di nuovo la ricorrenza

T (n) =

n + T (n/2) se n > 1

1 se n = 1

e dimostriamo, applicando il metodo della sostituzione, che

T (n) = O(n)




Metodo della sostituzione

Dobbiamo dimostrare che che esistono delle costanti positive c edn0 tali che 0 ≤ T (n) ≤ cn per ogni n ≥ n0

Caso base n = 1: T (1) = 1 ≤ c1 = c per ogni costante c ≥ 1(positiva)

Passo induttivo: assumiamo T (n′) ≤ cn′ per ogni n′ < n. Allora

T (n) = n + T (n/2)≤ n + cn/2= n(1 + c/2) se scegliamo c ≥ 21

≤ cn

1Infatti se c ≥ 2, allora 1 ≤ c/2 e 1 + c/2 ≤ c/2 + c/2 = c




Teorema dell’esperto – Teorema Master

Permette di analizzare algoritmi basati sulla tecnica del Divide etImpera:

dividi il problema (di dimensione n) in a sotto-problemi didimensione n/b

risolvi i sotto-problemi ricorsivamente

ricombina le soluzioni

Sia f (n) il tempo per dividere e ricombinare istanze di dimensionen. La relazione di ricorrenza e data da:

T (n) =

aT (n/b) + f (n) se n > 1

1 se n = 1




Teorema dell’esperto – Teorema Master

Si consideri la ricorrenza

T (n) =

aT (n/b) + f (n) se n > 1

1 se n = 1

Distinguiamo tre casi:

1 f (n) = O(nlogb a−ε) per qualche costante ε > 0allora: T (n) = Θ(nlogb a)

2 f (n) = Θ(nlogb a),allora: T (n) = Θ(nlogb a log2 n)

3 f (n) = Ω(nlogb a+ε) per qualche costante ε > 0 eaf (n/b) ≤ cf (n), per qualche costante c < 1allora: T (n) = Θ(f (n))




Applicazioni del teorema dell’esperto

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

a = b = 2, logb a = 1f (n) = Θ(n) = Θ(nlogb a)

(caso 2 del teorema master)

⇓T (n) = Θ(nlogb a log2 n) = Θ(n log2 n)





T (n) = c + 9T (n/3)

a = 9, b = 3, logb a = log3 9 = 2f (n) = c = O(n) = O(nlogb a−ε) = O(n2−ε) con ε = 1


⇓T (n) = Θ(nlogb a) = Θ(n2)





T (n) = n + 3T (n/9)

a = 3, b = 9, logb a = log9 3 = 1/2 (3 =√

9 = 91/2)f (n) = n = Ω(n) = Ω(nlog9 3+ε) con ε = 1/2

inoltre,af (n/b) = 3f (n/9) = 3(n/9) = 1/3n ≤ cf (n), per c = 1/3


⇓T (n) = Θ(f (n)) = Θ(n)


Corso di Perfezionamento · 2020-02-05 · Divide et Impera Ricorrenze Tecniche di Programmazione...

Documents

Transcript of Corso di Perfezionamento · 2020-02-05 · Divide et Impera Ricorrenze Tecniche di Programmazione...