METODY

TWORZENIA ALGORYTMÓW

M.Skowrońska, WMiI UMK

METODA PRZYROSTOWA

M.Skowrońska, WMiI UMK

{Sortuje tablicę A[1..n] liczb rzeczywistych :

≤

}

1. for j := 2 to n do

begin

2. pom := A[j] ;

{ wstaw A[j] w posortowany ciąg A[1 .. j-1] }

3. i:= j-1;

4. while (i>0) and (A[i]>pom) do

4. while (i>0) and (A[i]>pom) do

begin

5. A[i+1]:= A[i];

6. i:= i-1;

end;

7. A[i+1]:= pom;

end;

M.Skowrońska, WMiI UMK

"DZIEL I ZWYCIĘśAJ"

3 ETAPY :

1. DZIEL

2. ZWYCIĘśAJ

2. ZWYCIĘśAJ

3. POŁĄCZ

M.Skowrońska, WMiI UMK

SORTOWANIE PRZEZ SCALANIE

5 2 4 6

1 3 2 6

5 2

4 6

1 3

2 6

5 2 4 6 1 3 2 6

5 2 4 6 1 3 2 6

2 5

4 6

2 6

1 3

2 4 5 6

1 2 3 6

1 2 2 3 4 5 6 6

M.Skowrońska, WMiI UMK

MERGE-SORT ( A, p, k);

{ Sortuje elementy w podtablicy A[p..k];

jeśli p >= k to podtablica jest już posortowana;
jeśli p < k to dzieli A[p..k] na dwie podtablice , sortuje każdą z nich

i łączy w posortowaną podtablicę A[p..k];}

begin

if p < k then

begin

q := (p+k)/2 ;

Złożoność : T(n) =

Θ

Θ

Θ

Θ

(nlgn)

q := (p+k)/2 ;

MERGE-SORT ( A, p, q );

MERGE-SORT ( A, q+1, k );
MERGE (A, p, q, k);

end

end;

MERGE-SORT( A, 1, n )

{ s

ortuje tablicę A[1..n] }

M.Skowrońska, WMiI UMK

ZAD. Napisz pseudokod procedury MERGE (A, p, q, k);

M.Skowrońska, WMiI UMK

ALGORYTMY ZACHŁANNE

(GREEDY ALGORITHMS)

M.Skowrońska, WMiI UMK

DANE : Z = {1, 2, ... n } - zbiór n zajęć , n>0

[ p

i

, k

i

) p

i

- czas rozpoczęcia zajęcia i

k

i

- czas zakończenia zajęcia i p

i

< k

i

PLANOWANIE ZAJĘĆ

WYNIK: Największy podzbiór PZ zbioru Z, który zawiera zajęcia zgodne,

tzn.: i, j

∈

PZ , to [ p

i

, k

i

)

∩

∩

∩

∩

[ p

j

, k

j

) =

∅

∅

∅

∅

M.Skowrońska, WMiI UMK

GREEDY-ACTIVITY-SELECTOR ( p, k, n);

{ p- tablica początków zajęć, k- tablica końców zajęć;

zakładamy, że k [1]

≤

k [2]

≤

...

≤

k [n] }

begin

PZ := {1};

for i := 2 to n do

if p [i]

≥

k [j] then

begin

PZ := PZ

∪

{i};

PZ := {1};
j := 1;

PZ := PZ

∪

{i};

j := i

end;

return PZ;

{ PZ - największy podzbiór zajęć

parami zgodnych }

end;

M.Skowrońska, WMiI UMK

B

C

A

E

3

5

2

1

6

D

1

5

10

M.Skowrońska, WMiI UMK

PROGRAMOWANIE DYNAMICZNE

Rozwiąż "małe" problemy.

Scharakteryzuj strukturę optymalnego rozwiązania

Zapamiętaj rozwiązania.

Użyj tych rozwiązań do rozwiązania "dużych" problemów

