Algorytmy Ksiazka

[ Pobierz całość w formacie PDF ]
SPIS TREĝCI
3.1.1 Przeszukiwanie w drzewach BST ..................................................................... 62
3.1.2 Inne operacje na drzewach BST....................................................................... 63
3.2 Kopce ....................................................................................................66
3.2.1 Definicja i wáasnoĞü kopca .............................................................................. 66
3.2.2 Algorytmy na kopcach...................................................................................... 68
3.2.3 Kolejki priorytetowe......................................................................................... 72
3.3 Przeszukiwanie w drzewach .................................................................76
3.3.1 Typy zadaĔ przeszukiwania.............................................................................. 76
3.3.2 Strategie wszerz i w gáąb.................................................................................. 79
3.3.3 Przeszukiwanie sterowane i niesterowane ....................................................... 81
3.3.4 Przeszukiwanie peáne ....................................................................................... 82
3.3.5 Generowanie dróg rozwiązaĔ.......................................................................... 83
WSTĉP............. ........................................................................................3
1 A
LGORYTMY I MODELE OBLICZEē
................................................... 7
1.1 PojĊcia podstawowe................................................................................ 7
1.2 ZáoĪonoĞü algorytmu .............................................................................. 9
1.3 Model obliczeniowy RAM ................................................................... 14
1.3.1 Opis maszyny RAM...........................................................................................14
1.3.2 Uproszczony jĊzyk programowania..................................................................18
1.3.3 ZáoĪonoĞü pesymistyczna i oczekiwana ............................................................21
1.3.4 ZáoĪonoĞü programów w jĊzyku RAM ..............................................................23
1.3.5 ZáoĪonoĞü programów w pseudokodzie ............................................................26
4 S
ORTOWANIE
.............................................................................87
4.1 Wprowadzenie ......................................................................................87
4.2 Algorytmy oparte na porównaniach......................................................89
4.2.1 Drzewa decyzyjne............................................................................................. 89
4.2.2 Dolne ograniczenie na czas sortowania .......................................................... 91
4.2.3 Algorytmy asymptotycznie optymalne .............................................................. 92
4.3 Sortowanie w czasie liniowym..............................................................97
4.3.1 Sortowanie przez zliczanie ............................................................................... 98
4.3.2 Sortowanie kubeákowe.................................................................................... 100
2 S
TRUKTURY DYNAMICZNE I REKURSJA
.................................... 31
2.1 Wprowadzenie ...................................................................................... 31
2.2 Listy ...................................................................................................... 31
2.2.1 Definicje i reprezentacja pamiĊciowa ..............................................................31
2.2.2 Podstawowe operacje na listach ......................................................................33
2.3 Stosy i kolejki ....................................................................................... 36
2.3.1 Stosy .................................................................................................................36
2.3.2 Kolejki ..............................................................................................................38
2.4 Obliczanie wartoĞci wyraĪeĔ z wykorzystaniem stosu ......................... 39
2.5 Grafy ..................................................................................................... 44
2.5.1 Grafy skierowane i nieskierowane ...................................................................44
2.5.2 Sposoby reprezentowania grafów ....................................................................46
2.6 Drzewa .................................................................................................. 48
2.6.1 Definicje ...........................................................................................................48
2.6.2 Drzewa binarne ................................................................................................50
2.6.3 UĪycie struktur wskaĨnikowych ........................................................................54
2.7
5
IBLIOGRAFIA
..........................................................................104
DODATEK
Z
ADANIA NA EGZAMINY I KOLOKWIA
...................................................105
Rekursja ................................................................................................ 56
3
ASTOSOWANIE DRZEW I ALGORYTMY PRZESZUKIWANIA
...... 61
3.1
Drzewa przeszukiwaĔ binarnych .......................................................... 61
- 5 -
- 6 -
1 Algorytmy i modele obliczeĔ
okreĞlonoĞü
, tzn. wymóg, aby kaĪda operacja w algorytmie byáa sformuáowana
w sposób zapewniający jej jednoznaczną interpretacjĊ. Zestawienie
wymienionych cech algorytmów pokazuje rys.1.2, a bardziej peáne ich
omówienie zawiera praca [7].
1.1 PojĊcia podstawowe
posiada
wejĞcie
posiada
wyjĞcie
PojĊciem
algorytm
okreĞla siĊ najczĊĞciej pewien przepis (sposób
postĊpowania), który ma prowadziü do rozwiązania okreĞlonego zadania.
Przyjmuje siĊ, Īe przepis ten jest na tyle precyzyjny, Īe posáugiwanie siĊ nim
polega wyáącznie na automatycznym wykonywaniu zawartych tam poleceĔ.
Zakáada siĊ dalej, Īe polecenia wystĊpujące w algorytmie są
wykonywalne
, tzn.
dostĊpne, a pisząc algorytm wystarczy siĊ nimi jedynie posáuĪyü. Zestaw
dostĊpnych poleceĔ zaleĪy od przyjĊtego modelu, w którym mają byü
realizowane obliczenia, okreĞlanego jako
model obliczeĔ
. Na rys.1.1 pokazano
znane z literatury przykáady modeli obliczeĔ [1].
Algorytm
jest wykonalny
jest okreĞlony
dochodzi do
punktu koĔcowego
Rys.1.2 Cechy algorytmów.
Do podstawowych pytaĔ pojawiających siĊ w trakcie teoretycznych badaĔ nad
obliczeniami naleĪą m.in.:
MODELE OBLICZEē
x Jak dla okreĞlonego zadania znaleĨü efektywny algorytm?
x JeĞli algorytm juĪ znaleziono, to jak porównaü go z innymi, które rozwiązują
podobne zadania?
x Jak udowodniü poprawnoĞü algorytmu?
x W jakim sensie moĪna wykazaü, Īe pewne algorytmy są „najlepszymi z
moĪliwych”?
Maszyna ze swobodnym
dostĊpem do pamiĊci
(model RAM)
Maszyna ze swobodnym
dostĊpem do pamiĊci
i pamiĊtanym programem
(model RASP)
Maszyna Turinga
(elementarny model
obliczeĔ)
Rys.1.1 Przykáady modeli obliczeĔ.
SpoĞród dziedzin zajmujących siĊ algorytmami istotne znaczenie
ma analiza
algorytmów
, której zasadnicze kierunki dotyczą
poprawnoĞci
i
záoĪonoĞci
obliczeniowej
(rys.1.3).
WykonalnoĞü moĪna rozpatrywaü takĪe w odniesieniu do pewnego zbioru
obiektów i dostĊpnych w nim pierwotnych operacji. Zbiór taki nazywa siĊ
dziedziną algorytmiczną
[4].
ANALIZA ALGORYTMÓW
Obok wykonalnoĞci, jako istotne dla algorytmów rozwaĪa siĊ takĪe pojĊcia
wejĞcia
i
wyjĞcia
. WejĞcie oznacza zwykle pewne dane pobierane przez
algorytm w celu ich przetworzenia, podczas gdy wyjĞcie odnosi siĊ do wyniku
dziaáania algorytmu. WaĪną wáaĞciwoĞcią wymaganą od algorytmu jest jego
skoĔczonoĞü
, co oznacza, Īe algorytm powinien zakoĔczyü swoje dziaáanie po
wykonaniu skoĔczonej liczby operacji. Dla algorytmów obowiązuje takĪe
PoprawnoĞü
algorytmów
ZáoĪonoĞü
obliczeniowa
Rys.1.3 Kierunki badaĔ analizy algorytmów.
- 7 -
- 8 -
PoprawnoĞü dotyczy przede wszystkim pojĊü i metod związanych z
dowodzeniem poprawnoĞci algorytmów, takich jak: wáasnoĞü stopu, czĊĞciowa
poprawnoĞü, metoda niezmienników itp. Zagadnienia te są na tyle waĪne, aby
poĞwiĊciü im odrĊbny wykáad i nie bĊdą tutaj omawiane.
czytamy "duĪe o od n kwadrat". Ogólnie biorąc, pewna nieujemna funkcja
jest
Og
, jeĞli istnieje taka staáa, Īe
n
c
0
d d
fn
cg n
Dziedziną, której poĞwiĊcimy znacznie wiĊcej miejsca bĊdzie natomiast
záoĪonoĞü obliczeniowa algorytmów i związane z nią pojĊcia, do których naleĪą
m.in.: záoĪonoĞü czasowa, pamiĊciowa, Ğrednia i pesymistyczna. Ten obszar
analizy algorytmów koncentruje siĊ na okreĞlaniu zasobów (czas obliczeĔ i
pamiĊü), jakie są potrzebne do wykonania badanego algorytmu.
dla wszystkich oprócz pewnego, byü moĪe pustego, zbioru nieujemnych
wartoĞci
n
.
n
Symbol jest zaliczany do tzw.
notacji asymptotycznych
, uĪywanych
do opisu asymptotycznego czasu dziaáania algorytmów. Na rysunku 1.4a
podano interpretacjĊ graficzną notacji . Wynika z niej, Īe przy pomocy
zapisu podaje siĊ górne ograniczenie funkcji z dokáadnoĞcią
do staáego wspóáczynnika. Bardziej precyzyjnie zapis ten oznacza, Īe istnieją
dodatnie staáe i takie, Īe na prawo od
n
wartoĞü
Ogn
O
1.2 ZáoĪonoĞü algorytmu
fn Og
n
Oceny záoĪonoĞci algorytmu moĪna dokonaü wedáug róĪnych kryteriów. CzĊsto
stosowana jest metoda polegająca na badaniu, jak zwiĊksza siĊ czas obliczeĔ
lub wielkoĞü pamiĊci potrzebnej do wykonania algorytmu, w miarĊ wzrostu
rozmiaru danych wejĞciowych. Rozmiar tych danych nazywaü bĊdziemy
rozmiarem zadania
, albo
rozmiarem wejĞcia
, przyjmując, Īe jest to konkretna
liczba charakteryzująca objĊtoĞü danych wejĞciowych. Jako przykáady
rozmiarów wejĞcia moĪna wymieniü:
x liczbĊ elementów tablicy wejĞciowej w algorytmach sortowania,
x liczbĊ krawĊdzi grafu w algorytmach operujących na grafach,
x wymiary macierzy w zadaniu mnoĪenia macierzy.
c
n
0
0
fn
jest zawsze nie
wiĊksza od
cg n
.
Ponadto na rys.1.4b i 1.4c przedstawiono w podobny sposób notacje
4
i ,
bĊdące takĪe przykáadami notacji asymptotycznych.
:
cg n
fn
cgn
2
fn
fn
cg n
cgn
1
Czas potrzebny na wykonanie algorytmu jako funkcja rozmiaru zadania jest
nazywany
záoĪonoĞcią czasową
tego algorytmu. Charakter tej záoĪonoĞci przy
dąĪeniu do wartoĞci granicznej wraz ze wzrostem rozmiaru zadania jest
okreĞlany jako
asymptotyczna záoĪonoĞü czasowa
. W analogiczny sposób
moĪna zdefiniowaü
pojĊcia záoĪonoĞci pamiĊciowej
i
asymptotycznej záoĪonoĞci
pamiĊciowej
.
n
0
n
n
0
n
n
0
n
fn
Ogn
fn
:
gn
fn
4
gn
a)
b)
Rys.1.4 Graficzna interpretacja notacji asymptotycznych.
c)
W odróĪnieniu od notacji , która ogranicza funkcjĊ z góry, notacja
(rys.1.4b) ogranicza funkcjĊ z doáu. Zapis
O
:
oznacza, Īe istnieją
dodatnie staáe i takie, Īe na prawo od
n
wartoĞü
fn
:
gn
Wprowadzenie asymptotycznej záoĪonoĞci algorytmu jest szczególnie waĪne,
gdyĪ przy jej pomocy moĪna okreĞliü rozmiar zadaĔ, które mogą byü
rozwiązane za pomocą tego algorytmu. JeĞli np. algorytm przetwarza wejĞcie o
rozmiarze , w czasie
cn
, gdzie jest pewną staáą, wówczas mówimy, Īe
záoĪonoĞü czasowa tego algorytmu jest rzĊdu
fn
jest zawsze
wiĊksza od . Przedstawiona na rys.1.4c notacja pozwala szacowaü
funkcjĊ z doáu i z góry. Pisząc zatem
c
n
0
0
cg n
n
2
c
fn
4
gn
wskazujemy, Īe istnieją
n
2
, co zapisujemy jako
On
2
i
- 9 -
- 10 -
fn
dodatnie staáe,
c
1
c
2
i
n
takie, Īe na prawo od
n
wartoĞü
0
0
fn
jest zawsze
Przykáad 1.2
[1]
wiĊksza od
cgn
1
i nie wiĊksza od
cgn
2
.
W dwóch pierwszych kolumnach tab.1.1 zamieszczono piĊü przykáadowych
algorytmów wraz z ich záoĪonoĞcią czasową, rozumianą tutaj jako liczba
jednostek czasu potrzebnych do obróbki (przetworzenia) wejĞcia o rozmiarze
n
.
JeĞli za jednostkĊ czasu przyjąü jedną milisekundĊ, to algorytm moĪe w
ciągu sekundy przetworzyü wejĞcie o rozmiarze 1000, natomiast algorytm
wejĞcie o rozmiarze zaledwie 9.
Przykáad 1.1
Przyjmując
A
1
fn
n
2
1
2
3
n
oraz
gn
n
2
A
5
wykaĪemy, Īe
fn
4
.
g
n
Tab.1.1 ZáoĪonoĞci czasowe i maksymalne rozmiary zadaĔ dla wybranych
algorytmów.
Aby tego dokonaü, naleĪy wyznaczyü dodatnie staáe,
c
i takie, Īe
1
c
n
0
2
ZáoĪonoĞü
1
2
Algorytm
Maksymalny rozmiar zadania
cn
2
d 3
n
d
c n
2
dla
n
t
n
0
.
(1.1)
czasowa
1 sekunda
1 minuta
1 godzina
1
2
A
1
n
1000
610
4
3,610
6
Dzieląc nierównoĞü (1.1) przez otrzymujemy zaleĪnoĞü
n
2
A
2
nn
lg
140
4893
2,010
5
1
dd
3
A
3
n
2
31
244
1897
c
c
A
4
1
n
2
n
3
10
39
153
A
5
2
n
1
2
3
9
15
21
z której wynika, Īe nierównoĞü jest speániona dla kaĪdego
d
n
c
n
t 1
,
2
W kolejnych kolumnach tab.1.1 zamieszczono maksymalne rozmiary zadaĔ
które mogą byü przetworzone przez rozwaĪane algorytmy, jeĞli za caákowity
czas obliczeĔ przyjąü odpowiednio 1 sekundĊ, 1 minutĊ i 1 godzinĊ.
jeĞli przyjąü
c
2
, a nierównoĞü
c
1
2
1
3
d
jest speániona dla kaĪdego
1
2
n
n
t 7
, jeĞli przyjąü
c
1
1
14
. Stąd dla
c
1
1
14
,
c
2
i
n
0
7
zachodzi
ZaáóĪmy dalej, Īe w pewnym okresie szybkoĞü komputerów wzrasta 10-krotnie.
W tab.1.2 pokazano, jak wzrosną rozmiary zadaĔ, które mogą byü przetworzone
przez algorytmy y , w wyniku takiego wzrostu szybkoĞci komputerów.
nierównoĞü (1.1), co oznacza, Īe
fn
4
.
gn
A
1
A
5
Mogáoby siĊ wydawaü, Īe imponujący wzrost szybkoĞci wspóáczesnych
komputerów powoduje, Īe prace nad poszukiwaniem efektywnych algorytmów
nie są uzasadnione. Celem kolejnych dwóch przykáadów bĊdzie wykazanie, Īe
tak nie jest, gdyĪ efektywne algorytmy mogą w sposób nie mniej istotny jak
rozwój sprzĊtu wpáywaü na wydajnoĞü komputerów (mierzoną np. rozmiarem
zadaĔ, które mogą byü rozwiązywane).
Tab.1.2 Wpáyw zwiĊkszenia szybkoĞci komputera na maksymalny rozmiar zadania.
Algorytm
ZáoĪonoĞü
Maksymalny rozmiar zadania
czasowa
przed zwiĊkszeniem
po zwiĊkszeniu
A
1
n
s
1
10
s
A
2
nn
s
2
~
10
dla duĪych
2
s
s
2
A
3
n
2
s
3
3,16
s
3
A
4
n
3
s
4
215
4
A
5
2
n
s
5
s
5
33
,
- 11 -
- 12 -
1
2
lg
,
s
ZauwaĪmy, Īe dla algorytmu 10-krotne zwiĊkszenie prĊdkoĞci komputera
pozwala zwiĊkszyü rozmiar zadania, które moĪe byü rozwiązane zaledwie o 3,
podczas gdy w przypadku algorytmu
A
5
W dotychczasowych rozwaĪaniach zwracaliĞmy uwagĊ przede wszystkim na to,
jakiego rzĊdu jest wzrost záoĪonoĞci. NaleĪy jednak pamiĊtaü o tym, Īe w
niektórych przypadkach istotna moĪe okazaü siĊ takĪe wartoĞü wspóáczynnika
staáego. W szczególnoĞci, przy mniejszym rozmiarze zadaĔ, algorytmy o duĪym
stopniu wzrastania záoĪonoĞci lecz mniejszym wspóáczynniku staáym mogą
okazaü siĊ bardziej efektywne od algorytmów o mniejszym stopniu wzrastania
záoĪonoĞci, ale duĪym wspóáczynniku staáym. Dla ilustracji przyjmijmy liczbĊ
sortowanych elementów w ostatnim przykáadzie jako
n
=10. W przypadku tak
maáego rozmiaru zadania algorytm uĪyty przez superkomputer wymaga jedynie
200 instrukcji, podczas gdy algorytm uĪyty przez mikrokomputer ok. 1500.
Oznacza to, Īe ze wzglĊdu na wiĊkszy wspóáczynnik staáy w wyraĪeniu na
záoĪonoĞü algorytmu korzyĞci z zastosowania dla mikrokomputera bardziej
wydajnego algorytmu uwidocznią siĊ dopiero dla zadaĔ o wiĊkszym rozmiarze.
A
3
rozmiar ten siĊ potraja.
Porównajmy teraz efekty zwiĊkszenia szybkoĞci komputerów z efektami
zastosowania bardziej efektywnego algorytmu. W tym celu powróümy do
tab.1.1 i przyjmijmy za podstawĊ porównania jedną minutĊ. Widaü przy tym, Īe
zamiana algorytmu na algorytm pozwala rozwiązaü zadanie 6-krotnie
wiĊksze. Natomiast zamiana na pozwala rozwiązaü zadanie o rozmiarze
125-krotnie wiĊkszym. Wyniki te oznaczają, Īe polepszenie osiągów
spowodowane zastosowaniem bardziej efektywnego algorytmu moĪe wyraĨnie
przewyĪszyü zyski wynikające ze zwiĊkszenia szybkoĞci komputerów.
A
4
A
3
A
2
A
4
Przykáad 1.3
[5]
Zakáada siĊ, Īe równolegle na dwóch komputerach o róĪnej mocy obliczeniowej
jest sortowana tablica zawierająca milion elementów (
n
1000000
).
1.3 Model obliczeniowy RAM
Przyjmujemy dalej, Īe na superkomputerze wykonującym 100 milionów
operacji na sekundĊ zastosowano algorytm sortowania o záoĪonoĞci , a na
mikrokomputerze wykonującym 1 milion operacji na sekundĊ zastosowano
inny algorytm sortowania o záoĪonoĞci . Przedstawimy teraz
szacunkowe obliczenia czasów jakie potrzebują oba komputery na posortowanie
tablicy wejĞciowej.
2
n
2
1.3.1 Opis maszyny RAM
50
n
lg
n
Dalsze rozwaĪania na temat algorytmów i ich záoĪonoĞci poprzedzimy
wprowadzeniem hipotetycznego modelu maszyny (urządzenia liczącego), za
pomocą którego bĊdą realizowane nasze algorytmy. JednoczeĞnie przyjmiemy
pewne ustalenia odnoĞnie tego, co bĊdzie okreĞlane pojĊciem „elementarny
krok obliczeĔ”. Z literatury znane są róĪne modele obliczeĔ (por.rys.1.1),
naleĪy jednak stwierdziü, Īe nie istnieje model uniwersalny, który byáby
najlepszy dla wszystkich przypadków.
Dla superkomputera:
210
10
instrukcji
instrukcji sek
6
2
|
20000
sek
. ,
|
5 56
godz
.
8
/
.
Tutaj przedstawiony zostanie rozwaĪany w [1] model maszyny ze swobodnym
dostĊpem do pamiĊci (model RAM –
Random Access Machine
). Model ten
reprezentuje maszynĊ z jednym sumatorem, w której program nie jest
przechowywany w pamiĊci, a zatem nie moĪe on modyfikowaü sam siebie.
Schemat modelu RAM (maszyny RAM) pokazano na rys.1.5. Maszyna skáada
siĊ z nastĊpujących trzech elementów:
x taĞmy wejĞciowej, z której dane mogą byü tylko czytane,
x taĞmy wyjĞciowej, na którą dane mogą byü tylko zapisywane,
x pamiĊci.
Dla mikrokomputera:
50 10 10
10
instrukcji
instrukcji sek
lg
6
|
1000
sek
.
|
16 67
, i
n.
6
/
.
UĪywając zatem algorytmu, którego czas dziaáania jest opisany funkcją
niĪszego rzĊdu (nawet jeĞli zostaá on napisany przez sáabszego programistĊ)
mikrokomputer dziaáa okoáo 20-krotnie szybciej niĪ superkomputer.
- 13 -
- 14 -
6
[ Pobierz całość w formacie PDF ]