Introduzione agli algoritmi e strutture dati 3/ed T. H. Cormen, C. E. Leiserson, R. L. Rivest, C....

Introduzione agli algoritmi e strutture dati 3/edT. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein

Copyright © 2010 – The McGraw-Hill Companies srl

Algoritmi come soluzioni di problemi computazionali.

INTRODUZIONE

Esempio1: problema dell’ordinamento.

Input: a1,a2,...,an

Output: a'1,a'2,...,a'n permutazione (riarrangiamento) di a1,a2,...,an tale che a'1 a'2 ... a'n.



Soluzione1: Algoritmo InsertionSort.

InsertionSort (A) n lunghezza[A] for j 2 to n do

inserisce A[j] nella sequenza ordinata A[1..j-1]x A[j]

i j - 1while i 1 and x < A[i] do A[i+1] A[i] i i – 1A[i+1] x



InsertionSort (A)

n lunghezza[A] for j 2 to n do

inserisce A[j] nella sequenza ordinata A[1..j-1] x A[j] i j – 1 while i 1 and x < A[i] do

A[i+1] A[i] i i – 1

A[i+1] x

void InsertionSort (vector<tipo> A) { int i,j,n = A.size(); tipo x; for (j = 1; j < n; j++) { // inserisce A[j] nella sequenza // ordinata A[0..j-1] x = A[j]; i = j – 1; while (i >= 0 && x < A[i]) { A[i+1] = A[i]; i--; } A[i+1] = x; } }



x 5 8 4 7 1 3 6

5 x 8 4 7 1 3 6 2

2 5 x 4 7 1 3 6 8

2 5 8 x 7 1 3 6 4

2 x 5 8 7 1 3 6

2 5 x 4 7 1 3 6

2 4 5 8 x 1 3 6 7

2 4 5 x 8 1 3 6

5 2 8 4 7 1 3 6

2 5 8 4 7 1 3 6

2 5 8 4 7 1 3 6

2 4 5 8 7 1 3 6

InsertionSort (A) n lunghezza (A) for j 2 to n do inserisce A[j] nella sequenza ordinata A[1..j-1] x A[j] i j – 1 while i 1 and x < A[i] do A[i+1] A[i] i i – 1 A[i+1] x



2 4 5 7 8 x 3 6 1

x 2 4 5 7 8 3 6

1 2 4 5 7 8 x 6 3

1 2 x 4 5 7 8 6

1 2 3 4 5 7 8 x 6

1 2 3 4 5 x 7 8

1 2 3 4 5 6 7 8

2 4 5 7 8 1 3 6

1 2 4 5 7 8 3 6

1 2 3 4 5 7 8 6

InsertionSort (A) n lunghezza (A) for j 2 to n do inserisce A[j] nella sequenza ordinata A[1..j-1] x A[j] i j – 1 while i 1 and x < A[i] do A[i+1] A[i] i i – 1 A[i+1] x

2 4 5 x 8 1 3 6



Analisi di InsertionSort: correttezza

InsertionSort (A) n lunghezza [A] A contiene a1,a2, ..., an for j 2 to n do A[1..j-1] è un permutazione ordinata di a1,..., aj-1 x A[j] i j - 1 A[1..i] è un permutazione ordinata di a1,..., aj-1 x = aj e i = j-1

Correttezza InsertionSort



A[1..i] è un permutazione ordinata di a1,..., aj-1 x = aj e i = j-1while i 1 and x < A[i] do A[1..i]A[i+2..j] è permutazione ordinata di a1,..., aj-1, x = aj, 1 i < j e x < A[i] A[i+1] A[i] A[1..i-1]A[i+1..j] è permutazione ordinata di a1,..., aj-1, x = aj, 1 i < j e x < A[i+1] i i – 1 A[1..i]A[i+2..j] è permutazione ordinata di a1,..., aj-1, x = aj, 0 i < j e x < A[i+2] A[1..i]A[i+2..j] è permutazione ordinata di a1,..., aj-1, x = aj, i < j e o i = 0 oppure A[i] x



A[1..i]A[i+2..j] è permutazione ordinata di a1,..., aj-1, x = aj, i < j e o i = 0 oppure A[i] x

A[1..i]·x·A[i+2..j] è permutazione ordinata di a1,..., aj A[i+1] x A[1..j] è permutazione ordinata di a1,..., ajA[1..j] è permutazione ordinata di a1,..., aj e j = n A[1..n] è permutazione ordinata di a1,..., an



Analisi di InsertionSort: complessitàInsertionSort (A) n lunghezza(A) for j 2 to n do x A[j]

i j - 1 while i 1 and x < A[i] do

A[i+1] A[i] i i – 1 A[i+1] x

n

j jtc25

0c

nc2

13 nc

14 nc

n

j jtc26 1

n

j jtc27 1

18 ncjt j 1

1c



caso migliore:

)1(001

)1()1()(

8272625

43210

ncccc

ncncncccnTn

j

n

j

n

j

ISmin

abn

cccccc

ncccccnT ISmin

)(

)()(

854310

85432

1jtjt j 1



caso peggiore:

)1()1()1(

)1()1()(

82726

2543210

ncjcjc

jcncncncccnT

n

j

n

j

n

j

ISmax

jt j

'''

)(

) ½ ½ ½(

)( ½)(

2

84310

8765432

2765

anbnc

ccccc

nccccccc

ncccnT ISmax

jt j 1



caso medio:

)1(

)1()1()(

82 2

172 2

16

2 2

1543210

nccc

cncncncccnT

n

jjn

jj

n

jjIS

med

12

1

2

1 jjjt

"""

)(4

1

)4

1

4

1

4

3(

)(

2

2765

8765432

854310

anbnc

nccc

nccccccc

ccccccnT ISmed

jt j 1



Soluzione2: Algoritmo MergeSort.

MergeSort (A,p,r) if p < r then

q (p+r)/2 MergeSort (A,p,q) MergeSort (A,q+1,r) Merge(A,p,q,r)



Merge (A,p,q,r) n1 q – p + 1 n2 r – q for i 1 to n1 do

L[i] A[p + i – 1] for j 1 to n2 do

R[j] A[q + j] L[n1 + 1] R[n2 + 1]



i j 1 for k p to r do

if L[i] R[j] then A[k] L[i]

i i + 1else A[k] R[j]

j j + 1



5 2 8 0 4 7 1 9 3 2 6

0 4 7

25

5 2 8

5 2 8 0 4 7

5 2 8 0 4 7 1 9 3 2 6

2 61 9 3

1 9 3 62

9140

5 2 8 0 4 7 1 9 3 2 6

5 2 8 0 4 7 1 9 3 2 6

5 2 8 0 4 7 2 61 9 3

5 2 8

25

0 4 7 1 9 3

40 91

62

0 1 2 2 3 4 5 6 7 8 9

0 2 4 5 7 8

2 5 8

2 5

5 2

8

1 2 3 6 9

0 4 7 2 61 3 9

0 4 7 1 9 3

40 91

62



MergeSort (A,p,r) Analisi: correttezza

A[p..r] contiene una sequenza ap,...,ar di n = r – p + 1 elementi if p < r then altrimenti n 1 e ap,...,ar è già ordinata

q (p+r)/2 n1 = q – p + 1 < n ed n2 = r – q < n

MergeSort (A,p,q) MergeSort (A,q+1,r) A[p..q] è una permutazione ordinata di ap,...,aq

A[q+1..r] è una permutazione ordinata di aq+1,...,ar

Merge(A,p,q,r) A[p..r] è una permutazione ordinata di ap,...,ar



Merge (A,p,q,r) Analisi: correttezza A[p..q] contiene ap,...,aq ordinata A[q+1..r] contiene aq+1,...,ar ordinata

n1 q – p + 1 n2 r – q for i 1 to n1 do L[i] A[p + i – 1] for j 1 to n2 do

R[j] A[q + j] L[1..n1] contiene ap,...,aq

R[1.. n2] contiene aq+1,...,ar

L[n1+1] R[n2+1] L[1..n1+1] contiene ap,...,aq, ed R[1.. n2 +1] contiene aq+1,...,ar,



i j 1 for k p to r do i n1+1, j n2+1, k = p+i+j-2 A[p..k-1] è permutazione ordinata di L[1..i-1] R[1..j-1] ed A[p..k-1] min(L[i],R[j]) if L[i] R[j] then i n1

A[k] L[i] i i + 1 else j n2

A[k] R[j] j j + 1 i = n1+1, j = n2+1, k = r+1 A[p..r] è una permutazione ordinata di L[1..n1] R[1.. n2] A[p..r] è una permutazione ordinata di ap,...,ar



Analisi: complessitàMerge (A,p,q,r) n1 q – p + 1 n2 r – q for i 1 to n1 do

L[i] A[p + i – 1] for j 1 to n2 do

R[j] A[q + j] L[n1+1] R[n2+1]

1c

2c

3c 114 nc

15nc

124 nc

25nc

6c

211 nnprn

2/11 npqn

2/2 nqrn



i j 1 for k p to r do

if L[i] R[j] then A[k] L[i]

i i + 1 else A[k] R[j]

j j + 1

7c 18 nc

111nc

210nc

nc9

110nc

211nc

abnccccccc

nccccccnT M

8764321

111098542

)()(



Analisi: complessitàMergeSort (A,p,r) if p < r then


1c

2c

3c

1nT MS

2nT MS

nT M

1 se2/2/1 se

1se1se

21321

21

nnTnTabnnc

nnTnTnTccc ncc

nT

MSMS

MMSMSMS



cnannbnnT MS 2log

abn

abn 1 abn 2

abn 1,1 abn 2,1 abn 1,2 abn 2,2

n2log

abn

abn 2

abn 4

c c c c c c c cc c c c c cn

1 se2/2/

1 sennTnTabnncnT MSMS

MS



Analisi: complessitàMergeSort (A,p,r) if p < r then


1c

2c

3c

1nT MS

2nT MS

nT M

1 se2/2/1 se

1se1se

21321

21

nnTnTabnnc

nnTnTnTccc ncc

nT

MSMS

MMSMSMS



cnannbnnT MS 2log

abn

abn 1 abn 2

abn 1,1 abn 2,1 abn 1,2 abn 2,2

n2log

abn

abn 2

abn 4

c c c c c c c cc c c c c cn

1 se2/2/

1 sennTnTabnncnT MSMS

MS



0'''

loglimlim

22

anbnc

ncnanbn

nT

nTnIS

max

MSmax

n

dunque esiste N tale che per ogni n > N .Quindi, qualunque siano i valori delle costanti a, b, c, a', b' e c' l’algoritmo MergeSort è superiore a InsertSort per array di dimensione sufficientemente grande.

nTnT ISmax

MSmax



Possiamo dire che “cresce come” n2 mentre “cresce come” n log2 n.

nT ISmax

nT MSmax

n n2 n log2 n

IS

n2 ns

MS

n log2 n ns10 100 33 0.1s 0.033s

100 10000 664 10s 0.664s

1000 106 9965 1ms 10s

10000 108 132877 0.1s 133s

106 1012 2·107 17m 20ms

109 1018 3·1010 70anni 30s



''

)(loglimlim 2

anb

cannbn

nT

nTnIS

min

MSmin

n

dunque esiste N tale che per ogni n > N.Quindi, qualunque siano i valori delle costanti a, b, c, a', b' e c' l’algoritmo InsertSort è superiore a MergeSort per array (quasi) ordinati e sufficientemente grandi.

nTnT ISmin

MSmin



InsertSort è pure superiore a MergeSort per array di piccola dimensione in quanto le costanti a, b, c in sono generalmente molto maggiori delle costanti a', b' e c' in

nT MSmax

nT ISmax

Questo suggerisce una modifica di MergeSort in cui per ordinare porzioni di array di dimensione minore di una certa costante k si usa InsertSort invece di usare ricorsivamente MergeSort.



Soluzione3: Algoritmo MergeInsSort.

MergeInsSort

MergeInsSort (A,p,r) if p < r then if r-p+1 < 32 then InsertSort(A,p,r) else q (p+r)/2 MergeInsSort (A,p,q) MergeInsSort (A,q+1,r) Merge(A,p,q,r)



E’ possibile ridurre le costanti di MergeSort utilizzando una versione bottom-up iterativa invece della versione top-down ricorsiva.

La versione bottom-up iterativa è la seguente:All’inizio l’array è suddiviso in n segmenti di 20 = 1 elementi che sono ovviamente ordinati.Ripete quindi la seguente operazione: se l’array è suddiviso in segmenti ordinati di 2k

elementi ciascuno usa Merge per riunire a due a due tali segmenti ottenendo un array suddiviso in segmenti ordinati di 2k+1 elementi ciascuno. Quando 2k n l’array è ordinato.



Soluzione4: Algoritmo MergeSortBin.

MergeSortBin (A) n length(A), b 1 while b < n do A è ordinato a blocchi lunghi b MergeBin(A,B,b) b 2·b B è ordinato a blocchi lunghi b

MergeBin(B,A,b) b 2·b A è ordinato



MergeBin (A,B,b) n length(A) , k 0 while k < n do A[k+1..n] è ordinato a blocchi lunghi b B[1..k] è ordinato a blocchi lunghi 2·b i k p min(i+b,n) j p q min(j+b,n) while i+1 p and j+1 q do k k + 1 if A[i+1] A[j+1] then

i i + 1 B[k] A[i]

else j j + 1

B[k] A[j]

while i+1 p do k k + 1

i i + 1 B[k] A[i] while j+1 q do k k + 1

j j + 1 B[k] A[j]



5 2 8 0 4 7 1 9 3 2 6 1 3857 0 b = 1

2 5 0 8 4 7 1 9 2 3 1 6 5 7 3 8 0 b = 2

0 1 2 4 5 7 8 9 1 2 3 3 5 6 7 8 0 b = 8

0 1 1 2 2 3 3 4 5 5 6 7 7 8 8 9 0 b = 16

0 0 1 1 2 2 3 3 4 5 5 6 7 7 8 8 9 b = 32

0 0 1 1 2 2 3 3 4 5 5 6 7 7 8 8 9 b = 64

0 2 5 8 1 4 7 9 1 2 3 6 3 5 7 8 0 b = 4



Algoritmo MergeSortBin su file

MergeSortBinFile (A) A file b 1 do A è ordinato a blocchi lunghi b Distribuisci(A, B, C, b) nb Riunisci(B, C, A, b) A è ordinato a blocchi lunghi 2·b b 2·b A è ordinato a blocchi lunghi b e contiene nb blocchi while nb > 1

MergeSort binario



Distribuisci (A, B, C, b) rewind(A) while not eof(A) do i 1 while i b and not eof(A) do read(A, x), write(B, x) i i +1 i 1 while i b and not eof(A) do read(A, y), write(C, y) i i +1



Riunisci (B,C,A,b) rewind(B), fB eof(B), if not fB then read(B, x) rewind(C), fC eof(C), if not fC then read(C, y) nb 0 while not fC do i 1, j 1, nb nb+1 while i b and not fB and j b and not fC do if x y then write(A, x), fB eof(B), if not fB then read(B, x) else write(A, y), fC eof(C), if not fC then read(C, y)



while i b and not fB do write(A, x), fB eof(B), if not fB then read(B, x) while j b and not fC do write(A, y), fC eof(C), if not fC then read(C, y) if not fB then nb nb +1 while not fB do write(A, x), fB eof(B), if not fB then read(B, x) return nb

Introduzione agli algoritmi e strutture dati 3/ed T. H. Cormen, C. E. Leiserson, R. L. Rivest, C....

Documents

Transcript of Introduzione agli algoritmi e strutture dati 3/ed T. H. Cormen, C. E. Leiserson, R. L. Rivest, C....