M.Skowrońska, WMiI UMK

Mnożenie ciągu macierzy

DANE

:

n

∈

N

,

p

0

, p

1

, ... , p

n

∈

N

A

1

, ... , A

n

- macierze prostokątne o elementach rzeczywistych,

A

i

ma rozmiar p

i-1

* p

i

.

WYNIK : A

1

* ... * A

n

obliczony w sposób optymalny, tzn.:

liczba wykonanych mnożeń elementów macierzy
jest najmniejsza

"Optymalne nawiasowanie"

M.Skowrońska, WMiI UMK

DANE : A

1

- 10x100 A

2

- 100x5 A

3

- 5x50

WYNIK : A

1

A

2

A

3

- optymalnie

(A

1

A

2

)A

3

A

1

A

2

10x100x5

= 5000 => A

1

A

2

(10x5)

(A

1

A

2

)A

3

10x5x50

= 2500

Przykład :

A

1

(A

2

A

3

)

1

2

3

ΣΣΣΣ

7500

A

2

A

3

100x5x50

= 25000 => A

2

A

3

(100x50)

A

1

(A

2

A

3

) 10x100x50

= 50000

ΣΣΣΣ

75000

M.Skowrońska, WMiI UMK

MATRIX-MULTIPLY ( A, B );

{ Oblicza iloczyn : C = A * B }

begin

if kol(A) <> rows(B) then error

else for i := 1 to rows (A) do

for j := 1 to kol (B) do

begin

begin

C [i,j ] := 0;

for k := 1 to kol (A) do

C [i,j ] := C [i,j] + A [i,k] * B [k,j] ;

end;

return C;

end;

M.Skowrońska, WMiI UMK

Struktura optymalnego nawiasowania :

m [i,j] = minimalna liczba mnożeń potrzebna do obliczenia iloczynu A

i

*...*A

j

0 dla i = j

m [i,j] =

m [i,j] =

min { m [i,k] + m [k+1, j ] + p

i-1

* p

k

* p

j;

} dla i < j

i

≤

k < j

M.Skowrońska, WMiI UMK

MATRIX-CHAIN-ORDER ( p );

{ p[0..n] – tablica rozmiarów macierzy A

1

, ... , A

n

,

tzn .: A

i

ma rozmiar p[i-1] * p[i] }

begin

n := length (p) - 1;
for i := 1 to n do

m [i,i] := 0;

for r := 2 to n do

for i := 1 to n-r+1 do

begin

j := i + r – 1;
m [i,j] :=

∞

;

for k := i to j–1 do

for k := i to j–1 do

begin

q := m [i,k] + m [k+1, j ] + p

i-1

* p

k

* p

j;

if q < m [i,j ] then begin

m [i,j ] := q ;

s [i,j] := k

end end end

return m and s

end ;

M.Skowrońska, WMiI UMK

M.Skowrońska, WMiI UMK

MATRIX-CHAIN-MULTIPLY ( A, s, i, j);

{Oblicza optymalnie iloczyn A

i

* A

i+1

* ... * A

j

}

begin

if j > i then

begin

X := MARTIX-CHAIN-MULTIPLY(A, s, i,s[i,j]);

Y := MARTIX-CHAIN-MULTIPLY(A, s, s[i,j ] +1, j);

Z := MATRIX-MULTIPLY ( X, Y );

Z := MATRIX-MULTIPLY ( X, Y );
return Z

end

else return A

i

end;

MATRIX-CHAIN-MULTIPLY( A, s, 1, n);

M.Skowrońska, WMiI UMK

REKURENCJA

Liczby Fibonacciego

DANE : n

∈

N; n>=0

WYNIK : n - ta liczba Fibonacciego

fib( n: integer) : integer;

fib( n: integer) : integer;

begin

if ( (n =0) or (n= 1)) then fib := 1;

else

fib := fib(n-1) + fib(n-2)

end;

