Metody algorytmiczne
z Wiadomo jak struktur maj algorytmy,
z Wiadomo jak stworzyć obiekty, którymi manipuluj
algorytmy,
z Wiadomo jak zapisać algorytmy aby wykonał je
procesor,
ale
z Jakie s metody Z\P\ ODQLD algorytmów???
z Niestety, na obmy lanie przepisów nie ma dobrych
przepisów
M.Rawski Wst p do Informatyki
Jak to zrobić?
z Ka de zadanie jest wyzwaniem dla projektanta.
z Istniej ogólne metody algorytmiczne, które
mog być przydatne w rozwi zywaniu zada
algorytmicznych.
z Pewne algorytmy wypływaj z pewnych ogólnych
wzorców.
z Wi c zanim zaczniemy wysilać umysł w celu
znalezienia rozwi zania warto wypróbować te
wzorce
M.Rawski Wst p do Informatyki
W druj i sprawdzaj
z Prosty przegl d struktury danych np. w celu
znalezienia najwi kszego elementu ze zbioru
danych przechowywanych w tej strukturze:
z iteracja %7Å„ np. wektor, lista
z iteracje zagnie d one %7Å„ np. tablice wielowymiarowe, listy
list itp.
z rekurencja %7Å„ np. drzewa
z Przegl d struktury = budowanie ci gu
zawieraj cego wszystkie obiekty w strukturze
M.Rawski Wst p do Informatyki
Przegl d drzewa w gł b
z 1. wstaw korze jako pierwszy element ci gu,
1
1
z 2. powtarzaj co nast puje, a do nadania
korzeniowi etykiety  zamkni ty :
2 6 8
y 2.1. wybierz z aktualnego ci gu ostatni
3 4 7 9
wierzchołek, który nie ma etykiety
 zamkni ty ,
5 10 11
y 2.2. je li wybrany wierzchołek nie ma potomstwa,
które jeszcze nie zostało dopisane do ci gu, to
Przegl d drzewa w gł b
nadaj mu etykiet  zamkni ty , w przeciwnym
przypadku dopisz do ci gu pierwszego (licz c
od lewej) jego potomka, który jeszcze nie
wyst puje w ci gu.
M.Rawski Wst p do Informatyki
Przegl d drzewa w szerz
z 1. nadaj etykiet  nowy wszystkim wierzchołkom
drzewa,
1
1
z 2. wstaw korze jako pierwszy element ci gu,
234
z 3. dopóki w tworzonym ci gu wyst puje
wierzchołek z etykiet  nowy , powtarzaj co
5 6 7 8
nast puje:
y 3.1. wybierz z aktualnego ci gu pierwszy
910 11
wierzchołek, który ma etykiet  nowy , dodaj
Przegl d drzewa wszerz
do ci gu wszystkich jego potomków w
kolejno ci od lewej i usu dla tego wierzchołka
etykiet  nowy .
M.Rawski Wst p do Informatyki
 W druj i sprawdzaj
