InstytutInformatyki
PolitechnikaęlĄska
Analiza Algorytmów
Opracowa l:ZbigniewCzech
materia�ydydaktyczne
Gliwice,luty1997
Spis tre sci
1Dowodzeniepoprawnoącialgorytmów 4
1.1 Aksjomaty arytmetyki liczb : : : : : : : : : : : : : : : : : : : : : : : 5
1.2 Prawa rachunku zda� : : : : : : : : : : : : : : : : : : : : : : : : : : : 5
1.3 Regu�y dowodzenia (wnioskowania) : : : : : : : : : : : : : : : : : : : 6
1.4 Dowodzenie sko�czonoąci algorytmów : : : : : : : : : : : : : : : : : : 9
2Z�oonoąóobliczeniowaalgorytmów 9
2.1 Obliczanie wartoąci wielomianu : : : : : : : : : : : : : : : : : : : : : 9
2.2 Mnoenie liczb ca�kowitych : : : : : : : : : : : : : : : : : : : : : : : : 10
2.3 Znajdowanie maksymalnego (minimalnego) elementu : : : : : : : : : 11
2.4 Jednoczesne znajdowanie maksymalnego i minimalnego elementu : : : 11
2.5 Mnoenie dwóch n-bitowych liczb dwójkowych : : : : : : : : : : : : : 12
2.6Sortowanieprzez�Ączenie: : : : : : : : : : : : : : : : : : : : : : 13
3Kopceikolejkipriorytetowe 13
3.1 Procedury operujĄce na kopcu : : : : : : : : : : : : : : : : : : : : : : 13
3.2 Operacje na kolejkach priorytetowych : : : : : : : : : : : : : : : : : : 15
3.3 Sortowanie przez kopcowanie : : : : : : : : : : : : : : : : : : : : : : : 15
4Wyszukiwanie 17
4.1 Wyszukiwanie liniowe (proste) : : : : : : : : : : : : : : : : : : : : : : 17
4.2 Wyszukiwanie liniowe z zastosowaniem wartownika : : : : : : : : : : 17
4.3 Algorytm wyszukiwania liniowego realizowanego w tablicy rekordów
uporzĄdkowanych rosnĄco wed�ug kluczy : : : : : : : : : : : : : : : : 18
4.4 Wyszukiwanie binarne (logarytmiczne) : : : : : : : : : : : : : : : : : 18
4.5 Drzewa poszukiwa� binarnych : : : : : : : : : : : : : : : : : : : : : 18
4.6 Wyszukiwanie mieszajĄce : : : : : : : : : : : : : : : : : : : : : : : : 23
4.6.1 Mieszanie otwarte : : : : : : : : : : : : : : : : : : : : : : : : : 23
4.6.2 Mieszanie zamkniŚte : : : : : : : : : : : : : : : : : : : : : : : 25
4.7 Minimalne, doskona�e funkcje mieszajĄce : : : : : : : : : : : : : : : : 27
5Operacjenatekstach 29
5.1 Wyszukiwanie � naiwne" : : : : : : : : : : : : : : : : : : : : : : : : : 29
5.2 Algorytm Knutha, Morrisa i Pratta (KMP) : : : : : : : : : : : : : : : 30
5.3 Wyszukiwanie niezgodnoąciowe : : : : : : : : : : : : : : : : : : : : : 31
5.4 Algorytm Boyera i Moora (BM) : : : : : : : : : : : : : : : : : : : : : 32
6Sortowanie 33
6.1 Sortowanie przez proste wstawianie : : : : : : : : : : : : : : : : : : : 33
6.2 Algorytm Shella, czyli sortowanie za pomocĄ malejĄcych przyrostów : 36
6.3 Sortowanie przez proste wybieranie : : : : : : : : : : : : : : : : : : : 37
6.4 Sortowanie przez prosta zamianŚ : : : : : : : : : : : : : : : : : : : : 39
6.5 Sortowanie szybkie { algorytm Quicksort : : : : : : : : : : : : : : : : 41
6.6 Inna wersja algorytmu Quicksort : : : : : : : : : : : : : : : : : : : : 44
2
6.7 Czasy wykonania programów sortowania : : : : : : : : : : : : : : : : 47
7Selekcja 47
8Algorytmysortowania,wktórychkorzystasiŚzeszczególnychw�a-
snoącikluczy 48
8.1 Sortowanie kube�kowe : : : : : : : : : : : : : : : : : : : : : : : : : : 49
8.2 Sortowanie pozycyjne : : : : : : : : : : : : : : : : : : : : : : : : : : : 50
9Sortowanieplikówsekwencyjnych 52
9.1 �Ączenie proste : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 52
9.2 �Ączenie naturalne : : : : : : : : : : : : : : : : : : : : : : : : : : : : 56
10Algorytmyzach�anne(ar�oczne) 59
10.1 Kolorowanie zach�anne : : : : : : : : : : : : : : : : : : : : : : : : : : 59
10.2 Problem komiwojaera : : : : : : : : : : : : : : : : : : : : : : : : : : 59
10.3 Znajdowanie najta�szych dróg | Algorytm Dijkstry : : : : : : : : : 60
11Algorytmygrafowe 60
11.1 Przeszukiwanie grafu w g�Ąb : : : : : : : : : : : : : : : : : : : : : : : 60
11.2 Przeszukiwanie grafu wszerz : : : : : : : : : : : : : : : : : : : : : : : 62
11.3 Wyznaczanie cykli podstawowych (fundamentalnych) : : : : : : : : : 64
11.4 Minimalne drzewa rozpinajĄce : : : : : : : : : : : : : : : : : : : : : : 65
11.5 Wyznaczanie cykli Eulera : : : : : : : : : : : : : : : : : : : : : : : : 66
12Wyszukiwaniewyczerpujace.Algorytmzpowrotami 67
13Przeszukiwanieheurystyczne 67
13.1 Przeszukiwanie wszerz : : : : : : : : : : : : : : : : : : : : : : : : : : 67
13.2 Przeszukiwanie w g�Ąb z iteracyjnym pog�Śbianiem : : : : : : : : : : 68
13.3 Przeszukiwanie wed�ug strategii �najlepszy wierzcho�ek jako pierwszy" 68
14Generowaniepermutacji 69
15Literatura 71
16Pytania 72
17PodziŚkowania 76
3
1 Dowodzenie poprawnoąci algorytmów
Przeddowodempoprawnoąci
f(nand(m> 0)g warunek wstŚpny (asercja wejąciowa)
> 0)
begin
il ocz y n := 0
N := n
repeat
iloczyn := iloczyn + m
N := N ; 1
untilN =0
end
f iloczyn = n mg warunek ostateczny (asercja wyjąciowa)
Poprzeprowadzeniudowodu
f(nand(m> 0)g
> 0)
begin
iloczyn := 0
N := n
repeat
fNiezmiennik: (iloczyn + Nand(N> 0)g
m = n m)
iloczyn := iloczyn + m
N := N ; 1
f(iloczyn + Nand(N � 0)g
m = n m)
untilN =0
f(iloczyn + Nand(N =0)g
m = n m)
end
filoczyn = n mg
Procesobliczeniowy
Instrukcje Wyniki oblicze� Niezmiennik pŚtli
n =5 m =8
ilocz yn := 0 N := n iloczyn = 0 N =5 m =8 ( 0 + 5 8 = 40) and (N > 0)
iloczyn := iloczyn + m N := N ; 1 iloczyn = 8 N =4 m =8 ( 8 + 4 8 = 40) and (N > 0)
iloczyn := iloczyn + m N := N ; 1 iloczyn =16 N =3 m =8 (16 + 3 8 = 40) and (N> 0)
iloczyn := iloczyn + m N := N ; 1 iloczyn =24 N =2 m =8 (24 + 2 8 = 40) and (N> 0)
iloczyn := iloczyn + m N := N ; 1 iloczyn =32 N =1 m =8 (32 + 1 8 = 40) and (N> 0)
iloczyn := iloczyn + m N := N ; 1 iloczyn =40 N =0 m =8 (40 + 0 8 = 40) and (N =0)
4
Proceduraassertorazprzyk�adjejuycia
procedureassert(b: Boolean t: string)
ifnotbthenwrite(t)
assert((nand(m> 0), \not 1")
> 0)
begin
iloczyn := 0
N := n
repeat
assert((iloczyn + Nand(N> 0), \not 2")
m = n m)
iloczyn := iloczyn + m
N := N ; 1
assert((iloczyn + Nand(N � 0), \not 3")
m = n m)
untilN =0
assert((iloczyn + Nand(N = 0), \not 4")
m = n m)
end
assert(iloczyn = n m, \not 5")
1.1Aksjomatyarytmetykiliczb
Przemiennoąódodawaniaimnoenia
x + y = y + x
x y = y x
�Ącznoąódodawaniaimnoenia
(x + y) + z = x +(y + z)
(x y) z = x (y z)
RozdzielnoąódodawaniaiodejmowaniawzglŚdemmnoenia
x (y + z) = x y + x z
x (y ; z) = x y ; x z
Inne
x +0 = x
x 0 =0
x 1 = x
1.2Prawarachunkuzda�
e1, e2, e3 | zdania
1.Prawaprzemiennoąci
(e1 ^ e2) (e2 ^ e1)
(e1 _ e2) (e2 _ e1)
(e1 e2) (e2 e1)
5
2.Prawa�acznoąci
e1 ^ (e2 ^ e3) (e1 ^ e2) ^ e3
e1 _ (e2 _ e3) (e1 _ e2) _ e3
3.Prawarozdzielnoąci
e1 _ (e2 ^ e3) (e1 _ e2) ^ (e1 _ e3)
e1 ^ (e2 _ e3) (e1 ^ e2) _ (e1 ^ e3)
4.PrawaDeMorgana
:(e1 ^ e2) :e1 _:e2
:(e1 _ e2) :e1 ^:e2
5.Prawopodwójnegoprzeczenia
:(:e1) e1
6.Prawowy lĄczonegoąrodka
e1 _:e1 true
7.Prawozaprzeczenia
e1 ^:e1 false
8.Prawoimplikacji
e1 ) e2 :e1 _ e2
9.Praworównowanoąci
(e1 e2) (e1 ) e2) ^ (e2 ) e1)
10.Prawaupraszczaniaalternatywy
e1 _ e1 e1
e1 _ true true
e1 _ false e1
e1 _ (e1 ^ e2) e1
11.Prawaupraszczaniakoniunkcji
e1 ^ e1 e1
e1 ^ true e1
e1 ^ false false
e1 ^ (e1 _ e2) e1
12.Prawoidentycznoąci
e1 e1
1.3Regu�ydowodzenia(wnioskowania)
F1 . . . Fn
G
6
F1 ::: Fn oraz G sa predykatami (asercjami).
Znaczenie: Jeąli F1 . . . Fn sĄ prawdziwe (za�oenia), to mona udowodnió, e G
jest prawdziwe (teza).
Instrukcjaprzypisania
fA(x E)g x := E fAg
Instrukcjazloona
fAg P1 fBg fBg P2 fC g
fAgbeginP1 endfC g
P2
Uogólnionaregu�adowodzeniadlainstrukcjizloonej
fAi;1 g Pi fAig dla i = 1 . . . n
fA0gbeginP1 endfAng
P2 . . . Pn
Regu�ydowodzeniawanedlakadejinstrukcji
fAg P fBg B ) C
1:
fAg P fC g
A ) B fBg P fC g
2:
fAg P fC g
Jednoczesnyzapisoburegu l
A ) B fBg P fC g C ) D
fAg P fDg
Instrukcjaalternatywy
fA ^ Bg P1 fC g fA ^ : Bg P2 fC g
fAgifBthenP1elseP2endiffC g
Instrukcjawarunkowa
fA ^ Bg P fC g fA ^ : B ) C g
fAgifBthenPendiffC g
Instrukcjaiteracji\dopóki"
fA ^ Bg P fAg
fAgwhileBdoPendwhilefA ^ : Bg
Instrukcjaiteracji\powtarzaj"
fAg P fC g fC ^ : B ) Ag
fAgrepeatPuntilB fC ^ Bg
Instrukcjeiteracji\dla"
1.forxtobdoSendfor
:= a
7
o znaczeniu
ifathen
Ź b
x := x1 S
x := x2 S
:::
x := xn S
endif
gdzie x1 = a, xn = b oraz xi = succ(xi;1) dla i = 2,. . . , n.
2.forxdowntoadoSendfor
:= b
o znaczeniu
ifbthen
� a
x := x1 S
x := x2 S
:::
x := xn S
endif
gdzie x1 = b, xn = a oraz xi = pred(xi;1) dla i = 2, . . . , n.
Regu�ydowodzenia
f(a Ź x Ź b) ^ P([a :: x))g S fP([a :: x])g
fP([forxtobdoSendforfP([a :: b])g
])g := a
f(a Ź x Ź b) ^ P((x :: b])g S fP([x :: b])g
fP([forxdowntoadoSendforfP([a :: b])g
])g := b
Przyk�ad
fAlgorytm dzielenia ca�kowitego:divy.g
q = x
f(xand(y > 0)g
� 0)
begin
q := 0
r := x
whilerdo
� y
f(xand(rand(r � y)g
= q y + r) � 0)
r := r ; y
q := 1 + q
endwhile
end
f(xand(0 Ź r < y)g
= q y + r)
8
1.4Dowodzeniesko�czonoącialgorytmów
Przyk�ad1
f(nand(m> 0)g
> 0)
begin
iloczyn := 0
N := n
repeat
f0 < N = N0g
iloczyn := iloczyn + m
N := N ; 1
f0 N< N0g
untilN =0
end
Przyk�ad2
f(xand(y > 0)g
� 0)
begin
q := 0
r := x
whilerdo
� y
fr > 0g
r := r ; y fr zmniejsza siŚ pozostajĄc nieujemne bo r yg
q := 1 + q
fr 0g
endwhile
end
2 Z�oonoąó obliczeniowa algorytmów
2.1Obliczaniewartoąciwielomianu
W(x) = anxn + an;1xn;1 + ::: + a2x2 + a1x + a0
Algorytm1: Bezpoąredni (na podstawie wzoru)
begin
W := a[0]
foritondo
:= 1
p := x
forjtoido
:= 1 ; 1
p := p x fPotŚgowanie zastĄpione mnoeniami.g
endfor
9
W := a[i] p + W
endfor
end
Algorytm2: Hornera
W(x) = (anxn;1 + an;1xn;2 + . . . + a2x + a1)x + a0 =
= ((anxn;2 + an;1xn;3 + . . . + a2)x + a1)x + a0 =
. . .
= ((. . . (anx + an;1)x + an;2)x + . . . + a2)x + a1)x + a0
begin
W := a[n]
foridownto0do
:= n ; 1
W := W x + a[i]
endfor
end
2.2Mnoenieliczbca�kowitych
Zadanie:Naley wymnoyó dwie liczby ca�kowite dodatnie: n m, n Ź m
Algorytm1
begin
iloczyn := 0
N := n
repeat
iloczyn := iloczyn + m
N := N ; 1
untilN =0
end
Algorytm2
begin
iloczyn := 0
N := n
s := m
whileN>do
0
ifoddthen
(N)
iloczyn := iloczyn + s
endif
Ndiv2
:= N
s := 2 s
endwhile
end
10
2.3Znajdowaniemaksymalnego(minimalnego)elementu
Algorytm1
begin
Max := A[1]
i := 1
whileido
< n
i := i +1
ifA[i]then
> Max
Max := A[i]
endif
endwhile
end
Algorytm2(z wartownikiem)
begin
i := 1
whileido
Ź n
Max := A[i]
A[n +1] := Max fUstawienie wartownika.g
i := i +1
whileA[i]do
< Max
i := i +1
endwhile
endwhile
end
2.4Jednoczesneznajdowaniemaksymalnegoiminimalnego
elementu
Zadanie: Naley znaleąó jednoczeąnie maksymalny i minimalny element w n-elemen-
towym zbiorze S
Algorytm1: Szukanie elementu maksymalnego i minimalnego oddzielnie
begin
Max := dowolny element zbioru S
forpozosta�ych elementówdo
x ze zbioru S
ifxthen
> Max
Max := x
endif
endfor
end
11
W podobny sposób mona znaleąó element minimalny.
Algorytm2: Metoda �dziel i zwyciŚaj" (ang. divide and conquer)
Ograniczenie: Liczba elementów zbioru S winna byó potŚgĄ liczby 2, tj. n =2k dla
pewnego k.
procedureMaxMin (S)
begin
if#Sthen
=2
Niech S = fa bg fa | element maksymalny
b |element minimalny.g
return(MAX (a b) MIN(a b))
else
Podzielió S na dwa równe podzbiory S1 i S2
(max1 min1) := MaxMin (S1)
(max2 min2) := MaxMin (S2)
return(MAX (max1 max2) MIN (min1 min2))
endif
end
2.5Mnoeniedwóchn-bitowychliczbdwójkowych
functionmult(x y n: integer): integer
fx oraz y sĄ liczbami ca�kowitymi ze znakiem (x y Ź 2n).
n jest potegĄ liczby 2. WartosciĄ funkcji jest x y.g
s: integer fs przechowuje znak x y.g
m1, m2, m3: integer fWartoąci iloczynów czeąciowych.g
a, b, c, d: integer fLewe i prawe po�ówki x i y.g
begin
s :=sign(x) sign(y)
x :=abs(x)
y :=abs(y) fUczynienie x i y dodatnimi.g
ifnthen
=1
if(xand(ythen
=1) =1)
return(1)
else
return(0)
endif
else
n
a := bardziej znaczĄce bitów x
2
n
b := mniej znaczĄce bitów x
2
n
c := bardziej znaczĄce bitów y
2
n
d := mniej znaczĄce bitów y
2
n
m1 := mult (a c )
2
12
n
m2 := mult (a ; b d ; c )
2
n
m3 := mult (b d )
2
n
2
return(s (m1 2n +(m1 + m2 + m3) 2 + m3))
endif
end fmultg
2.6Sortowanieprzez�Ączenie
procedureSORT (i j: integer )
begin
ifithen
= j
return(xi)
else
m := (i + j ; 1) = 2
return(��CZENIE (SORT (i m) SORT (m +1 j)))
endif
end
3 Kopce i kolejki priorytetowe
3.1ProceduryoperujĄcenakopcu
procedureprzemieąó w górŚ (p: integer)
fElement A[p] przemieszczany jest w górŚ kopca.
Warunek wstŚpny: kopiec(1 p ; 1) i p > 0.
Warunek ostateczny: kopiec(1 p).g
vard r: integer fd | dziecko, r | rodzicg
begin
d := p
loop
fNiezmiennik: kopiec (1 p) z wyjĄtkiem byó moe
relacji pomiŚdzy A[d] i jego rodzicem. 1 Ź d Ź p.g
ifdthen
=1
break
endif
rdiv2
:= d
ifA[r]then
Ź A[d]
break
endif
zamiana(A[r] A[d])
d := r
endloop
end fprzemieąó w góre g
Proceduraprzemieąózuyciemwartownika
w górŚ
13
procedureprzemieąó w górŚ (p: integer)
vard: integer
x: ... fTyp zgodny z typem A.g
begin
x := A[p]
A[0] := x fUstawienie wartownika.g
d := p
loop
rdiv2
:= d
ifA[r]then
Ź x
break
endif
A[d] := A[r]
d := r
endloop
A[d] := x
end fprzemieąó w górŚ g
procedureprzemieąó w dó�(p: integer)
fElement A[1] przemieszczany jest w dó� kopca.
Warunek wstŚpny: kopiec (2 p) i p � 0.
Warunek ostateczny: kopiec (1 p).g
vard r: integer
begin
r := 1
loop
fNiezmiennik: kopiec (1 p) z wyjĄtkiem byó moe relacji
pomiŚdzy A[r] i jego dzieómi. 1 Ź r Ź p.g
d := 2 r
ifdthen
> p
break
endif
fd jest dzieckiem lewym rg
if(dcand(A[dthen
+1 Ź p) +1] d := d +1
endif
fd jest najmniejszym dzieckiem rg
ifA[r]then
Ź A[d]
break
endif
zamiana(A[r] A[d])
r := d
endloop
end fprzemieąó w dó�g
14
3.2Operacjenakolejkachpriorytetowych
1.UczynieniekolejkipustĄ
n := 0
2.Operacjawstaw
procedurewstaw(t)
begin
ifnthen
� n max
b�Ąd
else
n := n +1
A[n] := t
fkopiec (1 n ; 1)g
przemieąó w górŚ (n)
fkopiec (1 n)g
endif
end fwstawg
3.Operacjausu� min
procedureusu� min(t)
begin
ifnthen
< 1
b�Ąd
else
t := A[1]
A[1] := A[n]
n := n ; 1
fkopiec (2 n)g
przemieąó w dó�(n)
fkopiec(1 n)g
endif
end fusu� ming
3.3Sortowanieprzezkopcowanie
type
typrecord
rekordowy =
klucz: typ klucza fTyp skalarny.g
fPozosta�e sk�adowe rekordu.g
end
var
A:array[1oftyp rekordowy fSortowana tablica.g
:: n]
15
Zmody kowanaproceduraprzemieąówdó�
procedureprzemieąó w dó�(l p: integer )
fElement A[l] przemieszczany jest w dó� kopca.
Warunek wstŚpny: kopiec (l +1 p) i l Ź p.
Warunek ostateczny: kopiec(l p).g
vard r: integer
t: typ rekordowy
begin
r := l t := A[r]
loop
fNiezmiennik: kopiec(l p) z wyjĄtkiem byó moe relacji
pomiŚdzy r i jego dzieómi. l Ź r Ź p.g
d := 2 r
ifdthen
> p
break
endif
fd jest dzieckiem lewym r.g
if(dcand(A[d +1]:kluczthen
< p) > A[d]:klucz)
d := d +1
endif
fd jest najwiŚkszym dzieckiem r.g
ift:kluczthen
� A[d]:klucz
break
endif
A[r] := A[d]
r := d
endloop
A[r] := t
end fprzemieąó w dó�g
proceduresortowanie przez kopcowanie
fSortowana jest tablica A[1 :: n].g
vari: integer
begin
fFaza 1: Budowanie kopca.g
foridiv2downto1do
:= n
fNiezmiennik: kopiec (i +1 n).g
przemieąó w dó� (i n)
fkopiec(i n).g
endfor
fkopiec (1 n).g
fFaza 2: W�aąciwe sortowanie.g
foridownto2do
:= n
fNiezmiennik: kopiec (1 i) i posortowane(i +1 n)
16
i A[1 :: i]:klucz Ź A[i +1 :: n]:klucz.g
zamiana(A[1] A[i])
fkopiec (2 i ; 1) i posortowane(i n)
i A[1 :: i ; 1]:klucz Ź A[i :: n]:klucz.g
przemieąó w dó� (1 i ; 1)
fkopiec(1 i ; 1) i posortowane(i n)
i A[1 :: i ; 1]:klucz Ź A[i :: n]:klucz.g
endfor
fposortowane(1 n)g
end fsortowanie przez kopcowanie g
4 Wyszukiwanie
4.1Wyszukiwanieliniowe(proste)
procedurewyszukiwanie liniowe 1(x: typ klucza
varjest: Boolean
vari: 1 :: n +1)
begin
i := 1
while(icand(A[i]:kluczdo
Ź n) <> x)
i := i +1
endwhile
jest := i <> (n +1)
end
4.2Wyszukiwanieliniowezzastosowaniemwartownika
procedurewyszukiwanie liniowe 2(x: typ klucza
varjest: Boolean
vari: 1 :: n +1)
begin
A[n +1]:klucz := x fWartownik.g
i := 1
whileA[i]:kluczdo
<> x
i := i +1
endwhile
jest := i <> (n +1)
end
17
4.3Algorytmwyszukiwanialiniowegorealizowanegowta-
blicyrekordówuporzĄdkowanychrosnĄcowed�ugklu-
czy
procedurewyszukiwanie liniowe 3(x: typ klucza
varjest: Boolean
vari: 1 :: n +1)
begin
i := 1
A[n +1]:klucz := 1 f1 > xg
whileA[i]:kluczdo
< x
i := i +1
endwhile
jest := A[i]:klucz = x
end
4.4Wyszukiwaniebinarne(logarytmiczne)
procedurewyszukiwanie binarne(x: typ klucza
varjest: Boolean
varm: 1 :: n)
varlewy prawy: 0 :: n +1
begin
lewy := 1
prawy := n
jest := false
repeat
m := (lewydiv2
+ prawy)
ifA[m]:kluczthen
= x
jest := true
else
ifA[m]:kluczthen
< x
lewy := m +1
else
prawy := m ; 1
endif
endif
untiljestor(lewy > prawy)
end fwyszukiwanie binarne g
4.5Drzewaposzukiwa�binarnych
type
wierzcho�ekrecord
drzewa =
klucz: typ klucza
18
lewy prawy: ^wierzcho�ek drzewa
end
odsy�acz =^wierzcho�ek drzewa
procedureszukaj(x:vart: odsy�acz)
klucz
fSzukanie klucza x w drzewie wskazanym przez t.g
varv: odsy�acz
begin
v := t
while(vnil)cand(v^.kluczdo
6 6
= = x)
ifxthen
< v^.klucz
v := v^.lewy
else
v := v^.prawy
endif
endwhile
return(v) nilto x nie wystŚpuje w drzewieg
fjeąli v =
end fszukajg
procedurewstawvart: odsy�acz)
(x: klucz
fWstawianie klucza x do drzewa wskazanego przez t.g
varv: odsy�acz
begin
v := t
while(vnil)cand(v^.kluczdofszukania klucza xg
6 6
= = x)
ifxthen
< v^.klucz
v := v^.lewy
else
v := v^.prawy
endif
endwhile
ifvnilthenfx jest w drzewieg
6
=
return
else
Wstawienie x na koniec ącieki
endif
end fwstawg
procedureusu�vart: odsy�acz)
(x: klucz
fUsuwanie klucza x z drzewa wskazanego przez t.g
varv w: odsy�acz
begin
v := t
while(vnil)cand(v^.kluczdofszukania klucza xg
6 6
= = x)
19
ifxthen
< v^.klucz
v := v^.lewy
else
v := v^.prawy
endif
endwhile
ifvnilthenfx nie wystŚpuje w drzewieg
=
return
else
if(v^:lewynil)or(v^:prawynil)thenfbrak lewego lub prawego poddrzewag
= =
Usu� wierzcho�ek v^ z drzewa
else
w := v^:prawy
whilew^ nie jest ko�cem ąciekido
w drzewie
w := w^:lewy fszukanie minimalnego elementu w prawym poddrzewieg
endwhile
Wstaw w^:klucz do v^:klucz i usu� wierzcho�ek w^ z drzewa
endif
endif
endusu�
Analizawyszukiwaniawdrzewachbinarnych
Wyznaczymy ąredniĄ liczbŚ porówna� wymaganych dla wyszukania klucza w drze-
wie wyszukiwa� binarnych. Zak�adamy, e:
1. Dane jest n rónych kluczy o wartoąciach 1 2 ::: n.
2. Klucze pojawiajĄ siŚ w losowej kolejnoąci.
3. Pierwszy klucz (a wiŚc korze� tworzonego drzewa) ma wartoąó i z prawdopodo-
bie�stwem 1=n. Wówczas lewe poddrzewo bŚdzie zawieraó i ; 1 wierzcho�ków,
a prawe poddrzewo n ; i wierzcho�ków.
Oznaczmy:
Pi;1 | ąrednia liczba porówna� konieczna do wyszukania dowolnego klucza w
lewym poddrzewie.
Pn;i | ta sama wielkoąó dla prawego poddrzewa.
(
Pni) | ąrednia liczba porówna� wymagana dla wyszukania klucza w drzewie o
n wierzcho�kach i o korzeniu i.
Wobec tego
(
Pni) =(Pi;1 +1)pi;1 +1 pi +(Pn;i +1)pn;i
20
gdzie pi;1, pi i pn;i to prawdopodobie�stwa, e bŚdziemy szukaó odpowiednio klucza
w lewym poddrzewie, klucza i-tego, oraz klucza w prawym poddrzewie. Zak�adajĄc,
e prawdopodobie�stwa szukania poszczególnych kluczy sĄ równe, otrzymujemy:
i ; 1 1 n ; i
pi;1 = pi = pn;i = :
n n n
Wobec tego
i ; 1 1 n ; i
(
Pni) = (Pi;1 +1) +1 +(Pn;i +1) =
n n n
1
= [(Pi;1 +1)(i ; 1) +1 +(Pn;i +1)(n ; i)] :
n
(
Wielkoąó Pni) jest wana tylko dla drzewa o korzeniu i. Naley jĄ uąrednió, tj.
uwzglŚdnió przypadek, e dowolny klucz moe wystĄpió w korzeniu. Oznaczmy tŚ
uąrednionĄ wartoąó przez Pn. Wówczas
n n
X X
1 1 1
(
Pn = Pni) = [(Pi;1 +1)(i ; 1) + 1 + (Pn;i + 1)(n ; i)]
n n n
i=1 i=1
n
X
1
= [Pi;1(i ; 1) + i ; 1 +1 + Pn;i(n ; i) + n ; i]
n2
i=1
n
X
1
= 1 + [Pi;1(i ; 1) + Pn;i(n ; i)] :
n2
i=1
Mamy
X X X
Pi;1(i ; 1) = Pi+1;1(i +1 ; 1) = Pi i
1ŹiŹn 0Źi+1Źn 0ŹiŹn;1
X X X
Pn;i(n ; i) = Pn;n+i(n ; n + i) = Pi i
1ŹiŹn 1Źn;iŹn 0ŹiŹn;1
a wiŚc
n;1
X
2
Pn =1 + i Pi:
n2
i=0
MnoĄc obie strony równania przez n2 otrzymujemy
n;1
X
n2Pn = n2 +2 i Pi: (1)
i=0
To samo równanie dla n ; 1
n;2
X
(n ; 1)2Pn;1 =(n ; 1)2 +2 i Pi: (2)
i=0
21
OdejmujĄc stronami (1) i (2) otrzymujemy
n2Pn ; (n ; 1)2Pn;1 = n2 ; (n ; 1)2 +2(n ; 1)Pn;1
n2Pn = Pn;1((n ; 1)2 +2(n ; 1)) + (n2 ; n2 +2n ; 1)
n2Pn = Pn;1(n ; 1)(n +1) +(2n ; 1) (3)
Zastosujemy metodŚ czynnika sumacyjnego [11, str. 41] (ang. summation factor me-
thod), która mówi, e rozwiĄzaniem równania rekurencyjnego o postaci
anTn = bnTn;1 + cn
gdzie ai bi = 0 dla i =1 . . . n, jest
6
n
X
1
Tn = (s1b1T0 + sk ck)
ansn
k=1
gdzie sn to w�aąnie czynnik sumacyjny o wartoąci
an;1 an;2 . . . a1
sn = :
bn bn;1 . . . b2
Równanie (3) ma postaó
n2Pn =(n +1)(n ; 1)Pn;1 +(2n ; 1)
a wiŚc an = n2 bn =(n + 1)(n ; 1) cn =2n ; 1. Wyliczmy wartoąó sn:
an;1 an;2 . . . a1 (n ; 1)2 (n ; 2)2 (n ; 3)2 . . . 32 22 12
sn = =
bn bn;1 . . . b2 (n + 1)(n ; 1) n(n ; 2) (n ; 1)(n ; 3) . . . 4 2 3 1
an;1 an;2 . . . a1 =(n ; 1)2 (n ; 2)2 . . . 32 22 12 =(n ; 1)! (n ; 1)!
bn . . . b2 =(n +1)(n ; 1) n(n ; 2) (n ; 1)(n ; 3) (n ; 2)(n ; 4) . . . 5 3 4 2 3 1
Wartoąó iloczynu bn bn;2 . . . b2 jest (n +1)!=2, a wartoąó iloczynu bn;1bn;3 . . . b1
jest (n ; 1)!. Wobec tego otrzymujemy
(n ; 1)! (n ; 1)! 2
sn = = :
(n+1)!
n(n +1)
(n ; 1)!
2
Poniewa P0 =0, to
n n n
X X X
1 1 2 n +1 2k ; 1
Pn = skck = (2k ; 1) = :
2
snan k=1 n2 k(k +1) n k(k +1)
n(n+1) k=1 k=1
2k;1
Rozk�adajĄc wyraenie na u�amki proste otrzymujemy
k(k+1)
2k ; 1 3 1
= ; :
k(k +1) k +1 k
22
Wobec tego
! !
n n n n
X X X X
n +1 1 1 n +1 1 1 1
Pn = 3 ; = 3 ; 3 +3 ; =
n k +1 k n n +1 k k
k=1 k=1 k=1 k=1
!
n
X
n +1 3(1 ; n ; 1) 1 n +1
= +2 =2 Hn ; 3:
n n +1 k n
k=1
4.6WyszukiwaniemieszajĄce
4.6.1Mieszanieotwarte
consta = fOdpowiednia sta�a.g
types�owoarray[1ofchar
= :: 10]
elementrecord
listy =
r: s�owo
nast: ^element listy
end
typ listowy =^element listy
s�ownikarray[0oftyp listowy
= :: a ; 1]
FunkcjamieszajĄca
functionh(x: s�owo): 0 :: a ; 1
vari suma: integer
begin
suma := 0
forito10do
:= 1
suma := suma + ord(x[i])
endfor
return(sumamoda)
end
ProceduryoperujĄcenas�owniku
procedureZERUJvarA: s�ownik)
(
vari: integer
begin
foritoado
:= 0 ; 1
A[i]nil
:=
endfor
end
functionJESTvarA: s�ownik): Boolean
(x: s�owo
varbieĄcy: typ listowy
begin
23
bieĄcy := A[h(x)]
whilebieĄcynildo
<>
ifbieĄcythen
^:r = x
return(true ) fS�owo znaleziono.g
else
bieĄcy := bieĄcy ^:nast
end
endwhile
return(false ) fS�owa nie znaleziono.g
end
procedureWSTAWvarA: s�ownik)
(x: s�owo
varkube�ek : 0 :: a ; 1
stara g�owa: typ listowy
begin
ifnotJESTthen
(x A)
kube�ek := h(x)
stara g�owa := A[kube�ek]
new(A[kube�ek])
A[kube�ek]^:r := x
A[kube�ek]^:nast :=stara g�owa
endif
end
procedureUSU�varA: s�ownik)
(x: s�owo
varbieĄcy : typ listowy
kube�ek : 0 :: a ; 1
begin
kube�ek := h(x)
ifA[kube�ek]nilthen
<>
ifA[kube�ek]^:rthen
= x
fS�owo x jest w pierwszym elemencie.g
A[kube�ek] := A[kube�ek]^:nast fUsuniŚcie s�owa
z listy.g
else
fS�owo x, jeąli wystŚpuje, nie jest zawarte
w pierwszym elemencie.g
bieĄcy := A[kube�ek] fZmienna bieĄcy wskazuje
na poprzedni element.g
whilebieĄcynildo
^:nast <>
ifbieĄcythen
^:nast^:r = x
fUsuniŚcie s�owa z listy.g
bieĄcy ^:nast :=bieĄcy ^:nast^:nast
return fWyjącie z procedury.g
else
24
fS�owa x jeszcze nie znaleziono.g
bieĄcy : = bieĄcy ^:nast
endif
endwhile
endif
endif
end
Rozk�adkluczywtablicy
i A0
i +1 A1
i +2 A2
i +3 A3
i +4 A4
i +5 A5
i +6 A6
i +7 A7
i +8 A8
i +9 A9
... ...
j A10
j +1 A11 A20
j +2 A12 A21 A30
j +3 A13 A22 A31 A40
j +4 A14 A23 A32 A41 A50
j +5 A15 A24 A33 A42 A51 A60
j +6 A16 A25 A34 A43 A52 A61 A70
j +7 A17 A26 A35 A44 A53 A62 A71 A80
j +8 A18 A27 A36 A45 A54 A63 A72 A81 A90
j +9 A19 A28 A37 A46 A55 A64 A73 A82 A91
j +10 A29 A38 A47 A56 A65 A74 A83 A92
j +11 A39 A48 A57 A66 A75 A84 A93
j +12 A49 A58 A67 A76 A85 A94
j +13 A59 A68 A77 A86 A95
j +14 A69 A78 A87 A96
j +15 A79 A88 A97
j +16 A89 A98
j +17 A99
4.6.2MieszaniezamkniŚte
0 0
constpuste = f10 odstŚpówg
25
usuniŚte = ' ' f10 gwiazdekg
types�owopackedarray[1ofchar
= :: 10]
s�ownikarray[0ofs�owo
= :: a ; 1]
procedureZERUJvarA: s�ownik)
(
vari: integer
begin
foritoado
:= 0 ; 1
A[i] := puste
endfor
end
functionszukaj(x:varA: s�ownik): integer
s�owo
fPrzeszukiwana jest tablica A poczynajĄc od kube�ka
h0(x) do momentu, gdy x zostaje znalezione albo
zostaje znaleziony kube�ek pusty albo te ca�a tablica
zostanie przeszukana. WartoąciĄ funkcji jest numer
kube�ka, na którym szukanie zostaje zako�czone,
wskutek jednego z wymienionych wyej powodów.g
varpocz i: integer
fZmienna pocz przechowuje wartoąó h0(x)
zmienna i zawiera liczbŚ dotychczas przeszukanych
kube�ków.g
begin
pocz := h0(x)
i := 0
while(iand(A[(poczmoda]and
< a) + i) <> x)
(A[(poczmoda]do
+ i) <> puste)
i := i +1
endwhile
return((poczmoda)
+ i)
end
functionszukajvarA: s�ownik): integer
1 (x: s�owo
fDzia�anie podobne do funkcji szukaj, z tĄ rónicĄ,
e przeszukiwanie tablicy A zostaje take zako�czone
po napotkaniu kube�ka z wartoąciĄ usuniŚte .g
functionJESTvarA: s�ownik): Boolean
(x: s�owo
begin
ifA[szukaj(x then
A)] = x
return(true )
else
return(false )
endif
26
end
procedureWSTAWvarA: s�ownik)
(x: s�owo
varkube�ek: 0 :: a ; 1
begin
ifA[szukaj(x then
A)] = x
return fx jest w tablicy.g
endif
kube�ek := szukaj 1(x A)
if(A[kube�ek]or(A[kube�ek]then
= puste) = usuniŚte )
A[kube�ek] := x
else
b�Ąd('b�Ąd w procedurze WSTAW : tablica jest pe�na')
endif
end
procedureUSU�varA: s�ownik)
(x: s�owo
varkube�ek : 0 .. a ; 1
begin
kube�ek := szukaj(x A)
ifA[kube�ek]then
= x
A[kube�ek] := usuniŚte
endif
end
4.7Minimalne,doskona�efunkcjemieszajĄce
1.Niech dany bŚdzie zbiór skrótów angielskich nazw miesiŚcy W = fJUN, SEP, DEC,
AUG, JAN, FEB, JUL, APR, OCT, MAY, MAR, NOVg
Wartoąci liczbowe przyporzĄdkowane poszczególnym literom:
A B C D E F G H I J K L M N O P Q R
4 5 2 0 0 0 3 0 0 0 0 6 0 0 5 1 0 6
S T U V W X Y Z
0 6 0 6 0 0 5 0
Jeeli nazwŚ kadego miesiĄca uwaaó za ciĄg trzech liter x1x2x3, to minimalna, do-
skona�a funkcja mieszajĄca ma postaó:
hd(x1x2x3) = liczba przyporzĄdkowana literze x2 +
liczba przyporzĄdkowana literze x3
27
hd(JUN) =0
hd(SEP) =1
hd(DEC ) =2
:::
hd(NOV ) =11
2.Niech dany bŚdzie zbiór s�ów zastrzeonych jŚzyka Pascal W = fDO, END, ELSE,
CASE, DOWNTO, GOTO, TO, OTHERWISE, TYPE, WHILE, CONST, DIV, AND,
SET, OR, OF, MOD, FILE, RECORD, PACKED, NOT, THEN, PROCEDURE,
WITH, REPEAT, VAR, IN, ARRAY, IF, NIL, FOR, BEGIN, UNTIL, LABEL,
FUNCTION, PROGRAMg, card(W) = 36.
Wartoąci liczbowe przyporzĄdkowane poszczególnym literom:
A B C D E F G H I J K L M N O P Q R
11 15 1 0 0 15 3 15 13 0 0 15 15 13 0 15 0 14
S T U V W X Y Z
6 6 14 10 6 0 13 0
hd(x1x2::: xn) = d�ugoąó s�owa n +
liczba przyporzĄdkowana literze x1 +
liczba przyporzĄdkowana literze xn
Np.:
hd(DO) = 2 + 0 + 0 = 2
hd(PROGRAM) = 7 + 15 + 15 = 37
Wartoąci hd dla s�ów DO..PROGRAM sĄ z zakresu 2..37. Funkcja jest wiŚc doskona�a
ale nie minimalna.
3.Minimalna, doskona�a funkcja mieszajĄca dla s�ów zastrzeonych jŚzyka Pascal
6000
s�owa:
varwarray[1ofchar fW = fw1 w2 . . . wNgg
: :: N]
hd(w) = (h0(w) + g h1(w)modN
+ g h2(w))
N = card(W)
h0(w) = d�ugoąó(w) + ( ord (w[i]), i := 1 do d�ugoąó(w)
z krokiem 3)
h1(w) = ( ord (w[i]), i := 1 do d�ugoąó(w)mod16
z krokiem 2)
h2(w) = (( ord (w[i]), i := 2 do d�ugoąó(w)mod16) + 16
z krokiem 2)
g | funkcja zadana przy pomocy tablicy
28
PrzyjŚto kod EBCDIC:
ord ('A') = 193, ord ('B') = 194, ... , ord ('I') = 201
ord ('J') = 209, ord ('K') = 210, ... , ord ('R') = 217
ord ('S') = 226, ord ('T') = 227, ... , ord ('Z') = 233
Zbiór s�ów zastrzeonych jŚzyka Pascal 6000 (card(W) = 36):
W= f AND, ARRAY, BEGIN, CASE, CONST, DIV, DO, DOWNTO, ELSE, END,
FILE, FOR, FUNCTION, GOTO, IF, IN, LABEL, MOD, NIL, NOT, OF,
OR, PACKED, PROCEDURE, PROGRAM, RECORD, REPEAT, SEGMENTED,
SET, THEN, TO, TYPE, UNTIL, VAR, WHILE, WITH g
i g(i) i g(i) i g(i) i g(i)
0 0 9 12 18 0 27 28
1 0 10 16 19 30 28 28
2 0 11 22 20 0 29 3
3 31 12 0 21 24 30 26
4 12 13 16 22 25 31 30
5 12 14 16 23 35
6 15 15 11 24 15
7 33 16 0 25 27
8 11 17 29 26 3
hd(NOT) = 0
hd(MOD) = 35
5 Operacje na tekstach
tekst:array[1ofchar
:: n]
wzorzec:array[1ofchar
:: m]
fZwykle zachodzi 1 Ź m Ź n.g
5.1Wyszukiwanie�naiwne"
functionwyszukiwanie naiwne: integer
vari j: integer
begin
i := 1
j := 1
repeat
iftekst[i]then
= wzorzec[j]
29
i := i +1
j := j +1
else
i := i ; j +2
j := 1
endif
until(jor(i > n)
> m)
ifjthen
> m
return(i ; m)
else
return(i) fWzorca nie znaleziono (i = n + 1).g
endif
end
5.2AlgorytmKnutha,MorrisaiPratta(KMP)
functionwyszukiwanie KMP : integer
vari j: integer
begin
i := 1
j := 1
repeat
if(jcor(tekst[i]then
=0) = wzorzec[j])
i := i +1
j := j +1
else
j := nast[j]
endif
until(jor(i > n)
> m)
ifjthen
> m
return(i ; m)
else
return(i)
endif
end
procedureinicjacja nast
vari j: integer
begin
i := 1
j := 0
nast[1] := 0
repeat
if(jor(wzorzec[i]then
=0) = wzorzec[j])
i := i +1
30
j := j +1
nast[i] := j
else
j := nast[j]
endif
untili > m
end
AlgorytmwyszukiwaniaKMPzwbudowanymwzorcem10100111
i := 0
0: i := i + 1
1:iftekst[i]thengoto0 i := i + 1
<> '1'
2:iftekst[i]thengoto1 i := i + 1
<> '0'
3:iftekst[i]thengoto1 i := i + 1
<> '1'
4:iftekst[i]thengoto2 i := i + 1
<> '0'
5:iftekst[i]thengoto3 i := i + 1
<> '0'
6:iftekst[i]thengoto1 i := i + 1
<> '1'
7:iftekst[i]thengoto2 i := i + 1
<> '1'
8:iftekst[i]thengoto2 i := i + 1
<> '1'
ifithen
> n +1
return(n +1)
else
return(i ; 8)
endif
5.3Wyszukiwanieniezgodnoąciowe
typeznak = (' ', 'A', 'B', ... , 'Z')
varskok1:array[znak]ofinteger
functionwyszukiwanie niezgodnoąciowe : integer
vari, j: integer
begin
i := m
j := m
repeat
iftekst[i]then
= wzorzec[j]
i := i ; 1
j := j ; 1
else
i := i + skok1[tekst[i]]
j := m
endif
until(jor(i > n)
< 1)
31
ifjthen
< 1
return(i + 1)
else
return(n +1)
endif
end
procedureinicjacja skok1
varj: znak
k: integer
begin
forjto'Z'do
:= ' '
skok1[j] := m
endfor
forktomdo
:= 1
skok1[wzorzec[k]] := m ; k
endfor
end
Mody kacjapŚtlirepeatwalgorytmiewyszukiwanianiezgodnoąciowego
repeat
iftekst[i]then
= wzorzec[j]
i := i ; 1
j := j ; 1
else
i := i + max(skok1[tekst[i]] skok2[j])
j := m
endif
until(jor(i > n)
< 1)
5.4AlgorytmBoyeraiMoora(BM)
procedurewyszukiwanie BM
varduy : integer := n + m fOgólnie winno zachodzió:
duy � n + m.g
i, j, k: integer
begin
fm Ź ng
i := m
loop
repeat
i := i + skok1[tekst[i]]
untili > n
ifithen
Ź duy
32
return(n +1) fWzorca nie znaleziono.g
endif
fZachodzi: tekst[i ; duy] = wzorzec[m].g
i := (i ; duy) ; 1
j := m ; 1
loop
ifjthen
=0
return(i + 1) fWzorzec znaleziono.g
endif
iftekst[i]then
= wzorzec[j]
i := i ; 1
j := j ; 1
else
break
endif
endloop
k := skok1[tekst[i]]
ifkthen
= duy
i := i + skok2[j]
else
i := i +max(k skok2[j])
endif
endloop
end
6 Sortowanie
type
typrecord
rekordu =
klucz : typ klucza fW zbiorze wartoąci typu typ klucza musi byó
zde niowana relacja liniowego porzĄdku.g
end
indeks = 0 .. n
var
A:array[1oftyp rekordu fTablica podlegajĄca sortowaniu.g
.. n ]
6.1Sortowanieprzezprostewstawianie
33
klucze poczĄtkowe 44 55 12 42 94 18 06 67
?
i = 2 44 55 12 42 94 18 06 67
?
i = 3 12 44 55 42 94 18 06 67
?
i = 4 12 42 44 55 94 18 06 67
?
i = 5 12 42 44 55 94 18 06 67
?
i = 6 12 18 42 44 55 94 06 67
?
i = 7 06 12 18 42 44 55 94 67
?
i = 8 06 12 18 42 44 55 67 94
Abstrakcyjnyzapisalgorytmu
foritondo
:= 2
fNiezmiennik: A[1 .. i ; 1] jest posortowane.g
x := A[i ]
Wstaw x w odpowiednim miejscu w A[1 .. i ; 1]
endfor
procedureproste wstawianie 1
var
i, j: indeks
x : typ rekordu
begin
foritondo
:= 2
fNiezmiennik: A[1 .. i ; 1] jest posortowane.g
x := A[i ]
j := i ; 1
while(jcand(x :kluczdo
> 0) < A[j]:klucz )
A[j +1] := A[j]
j := j ; 1
endwhile
A[j +1] := x
endfor
end
procedureproste wstawianie 2
var
34
i, j: indeks
x : typ rekordu
begin
foritondo
:= 2
fNiezmiennik: A[1 .. i ; 1] jest posortowane.g
x := A[i ]
A[0] := x fUstawienie wartownika.g
j := i ; 1
whilex:kluczdo
< A[j]:klucz
A[j +1] := A[j]
j := j ; 1
endwhile
A[j +1] := x
endfor
end
Niecolepszeustawieniewartownika
.
.
.
begin
fA[0]:klucz := ;1 g
foritondo
:= 2
fNiezmiennik: . . . g
x := A[i ]
j := i ; 1
while. . .
.
.
.
procedurepo�ówkowe wstawianie
var
i, j, l, m, p: indeks
x : typ rekordu
begin
foritondo
:= 2
fNiezmiennik: A[1 .. i ; 1] jest posortowane.g
x := A[i ]
l := 1
p := i ; 1
whileldo
Ź p
mdiv2
:= (l + p)
ifx:kluczthen
< A[m]:klucz
p := m ; 1
else
l := m +1
endif
35
endwhile
forjdowntoldo
:= i ; 1
A[j +1] := A[j]
endfor
A[l ] := x
endfor
end
6.2AlgorytmShella,czylisortowaniezapomocĄmalejĄ-
cychprzyrostów
type
indeks : ;h [1] .. n
var
A:array[;hoftyp rekordu
[1] + 1 .. n ]
proceduresortowanie Shella
const
t = 4
var
m : 1 .. t
i, j, k, w : indeks
harray[1ofinteger fTablica przyrostów.g
: .. t ]
x : typ rekordu
begin
h [1] := 40 h [2] := 13 h [3] := 4 h [4] := 1
formto4do
:= 1
k := h [m ]
w := ;k fMiejsce wartownika.g
foritondo
:= k +1
x := A[i ]
ifwthen
= 0
w := ;k
endif
w := w +1
A[w ] := x fUstawienie wartownika.g
j := i ; k
whilex:kluczdo
< A[j]:klucz
A[j + k] := A[j]
j := j ; k
endwhile
A[j + k] := x
endfor
endfor
end
36
ProstawersjasortowaniaShella
proceduresortowanie Shella 1
var
i, j, przyr : integer
x : typ rekordu
begin
przyrdiv2
:= n
whileprzyrdo
> 0
foritondo
:= przyr +1
j := i ; przyr
whilejdo
> 0
ifA[j]:klucz > A[jthen
+ przyr].klucz
zamiana (A[j], A[j + przyr])
j := j ; przyr
else
j := 0 fWyjącie z pŚtli.g
endif
endwhile
endfor
przyrdiv2
:= przyr
endwhile
end
6.3Sortowanieprzezprostewybieranie
44 55 12 42 94 18 06 67
6 6
06 55 12 42 94 18 44 67
6 6
06 12 55 42 94 18 44 67
6 6
06 12 18 42 94 55 44 67
06 12 18 42 94 55 44 67
6 6
06 12 18 42 44 55 94 67
06 12 18 42 44 55 94 67
6 6
06 12 18 42 44 55 67 94
foritondo
:= 1 ; 1
fNiezmiennik: A[1 .. i ; 1] jest posortowane.g
37
Przypisz zmiennej k indeks rekordu o najmniejszym kluczu
spoąród rekordów A[i .. n ]
Wymie� A[i ] z A[k ]
endfor
procedureproste wybieranie
var
i, j, k : indeks
x : typ rekordu
begin
foritondo
:= 1 ; 1
fNiezmiennik: A[1 .. i ; 1] jest posortowane.g
k := i
x := A[i ]
forjtondo
:= i +1
ifA[j]:kluczthen
< x :klucz
k := j
x := A[j]
endif
endfor
A[k ] := A[i ]
A[i ] := x
endfor
end
proceduresortowanie przez wybieranie 2
var
i, j, k, m, M, p, q : 1 .. n
min, Max : typ rekordu
begin
i := 1
j := n
whileido
< j
min := Max := A[j] fm i MsĄ wskaąnikami,g
m := M := j fodpowiednio, elementu g
k := i fminimalnego i maksymalnego.g
repeat
ifA[k ].klucz Źthen
A[k + 1].klucz
p := k
q := k +1
else
p := k +1
q := k
38
endif
ifA[p]:kluczthen
< min .klucz
min := A[p]
m := p
endif
ifA[q]:kluczthen
> Max :klucz
Max := A[q ]
M := q
endif
k := k +2
untilk � j
ifMthen
= i
A[m ] := A[j]
else
A[m ] := A[i ]
A[M ] := A[j]
endif
A[i ] := min
A[j] := Max
i := i +1
j := j ; 1
endwhile
end
foridownto2do
:= n
fNiezmiennik: A[i +1 .. n ] jest posortowane.g
Przypisz zmiennej k indeks rekordu o najwiŚkszym kluczu
spoąród rekordów A[1 .. i ]
Wymie� A[i ] z A[k ]
endfor
6.4SortowanieprzezprostazamianŚ
39
klucze numer przejącia
poczĄtkowe k=1 k=2 k=3 k=4 k=5 k=6 k=7
-
44 06 06 06 06 06 06 06
-
55 44 12 12 12 12 12 12
-
12 55 44 18 18 18 18 18
-
42 12 55 44 42 42 42 42
-
94 42 18 55 44 44 44 44
18 94 42 42 55 55 55 55
-
06 18 94 67 67 67 67 67
67 67 67 94 94 94 94 94
proceduresortowanie bĄbelkowe
var
i , j: indeks
t : typ rekordu
begin
foritondo
:= 2
forjdowntoido
:= n
ifA[j]:klucz A[j ; 1]:klucz
t := A[j]
A[j] := A[j ; 1]
A[j ; 1] := t
endif
endfor
endfor
end
proceduresortowanie mieszane
var
j, k, l, p: indeks
t : typ rekordu
begin
l := 2
p := n
k := n fPozycja ostatniej zamiany.g
repeat
40
forjdowntoldo
:= p
ifA[j]:klucz A[j ; 1]:klucz
t := A[j]
A[j] := A[j ; 1]
A[j ; 1] := t
k := j
endif
endfor
l := k +1
forjtopdo
:= l
ifA[j]:klucz A[j ; 1]:klucz
t := A[j]
A[j] := A[j ; 1]
A[j ; 1] := t
k := j
endif
endfor
p := k ; 1
untill > p
end
6.5Sortowanieszybkie{algorytmQuicksort
procedureQuicksort (i , j: integer)
1.ifA[i ] do A[j] zawierajĄ co najmniej dwathen
róne klucze
2. Niech v bŚdzie wiŚkszym z dwóch rónych kluczy najbardziej
na lewo po�oonych w ciĄgu
3. Dokonaó permutacji A[i ], . . . , A[j] tak, e dla pewnego k 2 [i +1, j]
podciĄg A[i ], . . . , A[k ; 1] sk�ada siŚ z kluczy mniejszych od v ,
a podciĄg A[k ], . . . , A[j] | z kluczy wiŚkszych lub równych v
4. Quicksort (i , k ; 1)
5. Quicksort (k , j)
6.endif
functionznajdą klucz osiowy (i , j: integer): integer
fWartoąciĄ funkcji jest indeks wiŚkszego z dwóch najbardziej na lewo po�oonych,
rónych kluczy ciĄgu A[i ], . . . , A[j],
bĄdą 0, gdy ciĄg sk�ada siŚ z identycznych kluczy.g
var
pierwszy : typ klucza
k : integer
begin
pierwszy := A[i].klucz
41
forktojdo
:= i +1
ifA[k ]:kluczthen
> pierwszy
return(k)
else
ifA[k ]:kluczthen
< pierwszy
return(i )
endif
endif
endfor
return(0) fNie znaleziono rónych kluczy.g
end
functionpodzia� (i , j: integer klucz osiowy : typ klucza): integer
fDokonuje siŚ podzia�u ciĄgu A[i ], . . . , A[j] tak, e klucze < klucz osiowy
znajdĄ siŚ po lewej stronie, a klucze � klucz osiowy po prawej stronie ciĄgu.
WartoąciĄ funkcji jest poczĄtek prawej grupy kluczy.g
var
l, p: integer
begin
l := i
p := j
repeat
zamiana (A[l ], A[p])
whileA[l ].kluczdo
< klucz osiowy
l := l +1
endwhile
whileA[p].kluczdo
� klucz osiowy
p := p ; 1
endwhile
untill > p
return(l )
end
procedureQuicksort (i , j: integer)
fSortowana jest tablica A[i ], . . . , A[j].g
var
klucz osiowy : typ klucza
indeks klucza osiowego : integer
k : integer fPoczĄtek grupy kluczy � klucz osiowy.g
begin
indeks klucza osiowego := znajdą klucz osiowy (i , j)
ifindeks kluczathen
osiowego = 0
6
42
klucz osiowy := A[indeks klucza osiowego ].klucz
k := podzia� (i , j, klucz osiowy )
Quicksort (i , k ; 1)
Quicksort (k , j)
endif
end
procedurequicksort
proceduresort (l, p: indeks )
var
i , j: indeks
x, t : typ rekordu
begin
i := l
j := p
Wybierz losowo rekord x fnp.div2]g
x := A[(l + p)
repeat
whileA[i ]:kluczdo
< x:klucz
i := i + 1
endwhile
whilex :kluczdo
< A[j]:klucz
j := j ; 1
endwhile
ifithen
Ź j
t := A[i ]
A[i ] := A[j]
A[j] := t
i := i + 1
j := j ; 1
endif
untili > j
iflthen
< j
sort (l, j)
endif
ifithen
< p
sort (i , p)
endif
end
begin
sort (1, n )
end
43
procedureQuicksort 1 (i, j: integer)
fSortowana jest tablica A[i .. j].g
var
klucz osiowy : typ klucza
indeks klucza osiowego : integer
k : integer fPoczĄtek grupy kluczy � klucz osiowy.g
x : typ rekordu
l, m : integer
begin
ifjthen
; i +1 Ź 9
forltojdo
:= i + 1
fNiezmiennik: A[i .. l ; 1] jest posortowane.g
x := A[l ]
m := l ; 1
while(m>cand(x:kluczdo
i ; 1) < A[m]:klucz )
A[m +1] := A[m ]
m := m ; 1
endwhile
A[m +1] := x
endfor
else
indeks klucza osiowego := znajdą klucz osiowy (i, j)
ifindeks kluczathen
osiowego =0
6
klucz osiowy := A[indeks klucza osiowego ].klucz
k := podzia� (i , j, klucz osiowy)
Quicksort 1 (i , k ; 1)
Quicksort 1 (k, j)
endif
endif
end
6.6InnawersjaalgorytmuQuicksort
Dana jest nastŚpujĄca wersja algorytmu sortowania szybkiego
procedureqsort (g, d : indeks )
var
i, s : indeks
t : typ rekordu
begin
ifdthen
< g
t := A[d] ft. klucz jest kluczem osiowymg
s := d
foritogdo
:= d +1
fNiezmiennik: A[d +1 :: s] < t Ź A[s +1 :: i ; 1] g
44
ifA[i]:kluczthen
< t:klucz
s := s +1
Zamie� (A[s] A[i])
endif
endfor
Zamie� (A[d] A[s])
fNiezmiennik: A[d :: s ; 1] < A[s] Ź A[s +1 :: g] g
qsort (d s ; 1)
qsort (s +1 g)
endif
end
Wyznaczymy z�oonoąó ąredniĄ tego algorytmu. W tym celu za�oymy, e:
1. CiĄg kluczy rekordów w tablicy A jest losowĄ permutacjĄ liczb ca�kowitych 1
. . . n.
2. WystĄpienie kadej permutacji jest jednakowo prawdopodobne.
3. Pierwsze wywo�anie procedury ma postaó qsort (1 n).
4. OperacjĄ dominujĄcĄ jest porównanie kluczy rekordów.
Zauwamy, e dla d � g wykonuje siŚ 0 porówna�. Wobec tego
Tsr(0) = Tsr(1) = 0:
Porównania kluczy rekordów wykonywane sĄ g ; d razy, wobec tego przy wywo�aniu
qsort (1 n) porówna� wykonanych bŚdzie n; 1. Za�ómy, e kluczem osiowym zostaje
wartoąó i. Wówczas na lewo od klucza osiowego tra i ; 1 rekordów, a na prawo od
klucza osiowego n ; i rekordów. Wobec tego wykonamy wówczas
n ; 1 + T(i ; 1) + T(n ; i)
porówna�. Wartoąó tŚ musimy uąrednió po wszystkichwartoąciach i z przedzia�u 1::n.
Poniewa kada permutacja jest jednakowo prawdopodobna, to prawdopodobie�stwo,
1
e kluczem osiowym bŚdzie wartoąó i wynosi . Wobec tego
n
n
X
1
Tsr(n) = (n ; 1 + Tsr(i ; 1) + Tsr(n ; i)) =
n
i=1
X X
1 1
= n ; 1 + Tsr(i ; 1) + Tsr(n ; i)
n n
1ŹiŹn 1ŹiŹn
Poniewa
X X X
Tsr(i ; 1) = Tsr(i +1 ; 1) = Tsr(i)
1ŹiŹn 1Źi+1Źn 0ŹiŹn;1
X X X
Tsr(n ; i) = Tsr(n ; (n ; i)) = Tsr(i)
1ŹiŹn 1Źn;iŹn 0ŹiŹn;1
45
otrzymujemy
n;1
X
2
Tsr(n) = n ; 1 + Tsr(i): (4)
n
i=0
MnoĄc obie strony równania (4) przez n otrzymujemy
n;1
X
nTsr(n) = n2 ; n +2 Tsr(i): (5)
i=0
Równanie (5) dla n ; 1 ma postaó
n;2
X
(n ; 1)Tsr(n ; 1) = (n ; 1)2 ; (n ; 1) + 2 Tsr(i): (6)
i=0
OdejmujĄc stronami (5) i (6) otrzymujemy
n;1 n;2
X X
nTsr(n) ; (n ; 1)Tsr(n ; 1) = n2 ; n ; (n ; 1)2 + n ; 1 + 2 Tsr(i) ; 2 Tsr(n)
i=0 i=0
nTsr(n) = (n +1)Tsr(n ; 1) + 2(n ; 1): (7)
Do znalezienia rozwiĄzania (6) zastosujemy metodŚ czynnika sumacyjnego [11, str.
41]. Z (7) wynika, i an = n bn = n +1 cn =2(n ; 1). Wobec tego
an;1an;2 a1 (n ; 1)(n ; 2) 3 2 1 2
sn = = =
bnbn;1 b2 (n +1)n(n ; 1)(n ; 2) 3 (n +1)n
Poniewa Tsr(0) = 0, otrzymujemy
n
X
1
Tsr(n) = skck =
sncn k=1
n
X
1 2
= 2(k ; 1) =
2
n k(k +1)
n(n+1) k=1
n
X
k ; 1
= 2(n +1) =
k(k +1)
k=1
!
n n
X X
1 1
= 2(n +1) ; +2 =
k k +1
k=1 k=1
!
n n
X X
1 1 2
= 2(n +1) ; +2 + ; 2 =
k
k=1 k=1
!k n +1
n
X
1 2n
= 2(n +1) ; =
k n +1
k=1
= 2(n +1)Hn ; 4n:
2
46
6.7Czasywykonaniaprogramówsortowania
Tabela I.
CiĄgi odwrot.
CiĄgi
Metoda sortowania
CiĄgi uporzĄdk.
uporzĄdk.
losowe
Wstawianie proste 12 23 366 1444 704 2836
Wstawianie po�ówkowe 56 125 373 1327 662 2490
Wybieranie proste 489 1907 509 1956 695 2675
Sortowanie bĄbelkowe 540 2165 1026 4054 1492 5931
Sortowanie bĄbelkowe ze znacznikiem 5 8 1104 4270 1645 6542
Sortowanie mieszane 5 9 961 3642 1619 6520
Sortowanie metodĄ Shella 58 116 127 349 157 492
Sortowanie stogowe 116 253 110 241 104 226
Sortowanie szybkie 31 69 60 146 37 79
Sortowanie przez �Ączenie 99 234 102 242 99 232
Tabela II. (klucze wraz ze zwiĄzanymi z nimi danymi)
CiĄgi odwrot.
CiĄgi
Metoda sortowania
CiĄgi uporzĄdk.
uporzĄdk.
losowe
Wstawianie proste 12 46 366 1129 704 2150
Wstawianie po�ówkowe 46 76 373 1105 662 2070
Wybieranie proste 489 547 509 607 695 1430
Sortowanie bĄbelkowe 540 610 1026 3212 1492 5599
Sortowanie bĄbelkowe ze znacznikiem 5 5 1104 3237 1645 5762
Sortowanie mieszane 5 5 961 3071 1619 5757
Sortowanie metodĄ Shella 58 186 127 373 157 435
Sortowanie stogowe 116 264 110 246 104 227
Sortowanie szybkie 31 55 60 137 37 75
Sortowanie przez �Ączenie 99 196 102 195 99 187
7 Selekcja
A:array[1oftyp klucza
.. n]
functionselekcja (i, j, k : integer): typ klucza
fZnajdowany jest k -ty najmniejszy klucz w tablicy A[i .. j].g
var
klucz osiowy : typ klucza
47
indeks klucza osiowego : integer
m : integer fPoczĄtek grupy kluczy � klucz osiowy.g
begin
indeks klucza osiowego := znajdą klucz osiowy (i, j)
ifindeks kluczathen
osiowego =0
6
klucz osiowy := A[indeks klucza osiowego ]
m := podzia� (i, j, klucz osiowy )
ifkthen
Ź m ; i
return(selekcja (i , m ; 1, k ))
else
return(selekcja (m, j, k ; m + i))
endif
else
return(A[i ])
endif
end
8 Algorytmy sortowania, w których korzysta siŚ
ze szczególnych w�asnoąci kluczy
typetyprecord
rekordu =
klucz : 1 .. n
. . .
end
varA,array[1oftyp rekordu
B : .. n]
Algorytm1
foritondo
:= 1
B [A[i ].klucz ] := A[i ]
endfor
Algorytm2
foritondo
:= 1
whileA[i]:kluczdo
6
= i
zamiana (A[i ], A[A[i ].klucz ])
endwhile
endfor
48
8.1Sortowaniekube�kowe
type
typ klucza = 1 .. m flub znakowy ogólnie typ dyskretny,
w zbiorze wartoąci którego istnieje
relacja porzĄdkug
typrecord
rekordu =
klucz : typ klucza
. . .
end
elementrecord
listy =
r : typ rekordu
nast : ^element listy
end
typ listowy =^element listy
var
A:array[1oftyp rekordu fTablica rekordów do sortowania.g
.. n ]
Barray[typoftyp listowy fTablica kube�ków.
: klucza ]
W kube�ku rekordy sa po�Ączone w listŚ.g
Carray[typoftyp listowy fTablica odsy�aczy
: klucza ]
do ko�ców list w kube�kach.g
proceduresortowanie kube�kowe
var
i : integer
p, v : typ klucza
begin
forvtowysokido
:= niski klucz klucz
Bnil
[v ] :=
Cnil
[v ] :=
endfor
foritondo
:= 1
WSTAW (A[i], B [A[i].klucz ], C [A[i].klucz ])
endfor
p := niski klucz
whileBnildo
[p] =
p := succ (p)
endwhile
ifp =then
6 wysoki klucz
forvtowysokido
:= succ (p) klucz
ifB[v]nilthen
6
=
PO��CZ (C [p], B [v], C [v])
endif
49
endfor
endif
end
procedureWSTAW (xvarl, m : typ listowy )
: typ rekordu
var
temp: typ listowy
begin
temp := l
new (l )
l^.r := x
l^.nast := temp
iftempnilthen
=
m := l
endif
end fWSTAW g
procedurePO��CZvarlC1 : typ listowy lB2, lC2 : typ listowy )
(
fParametry sĄ odsy�aczami do poczĄtków i ko�ców �Ączonych list.g
begin
lC1 ^.nast := lB2
lC1 := lC2
end fPO��CZg
8.2Sortowaniepozycyjne
proceduresortowanie pozycyjne
fSortowana jest lista A o n rekordach, kt orych klucze
sk�adajĄ siŚ z p ol f1, f2, . . . , fk
o typach odpowiednio t1, t2, . . . , tk.g
begin
foridownto1do
:= k
forkadej warto scido
v typu ti
Bi[v]nil fOpr onianie kube�k ow.g
:=
endfor
forkadego rekordudo
r na li scie A
przesu r z A na koniec listy kube�ka Bi[v],
n
gdzie v jest warto sciĄ pola fi klucza rekordu r
endfor
forkadej warto sci v typu ti, od najmniejszej do
najwiŚkszejdo
do�Ącz Bi[v] na koniec listy A
50
endfor
endfor
end
Praktycznaimplementacjaalgorytmusortowaniapozycyjnego
SortowanielistyrekordówAwed�ugdat:
type
typrecord
rekordu =
dzie� : 1 .. 31
mies : (sty, ..., gru)
rok : 1900 .. 1999
fInne pola rekordu.g
end
elementrecord
listy =
r : typ rekordu
nast : ^element listy
end
typ listowy =^element listy
var
A: typ listowy
proceduresortowanie wg dat
fSortowana jest lista A o n rekordach, których klucze sĄ datami.g
var
p3, v3 : 1900 .. 1999
p2, v2 : (sty , . . . , gru )
p1 , v1 : 1 .. 31
B3,array[1900oftyp listowy
C3 : .. 1999]
B2,array[(sty,oftyp listowy
C2 : . . . , gru)]
B1array[1oftyp listowy
, C1 : .. 31]
begin
fSortowanie rekordów wed�ug dni.g
forv1to31do
:= 1
B1nil
[v1 ] :=
C1nil
[v1 ] :=
endfor
whileAnildo
6
=
fWstawienie rekordu A^.r na koniec listy kube�ka
okreąlonego przez klucz rekordu.g
DO��CZ (A^.r, B1 [A^.r.dzie� ], C1 [A^.r.dzie� ])
A := A^.nast
endwhile
51
p1 := 1
whileB1nildo
[p1 ] =
p1 := succ (p1 )
endwhile
ifp1then
6
= 31
forv1to31do
:= succ (p1 )
fPrzy�Ączenie list wszystkich kube�ków do ko�ca listy
wskazanej przez B1 [p1 ].g
ifB1[v1nilthen
] =
6
PO��CZ (C1 [p1 ], B1 [v1 ], C1 [v1 ])
endif
endfor
endif
A := B1 [p1 ]
fDokonaó podobnie sortowania kube�kowego listy A wed�ug pól A^.r.mies
oraz A^.r. rok.g
end
procedureDO��CZ (xvarlB , lC : typ listowy )
: typ rekordu
var
temp: typ listowy
begin
iflBnilthen
=
new (lC )
lC^.r := x
lC^.nastnil
:=
lB := lC
else
temp := lC
new (lC )
lC^.r := x
lC^.nastnil
:=
temp^.nast := lC
endif
end fDO��CZg
9 Sortowanie plików sekwencyjnych
9.1�Ączenieproste
proceduresortowanie przez �Ączenie proste
vari j k l: indeks
52
góra : Boolean
p: integer fd�ugoąó �Ączonych podciĄgówg
begin
góra := true
p := 1
repeat
ifgórathenfInicjowanie indeksów.g
i := 1 j := n k := n + 1 l := 2 n
else
i := n + 1 j := 2 n k := 1 l := n
endif
\�Ącz p{tki z i{ciĄgu oraz j{ciĄgu do
k{ciĄgu oraz l{ciĄgu."
góranotgóra
:=
p := 2 p
untilp = n
end
LĄczeniep-tekmonazapisaónastŚpujĄco:
h := 1
m := n fm okreąla liczbŚ rekordów do po�Ączenia.g
repeat
q := p
r := p
m := m ; 2 p
Po�Ącz q rekordów z i{ciĄgu oraz r rekordów z j{ciĄgu
k jest indeksem ciĄgu wynikowego z przyrostem h
h := ; h
Zamie� k z l
untilm = 0
while(qand(rdo
<> 0) <> 0)
fWybieranie rekordu z i{ciĄgu lub j{ciĄgu.g
ifA[i]:kluczthen
< A[j]:klucz
Przemieąó rekord z i do k, zwiŚksz i oraz
uaktualnij k
q := q ; 1
else
Przemieąó rekord z j do k, zmniejsz j oraz
uaktualnij k
r := r ; 1
endif
endwhile
53
Skopiuj koniec i{ciĄgu
Skopiuj koniec j{ciĄgu
CiĄginstrukcji:
q := p
r := p
m := m ; 2 p
przyjmujepostaó:
fq wyznacza d�ugoąó i{ciĄgu, zaą r | j{ciĄgu.g
ifmthen
� p
q := p
else
q := m
endif
m := m ; q
ifmthen
� p
r := p
else
r := m
endif
m := m ; r
Pe�nyalgorytmsortowania
proceduresortowanie przez �Ączenie proste
vari j k l t: indeks
h m p q r: integer
góra : Boolean
begin
góra := true
p := 1
repeat
ifgórathenfInicjowanie indeksów.g
i := 1 j := n k := n + 1 l := 2 n
else
i := n + 1 j := 2 n k := 1 l := n
endif
h := 1
m := n
repeat
f�Ączenie p-tki z i{ciĄgu oraz j{ciĄgu do k{ciĄgu.g
54
ifmthen
� p
q := p
else
q := m
endif
m := m ; q
ifmthen
� p
r := p
else
r := m
endif
m := m ; r
while(qand(rdof�Ączenie ciĄgów.g
<> 0) <> 0)
ifA[i]:kluczthen
< A[j]:klucz
A[k] := A[i]
i := i + 1
k := k + h
q := q ; 1
else
A[k] := A[j]
j := j ; 1
k := k + h
r := r ; 1
endif
endwhile
fKopiowanie ko�ca i{ciĄgu.g
whileqdo
<> 0
A[k] := A[i]
i := i + 1
k := k + h
q := q ; 1
endwhile
fKopiowanie ko�ca j{ciĄgu.g
whilerdo
<> 0
A[k] := A[j]
j := j ; 1
k := k + h
r := r ; 1
endwhile
h := ; h
fZamiana k z l.g
t := k
k := l
l := t
untilm = 0 fKoniec fazy (przebiegu).g
55
góranotgóra
:=
p := 2 p
untilp � n fKoniec sortowania.g
ifnotgórathen
foritondo
:= 1
A[i] := A[i + n]
endfor
endif
end
9.2�Ączenienaturalne
c: 22 36 06 79 26 45 75 13 31 62 27 76 33 16 62 47
Przebieg 1. a: 22 36 ' 26 45 75 ' 27 76 ' 16 62 '
b: 06 79 ' 13 31 62 ' 33 ' 47
= c: 06 22 36 79 ' 13 26 31 45 62 75 ' 27 33 76 ' 16 47 62
Przebieg 2. a: 06 22 36 79 ' 27 33 76 '
b: 13 26 31 45 62 75 ' 16 47 62
= c: 06 13 22 26 31 36 45 62 75 79 ' 16 27 33 47 62 76
Przebieg 3. a: 06 13 22 26 31 36 45 62 75 79 '
b: 16 27 33 47 62 76
= c: 06 13 16 22 26 27 31 33 36 45 47 62 62 75 76 79
typetaąma leoftyp rekordu
=
varc: taąma fPlik do sortowania.g
proceduresortowanie przez �Ączenie naturalne
varl: integer fOznacza liczbŚ serii w pliku c.g
a b: taąma
begin
repeat
rewrite (a) fUczynienie plikówg
rewrite (b) fa i b pustymi.g
reset (c) fPrzygotowanie pliku c do czytania.g
rozdzielanie
reset (a)
reset (b)
rewrite (c)
l := 0
�Ączenie
untill = 1
end
procedurerozdzielanie fZ c na a i b.g
begin
repeat
56
kopiuj seriŚ (c a)
ifnoteof(c)then
kopiuj seriŚ (c b)
endif
untileof(c)
end
procedure�Ączenie fZ a i b na c.g
begin
repeat
�Ącz serie
l := l + 1
untileof(b)
ifnoteof(a)then
kopiuj seriŚ (a c)
l := l + 1
endif
end
procedurekopiujvarx y: taąma)
seriŚ (
fKopiowanie jednej serii z pliku x do y.
ks jest globalnĄ zmiennĄ boolowskĄ okreąlajĄcĄ,
czy osiĄgniŚto koniec serii.g
begin
repeat
kopiuj(x y)
untilks
end
procedurekopiuj(varx y: taąma)
fKopiowanie jednego elementu z pliku x do y.g
varbuf: typ rekordu
begin
read (x buf)
write (y buf)
ifeof(x)then
ks := true
else
ks := buf. klucz > x^:klucz
endif
end
procedure�Ącz serie
f�Ączenie po jednej serii z a i b oraz
przes�anie serii wynikowej do c.g
57
begin
repeat
ifa^:kluczthen
< b^:klucz
kopiuj(a c)
ifksthen
kopiuj seriŚ (b c)
endif
else
kopiuj(b c)
ifksthen
kopiuj seriŚ (a c)
endif
endif
untilks
end
Przyk�ad1
c: 03 02 05 11 07 13 19 17 23 31 29 37 43
a: 03 ' 07 13 19 ' 29 37 43 '
b: 02 05 11 ' 17 23 31
c: 02 03 05 07 11 13 17 19 23 29 31 37 43
Przyk�ad2
c: 13 57 17 19 11 59 23 29 07 61
a: 13 57 ' 11 59 ' 07 61 '
b: 17 19 ' 23 29 '
c: 13 17 19 23 29 57 11 59
Poprawionaprocedura�Ączenia
procedure�Ączenie fZ a i b na c.g
begin
repeat
�Ącz serie
l := l + 1
untileof(a)oreof(b)
whilenoteof(a)do
kopiuj seriŚ (a c)
l := l + 1
endwhile
whilenoteof(b)do
58
kopiuj seriŚ (b c)
l := l + 1
endwhile
end
10 Algorytmy zach�anne (ar�oczne)
10.1Kolorowaniezach�anne
procedurekolorowanie zach�anne (G : graf
varnowy kolor : zbiór)
fProcedura do�Ącza do zbioru nowy kolor te
wierzcho�ki grafu, którym mona przyporzĄdkowaó
ten sam kolor.g
varjest : Boolean
v w: integer
begin
nowy kolor :=
v := pierwszy niepokolorowany wierzcho�ek w G
whilevnulldo
<>
jest := false
w := pierwszy wierzcho�ek w zbiorze nowy kolor
whilewnullcandnotjestdo
<>
ifistnieje krawŚdą pomiŚdzythen
v i w w G
jest := true
endif
w := nastŚpny wierzcho�ek w zbiorze nowy kolor
endwhile
ifjestthen
= false
Oznacz v jako pokolorowany
Do�Ącz v do zbioru nowy kolor
endif
v := nastŚpny niepokolorowany wierzcho�ek w G
endwhile
end
10.2Problemkomiwojaera
procedurekomiwojaervardroga : ciĄg krawŚdzi)
(G : graf
fWyznacza siŚ drogŚ o minimalnymkoszcie w gra e G.g
vari: integer
min : real
59
begin
min := 1
forito(ndo
:= 1 ; 1)!
p := i{ta permutacja wierzcho�ków v1 v2 ::: vn;1
fNiech d(p) jest drogĄ w gra e G odpowiadajĄcĄ
permutacji p jego wierzcho�ków.g
ifkoszt(d(p))then
< min
droga := d(p)
min := koszt(d(p))
endif
endfor
end
10.3Znajdowanienajta�szychdróg|AlgorytmDijkstry
procedureDijkstra
fObliczane sĄ koszty najta�szych dróg z wierzcho�ka 1
do kadego innego wierzcho�ka w gra e zorientowanym.g
begin
S := f1g
foritondo
:= 2
D[i] := C [1 i] fInicjalizacja tablicy D.g
endfor
foritondo
:= 1 ; 1
Wybraó wierzcho�ek w ze zbioru V ; S taki,
e D[w] jest minimalne
Do�Ączyó w do S
forkadego wierzcho�ka v w zbiorzedo
V ; S
D[v] := min(D[v] D[w] + C [w v])
endfor
endfor
end
11 Algorytmy grafowe
11.1Przeszukiwaniegrafuwg�Ąb
procedurewg(v)
fPrzeszukiwanie w g�Ąb z wierzcholka v.g
begin
znacznik[v] := odwiedzony
foru 2 listydo
incydencji[v]
60
ifznacznik[u] = nieodwiedzonythen
fKrawŚdą (v w) wstawiana jest do drzewa
rozpinajĄcego.g
wg(u)
endif
endfor
end
begin
fPrzeszukiwanie grafu G = (V E) w g�Ąb.g
forvdo
2 V
znacznik[v] := nieodwiedzony
endfor
forvdo
2 V
ifznacznik[v] = nieodwiedzonythen
wg(v)
endif
endfor
end
Zastosowaniemetodyprzeszukiwaniawg�Ąb|wyszukiwaniesk�adowych
spójnoąci
varcompnumarray[1ofinteger fcompnum[v] jest
: :: jVj]
numerem sk�adowej spójnoąci, do której naley wierzcho�ek vg
forvdo
2 V
compnum[v] := 0
endfor
c := 0
forvdo
2 V
ifcompnum[v]then
= 0
c := c + 1
COMP(v)
endif
endfor
procedureCOMP(x: wierzcho�ek)
begin
compnum(x) := c
forwdo
2 adj[x]
ifcompnum[w]then
= 0
COMP(w)
61
endif
endfor
end
Nierekursywnawersjaproceduryprzeszukiwaniawg�Ąb
procedurewg1 (v)
fNa poczĄtku procesu przeszukiwania P[t] = wskaąnik
do pierwszego rekordu listy adj[t] dla kadego u.g
begin
stos ( stos ( v odwiedą v nowy[v] := false
whilestosdo
<>
t := top(stos) fodczytaj szczytowy
element stosug
while(P[t]nil)cand(notnowy[P[t]^:wierzch])do
<>
P[t] := P[t]^:nast fznajdą \nowy" wierzcho�ek
na liącie adj[t]g
endwhile
ifP[t]nilthenfnowy wierzcho�ek znalezionyg
<>
t := P[t]^:wierzch stos ( t
odwiedą t nowy[t] := false
elsefwierzcho�ek t zosta� wykorzystanyg
t ( stos fzdejmij szczytowy wierzcho�ek ze stosug
endif
endwhile
end
11.2Przeszukiwaniegrafuwszerz
procedurewsz(v)
fPrzeszukiwanie wszerz z wierzcho�ka v.g
varK : kolejka wierzcho�ków (typu FIFO)
begin
znacznik[v] := odwiedzony
wstaw do kolejki (v K)
whilenotpustado
kolejka (K)
x := pierwszy(K)
usu� pierwszy z kolejki (K)
fory 2 listydo
incydencji[x]
ifznacznik[y] =then
nieodwiedzony
znacznik[y] := odwiedzony
wstaw do kolejki (y K)
fKrawedą (x y) wstawiana jest do drzewa
62
rozpinajĄcego.g
endif
endfor
endwhile
end
begin
fPrzeszukiwanie grafu G = (V E) wszerz.g
forvdo
2 V
znacznik[v] := nieodwiedzony
endfor
forvdo
2 V
ifznacznik[v] = nieodwiedzonythen
wsz(v)
endif
endfor
end
AlternatywnawersjaBFS
kolejka ( kolejka ( v nowy[v] := false
whilekolejkado
<>
p ( kolejka fpobierz p z kolejki (tj. z usuniŚciem)g
forndo
2 adj[p]
ifnowy[n]then
kolejka ( u
nowy[u] := false
endif
endfor
endwhile
Zastosowanieprzeszukiwaniagrafuwszerz|znajdowanienajkrótszejdro-
gipomiŚdzywierzcho�kamivixwgra e
varpredarray[1of1 :: jVj fwierzcho�ki poprzedzajĄce
: :: jVj]
na najkrótszej drodzeg
odl:array[1ofinteger fd�ugoąó najkrótszej drogig
:: j Vj]
begin
forvdo
2 V
nowy[v] := true
endfor
kolejka := pusta kolejka kolejka ( v0 nowy[v0] := false
pred [v0] := ;1
odl[v0] := 0
63
whilenowy[x]do
p ( kolejka
forudo
2 adj[p]
ifnowy[u]then
kolejka ( u nowy[u] := false
pred[u] := p odl[u] := odl[p] + 1
endif
endfor
endwhile
end
11.3Wyznaczaniecyklipodstawowych(fundamentalnych)
begin
forxdo
2 V
num[x] := 0 finicjacja numeracji wierzcho�kówg
endfor
i := 0 flicznik do numeracji kolejnych wierzcho�ków
odwiedzanych w g�Ąbg
j := 0 flicznik cykli fundamentalnychg
k := 0 fwskaąnik stosug
forxdo
2 V
ifnum[x]then
= 0
k := k + 1
stos[k] := x
ZNAJD� CYKLE (x 0)
k := k ; 1
endif
endfor
end
procedureZNAJD� CYKLE (v u) fv | wierzcho�ek aktualny,
u | wierzcho�ek poprzednig
begin
i := i + 1 fOdwiedzone wierzcho�ki zostajĄ ponumerowaneg
num[v] := i frosnĄco zgodnie z licznikiem i.g
forwdo
2 adj[v]
ifnum[w]then
= 0
k := k + 1
stos[k] := w
ZNAJD� CYKLE (w v)
k := k ; 1
else
64
ifnum[w]candwthen
< num[v] <> u
j := j + 1 flicznik cyklig
\ sj jest cyklem (w stos[k] stos[k ; 1] ::: stos[t])
gdzie stos[t] = w stos[k] = v"
endif
endif
endfor
end
11.4MinimalnedrzewarozpinajĄce
AlgorytmKruskala
T { zbiór krawŚdzi minimalnego drzewa rozpinajĄcego VS { rodzina (zbiór) roz�Ącz-
nych zbiorów wierzcho�ków
begin
T :=
VS :=
Skonstruuj kolejkŚ priorytetowĄ Q zawierajĄcĄ
wszystkie krawŚdzie ze zbioru E
forvdo
2 V
Dodaj fvg do VS
endfor
whilejdo
VS j > 1
Wybierz z kolejki Q krawŚdą (v w) o najmniejszym koszcie
Usu� (v w) z Q
ifv i w naleĄ do rónych zbiorów W1 i W2
naleĄcychthen
do VS
ZastĄp W1 i W2 w VS przez W1 [ W2
Dodaj (v w) do T
endif
endwhile
end
AlgorytmnajbliszegosĄsiedztwa(PrimaiDijkstry)
(n = j Vj )
varnear:array[1of1 :: n fdla kadego wierzcho�ka v,
:: n]
który nie znalaz� siŚ jeszcze w drzewie, element
near[v] zapamiŚtuje najbliszy mu wierzcho�ek drzewag
dist:array[1of1 :: n fdist[v] zapamiŚtuje
:: n]
odleg�oąó v od najbliszego mu wierzcho�ka drzewag
65
W = [wij] fmacierz kosztówg
begin
Wybierz arbitralnie v0
forvdo
2 V
dist[v] := W[v v0] fkoszt krawŚdzi (v0 v)g
near[v] := v0
endfor
Vt := fv0g fwierzcho�ki drzewag
Et := fkrawŚdzie drzewag
Wt := 0 fsumaryczny koszt drzewag
whileVtdo
<> V
v := wierzcho�ek z V ; Vt o najmniejszej
wartoąci dist[v]
Vt := Vt [ fvg
Et := Et [ f(v near(v))g
Wt := Wt + dist[v]
forxdo
2 V ; Vt
ifdist[x]then
> W[v x]
dist[x] := W[v x]
near[x] := v
endif
endfor
endwhile
end
11.5WyznaczaniecykliEulera
begin
STOS ( foprónianieg
CE ( fstosówg
v := dowolny wierzcho�ek grafu
STOS ( v
whileSTOSdo
6
=
v := szczyt(STOS ) fv jest szczytowym elementem stosug
ifinc[v]thenflista incydencji v jest niepustag
6
=
u := pierwszy wierzcho�ek listy inc [v]
STOS ( u
fusuwanie krawŚdzi (u v) z grafug
inc [v] := inc [v] ;fug
inc [u] := inc [u] ;fvg
elseflista incydencji v jest pustag
v ( STOS fprzeniesienie szczytowego wierzcho�ka stosu STOS g
CE ( v fdo stosu CE g
66
endif
endwhile
end
12 Wyszukiwanie wyczerpujace. Algorytm z po-
wrotami
procedurewyszukiwanie z powrotami
begin
Wyznacz S1 fna podstawie A1 i ogranicze�g
k := 1
whilekdo
> 0
whileSkdo
<>
ak := element z Sk
Sk := Sk { fakg
if(a1, a2, ... , ak) jestthen
rozwiĄzaniem
write((a1, a2, ... , ak))
endif
k := k + 1
Wyznacz Sk fna podstawie Ak i ogranicze
ng
endwhile
k := k ; 1 fpowrótg
endwhile
end
13 Przeszukiwanie heurystyczne
13.1Przeszukiwaniewszerz
procedureBFS
begin
Q ( fzerowanie kolejkig
Q ( s0 fstan poczĄtkowy do kolejkig
loop
ifkolejkathen
Q pusta
return(poraka)
endif
s ( Q fpobranie stanu z kolejkig
Wygenerowanie nastŚpników sj stanu s na podstawie
operatora dla stanu s
Wstawienie stanów sj do kolejki
67
ifdowolny stan sj jest stanemthen
ko�cowym
return(sukces)
endif
endloop
endBFS
13.2Przeszukiwaniewg�Ąbziteracyjnympog�Śbianiem
procedureDFS (s, g�Śbokoąó, odciŚcie )
fPrzeszukiwanie w g�Ąb z odciŚciem. s | bieĄcy stan,
g�Śbokoąó | bieĄca g�Śbokoąó.g
begin
forsj 2do
nastŚpniki (s)
ifsj jest stanemthen
ko�cowym
return(sukces) fznaleziono rozwiĄzanieg
endif
ifg�Śbokoąóthen
+1 < odciŚcie
DFS (sj, g�Śbokoąó +1, odciŚcie )
endif
endfor
endDFS
forodciŚcietoodciŚciedo
:= 1 max
DFS (s0, 0, odciŚcie )
endfor
return(poraka)
13.3Przeszukiwaniewed�ugstrategii�najlepszywierzcho-
�ekjakopierwszy"
^
OTWARTE ( (s f(s)) fwierzcho�ek poczĄtkowy na listŚg
whilelista OTWARTEdo
nie pusta
^
(*) Pobranie z listy OTWARTE wierzcho�ka i o minimalnej wartoąci f(i)
^
ZAMKNIąTE ( (i f(i))
ifi jest wierzcho�kiemthen
ko�cowym
return(sukces)
endif
Rozszerzenie wierzcho�ka i przez wyznaczenie wszystkich jego
^
nastŚpników j i obliczenie f(j)
ifj nie wystŚpuje na listach OTWARTE ithen
ZAMKNIąTE
^
OPEN ( (j f(j))
68
Ustanowienie wskaąnika od wierzcho�ka j do jego poprzednika i
(aby umoliwió odtworzenie rozwiĄzania ko�cowego)
else
(**)ifj wystŚpuje na liącie OTWARTE lubthen
ZAMKNIąTE
^ ^
ifnowe f(j)then
< stare f(j)
^ ^
stare f(j) := nowe f(j)
Ustanowienie wskaąnika od j do nowego poprzednika i
endif
ifwierzcho�ek j jest na liąciethen
ZAMKNIąTE
^
PrzesuniŚcie (j f(j)) na listŚ OTWARTE
endif
endif
endif
endwhile
return(poraka)
14 Generowanie permutacji
procedurePERMUTACJE (n, m)
begin
(p1 p2 . . . pm) := (1 2 . . . m)
Wyprowadą (p1 p2 . . . pm) na wyjącie
u1, u2, . . . , un := (1 1 . . . 1)
foritonPmdo
:= 1 ; 1
NASTąPNA PERMUTACJA(n, m, p1, p2, . . . , pm)
endfor
end
procedureNASTąPNA PERMUTACJA(n, m, p1, p2, . . . , pm)
begin
foritomdo
:= 1
u[pi] := 0 fzaznaczenie, które elementy sĄ w permutacjig
endfor
fZnalezienie najwiŚkszego, nieuywanego elementu w zbiorze f1, 2, . . . , ng.g
f := n
whileu[f]do
<> 1
f := f ; 1
endwhile
fZnalezienie najbardziej na prawo po�oonego,
mody kowalnego elementu permutacji.g
k := m +1
i := 0 fIndeks elementu permutacji, który zostanie zmody kowany.g
69
whileido
= 0
k := k ; 1
u[pk] := 1
ifpkthenfuaktualnij pkg
< f
Znajdą najmniejsze j takie, e pk < j n oraz u[j] =1
i := k
pi := j fzmody kowanie permutacjig
u[pi] := 0
else
f := pk fnajwiŚkszy, nieuywany element jest ustawiany na wartoąó pk g
endif
endwhile
fUaktualnienie elementów leĄcych na prawo od pig
forktomdo
:= 1 ; i
ifu[s] jest k-tĄ pozycjĄ w tablicythen
u równĄ 1
pi+k := s
endif
endfor
fPrzywróó 1-ki w tablicy u.g
forktoido
:= 1
u[pk] := 1
endfor
Wyprowadą (p1 p2 . . . pm) na wyjącie
end
procedureRZ�D (n, m, p1, p2, . . . , pm, d)
begin
foritomdo
:= 1
d := 0
forjtoido
:= 1 ; 1
ifpithen
< pj
d := d +1
endif
endfor
ri := pi ; i + d
endfor
d := rm +1
waga := 1
forkdownto1do
:= m ; 1
waga := (n ; k) waga
d := d + rk waga
endfor
endRZ�D
70
procedureRZ�D ODWR (n, m, d, p1, p2, . . . , pm)
begin
d := d ; 1
foritondo
:= 1
si := 0
endfor
a := 1 fobliczenie (n ; m + 1)(n ; m + 2) . . . (n ; 1)g
foridownto1do
:= m ; 1
a := a (n ; m + i)
endfor
fwyznaczanie pi, i = 1, 2, . . . , mg
foritomdo
:= 1
r := b d=ac
d := d ; r a
ifnthen
> i
a := a=(n ; i)
endif
k := 0 j := 0
fszukanie (r + 1)-ego elementu tablicy s równego 0g
whilekdo
< r +1
j := j +1
ifsjthenfelement = j nie wystĄpi� jeszcze w permutacjig
=0
k := k +1
endif
endwhile
pi := j felement permutacji = jg
sj := 1 fw permutacji wystĄpi� element = jg
endfor
endRZ�D ODWR
15 Literatura
[1] Wirth, N., Algorytmy + Struktury Danych = Programy, WNT, Warszawa, 1980.
[2] Banachowski, L., Kreczmar, A., Elementy Analizy Algorytmów, WNT, Warszawa,
1982.
[3] Alagió, S., Arbib, M.A., Projektowanie Programów Poprawnych i Dobrze Zbudo-
wanych, WNT, Warszawa, 1982.
[4] Aho, A.V., Ullman, J.D., Projektowanie i Analiza Algorytmów Komputerowych,
PWN, Warszawa, 1983.
[5] Reingold, E.M., Nievergelt, J., Deo, N., Algorytmy Kombinatoryczne, PWN, War-
szawa, 1985.
71
[6] Bentley, J., Pere�ki Oprogramowania, WNT, Warszawa, 1986.
[7] Lipski, W., Kombinatoryka dla Programistów, WNT, Warszawa, 1987.
[8] Banachowski, L., Kreczmar, A., Rytter, W., Analiza Algorytmów i Struktur Da-
nych, WNT, Warszawa, 1987.
[9] Harel, D., Rzecz o Istocie Informatyki. Algorytmika, WNT, Warszawa, 1992.
[10] Banachowski, L., Diks, K., Rytter, W., Algorytmy i Struktury Danych, WNT,
Warszawa, 1996.
[11] Graham, R.L., Knuth, D.E., Patashnik, O., Matematyka Konkretna, PWN, War-
szawa, 1996.
[12] Cormen, T.H., Leiserson, C.E., Rivest, R.L., Wprowadzenie do Algorytmów,
WNT, Warszawa, 1997.
16 Pytania
1. Metody empirycznego testowania programów. Dlaczego testowanie empiryczne
jest niedoskona�e? Co sĄdzi Dijkstra o testowaniu empirycznym?
2. Co to sĄ: aksjomat, asercja, regu�a dowodzenia? Podaó aksjomaty liczb ca�-
kowitych i rzeczywistych. Co to sĄ: zdanie, predykat. Podaó kilka aksjomatów
rachunku zda�.
3. Podaó i omówió na wybranych przyk�adach regu�y dowodzenia dla instrukcji
przypisania oraz instrukcji z�oonej.
4. Podaó i omówió na wybranych przyk�adach regu�y dowodzenia dla instrukcji
alternatywy oraz instrukcji warunkowej.
5. Podaó i omówió na wybranym przyk�adzie regu�Ś dowodzenia dla instrukcji
iteracji \dopóki". Co to jest niezmiennik pŚtli?
6. Podaó i omówió na wybranym przyk�adzie regu�Ś dowodzenia dla instrukcji
itracji \powtarzaj". Co to jest niezmiennik pŚtli?
7. Podaó i omówió na wybranym przyk�adzie regu�y dowodzenia dla instrukcji
iteracji \dla". Co to jest niezmiennik pŚtli?
8. CzŚąciowa oraz pe�na poprawnoąó algorytmu. Jak dowodzi siŚ dochodzenie ob-
licze� algorytmu do punktu ko�cowego (w�asnoąó stopu)?
9. Podaó de nicje pojŚó: rozmiar danych, dzia�anie dominujĄce, z�oonoąó cza-
sowa algorytmu, z�oonoąó pamiŚciowa algorytmu. Wymienió typowe funkcje
okreąlajĄce z�oonoąci obliczniowe algorytmów. Po co wyznacza siŚ z�oonoąó
obliczeniowĄ algorytmu?
72
10. Co rozumiesz przez: z�oonoąó pesymistycznĄ algorytmu, z�oonoąó ąredniĄ al-
gorytmu? Udowodnij, e W(n) = amnm + . . . + a1n + a0 = O(nm) dla n > 0.
11. Jak brzmi de nicja O-notacji? Podaó i udowodnió trzy dowolne w�asnoąci rzŚdu
funkcji.
12. Okreąlió z�oonoąó obliczeniowĄ algorytmu wyznaczania wartoąci wielomianu
dla przypadków: (a) korzystajĄc bezpoąrednio ze wzoru, (b) korzystajĄc ze sche-
matu Hornera.
13. Podaó dwa algorytmy znajdowania maksymalnego elementu w tablicy. Wyzna-
czyó i porównaó ich z�oonoąci.
14. Podaó algorytmy znajdowania elementu maksymalnego i minimalnego w zada-
nym zbiorze dla przypadków: (a) kolejne znajdowanie elementu maksymalnego a
nastŚpnie minimalngo, (b) dzielenie zadania na podzadania. Okreąlió z�oonoąó
obliczniowĄ algorytmów.
15. Podaó algorytm mnoenia dwóch n -bitowych liczb dwójkowych z zastosowa-
niem metody dzielenia zadania na podzadania. Okreąlió z�oonoąó obliczeniowĄ
algorytmu.
16. Wyprowadzió rozwiĄzania równa� rekurencyjnych: T(n) = b dla n = 1 oraz
n
T(n) = aT( ) + bn dla n > 1. Podaó interpretacjŚ rozwiĄza�.
c
17. Omówió zasadŚ równowaenia rozmiarów podzada� na przyk�adzie zadania sor-
towania, rozwaajĄc algorytm sortowania przez wybór prosty oraz rekursywny
algorytm sortowania przez �Ączenie. Okreąlió z�oonoąci obliczeniowe algoryt-
mów.
18. Sformu�owaó zadanie sortowania. Podaó ogólnĄ klasy kacjŚ algorytmów sorto-
wania oraz klasy kacjŚ algorytmów sortowania wewnŚtrznego. Podaó de nicje
pojŚó: drzewo decyzyjne sortowania, g�Śbokoąó i wysokoąó wierzcho�ka w drze-
wie, wysokoąó drzewa. Okreąlió kres dolny z�oonoąci obliczeniowej algorytmów
sortowania wewnŚtrznego z pomocĄ porówna�.
19. Podaó w�asnoąci kopca oraz omówió sposób jego implementacji. Podaó i wyjaąnió
dzia�anie procedur: przemieąó w górŚ i przemieąó w dó� .
20. Podaó abstrakcyjny opis kolejki priorytetowej. Podaó i wyjaąnió dzia�anie pro-
cedur wstaw i usu� min dla kolejki implementowanej z pomocĄ kopca. Jakie sĄ
inne moliwe implementacje kolejki? Porównaó je ze sobĄ pod kĄtem z�oonoąci
obliczeniowej.
21. Podaó algorytm budowania kopca (faza 1. sortowania przez kopcowanie). Wy-
znaczyó jego z�oonoąó pesymistycznĄ.
22. Podaó algorytm sortowania przez kopcowanie oraz okreąlió jego pesymistycznĄ
z�oonoąó obliczeniowĄ.
73
23. Podaó algorytm sortowania liczb naturalnych z zakresu [1::n] o z�oonoąci linio-
wej. Czy przy sortowaniu niezbŚdna jest dodatkowa tablica?
24. Podaó algorytm sortowania kube�kowego. Jaka jest jego z�oonoąó? Co to jest
porzĄdek leksykogra czny? Podaó algorytm sortowania pozycyjnego. Jaka jest
jego z�oonoąó?
25. Podaó algorytm sortowania przez proste wstawianie (z wartownikiem). Okreąlió
jego z�oonoąó pesymistycznĄ oraz ąredniĄ.
26. Podaó algorytm sortowania metodĄ Shella. Jak naley dobieraó przyrosty? Jaka
jest z�oonoąó algorytmu?
27. Podaó algorytm sortowania przez proste wybieranie. Okreąlió jego z�oonoąó
pesymistycznĄ oraz ąredniĄ. Jakie sĄ moliwoąci ulepszania algorytmu?
28. Podaó algorytm sortowania bĄbelkowego. Jaka jest jego z�ozonoąó? Jakie sĄ
moliwoąci ulepszania algorytmu?
29. Podaó algorytm sortowania szybkiego (Quicksort). Co warunkuje jego szybkie
dzia�anie.
30. Wyznaczyó z�oonoąó pesymistycznĄ i ąredniĄ algorytmu sortowania szybkiego.
31. Omówió dwie metody wyznaczania k-tego co do wielkoąci klucza w tablicy: a)
mody kacja algorytmu sortowania przez kopcowanie b) algorytm rekursywny.
Jakie sĄ z�oonoąci tych metod?
32. Podaó algorytm sortowania plików sekwencyjnych przez �Ączenie proste (na
\ąrednim" poziomie abstrakcji). Jaka jest z�oonoąó algorytmu?
33. Podaó algorytm sortowania plików sekwencyjnych przez �Ączenie naturalne (na
\ąrednim" poziomie abstrakcji). Jaka jest z�oonoąó algorytmu?
34. Omówió idee sortowania przez wielokierunkowe �Ączenie wywaone oraz sorto-
wania polifazowego. Jakie sĄ z�oonoąci tych metod?
35. Sformu�owaó zadanie wyszukiwania. Podaó algorytmy wyszukiwania liniowego
(bez wartownika i z wartownikiem) oraz okreąlió ich z�oonoąci ąrednie i pesy-
mistyczne.
36. Podaó algorytm wyszukiwania binarnego. Okreąlió jego z�oonoąó pesymistycznĄ.
37. Porównaó algorytmy wyszukiwania liniowego i binarnego pod kĄtem pesymi-
stycznej z�oonoąci obliczeniowej oraz narzutu zwiĄzanego z koniecznoąciĄ reor-
ganizacji pliku rekordów.
38. Podaó w�asnoąci drzewa poszukiwa� binarnych oraz procedury szukaj i wstaw
operujĄce na drzewie. Jaki jest koszt wyszukiwania klucza w drzewie?
74
39. Podaó i omówió procedurŚ usuwania klucza z drzewa poszukiwa� binarnych.
40. Dla metody mieszania otwartego podaó procedury wyszukiwania, wstawiania i
usuwania elementu z tablicy mieszajĄcej. Jaka jest ąrednia z�oonoąó oblicze-
niowa kadej z procedur?
41. Dla metody mieszania zamkniŚtego podaó procedury wyszukiwania, wstawiania
i usuwania elementu z tablicy mieszajĄcej.
42. Podaó wymagania jakie powinna spe�niaó podstawowa funkcja mieszajĄca. Wy-
mienió i omówió czŚsto stosowane podstawowe funkcje mieszajĄce.
43. Omówió metody przezwyciŚania kolzji w metodzie mieszania zamkniŚtego. Ja-
kie sĄ wady i zalety wyszukiwania i wstawiania mieszajĄcego?
44. Okreąlió z�oonoąó obliczeniowĄ mieszania zamkniŚtego. Jak naley dobraó ob-
jŚtoąó tablicy mieszajĄcej?
45. Na czym polega restrukturyzacja tablic mieszajĄcych? Co to jest minimalna
doskona�a funkcja mieszajĄca? Podaó przyk�ad takiej funkcji.
46. Podaó algorytm �naiwny" wyszukiwania wzorca w tekącie. Jaka jest jego z�oo-
noąó?
47. Podaó algorytm wyszukiwania Knutha, Morrisa i Pratta. Jak wyznacza siŚ war-
toąci elementów tablicy nast ?
48. Dla wybranego przyk�adu podaó algorytm wyszukiwania Knutha, Morrisa i
Pratta z \wbudowanym" wzorcem. Co to jest kompilator procedur wyszuki-
wania?
49. Podaó algorytm wyszukiwania niezgodnoąciowego. Omówió jego dzia�anie na
przyk�adzie. Jak wyznacza siŚ wartoąci elementów tablicy skok 1 .
50. Podaó algorytm wyszukiwania Boyera i Moora. Czy jest on bardziej efektywny
od algorytmu wyszukiwania niezgodnoąciowego.
51. Omówió ideŚ algorytmu zach�annego na przyk�adzie projektowania sekwencji
zmiany ąwiate� dla skrzyowania. Na czym polega problem kolorowania grafu?
52. Sformu�owaó problem komiwojaera. Podaó: a) algorytm typu \sprawdą wszyst-
kie moliwoąci" b) algorytm heurystyczny oparty na postŚpowaniu zach�annym.
Jakie sĄ z�oonoąci algorytmów?
53. Sformu�owaó i porównaó problemy znalezienia marszruty komiwojaera , cyklu
Eulera i cyklu Hamiltona.
54. Podaó algorytm Dijkstry znajdowania najkrótszych dróg z ustalonego wierz-
cho�ka. Objaąnió jego dzia�anie na wybranym przyk�adzie.
75
55. Omówió przeszukiwanie grafu wg�Ąb. Podaó zastosowanie tego przeszukiwania
dla problemu znajdowania sk�adowych spójnoąci.
56. Omówió przeszukiwanie grafu wszerz. Podaó zastosowanie tego przeszukiwania
dla problemu znajdowania najkrótszej ącieki w gra e (d�ugoąó ącieki liczona
liczbĄ krawŚdzi).
57. Podaó i omówió algorytm znajdowania cykli fundamentalnych w gra e. Jaka
jest jego z�oonoąó?
58. Podaó i omówió algorytm Kruskala znajdowania minimalnego drzewa rozpina-
jĄcego. Jaka jest jego z�oonoąó?
59. Podaó i omówió algorytm Prima i Dijkstry znajdowania minimalnego drzewa
rozpinajĄcego. Jaka jest jego z�oonoąó?
60. Podaó i omówió algorytm wyznaczania cykli Eulera. Jaka jest jego z�oonoąó?
n
61. Podaó i omówió algorytm wyznaczania Pm permutacji. Jaka jest jego z�oo-
noąó?
17 PodziŚkowania
W przygotowaniu pierwszej wersji niniejszych materia�ów uczestniczy�y Beata Bart-
kowiak i Beata Gawlik, zaą drugĄ wersjŚ przygotowali Magdalena Biedzka i Zdzis�aw
Koch. KolejnĄ wersjŚ przygotowa�y Zo a Imiela oraz Boena Bartoszek. Wersje na-
stŚpne przygotowali Mohamed Daghestani oraz Ilona Bargie�, Wojciech Mikanik i
Joanna Sim cak. Wszystkim tym osobom sk�adam serdeczne podziŚkowania.
76