złożoność O(c

n

)

c = ((1+

√√√√

5)/2

M.Skowrońska, WMiI UMK

f8

f6

f7

f4 f5 f5 f6

f2

f3

f3

f4

f3

f4 f4 f5

fib(8)

f2

f3

f3

f4

f3

f4 f4 f5

f0 f1 f1

f2

f1

f2

f2

f3

f1

f2

f2

f3

f2

f3

f3

f4

f0 f1 f0 f1 f0 f1 f1

f2

f0 f1 f0 f1 f1

f2

f0 f1 f1

f2

f1

f2

f2

f3

f0 f1 f0 f1 f0 f1 f0 f1 f0 f1 f1

f2

f0 f1

M.Skowrońska, WMiI UMK



metoda dynamiczna -

złożoność O(n)

fib ( n: integer ) : integer;

f1, f2, f, k : integer;
begin

if ( n = 0 )or( n=1 )then fib := 1

else

begin

f1: = f2: = 1;

f1: = f2: = 1;

for k:= 2 to k := n-1 do

begin

f := f1 + f2;
f1 := f2;
f2 := f;

end;

end

end;

M.Skowrońska, WMiI UMK

PROBLEM PLECAKOWY

• Dyskretny problem plecakowy

DANE : n

∈

N

,

W

∈

Z

≥

0

P = {p

1

, ... , p

n

}, p

i

∈

N

c

1

, ... , c

n

∈

Z

≥

0

, w

1

, ... , w

n

∈

Z

≥

0

WYNIK : { p

i1

, ... , p

ik

} : {p

i1

, ... , p

ik

}

⊆

P , k

≤

n, w

i1

+ ... + w

ik

≤

W,

c

i1

+ ... + c

ik

= max { c

j1

+ ... + c

jr

: r

≤

n, {p

j1

, ... , p

jr

}

⊆

P, w

j1

+ ... + w

jk

≤

W }

M.Skowrońska, WMiI UMK

• Ciągły problem plecakowy

DANE : n

∈

N

,

W

∈

Z

≥

0

P= {p

1

, ... , p

n

} p

i

∈

N , i=1,...,n

c

1

, ... , c

n

∈

Z

≥

0

, w

1

, ... , w

n

∈

Z

≥

0

WYNIK : { p

i1

, ... , p

ik

} , { b

i1

, ... , b

ik

} : {p

i1

, ... , p

ik

}

⊆

P , b

ir

≤

w

ir

,

WYNIK : { p

i1

, ... , p

ik

} , { b

i1

, ... , b

ik

} : {p

i1

, ... , p

ik

}

⊆

P , b

ir

≤

w

ir

,

b

i1

+ ... + b

ik

≤

W, r=1,...,k, k

≤

n,

(c

i1

/w

i1

)b

i1

+ ... + (c

ik

/w

ik

)b

ik

=

max {(c

j1

/w

j1

)b

j1

+ ... + (c

jr

/w

jr

)b

jr

: r

≤

n, {p

j1

, ... , p

jr

}

⊆

P, w

j1

+ ... + w

jr

≤

W }

M.Skowrońska, WMiI UMK

10
kg

20
kg

30
kg

60 zł 100 zł 120 zł

P1

P2

P3

50

kg

20

30

Rozw. optymalne dla
problemu dyskretnego 1.

Plecak

P3

P2

60 zł 100 zł 120 zł

problemu dyskretnego 1.
120 + 100 =220 zł

Plecak

2. Wybór zachłanny - według ceny jednostkowej

P1 : 6 zł/kg

P2 : 5 zł/kg
P3 : 4 zł/kg

Problem dyskretny : nie daje rozwiązania optymalnego 10*6 + 20 *5 = 160
Problem ciągły : otrzymamy rozwiązanie optymalne 10*6 + 20*5 *+20*4 = 240

1.

Problem dyskretny : wybór zachłanny - według ceny produktu