z Znajdowanie najwi kszej przek tnej w wielok cie
wypukłym
1
1 - liczba wierzchołków
6
2
Struktura danych dla opisu wielok ta -
tablica dwuwymiarowa: 5
1 23... 1
; [1 [2 [3 ... [1
4
3
< \1 \2 \3 ... \1
M.Rawski Wst p do Informatyki
 W druj i sprawdzaj cd.
z Co przegl damy? Np. tablic długo ci wszystkich
odcinków pomi dzy wierzchołkami
123...1
1 G G ... G
2 G G d
3 G G d
1G G G ...
z Przejrzenie górnej trójk tnej połowy tablicy (liczba
elementów 1(1 - 1)/2) pozwala znale ć element o
najwi kszej warto ci.
z Czy nie wystarczy przeszukać tylko wybranych par?
M.Rawski Wst p do Informatyki
 W druj i sprawdzaj - mo na inaczej
A B C
1
1 1
6
6 6
2
G25 2
2
G24
5 5
G35
5
4 3 4 4 3
3
D E F
1
1 1
6 6 6
2
G13 2
2
G36
5
5 5
G14 3
4 3 4 4
3
z Czyli dla 6 wierzchołków wystarczy 6 zamiast 15
kroków ( 15 = 6(6-1)/2 )
M.Rawski Wst p do Informatyki
Dziel i zwyci aj
z Je li nie mo esz uporać si z rozwi zaniem zadania
w cało ci, to spróbuj dzielić je na mniejsze o takiej
samej strukturze i stosuj rekurencyjnie algorytm
rozwi zywania. Uzyskane rozwi zania małych zada
ł cz w rozwi zania tych zada , które były wcze niej
dzielone.
M.Rawski Wst p do Informatyki
Dziel i zwyci aj - min-max
15 7 45 8 12 11 4 34
z 1. je li / zawiera tylko jeden element, to
PODZIAA

jest to jednocze nie max i min, je li
15 7 45 812 11 4 34
dwa to mniejszy jest min wi kszy max
PODZIAA
PODZIAA

z 2. w przeciwnym razie wykonaj co nast puje:
15 7 45 8 12 11 4 34
y 2.1. podziel list / na dwie cz ci /1 i /2;
y 2.2. znajd ich skrajne elementy max1, max2
45 8 34 4
i min1, min2;
y 2.3. wybierz mniejszy z min1 i min2 - to jest
min;
45 4
y 2.4. wybierz mniejszy z max1 i max2 - to
jest max;
M.Rawski Wst p do Informatyki
Dziel i zwyci aj - min-max cd.
3URFHGXUD znajd -min-max (L):
z 1. je li / zawiera tylko jeden element, to jest to jednocze nie max i
min, je li dwa to mniejszy jest min wi kszy max;
z 2. w przeciwnym razie wykonaj co nast puje:
y 2.1. podziel list / na dwie cz ci /1 i /2;
y 2.2. wywołaj znajd -min-max (L1): otrzymane wyniki umie ć w max1
i min1;
y 2.3. wywołaj znajd -min-max (L2): otrzymane wyniki umie ć w max2
i min2;
y 2.3. wybierz mniejszy z min1 i min2 - to jest min;
y 2.4. wybierz mniejszy z max1 i max2 - to jest max;
z 3. zwróć warto ci min i max jako wynik działania;
M.Rawski Wst p do Informatyki
Sortowanie przez scalanie
SURFHGXUD VRUWXM OLVW /
z 1. je li / zawiera tylko jeden
element, to jest posortowana;
5 12 17 7 20 21
z 2. w przeciwnym razie wykonaj co
nast puje:
y 2.1. podziel list / na dwie połowy /1
i /2;
5 7 12 17 20 21
y 2.2. wywołaj VRUWXM OLVW /1;
y 2.3. wywołaj VRUWXM OLVW /2;
y 2.4. scal posortowane listy /1 i /2 w
jedn posortowan list ;
z 3. wróć do poziomu wywołania.
M.Rawski Wst p do Informatyki
Sortowanie przez scalanie c.d.
15 7 45 8 12 11 4 34
PODZIAA

15 7 45 812 11 4 34
PODZIAA
PODZIAA

15 7 45 8 12 11 4 34
PP PP
15 7 45 8 12 11 4 34
SS SS
7 15 8 45 11 12 4 34
SCALANIE SCALANIE
7 8 15 45 4 11 12 34
SCALANIE
4 7 8 11 12 15 34 45
M.Rawski Wst p do Informatyki
Metoda zachłanna
z Istniej zadania, których rozwi zanie mo e być
budowane z elementów dobieranych kolejno według
zasady  id naprzód, łap najlepsze z tego co pod
r k i nigdy potem nie oddawaj tego co ju masz .
z 3U]\NáDG PHWRG\ Å‚]DFKáDQQHM´ Z\]QDF]DQLH
PLQLPDOQHJR GU]HZD UR]SLQDM FHJR Z JUDILH
z Problem polega na znalezieniu najta szej sieci
poł cze wi cej wszystkie podane punkty. -
Budowa kolei
M.Rawski Wst p do Informatyki
Metoda zachłanna - Budowa kolei
z Problem polega na znalezieniu najta szej sieci
poł cze wi cej wszystkie podane punkty.
26
3 3
17 14
12 13
13
15
9 9
7 7
10 10
11 11
8
6 6
16
4 4
Spójny graf z wagami kraw dzi Minimalne drzewo rozpinaj ce
(koszt: 63)
M.Rawski Wst p do Informatyki
Metoda zachłanna - Budowa kolei c.d.
z Algorytm:
z 1. wybierz najkrótszy odcinek drogi
z 2. powtarzaj co nast puje, a do poł czenia wszystkich punktów:
y 2.1. wybierz najkrótszy odcinek spo ród tych odcinków, które
ł cz jedno z ju poł czonych miast z jakimkolwiek miastem
jeszcze nie poł czonym
M.Rawski Wst p do Informatyki
Programowanie dynamiczne
z Jaka jest najkrótsza droga ł cz ca miasto A z
miastem G?
2
F
B
5
3
A
11 7
3
E
7
5
14
C
7
G
6
6
D
Skierowany graf acykliczny
(spójny)
M.Rawski Wst p do Informatyki
Programowanie dynamiczne c.d.
z Metoda zachłanna:
z Najkrótsza droga:
F
B
F
5
B
3
A
A
E
3
E
5
C
C
G
G
6
6
D
D
cie ka najkrótsza
cie ka wyznaczona metod
(koszt: 13)
zachłann (koszt: 15)
M.Rawski Wst p do Informatyki
Programowanie dynamiczne
z Zasada (optymalno ci Bellmana):
je eli znamy najlepsz drog przej cia od punktu
pocz tkowego do punktu ko cowego prowadz c przez
kolejne punkty, to ka dy fragment tej drogi pomi dzy
dowolnym punktem po rednim a punktem ko cowym
jest najlepsz drog przej cia od tego punktu do punktu
ko cowego.
M.Rawski Wst p do Informatyki
Programowanie dynamiczne
L(A) = ?
z Realizacja metody:
2
F
B
5
z L(X) - oznacza długo ć najkrótszej cie ki od
3
A
11 7
punktu X do punktu G
3
E
7
5
 L(G) = 0, L(D) = 6, L(E) = 5, L(F) = 7 14
C
7
G
6
 L(C) = min ( 6 + L(D), 7 + L(E) ) =
6
D
min ( 12, 12) = 12
Skierowany graf acykliczny
 L(B) = min ( 3 + L(E), 2 + L(F) ) =
(spójny)
min ( 8, 9) = 8
 L(A) = min ( 14 + L(D), 3 + L(C), 5 + L(B) )
=
min ( 20, 15, 13) = 13
M.Rawski Wst p do Informatyki