METODY

TWORZENIA

ALGORYTMÓW

METODA PRZYROSTOWA

SORTOWANIE PRZEZ WSTAWIANIE

DANE : 6, 5 2 4 6 1 3

1 2 3 4 5 6

posortowany ciąg

1 2 4 5 6

posortowany podciąg 5-

elementowy

2 4 5 6

posortowany podciąg 4-

elementowy

2 4 5

posortowany podciąg 3-

elementowy

2 5

posortowany podciąg 2-

elementowy

5

posortowany podciąg 1-

elementowy

"DZIEL I ZWYCIĘŻAJ"

Zasada : problem rozmiaru n jest dzielony
na kilka problemów podobnych do problemu
początkowego
ale rozmiarów mniejszych niż n;
problemy "mniejsze" są rozwiązywane
i ich rozwiązania są łączone w rozwiązanie wyjściowego
problemu.

Wykorzystuje rekurencję.

SORTOWANIE

5 2 4 6 1
3 2 6

2 5

4 6

2 6

1 3

5 2 4 6

1 3 2 6

5 2

4 6

1 3

2 6

2 4 5 6

1 2 3 6

1 2 2 3 4 5
6 6

5 2 4 6 1 3
2 6

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 dzielimy A[p..k] na dwie podtablice i sortujemy każdą
z nich }

begin
if p < k then
begin
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 ) -

sortuje tablicę A[1..n]

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



(nlgn)

ALGORYTMY ZACHŁANNE

(GREEDY ALGORITHMS)

Zasada: w każdym kroku wykonuje działanie,
które w danej chwili jest najkorzystniejsze,
czyli wybiera lokalnie optymalną możliwość
w nadziei , że doprowadzi to do globalnie optymalnego
rozwiązania

Uwaga: Nie zawsze prowadzi do optymalnego rozwiązania

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

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

) =



PLANOWANIE ZAJĘĆ

GREEDY-ACTIVITY-SELECTOR ( p, k);

{ p- tablica początków zajęć, k- tablica końców zajęć;
zakładamy, że k [1]



k [2]



...



k [n] }

begin

n := length [p];
PZ := {1};
j := 1;

for i := 2 to n do

if p [i]  k [j] then

begin
PZ := PZ  {i};

j := i
end;
return PZ;
{ PZ - największy podzbiór
zajęć
parami zgodnych }
end;

PROGRAMOWANIE DYNAMICZNE



Rozwiąż "małe" problemy.



Zapamiętaj rozwiązania.



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

Zasada:



Liczby Fibonacciego

DANE :

n



N; n>0

WYNIK :

n - ta liczba Fibonacciego



metoda rekurencyjna

-

złożoność

O(n

n

)

fib( n: integer) : integer;
begin
if ( (n =1) or (n= 2)) then fib := 1;
else

fib := fib(n-1) +

fib(n-2)

end;



Liczby

Fibonacciego



metoda dynamiczna

-

złożoność

O(n)

fib ( n: integer ) : integer;
f1, f2, f, k : integer;
begin
if ( n < 2 ) then fib := n;
else
begin

f1 = f2 = 1;

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

f := f1 + f2;

f2 := f1;
f1 := f;

end;
end
end;



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

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

A

3

)

A

1

A

2

10x100x5

= 5000 => A

1

A

2

(10x5)

(A

1

A

2

)A

3

10x5x50 = 2500





7500

A

2

A

3

100x5x50

= 25000 => A

2

A

3

(100x50)

A

1

(A

2

A

3

) 10x100x50

= 5000





75000

Przykład :

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] =

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

i-1

* p

k

* p

j;

} dla

i < j

i  k < j

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
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 ;

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 );
return Z
end
else return A

i

end;

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
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;