SPIS TRE

ĝCI

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

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

Rekursja ................................................................................................ 56

3

Z

ASTOSOWANIE DRZEW I ALGORYTMY PRZESZUKIWANIA

...... 61

3.1

Drzewa przeszukiwa

Ĕ binarnych .......................................................... 61

- 5 -

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

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

5

B

IBLIOGRAFIA

..........................................................................104

DODATEK

Z

ADANIA NA EGZAMINY I KOLOKWIA

...................................................105

- 6 -

1 Algorytmy i modele oblicze

Ĕ

1.1 Poj

Ċcia podstawowe

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

MODELE OBLICZE

ē

Maszyna ze swobodnym

dost

Ċpem do pamiĊci

i pami

Ċtanym programem

(model RASP)

Maszyna ze swobodnym

dost

Ċpem do pamiĊci
(model RAM)

Maszyna Turinga

(elementarny model

oblicze

Ĕ)

Rys.1.1 Przyk

áady modeli obliczeĔ.

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

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

- 7 -

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

jest wykonalny

jest okre

Ğlony

posiada

wyj

Ğcie

posiada

wej

Ğcie

dochodzi do

punktu ko

Ĕcowego

Algorytm

Rys.1.2 Cechy algorytmów.

Do podstawowych pyta

Ĕ pojawiających siĊ w trakcie teoretycznych badaĔ nad

obliczeniami nale

Īą m.in.:

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”?

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).

ANALIZA ALGORYTMÓW

Poprawno

Ğü

algorytmów

Z

áoĪonoĞü

obliczeniowa

Rys.1.3 Kierunki bada

Ĕ analizy algorytmów.

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

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.

1.2 Z

áoĪonoĞü algorytmu

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.

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.

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

, co zapisujemy jako

i

n

2

c

n

2

 

O n

2

- 9 -

czytamy "du

Īe o od n kwadrat". Ogólnie biorąc, pewna nieujemna funkcja

jest

 

f n

 



n



O g

, je

Ğli istnieje taka staáa

,

Īe

c



d

d

f n

n

 





O g n

 



f n

O g

c

 

cg n

a)

 





O g n

n

0









f n

c

 

cg n







0

cg n





dla wszystkich

oprócz pewnego, by

ü moĪe pustego, zbioru nieujemnych

warto

Ğci

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

Ğü

O

 

n

n

0

0

 

f n

jest zawsze nie

wi

Ċksza od

.

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.

:

 

f n

 

cg n

 

f n

n

 

f n

n

0

c)

 

 





f n

g n

4

 

c g n

1

 

c g n

2

n

n

 

f n

 

cg n

n

0

 



f n

g n

:

b)

Rys.1.4 Graficzna interpretacja notacji asymptotycznych.

W odró

Īnieniu od notacji

, która ogranicza funkcj

Ċ z góry, notacja

(rys.1.4b) ogranicza funkcj

Ċ z doáu. Zapis

O

:



 





g n

:

0

oznacza,

Īe istnieją

dodatnie sta

áe

i

takie,

Īe na prawo od

n

warto

Ğü

n

0

 

f n

jest zawsze

wi

Ċksza od

. Przedstawiona na rys.1.4c notacja pozwala szacowa

ü

funkcj

Ċ z doáu i z góry. Pisząc zatem



 





g n

4

f n

wskazujemy,

Īe istnieją

- 10 -

dodatnie sta

áe

,

i

n

takie,

Īe na prawo od

n

warto

Ğü

c

1

c

2

0

0

 

f n

jest zawsze

wi

Ċksza od

i nie wi

Ċksza od



c g n



1

 

c g n

2

.

 

f n

n

2

n

 3

1

2



n

2

 

f n

g

c

n

0

n

2

2

d

 n

3

1

2

n

0

n

3

1

2

3

2



d

n

c

1

2

c

0

Przyk

áad 1.1

Przyjmuj

ąc

oraz



g n

wyka

Īemy, Īe

 





n

4

.

Aby tego dokona

ü, naleĪy wyznaczyü dodatnie staáe

,

c

i

takie,

Īe

1

2

c n

c n

1

2

2

d

dla

n

.

(1.1)

t

Dziel

ąc nierównoĞü (1.1) przez

otrzymujemy zale

ĪnoĞü

n

2

c

c

1

2

1

2

d



d

z której wynika,

Īe nierównoĞü

jest spe

ániona dla kaĪdego

,

je

Ğli przyjąü

n

t 1

c

2

, a nierówno

Ğü

c

n

1

1

2

3

d



jest spe

ániona dla kaĪdego

, je

Ğli przyjąü

n

t 7

c

1

1

14

. St

ąd dla

c

,

1

1

14

2

1

2

i

n

zachodzi

nierówno

Ğü (1.1), co oznacza, Īe

7

 

 





f n

g n

4

.

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).

- 11 -

Przyk

áad 1.2 [1]

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.

A

1

A

5

Tab.1.1

Z

áoĪonoĞci czasowe i maksymalne rozmiary zadaĔ dla wybranych

algorytmów.

Algorytm

Z

áoĪonoĞü

Maksymalny rozmiar zadania

czasowa

1 sekunda

1 minuta

1 godzina

A

1

n

1000

6

˜10

4

3,6

˜10

6

A

2

n

n

lg

140

4893

2,0

˜10

5

A

3

n

2

31

244

1897

A

4

n

3

10

39

153

A

5

2

n

9

15

21

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Ċ.

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.

A

1

A

5

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

1

s

A

2

n

n

lg

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

2 15

4

, s

A

5

2

n

s

5

s

5

3 3

 ,

- 12 -

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

rozmiar ten si

Ċ potraja.

A

5

A

3

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

).

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

2

n

50n lg n

Dla superkomputera:

 

2 10

10

20000

5 56

6

2

8

˜

|

|

instrukcji

instrukcji sek

sek

godz

/

.

.

,

.

Dla mikrokomputera:

50 10

10

10

1000

16 67

6

6

6

˜

|

|

lg

/

.

.

,

mi

instrukcji

instrukcji sek

sek

n.

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 -

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.

1.3 Model obliczeniowy RAM

1.3.1

Opis maszyny RAM

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.

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.

- 14 -

Ta

Ğma wejĞciowa stanowi ciąg klatek, z których kaĪda moĪe zawieraü liczbĊ

ca

ákowitą. KaĪdorazowo, kiedy z taĞmy wejĞciowej zostanie odczytana liczba,

g

áowica czytająca jest przesuwana o jedną pozycjĊ w prawo. Analogicznie

ta

Ğma wyjĞciowa jest takĪe ciągiem klatek (na początku pustych), do których

maszyna mo

Īe tylko zapisywaü. Po zapisie do kolejnej klatki gáowica

zapisuj

ąca jest przesuwana o jedną klatkĊ w prawo. PamiĊü skáada siĊ z

rejestrów

, z których ka

Īdy moĪe przechowywaü (pamiĊtaü)

dowoln

ą liczbĊ caákowitą. Rejestr peáni w obliczeniach specjalną rolĊ i jest

nazywany

sumatorem. Na liczb

Ċ rejestrów nie nakáadamy górnego

ograniczenia, zak

áadając, Īe rozmiar zadania jest zawsze na tyle maáy, Īe mieĞci

si

Ċ ono w pamiĊci, a liczby caákowite biorące udziaá w obliczeniach mieszczą

si

Ċ w pojedynczych komórkach (rejestrach).

,...

,

,

,

3

2

1

0

r

r

r

r

0

r

PROGRAM

. . .

0

r

1

r

2

r

3

r

Sumator

Pami

Ċü

. . .

Ta

Ğma wejĞciowa

. . .

Ta

Ğma wyjĞciowa

Licznik

rozkazów

2

y

1

y

n

x

3

x

2

x

1

x

Rys.1.5 Schemat maszyny RAM [1].

Program maszyny RAM to ci

ąg poleceĔ (inaczej: instrukcji, rozkazów lub

komend), które mog

ą byü poprzedzone etykietą. Licznik rozkazów zawiera

numer kolejnego rozkazu do wykonania. Dok

áadny typ komend nie jest istotny,

o ile przypominaj

ą one te, które wystĊpują w realnych komputerach.

Przyjmiemy,

Īe są dostĊpne komendy arytmetyczne, wejĞcia/wyjĞcia oraz

komendy skoku bezwarunkowego i warunkowego, a tak

Īe wystĊpuje

mo

ĪliwoĞü adresowania poĞredniego. Wszystkie obliczenia są prowadzone na

sumatorze, którym jest rejestr

r

. Przyk

áadowy zestaw poleceĔ maszyny RAM

zamieszczono w tab.1.3.

0

- 15 -

Tab.1.3 Polecenia maszyny RAM.

L.p.

Kod

operacji

Adres

L.p.

Kod

operacji

Adres

1.

LOAD

operand

7.

READ

operand

2.

STORE

operand

8.

WRITE

operand

3.

ADD

operand

9.

JUMP

etykieta

4.

SUB

operand

10.

JGTZ

etykieta

5.

MULT

operand

11.

JZERO

etykieta

6.

DIV

operand

12.

HALT

W ogólnym przypadku komenda sk

áada siĊ z kodu operacji i adresu, który moĪe

by

ü operandem lub etykietą (wyjątkiem jest komenda HALT, gdzie adres nie

wyst

Ċpuje). Etykietą jest nazwa symboliczna, a operand moĪe naleĪeü do

jednego z trzech nast

Ċpujących typów:

=i

-

liczba ca

ákowita i; operand tego typu nazywamy literaáem,

i

-

zawarto

Ğü rejestru o numerze i (i powinno byü nieujemne),

*i

-

warto

Ğcią operandu jest zawartoĞü rejestru j, gdzie j jest liczbą

nieujemn

ą przechowywaną w rejestrze i (adresacja poĞrednia).

Rozwa

Īymy dalej pewne odwzorowanie c zbioru liczb caákowitych

nieujemnych na zbiór liczb ca

ákowitych takie, Īe

oznacza zawarto

Ğü

rejestru o numerze i. Odwzorowanie pozwala zatem przedstawi

ü mapĊ

pami

Ċci (rejestrów) maszyny RAM i wraz z zawartoĞcią licznika rozkazów

definiuje tzw. znaczenie programu w danej chwili. Na pocz

ątku przyjmuje siĊ

, oraz zak

áada, Īe licznik rozkazów wskazuje na pierwszą

komend

Ċ do wykonania, a taĞma wyjĞciowa jest pusta. Po wykonaniu pewnego

rozkazu

licznik rozkazów automatycznie wskazuje na rozkaz

za

wyj

ątkiem przypadków, kiedy rozkazem

k

-tym by

á któryĞ z nastĊpujących

rozkazów: JUMP, JGTZ, JZERO lub HALT.

)

(i

c

c

0

,

0

)

(

t

i

i

c

k



1



k



Aby w pewien formalny sposób opisa

ü dziaáanie komend z tab.1.3

wprowadzimy jeszcze funkcj

Ċ

 

a

v

wyznaczaj

ącą wartoĞü operandu w

nast

Ċpujący sposób:

a

 

i

i

v

 

 

i

c

i

v

 

 





i

c

c

i

v

*

.

- 16 -

Opis komend maszyny RAM, z wykorzystaniem wprowadzonych notacji
zestawiono w tab.1.4.

Tab.1.4 Opis polece

Ĕ maszyny RAM.

Komenda

Opis dzia

áania

LOAD

a

 

 

a

v

c

m

0

, co oznacza zapis warto

Ğci operandu do

rejestru 0 (sumatora).

a

STORE

i

 

 

0

c

i

c

m

STORE

*

i

 

 

 

0

c

i

c

c

m

ADD

a

 

   

a

v

c

c



m 0

0

SUB

a

 

   

a

v

c

c



m 0

0

MULT

a

 

   

a

v

c

c

u

m 0

0

DIV

a

 

   

¬

¼

a

v

c

c

/

0

0

m

READ

i

 

m

i

c

kolejny symbol wej

Ğciowy

READ

*

i

 

 

m

i

c

c

kolejny symbol wej

Ğciowy

WRITE

a

 

a

v

jest zapisywane do tej klatki ta

Ğmy wyjĞciowej, przy której

aktualnie znajduje si

Ċ gáowica

JUMP

b

Licznik rozkazów jest ustawiany na komend

Ċ z etykietą

b

JGTZ

b

Je

Ğli

, to licznik rozkazów jest ustawiany na komend

Ċ z

etykiet

ą

b

; w przeciwnym razie na komend

Ċ nastĊpną

 

0

0

!

c

JZERO

b

Je

Ğli

 

0

0

c

, to licznik rozkazów jest ustawiany na komend

Ċ z

etykiet

ą

b

; w przeciwnym razie na komend

Ċ nastĊpną

HALT

Zatrzymanie programu

Przyk

áad 1.4

Wyznaczy

ü wartoĞü funkcji:

 

¯

®

­

t

1

dla

0

dla

0

n

n

n

n

f

n

.

Odpowiedni program dla maszyny RAM ma posta

ü:

Etykieta

Komenda

Adres

Komentarz

READ

1

Wczytaj liczb

Ċ n do rejestru 1

- 17 -

LOAD

1

Umie

Ğü n w sumatorze

JGTZ

dod

Wykonuj obliczenia tylko wtedy, gdy

n>0

WRITE

=0

W przypadku gdy n=0 wypisz 0

JUMP

Koniecjesli

Skocz na koniec programu

dod: LOAD

1

Umie

Ğü n w sumatorze

STORE

2

Zapisz n do rejestru 2

LOAD

1

Umie

Ğü n w sumatorze

SUB

=1

Oblicz n-1

STORE

3

Zapisz n-1 do rejestru 3

dopoki: LOAD

3

Umie

Ğü zawartoĞü rejestru 3( licznik

p

Ċtli) w sumatorze

JGTZ

Kontyn

Kontynuuj, je

Ğli w rejestrze 3 jest

liczba wi

Ċksza od 0

JUMP

Koniecdopoki

Skocz do wypisania wyniku

Kontyn: LOAD

2

Zapisz iloczyn cz

ąstkowy do sumatora

MULT

1

Pomnó

Ī iloczyn cząstkowy przez n

STORE

2

Zapisz nowy iloczyn cz

ąstkowy do

rejestru 2

LOAD

3

Umie

Ğü licznik pĊtli w sumatorze

SUB

=1

Odejmij 1 od licznika p

Ċtli

STORE

3

Zapisz now

ą wartoĞü licznika pĊtli w

sumatorze

JUMP

Dopoki

Skocz do sprawdzenia warunku p

Ċtli

Koniecdopoki: WRITE

2

Wypisz zawarto

Ğü rejestru 2 (tj.

obliczone

n

)

n

Koniecjesli: HALT

Koniec programu

1.3.2 Uproszczony j

Ċzyk programowania

Celem uzyskania bardziej przejrzystego zapisu algorytmów wykonywalnych w
ramach modelu RAM do

Ğü czĊsto uĪywa siĊ uproszczonego jĊzyka wyĪszego

poziomu, okre

Ğlanego jako pseudojĊzyk lub pseudokod [1, 5]. W

prezentowanych dalej przyk

áadach najczĊĞciej uĪywany bĊdzie jĊzyk

wzorowany na pseudokod zaproponowany w [5]. Poni

Īej przedstawiony

zostanie pewien nieformalny opis tego j

Ċzyka.

- 18 -

1. Pseudokod tym ró

Īni siĊ od typowego jĊzyka programowania, Īe dopuszcza

dowolny typ opisu matematycznego, a nawet s

áownego, jeĞli tylko jest on w

pe

áni zrozumiaáy i moĪe zostaü przetáumaczony na komendy prostego

modelu, np. modelu RAM.

2. Nie ustala si

Ċ z góry dopuszczalnych typów danych, a zmiennymi są

zwykle liczby i tablice. Dodatkowe typy, jak: listy, kolejki, stosy, grafy itp.
s

ą wprowadzane w razie potrzeby. Tam, gdzie to moĪliwe, unika siĊ ich

formalnego opisu.

3. Stosuje si

Ċ tradycyjny zapis matematyczny oraz konstrukcje znane z

j

Ċzyków programowania typu Pascal i C. Do podstawowych operatorów

pseudokodu nale

Īą:

a) nadawanie

warto

Ğci

zmienna

m wyraĪenie

b) operator

warunkowy

je

Ğli warunek

to

operator(y)

inaczej

operator(y)

c) operator

p

Ċtli dopóki

dopóki

warunek

wykonuj

operator(y)

d) operator

p

Ċtli powtarzaj

powtarzaj

operator(y)

a

Ī_do warunek

e) operator

p

Ċtli dla

dla

zmienna

m wartoĞü_początkowa [w_dóá_]do wartoĞü_koĔcowa

wykonuj

operator(y)

4. Blok polece

Ĕ pseudojĊzyka (instrukcjĊ záoĪoną) wydzielamy za pomocą

nawisów klamrowych { i }. Mo

Īna takĪe stosowaü „wciĊcia” celem

zwi

Ċkszenia czytelnoĞci programu.

- 19 -

5. Symbol „

” oznacza,

Īe reszta wiersza jest komentarzem.

6. Wielokrotne przypisywanie w postaci

i

e

j

m

m

oznacza przypisanie

zmiennym

oraz warto

Ğci wyraĪenia

. Jest ono równowa

Īne

przypisaniu

áącznie z przypisaniem

i

j

j

e

j

i

e

m

m

.

7. Zmienne s

ą z zaáoĪenia lokalne w danej procedurze, chyba, Īe wyraĨnie

zaznaczono inaczej.

8. Dost

Ċp do elementu tablicy odbywa siĊ przez podanie jej nazwy oraz

indeksu

Īądanego elementu w nawiasie kwadratowym, np.

> @

i

A

jest

i

-tym

elementem tablicy

A

. Zapis

> @

j

A ..

1

oznacza natomiast podtablic

Ċ tablicy

A

z

áoĪoną z elementów

> @ > @

> @

j

A ,

1

A

A

,...

2

.

9. Dane z

áoĪone z kilku czĊĞci są zorganizowane jako obiekty záoĪone z

atrybutów (pól). Odwo

áanie do konkretnego atrybutu pewnego obiektu

nast

Ċpuje przez podanie nazwy tego obiektu w nawiasach kwadratowych

poprzedzonej nazw

ą atrybutu, np.

> @

x

f

jest odwo

áaniem do atrybutu

obiektu

f

x

.

10. Zmienna odpowiadaj

ąca tablicy lub obiektowi jest traktowana jako

wska

Ĩnik do danych reprezentujących tĊ tablicĊ lub ten obiekt. Dla

wszystkich pól

obiektu

f

x

przypisanie

x

y

m

powoduje

> @

>

x

f

y

f

@

.

Ponadto je

Ğli teraz wykonamy

> @

3

m

x

f

, to w nast

Ċpstwie nie tylko

, lecz tak

Īe

> @

3

x

f

> @

3

y

f

. Wska

Ĩnik, który na nic nie wskazuje

posiada specjaln

ą wartoĞü nil.

11. Parametry s

ą przekazywane do procedury przez wartoĞü, tzn., Īe

wywo

áywana procedura otrzymuje swoją kopiĊ parametrów, a zmiany

wewn

Ċtrzne tych kopii nie są widoczne przez program wywoáujący.

Obiekty s

ą przekazywane przez wskaĨniki do nich. JeĞli na przykáad obiekt

x

jest parametrem procedury, to przypisanie

y

x

m

wewn

ątrz procedury

nie jest widoczne na zewn

ątrz, ale przypisanie

> @

3

m

x

f

jest widoczne.

Przyk

áad 1.5

- 20 -

Zapisany w pseudokodzie algorytm K.1.1 oblicza warto

Ğü funkcji z przykáadu

1.4.

K.1.1

POT

ĉGA-N-DO-N

1 czytaj r1
2 je

Ğli r1

d0 to pisz 0

3 inaczej { r2

m

r1

4

r3

m

r1-1

5

dopóki

r3>0

6

wykonuj

{ r2

m

r2*r1

7 r3

m

r3-1 }

8 pisz r2 }

Numerowanie wierszy programu w pseudokodzie pozwala

áatwiej odwoáywaü

si

Ċ do tych wierszy w opisach prezentowanych algorytmów.

Programy w pseudokodzie s

ą równowaĪne programom RAM w tym sensie, Īe

jest mo

Īliwe ich táumaczenie na program w jĊzyku maszyny RAM. Problem

takiej translacji stanowi jednak odr

Ċbne zagadnienie i nie bĊdzie tutaj

omawiany.

W literaturze z dziedziny algorytmów obok pseudokodów zbli

Īonych do

zdefiniowanego, s

ą uĪywane takĪe popularne jĊzyki programowania, np. Pascal

[3, 4] lub C [6].

1.3.3 Z

áoĪonoĞü pesymistyczna i oczekiwana

Jak ju

Ī wspomniano, dwa podstawowe wskaĨniki efektywnoĞci algorytmów

stanowi

ą záoĪonoĞü pamiĊciowa i záoĪonoĞü czasowa bĊdące funkcjami

rozmiaru wej

Ğcia. Za jednostkĊ záoĪonoĞci pamiĊciowej przyjmuje siĊ zwykle

s

áowo pamiĊci maszyny. Natomiast w przypadku záoĪonoĞci czasowej, która

powinna by

ü niezaleĪna od komputera, jĊzyka programowania i sposobu

zakodowania programu, rozwa

Īa siĊ tzw. operacje dominujące. Są to operacje

charakterystyczne dla danego algorytmu, a ich liczba jest proporcjonalna do
liczby wykona

Ĕ wszystkich operacji jednostkowych w dowolnej realizacji

komputerowej danego algorytmu [3]. Na przyk

áad w algorytmach wyznaczania

warto

Ğci wielomianów mogą to byü podstawowe operacje arytmetyczne, a w

algorytmach sortowania – operacje porównania dwóch elementów sortowanej

- 21 -

tablicy. Za jednostk

Ċ záoĪonoĞci czasowej przyjmuje siĊ wtedy wykonanie

jednej operacji dominuj

ącej.

Je

Ğli dla ustalonego rozmiaru wejĞcia w charakterze miary záoĪonoĞci przyjąü

najwi

Ċkszą ze záoĪonoĞci dla wszystkich moĪliwych wejĞü danego rozmiaru, to

taka z

áoĪonoĞü jest okreĞlana jako pesymistyczna. JeĞli natomiast jako miarĊ

z

áoĪonoĞci przyjąü pewną „Ğrednią” záoĪonoĞü dla wszystkich wejĞü danego

rozmiaru to tak

ą záoĪonoĞü okreĞlamy jako oczekiwaną. Zazwyczaj záoĪonoĞü

oczekiwana jest trudniejsza do okre

Ğlenia niĪ záoĪonoĞü pesymistyczna.

Poj

Ċcia záoĪonoĞci pesymistycznej i záoĪonoĞci oczekiwanej moĪna takĪe

wprowadzi

ü w sposób formalny. Uczynimy to w stosunku do záoĪonoĞci

czasowej u

Īywając nastĊpujących oznaczeĔ:

d

n

- rozmiar zestawu danych

d

,

n

D

- zbiór zestawów danych wej

Ğciowych rozmiaru

n

,

 

d

r

- Liczba operacji dominuj

ących dla zestawu danych wejĞciowych

,

d

n

X

- Zmienna losowa, której wartoĞcią jest

 

d

r

dla

n

D

d



,

nk

p

- Rozkáad prawdopodobieĔstwa zmiennej losowej

, tzn.

prawdopodobie

Ĕstwo, Īe dla danych rozmiaru

algorytm wykona

operacji dominuj

ących

n

X

n

k





0

t

k

.

Rozk

áad prawdopodobieĔstwa zmiennej losowej

wyznacza si

Ċ na

podstawie informacji o zastosowaniach rozwa

Īanego algorytmu. W pewnych

przypadkach mo

Īna zaáoĪyü, Īe jest to rozkáad równomierny, tzn. kaĪdy zestaw

danych rozmiaru

n

mo

Īe pojawiü siĊ na wejĞciu algorytmu z jednakowym

prawdopodobie

Ĕstwem.

n

X

Definicja 1.1

Pesymistyczna z

áoĪonoĞü czasowa algorytmu to funkcja rozmiaru wejĞcia

okre

Ğlona nastĊpująco:

 

 

^

`

n

D

d

d

r

n

W



:

sup

,

gdzie sup oznacza górny kres zbioru.

- 22 -

Definicja 1.2

Oczekiwana z

áoĪonoĞü czasowa to funkcja rozmiaru wejĞcia okreĞlona

nast

Ċpująco

.

 

¦

t

0

k

nk

kp

n

A

Jest to zatem warto

Ğü oczekiwana zmiennej losowej

.

n

X

1.3.4 Z

áoĪonoĞü programów w jĊzyku RAM

W celu otrzymania z

áoĪonoĞci czasowej i pamiĊciowej programów RAM naleĪy

okre

Ğliü czas niezbĊdny do wykonania kaĪdej komendy RAM oraz objĊtoĞü

pami

Ċci uĪywanej przez kaĪdy z rejestrów, przyjmując przy tym pewne kryteria

wagowe. Rozwa

Īa siĊ nastĊpujące kryteria [1]:

x

równomierne kryterium wagowe oraz

x

logarytmiczne kryterium wagowe.

W przypadku równomiernego kryterium wagowego zak

áada siĊ, Īe kaĪda

komenda RAM potrzebuje na jej wykonanie jednej jednostki czasu, a ka

Īdy

rejestr wykorzystuje jedn

ą jednostkĊ pamiĊci.

Logarytmiczne kryterium wagowe jest oparte na za

áoĪeniu, Īe koszt wykonania

ka

Īdej komendy (jej waga) jest proporcjonalna do dáugoĞci operandów.

Rozwa

Īymy nastĊpującą funkcjĊ logarytmiczną okreĞloną na zbiorze liczb

ca

ákowitych

 

¬ ¼

¯

®

­

z



.

0

,

1

,

0

,

1

lg

i

i

i

i

l

Posta

ü tej funkcji uwzglĊdnia fakt, Īe dwójkowy zapis liczby caákowitej w

rejestrze wymaga

i

¬ ¼

1

lg



i

bitów (zapis

oznacza

log

).

lg

2

W celu wyznaczenia logarytmicznej z

áoĪonoĞci czasowej programów w jĊzyku

RAM, okre

Ğla siĊ wagi logarytmiczne dla poszczególnych typów operandów

oraz komend maszyny RAM. Wagi logarytmiczne

 

a

t

dla wszystkich trzech

typów operandów podano w tab.1.5, a wagi dla komend w tab.1.6.

Tab.1.5 Wagi logarytmiczne operandów.

- 23 -

Operand

a

Waga logarytmiczna

 

a

t

=

i

 

i

l

i

 

 

 

i

c

l

i

l



i

*

 

 

 

 

 





i

c

c

l

i

c

l

i

l





Tab.1.6 Wagi logarytmiczne komend.

Komenda

Waga logarytmiczna

LOAD

a

 

a

t

STORE

i

 



 

i

l

c

l



0



STORE

* i

 



  

 

 

i

c

l

i

l

c

l





0

ADD

a

 



 

a

t

c

l



0



SUB

a

 



 

a

t

c

l



0



MULT

a

 



 

a

t

c

l



0



DIV

a

 



 

a

t

c

l



0



READ

i



  

i

l

wejscie

l



READ

*i



  

 

 

i

c

l

i

l

wejscie

l





WRITE

a

 

a

t

JUMP

b

1

JGTZ

b

 





0

c

l

JZERO

b

 





0

c

l

HALT

1

Dla przyk

áadu wyznaczymy wagĊ logarytmiczną komendy ADD *i. Najpierw

jest okre

Ğlany stopieĔ trudnoĞci w dekodowaniu adresu operandu *i.

Przeg

áądanie liczby caákowitej i zajmuje czas

 

i

l

. Nast

Ċpnie naleĪy odczytaü

zawarto

Ğü

rejestru i pozwalaj

ącą ustaliü rejestr gdzie umieszczono

dodawan

ą liczbĊ, co wymaga czasu

 

i

c

 





i

c

l

. Wreszcie odczyt zawarto

Ğci

rejestru

, tj. samej adresowanej liczby wymaga czasu

 





i

c

c



i

c



 









i

c

c

l

. W sumie

odczyt dodawanej liczby zajmuje

 

 





 









i

c

c

i

c

l

l

i

l





jednostek czasu.

Poniewa

Ī komenda ADD*i dodaje liczbĊ caákowitą

 





i

c

c

do liczby ca

ákowitej

- 24 -

 

0

c

w sumatorze, zatem waga dla ca

áej komendy jest równa sumie

 



  

 





 









i

c

c

l

i

c

l

i

l







c

l

0

.

 

¦

i

i

x

l

i

x

1



n

 

  



n

i

n

l

n

l

i

lg

1



|







,

lg

1

1

1

n

i

n

i

¦









n

n lg

2

 

n

n lg

|

n

l

n

Rozwa

Īymy teraz problem okreĞlania logarytmicznej záoĪonoĞci pamiĊciowej

programu RAM. Przyjmuje si

Ċ, Īe jest to suma

,

w której uwzg

áĊdniono wszystkie rejestry i (áącznie z sumatorem) biorące udziaá

w obliczeniach, a przez

oznaczono najwi

Ċkszą wartoĞü bezwzglĊdną liczby

ca

ákowitej, która w trakcie obliczeĔ pojawiáa siĊ w i-tym rejestrze.

Przyk

áad 1.6

Dokona

ü oceny záoĪonoĞci obliczeniowej programu obliczającego wartoĞü

funkcji z przyk

á.1.4.

Nietrudno zauwa

Īyü, Īe ze wzglĊdu na záoĪonoĞü czasową dominującym

fragmentem jest p

Ċtla zawierająca komendĊ MULT. Gdy komenda ta wykonuje

si

Ċ po raz i-ty, to sumator zawiera

, a rejestr 1 zawiera . W sumie komenda

MULT wykonuje si

Ċ

razy. Przyjmuj

ąc równomierne kryterium wagowe,

ka

Īda z komend MULT wymaga czasu równego jednej jednostce, a zatem na

wykonanie wszystkich tych komend potrzebny jest czas

i

n

n

 

n

O

. W przypadku

kryterium logarytmicznego i-ta komenda MULT zajmuje czas

a zatem czas wykonania wszystkich komend MULT jest równy

tzn.

O

.

Z

áoĪonoĞü pamiĊciowa jest wyznaczana wielkoĞcią liczb przechowywanych w

rejestrach od 0 do 3. Dla równomiernego kryterium wagowego z

áoĪonoĞü ta jest

pewn

ą staáą, a jej asymptotyczną granicĊ górną oznaczaü bĊdziemy jako

.

Poniewa

Ī najwiĊkszą z przechowywanych w rejestrach liczb jest

, a

 

1

O

n

n

, st

ąd w przypadku kryterium logarytmicznego otrzymujemy

z

áoĪonoĞü pamiĊciową

O

.





n

n lg

- 25 -

Nale

Īy zauwaĪyü, Īe dla tego programu równomierne kryterium wagowe jest

uzasadnione tylko w przypadku, je

Ğli liczba

mo

Īe byü zapisana w postaci

jednego s

áowa maszynowego. JeĞli tak nie jest, wówczas nawet logarytmiczna

z

áoĪonoĞü czasowa jest do pewnego stopnia nierealistyczna, gdyĪ zakáada ona,

Īe dwie liczby caákowite i i j mogą byü pomnoĪone w czasie

n

n

   





j

l

i

l

O



, co

nie jest bynajmniej oczywiste [1].

1.3.5 Z

áoĪonoĞü programów w pseudokodzie

Wprawdzie podstawowe miary z

áoĪonoĞci zostaáy przez nas okreĞlone w

terminach modelu obliczeniowego RAM, lecz w wielu przypadkach ocena
z

áoĪonoĞci konkretnego algorytmu moĪe byü dokonana na podstawie jego

zapisu w pseudokodzie.

Podobnie jak dla j

Ċzyka RAM, takĪe w tym przypadku istotny bĊdzie czas i

pami

Ċü potrzebne do wykonania komend pseudokodu. Sposób oceny záoĪonoĞci

czasowej algorytmu zapisanego w pseudokodzie ilustruje rozwa

Īany w [5]

przyk

áad sortowania przez wstawianie. Algorytm ten przedstawiono w

pierwszej kolumnie tab.1.7, a koszt wykonania poszczególnych instrukcji i
liczb

Ċ ich wykonaĔ odpowiednio w kolumnach drugiej i trzeciej.

Przyj

Ċto, Īe n oznacza liczbĊ elementów tablicy A, tzn. jest równe wartoĞci

atrybutu

> @

A

length

. Przez

t

oznaczono liczb

Ċ sprawdzeĔ warunku wejĞcia do

p

Ċtli dopóki w wierszu 5 dla pewnej wartoĞci j. W celu oceny záoĪonoĞci

obliczeniowej oblicza si

Ċ caákowity czas dziaáania algorytmu, który jest sumą

czasów dzia

áania poszczególnych instrukcji. JeĞli koszt (czas wykonania)

pewnej instrukcji powtarzanej

n

razy wynosi

c

, to ca

ákowity koszt wykonania

tej instrukcji wynosi

c

.

j

i

n

i

Tab.1.7 Wp

áyw instrukcji algorytmu sortowania przez wstawianie na jego záoĪonoĞü.

- 26 -

Instrukcje

Koszt

Liczba
wykona

Ĕ

SORT-WSTAW (A)

1 dla j

m2 do length[A]

1

c

n

2

wykonuj { key

mA[j]

2

c

1



n

3

 Wstaw A[j] do posortowanego ciągu A[1..j-1].

0

1



n

4

i

mj-1

4

c

1



n

5

dopóki i>0 i A[i]>key

5

c

¦

n

j

j

t

2

6

wykonuj { A[i+1]

mA[i]

6

c





¦



n

j

j

t

2

1

7

i

mi-1 }

7

c





¦



n

j

j

t

2

1

8

A[i+1]

mkey }

8

c

1



n

Sumuj

ąc koszty wykonania poszczególnych instrukcji z tab.1.7 otrzymujemy

 





















1

1

1

1

1

8

2

7

2

6

2

5

4

2

1























¦

¦

¦

n

c

t

c

t

c

t

c

n

c

n

c

n

c

n

T

n

j

j

n

j

j

n

j

j

.

Zauwa

Īmy, Īe w przypadku, gdy tablica wejĞciowa jest juĪ posortowana (tzw.

przypadek optymistyczny), mamy

1

j

t

dla

,

n

j

,...,

3

,

2

co daje minimalny czas dzia

áania algorytmu równy

 























.

1

1

1

1

8

5

4

2

8

5

4

2

1

8

5

4

2

1

c

c

c

c

n

c

c

c

c

c

n

c

n

c

n

c

n

c

n

c

n

M



































Jak wida

ü, wielkoĞü ta jest funkcją liniową wzglĊdem

n

.

W przypadku

pesymistycznym (tablica jest posortowana w porz

ądku

odwrotnym) mamy

j

t

j

dla

.

n

j

,...,

3

,

2

Z uwgl

Ċdnieniem zaleĪnoĞci

- 27 -





1

2

1

2





¦

n

j

n

n

j

oraz









¦





n

j

n

n

j

2

2

1

1

otrzymujemy

 





























,

2

2

2

2

2

2

1

2

1

2

1

1

2

1

1

1

8

5

4

2

8

7

6

5

4

2

1

2

7

6

5

8

7

6

5

4

2

1

c

c

c

c

n

c

c

c

c

c

c

c

n

c

c

c

n

c

n

n

c

n

n

c

n

n

c

n

c

n

c

n

c

n

W









¸

¹

·

¨

©

§















¸

¹

·

¨

©

§









¸

¹

·

¨

©

§







¸

¹

·

¨

©

§





¸

¹

·

¨

©

§















n

co oznacza,

Īe pesymistyczna záoĪonoĞü czasowa tego algorytmu jest funkcją

kwadratow

ą wzglĊdem

. Stosuj

ąc poznaną notacjĊ asymptotyczną zapiszemy,

Īe pesymistyczny czas dziaáania algorytmu sortowania przez wstawianie wynosi

 

2

n

O

. W analizowanych dalej algorytmach zwykle b

Ċdziemy rozwaĪaü

przypadek pesymistyczny.

Pytania kontrolne

1. Poda

ü definicjĊ oraz charakterystyczne cechy algorytmu.

2. Okre

Ğliü nastĊpujące pojĊcia:

a) analiza algorytmów;
b) z

áoĪonoĞü obliczeniowa algorytmu;

c) poprawno

Ğü algorytmu;

d) asymptotyczna z

áoĪonoĞü czasowa;

e) rozmiar zadania.

3. Poda

ü definicjĊ i ilustracjĊ graficzną asymptotycznej granicy górnej.

4. Poda

ü definicjĊ i ilustracjĊ graficzną asymptotycznej granicy dolnej.

5. Wyja

Ğniü sens zapisu

 

 





f n

g n

4

.

6. Scharakteryzowa

ü model obliczeniowy RAM.

7. Omówi

ü komendy maszyny RAM.

- 28 -

8. Wymieni

ü podstawowe konwencje zapisu algorytmów w pseudojĊzyku.

9. Okre

Ğliü nastĊpujące pojĊcia:

a) z

áoĪonoĞü pamiĊciowa;

b) operacja dominuj

ąca;

c) z

áoĪonoĞü czasowa;

d) z

áoĪonoĞü pesymistyczna;

e) z

áoĪonoĞü oczekiwana (Ğrednia).

10. Poda

ü formalną definicjĊ záoĪonoĞci pesymistycznej i záoĪonoĞci

oczekiwanej.

11. Na czym polegaj

ą: równomierne i logarytmiczne kryterium wagowe?

12. Poda

ü wagi logarytmiczne operandów w poleceniach maszyny RAM.

13. Poda

ü i uzasadniü wagi logarytmiczne komend LOAD, ADD, READ,

JGTZ, HALT.

14. Poda

ü i uzasadniü wagi logarytmiczne komend STORE, MULT, WRITE,

JUMP, JZERO.

Zadania

1. Wykaza

ü, Īe:

a)

; b)



6

2

n

O n



3

 

3

n

n

z 4

6

; c)

2

 

1

2

3

2

2

n

n

n



:

;

d) dla funkcji kwadratowej

 

f n

an

bn

c





2

, gdzie

i s

ą

sta

áymi oraz

, zachodzi

a b

,

c

a

! 0

 

 

f n

n

4

2

.

2. Zapisa

ü w jĊzyku maszyny RAM algorytm czytający liczby wejĞciowe, aĪ

do napotkania zera. Obliczy

ü sumĊ tych liczb i wypisaü wynik.

3. Zapisa

ü w pseudojĊzyku nastĊpujące algorytmy:

a)

Wyznaczanie najwi

Ċkszego wspólnego podzielnika dwóch liczb

(algorytm Euklidesa)

b)

Poszukiwanie maksymalnej warto

Ğci w tablicy jednowymiarowej

c)

Sortowanie przez selekcj

Ċ tablicy A záoĪonej z n elementów.

Znajdujemy najmniejszy element w tablicy i wstawiamy go na

- 29 -

pierwsze miejsce. Nast

Ċpnie znajdujemy drugi najmniejszy element i

wstawiamy go na drugie miejsce. W ten sposób post

Ċpujemy dla

wszystkich n elementów tablicy A.

4.

Dany jest nast

Ċpujący algorytm:

MAX
1 czytaj x
2 max

mx

3 dopóki x

z

0

4

wykonuj { je

Ğli x>max

5

to max

mx

6

czytaj x }

7 pisz max

a) Napisa

ü program w jĊzyku maszyny RAM realizujący ten algorytm

b) Okre

Ğliü záoĪonoĞü czasową i pamiĊciową programu RAM.

5.

Zapisa

ü w pseudojĊzyku algorytm, którego zadaniem jest sprawdzenie, czy

na wej

Ğciu pojawiáa siĊ jednakowa liczba jedynek i dwójek. Po

przeczytaniu 0, algorytm wypisuje 1, je

Ğli liczba jedynek i dwójek byáa

jednakowa i zatrzymuje si

Ċ. Zakáadamy, Īe oprócz 0, 1 i 2 na wejĞciu nie

mog

ą pojawiü siĊ Īadne inne symbole. Dla danego algorytmu wykonaü

tak

Īe nastĊpujące zadania:

a)

Napisa

ü program w jĊzyku maszyny RAM realizujący ten algorytm

b)

Okre

Ğliü záoĪonoĞü czasową i pamiĊciową programu RAM.

6.

Napisa

ü w pseudojĊzyku algorytm wyznaczania wartoĞci

dla podanej

liczby nieujemnej n, a nast

Ċpnie:

!

n

a) Napisa

ü program w jĊzyku maszyny RAM realizujący ten algorytm

b) Okre

Ğliü záoĪonoĞü czasową i pamiĊciową programu RAM.

Zadania 4,5,6 wykona

ü przyjmując zarówno równomierne, jak i

logarytmiczne kryterium wagowe.

- 30 -

2

Struktury dynamiczne i rekursja

2.1 Wprowadzenie

Istnieje obszerna klasa elementarnych struktur danych, które wymagaj

ą staáej,

okre

Ğlanej w chwili ich utworzenia, wielkoĞci pamiĊci. Przykáadami są znane z

Pascala typy liczbowe, logiczne, tablice i

rekordy.

Tymczasem

w

rozwi

ązywaniu wielu problemów przydatne okazują siĊ takie struktury, których

chwilowa posta

ü i rozmiar zmieniają siĊ w trakcie przetwarzania, a pamiĊü dla

nich jest wydzielana i zwalniana w miar

Ċ potrzeby. Tego typu obiekty tworzą

klas

Ċ tzw. struktur dynamicznych, do których zaliczamy m.in.: listy, stosy,

kolejki i drzewa. Wiele struktur dynamicznych posiada charakter rekursywny,
st

ąd algorytmy operujące na takich strukturach wygodnie jest konstruowaü

stosuj

ąc rekursjĊ.

2.2 Listy

2.2.1

Definicje i reprezentacja pami

Ċciowa

Podstawow

ą strukturą dynamiczną jest lista. NajproĞciej listĊ moĪna okreĞliü

jako sko

Ĕczony ciąg elementów naleĪących do pewnego zbioru. JeĪeli jest to

ci

ąg:

, to list

Ċ czĊsto zapisuje siĊ w postaci:

n

e

e

e

,...,

,

2

1





n

e

e

e

...

2

1

.

Najprostsz

ą realizacją listy jest dynamiczna struktura pamiĊci pokazana na

rys.2.1.

e

1

na pierwszy

e

2

e

n

. . .

nil

element

wska

Ĩnik

Rys.2.1 Lista jednokierunkowa.

- 31 -

Elementarny sk

áadnik tej struktury skáada siĊ z dwóch pól, które moĪna

traktowa

ü jako odrĊbne komórki pamiĊci. Pierwsze z pól zawiera sam

pami

Ċtany element (jego zawartoĞü informacyjną), a drugie tzw. wskaĪnik

informuj

ący o poáoĪeniu nastĊpnego elementu w liĞcie. Wyjątkiem jest ostatni

sk

áadnik, gdzie w polu wskaĪnika umieszczono symbol nil, informujący, Īe w

tym miejscu nie wyst

Ċpuje wskaĨnik na Īaden element. WskaĨnik na pierwszy

element jest tak

Īe pamiĊtany w specjalnie do tego celu przeznaczonej zmiennej.

Struktura przedstawiona na rys.2.1 jest przyk

áadem tzw. listy jednokierunkowej,

w której pojedynczy sk

áadnik zawiera wskaĨnik tylko na element nastĊpny.

Najcz

ĊĞciej listĊ przedstawia siĊ w postaci nieco bardziej rozbudowanej

struktury okre

Ğlanej jako lista dwukierunkowa pokazana na rys.2.2.

e

1

head [L]

e

2

. . .

e

n

nil

nil

Rys.2.2 Lista dwukierunkowa.

Pojedynczy sk

áadnik listy dwukierunkowej zawiera pole informacyjne i dwa

pola wska

Ĩników: lewy wskazujący na poprzedni element oraz prawy

wskazuj

ący na element nastĊpny. ZauwaĪmy, Īe lewy wskaĨnik pierwszego

elementu i prawy wska

Ĩnik ostatniego elementu listy dwukierunkowej

zawieraj

ą symbol nil (nie wskazują na Īadne elementy). Taka organizacja list

sprawia,

Īe w odróĪnieniu od tablic, gdzie uĪywa siĊ indeksów, tutaj porządek

elementów jest okre

Ğlony za pomocą wskaĨników związanych z kaĪdym

elementem listy.

Przetwarzaj

ąc listy w pseudokodzie wprowadzimy specjalną zmienną typu lista

repezentuj

ącą strukturĊ z rys. 2.2. Przyjmuje siĊ, Īe wskaĨnik na pierwszy

element listy jest pami

Ċtany jako wartoĞü jej atrybutu o nazwie head.

Zak

áadając zatem, Īe L jest zmienną oznaczającą listĊ z rys.2.2, odwoáanie do

wska

Ĩnika na początek tej listy zapisujemy jako head[L]. Operacje na listach

cz

Ċsto wymagają uĪycia atrybutów takĪe dla pojedynczego elementu listy. JeĞli

przyj

ąü, Īe x jest elementem listy dwukierunkowej, to odwoáania do jego pól są

mo

Īliwe za pomocą nastĊpujących atrybutów (rys.2.3):

prev[x] - wska

Ĩnik na poprzedni element,

key[x] -

zawarto

Ğü informacyjna elementu,

next[x] - wska

Īnik na nastĊpny element.

- 32 -

prev

next

key

e

i

Rys.2.3 Pola odpowiadaj

ące atrybutom elementu listy.

Wprowadzony wcze

Ğniej symbol nil moĪna takĪe traktowaü jako „wskaĨnik

pusty”, st

ąd head[L]=nil oznacza, Īe lista L jest pusta (nie zawiera Īadnych

elementów). Z kolei spe

ánienie równoĞci prev[x]=nil oznacza, Īe element x nie

ma poprzednika, je

Ğli natomiast next[x]=nil, to element x nie ma nastĊpnika.

2.2.2

Podstawowe operacje na listach

Poszukiwanie elementu w li

Ğcie

Rozwa

Īymy funkcjĊ LISTA-POSZ z parametrami L i k, wyznaczającą pierwszy

napotkany element listy L, którego pole key[x] (pole klucza) ma warto

Ğü k. W

wyniku funkcja zwraca wska

Ĩnik na ten element, a jeĞli elementu nie

znaleziono, jest zwracana warto

Ğü nil. Przykáadowy zapis funkcji LISTA-POSZ

przedstawiono w postaci kodu K.2.1.

K.2.1

LISTA-POSZ(L,k)
1 x

m

head[L]

2 dopóki x

znil i key[x] zk

3

wykonuj

x

m

next[x]

4 zwró

ü x

Poszukiwanie w tym algorytmie odbywa si

Ċ metodą przeglądania kolejnych

elementów listy L. Na pocz

ątku zmiennej x jest nadawana wartoĞü wskaĪnika na

pocz

ątek listy. NastĊpnie w pĊtli dopóki x przyjmuje wartoĞci wskaĨników na

kolejne elementy listy, a

Ī do znalezienia poszukiwanego elementu lub

wyczerpania elementów listy. Je

Ğli liczbĊ elementów listy oznaczyü przez n, to

pesymistyczny czas dzia

áania tego algorytmu wynosi O(n), poniewaĪ w

najgorszym przypadku oka

Īe siĊ konieczne sprawdzenie wszystkich elementów

listy.

- 33 -

Wstawianie elementu do listy

Kod K.2.2 zawiera procedur

Ċ LISTA-WSTAW z parametrami L i x, która

do

áącza nowy element x na początek listy L.

K.2.2

LISTA-WSTAW(L,x)
1 next[x]

m

head[L]

2 je

Ğli head[L]

znil

3

to

prev[head[L]]

m

x

4 head[L]

m

x

5 prev[x]

m

nil

Wstawianie nowego elementu x na pocz

ątek listy niepustej listy L zilustrowano

na rys.2.4.

nil

e

1

head [L]

. . .

e

n

nil

nil

x

e

dod

e

1

head [L]

. . .

e

n

nil

nil

x

e

dod

e

1

head [L]

. . .

e

n

nil

x

e

dod

e

1

head [L]

. . .

e

n

nil

x

e

dod

a)

e

1

head [L]

. . .

e

n

nil

x

e

dod

b)

c)

e)

d)

Rys.2.4 Wstawianie nowego elementu do listy.

- 34 -

Przed wykonaniem procedury wstawiania head[L] jest wska

Ĩnikiem na

pocz

ątek listy, a x wskazuje na nowy element (rys.2.4a). Pierwszą operacją

wykonywan

ą w linii 1 kodu K.2.2 jest nadanie wskaĨnikowi next[x] wartoĞci

head[L], co prowadzi do sytuacji pokazanej na rys.2.4b. Kolejne operacje
odpowiadaj

ące liniom 3, 4 i 5 algorytmu przedstawiono odpowiednio na

rys.2.4c, 2.4d i 2.4e.

Czas dzia

áania procedury LISTA-WSTAW nie zaleĪy od liczby elementów w

li

Ğcie L, a zatem moĪe byü zapisany jako O(1).

Usuwanie elementu z listy

Wprowadzimy procedur

Ċ LISTA-USUē(L,x) (kod K.2.3), która usuwa z listy L

element x.

K.2.3

LISTA-USU

ē(L,x)

1 je

Ğli prev[x]

znil

2

to

next[prev[x]]

m

next[x]

3

inaczej

head[L]

m

next[x]

4 je

Ğli next[x]

znil

5

to

prev[next[x]]

m

prev[x]

Wprawdzie procedura LISTA-USU

ē dziaáa w czasie

O(1), jednak

pesymistyczny koszt usuni

Ċcia elementu x, dla którego zamiast wskaĨnika

znana by

áaby tylko zawartoĞü informacyjna (key[x]) wynosi O(n). Wynika to z

konieczno

Ğci uprzedniego znalezienia elementu x, co wymagaáoby uĪycia

funkcji LISTA-POSZ (kod K.2.1).

Przedstawienie list za pomoc

ą tablic

Reprezentacja list w pami

Ċci jest moĪliwa takĪe bez uĪycia wskaĨników. Jeden

ze sposobów polegaj

ący na uĪyciu tablic jednowymiarowych pokazano na

rys.2.5.

- 35 -

9

head [L]

nil

1

nil

16

4

3

4

5

nil

1

2

1

2

3

4

5

6

7

8

2

16

7

5

9

nil

next

key

a)

b)

prev

Rys.2.5 Reprezentowanie listy przy pomocy tablic jednowymiarowych.

Rysunek 2.5a przedstawia list

Ċ (9 16 4 1) jako strukturĊ zbudowaną przy

pomocy wska

Ĩników. Ta sama lista moĪe byü przedstawiona za pomocą trzech

tablic: next, key i prev w sposób pokazany na rys.2.5b. Tablica key zawiera
warto

Ğci kluczy (czĊĞü informacyjną) elementów listy, a wskaĨniki są

reprezentowane przez tablice next i prev. Zatem dla pewnego indeksu i warto

Ğci

prev[i], key[i] oraz next[i] le

Īące w kolumnie i okreĞlają pojedynczy element

listy. Na przyk

áad element listy o kluczu 16 posiada poprzednika, którym jest

element przechowywany w tablicy key z indeksem 7. Jest to element o warto

Ğci

klucza 9.

W podanym przyk

áadzie do reprezentacji list uĪyto trzech tablic. Innym

mo

Īliwym sposobem jest uĪycie do tego celu tylko jednej tablicy.

2.3 Stosy i kolejki

Stosy i kolejki reprezentuj

ą grupĊ obiektów, okreĞlanych jako struktury z

ograniczonym dost

Ċpem. Ograniczenie polega na tym, Īe tryb dodawania i

usuwania elementów jest z góry ustalony i charakterystyczny dla danej
struktury.

2.3.1 Stosy

Struktura nazywana stosem posiada ustalony element nazywany wierzcho

ákiem,

który jest jedynym dost

Ċpnym w danej chwili jej skáadnikiem. Sytuacja taka

oznacza,

Īe dowolna operacja usuwania ze stosu moĪe dotyczyü tylko jego

aktualnego wierzcho

áka. Ponadto dodanie nowego elementu do stosu jest

mo

Īliwe tylko przez umieszczenie tego elementu na „szczycie” stosu, tak aby

- 36 -

sta

á siĊ on nowym wierzchoákiem. Mówimy, Īe elementy stosu są obsáugiwane

wed

áug porządku LIFO (Last In First Out), co oznacza „ostatni przyszedá,

pierwszy wyszed

á”.

Sugestywn

ą ilustracją stosu moĪe byü pewna liczba talerzy poukáadanych jeden

na drugim. Przy dodawaniu kolejnego talerza

najbardziej

rozs

ądnym

post

Ċpowaniem jest umieszczenie go na samej górze. W przypadku pobierania

talerza, zdejmujemy ten, który znajduje si

Ċ na szczycie, tj. zostaá poáoĪony jako

ostatni.

Jako struktury reprezentuj

ącej stos w pamiĊci moĪna uĪyü tablicy

jednowymiarowej

. Dla tej tablicy okre

Ğlimy atrybut top[S] podający

numer (indeks) elementu ostatnio umieszczonego na stosie. Stos sk

áada siĊ

zatem z elementów

>

n

S ..

1

> @

@

> @

> @

>

@

S

top

S

,...,

2

S

S ,

1

, gdzie

> @

1

S

oznacza element na dnie

stosu, a

> @

>

@

S

top

S

> @

S

top

jest elementem na wierzcho

áku stosu (rys.2.6). Przyjmuje

si

Ċ, Īe jeĞli

, to stos jest pusty i próba pobrania elementu z takiego

stosu spowoduje komunikat o b

áĊdzie „niedomiaru“.

0

Rys.2.6 Stos.

S[1]

S[2]

S[3]

S[4]

15

top[S]=4

6

2

9

S[top[S]]= 9
S[1]= 15

Tradycyjnie operacj

Ċ umieszczania na stosie nazywa siĊ PUSH, a operacjĊ

zdejmowania ze stosu – POP. Pos

áugując siĊ zdefiniowaną tutaj „tablicową“

reprezentacj

ą stosu operacjĊ umieszczania elementu x na stosie S moĪna napisaü

w postaci prostej procedury (kod K.2.4).

K.2.4

PUSH(S,x)
1 top[S]

m

top[S]+1

2 S[top[S]]

m

x

Kod K.2.5 zawiera procedur

Ċ zdejmowania ze stosu. Procedura ta wykorzystuje

funkcj

Ċ STOS-PUSTY(S), sprawdzającą czy stos jest pusty (kod K.2.6)

- 37 -

K.2.5

POP(S)
1 je

Ğli STOS-PUSTY(S)

2

to

b

áąd „niedomiar”

3

inaczej

{top[S]

m

top[S]-1

4 { zwró

ü S[top[S]+1]}

K.2.6

STOS-PUSTY(S)
1 je

Ğli top[S]=0

2

to

TRUE

3

inaczej

FALSE

Nale

Īy zauwaĪyü, Īe uĪycie procedury PUSH wymaga podania dwóch

argumentów, podczas gdy w przypadku procedury POP wystarczy tylko jeden
(identyfikator stosu). Wynika to st

ąd, Īe pobieranym elementem stosu moĪe byü

w danej chwili tylko jego wierzcho

áek, tzn. element S[top[S]].

2.3.2 Kolejki

Poj

Ċciem kolejka okreĞla siĊ strukturĊ z ograniczonym dostĊpem, dla której

okre

Ğlono początek i koniec. Prostą ilustracją moĪe byü kolejka osób do kasy, w

której nowe osoby maj

ą prawo ustawiü siĊ na koĔcu, a obsáugiwana jest zawsze

osoba z pocz

ątku. Tak jak w przypadku stosu, procedura obsáugi kolejki ma

ogólnie przyj

Ċtą nazwĊ. Mówimy, Īe elementy kolejki są obsáugiwane wedáug

porz

ądku FIFO (First In First Out), co oznacza „pierwszy przyszedá, pierwszy

wyszed

á”

Podobnie jak dla stosu przyjmiemy tablicow

ą implementacjĊ kolejki zakáadając,

Īe elementy kolejki są pamiĊtane w tablicy jednowymiarowej

Q

.

Pos

áuĪymy siĊ nastĊpującymi atrybutami tablicy Q (rys.2.7):

> @

n

..

1

head[Q]

- indeks elementu znajduj

ącego siĊ na początku kolejki (gáowa),

tail[Q]

- indeks pierwszego wolnego elementu na ko

Ĕcu kolejki (ogon).

Q

head[Q]=7

15

1

2

3

4

5

6

7

8

9

10

11

12

6

9

8

4

13

14

15

tail[Q]=12

Q[7]=15

Rys.2.7 Kolejka.

W procedurach wstawiania i usuwania elementu z kolejki b

Ċdziemy zakáadaü,

Īe tablica

Q

jest cykliczna, tzn. po elemencie

>

n

..

1

@

> @

n

Q

nast

Ċpuje element

- 38 -

> @

1

Q

. Na pocz

ątku przyjmuje siĊ

> @

> @

1

Q

tail

Q

head

. Spe

ánienie warunku

oznacza,

Īe kolejka jest pusta. JeĞli natomiast zachodzi

równo

Ğü

> @

> @

Q

tail

Q

> @

head

> @

1



Q

tail

Q

head

, to kolejka jest pe

ána. Przyjmując tablicową

reprezentacj

ą kolejki operacjĊ umieszczania nowego elementu x w kolejce Q

mo

Īna napisaü w postaci procedury ENQUEUE(Q,x) (kod K.2.7), a operacjĊ

usuwania z kolejki jako funkcj

Ċ DEQUEUE(Q) (kod K.2.8).

1

2



2









 











7

6

4



5



 











7

6

4

8

9





K.2.7

ENQUEUE(Q,x)
1 Q[tail[Q]]

m

x

2 je

Ğli tail[Q]= length[Q]

3

to tail[Q]

m

1

4

inaczej tail[Q]

m

tail[Q]+1

K.2.8

DEQUEUE(Q)
1 x

m

Q[head[Q]]

2 je

Ğli head[Q]= length[Q]

3

to head[Q]

m

1

4

inaczej head[Q]

m

head[Q]+1

5 zwró

ü x

Obie procedury dzia

áają w czasie O(1). PrzyjĊto takĪe, Īe w przypadku

dodawania nowego elementu kolejka nie jest pe

ána, a w przypadku, usuwania,

kolejka nie jest pusta.

2.4 Obliczanie warto

Ğci wyraĪeĔ z wykorzystaniem stosu

Zastosowanie stosu mo

Īna pokazaü na przykáadzie obliczania wartoĞci prostych

wyra

ĪeĔ arytmetycznych, w których wystĊpują tylko liczby caákowite 0...9,

nawiasy ‘(‘ i ‘)' oraz operacje dodawania i mno

Īenia. Do klasy takich wyraĪeĔ

nale

Īą np.:





,





7

1

,

8

9



, itp.

Stos okazuje si

Ċ byü wygodnym miejscem do pamiĊtania wyników poĞrednich

w takich obliczeniach. Na przyk

áad wartoĞü wyraĪenia

5

mo

Īe byü wyznaczona w wyniku ciągu operacji na stosie pokazanych na

rys.2.8.

- 39 -

a)

ZERUJ(S) PUSH(S,5) PUSH(S,9)

5

5

9

b)

c)

PUSH(S,8)

PUSH(S,POP(S)+POP(S))

5

5

17

d)

e)

9

8

PUSH(S,4)

PUSH(S,POP(S)*POP(S))

5

5

17

f)

g)

17

4

4

6

PUSH(S,POP(S)*POP(S))

PUSH(S,6)

5

5

408

17

24

i)

h)

PUSH(S,7)

5

5

415

j)

k)

408

7

PUSH(S,POP(S)*POP(S))

PUSH(S,POP(S)+POP(S))

2075

l)

Rys.2.8 U

Īycie stosu do wyznaczania wartoĞci wyraĪenia.

Podczas wykonywania dowolnej operacji odpowiednie operandy s

ą pobierane

ze stosu, a wynik jest umieszczany tak

Īe na stosie. ZauwaĪmy, Īe taki sposób

wykonywania oblicze

Ĕ wymaga, aby operandy byáy umieszczone na stosie,

zanim zostanie napotkany znak operacji. Po

Īądane byáoby zatem, aby

wyra

Īenie zostaáo wczeĞniej zapisane w pewnej postaci poĞredniej, w której

operandy wyst

Ċpują zawsze przed znakiem operacji. Dla naszego wyraĪenia jest

to zatem ci

ąg znaków:

5 9 8 + 4 6 * * 7 + *.

Taki zapis wyra

ĪeĔ jest nazywany zapisem postfiksowym albo odwrotnym

zapisem polskim. W odró

Īnieniu od zapisu postfiksowego, tradycyjny zapis

matematyczny, gdzie operandy s

ą oddzielone znakiem operacji bĊdziemy

nazywa

ü zapisem infiksowym. Istotną wáaĞciwoĞcią zapisu postfiksowego jest

tak

Īe to, Īe nie wymaga on nawiasów. Pomimo braku nawiasów wyraĪenia są

obliczane od lewej strony do prawej we w

áaĞciwej kolejnoĞci. Notacja

- 40 -

postfiksowa okazuje si

Ċ byü idealnym zapisem poĞrednim dla wyraĪeĔ

arytmetycznych, które maj

ą byü obliczane za pomocą stosu. Mechanizm ten

mo

Īna zastosowaü w kalkulatorach i w komputerowej realizacji jĊzyków

programowania.

Naszym zadaniem jest opracowanie algorytmu, który przekszta

áca tradycyjny

zapis infiksowy w odwrotny zapis polski. Wcze

Ğniej jednak przedstawimy

pomocnicz

ą procedurĊ LISTA-ODWR(L) (kod K.2.9), która realizuje prostą,

ale przydatn

ą operacjĊ odwracania kolejnoĞci elementów w liĞcie L.

K.2.9

LISTA-ODWR(L)
1 x

m

head[L]

2 head[LR]

m

nil

3 dopóki x

znil

4 wykonuj { LISTA-WSTAW(LR,x)
5

x

m

next[x] }

6 head[L]

m

head[LR]

Procedura LISTA-ODWR(L) korzysta ze zmiennej roboczej LR, która jest typu
lista i s

áuĪy do budowania listy odwróconej. Wykorzystuje siĊ przy tym

przedstawion

ą wczeĞniej procedurĊ wstawiania nowego elementu do listy. Po

zbudowaniu listy odwróconej wska

Īnik na jej początek staje siĊ wartoĞcią

wska

Ĩnika na początek listy L (linia 6 w kodzie K.2.9). Kolejne etapy

odwracania przyk

áadowej listy (9 16 4) za pomocą procedury LISTA-

ODWR(L) pokazano na rysunku 2.9.

- 41 -

9

head [L]

nil

16

4

a)

head [LR]=nil

nil

9

head [L]

nil

16

4

b)

nil

9

head [L]

nil

16

4

d)

nil

9

head [LR]

nil

nil

4

head [LR]

nil

16

9

nil

9

head [L]

nil

16

4

c)

nil

16

head [LR]

nil

9

nil

9

head [L]

nil

16

4

e)

nil

4

head [LR]

nil

16

9

nil

Rys.2.9 Odwracanie listy.

Procedura odwracania listy zostanie wykorzystana w opisanym dalej
algorytmie INF-PSF przej

Ğcia od zapisu infiksowego do zapisu

postfiksowego. Przyk

áadowe wyraĪenie infiksowe jest przeksztaácane na

wyra

Īenie postfiksowe w sposób pokazany na rys.2.10.

- 42 -

tablica TWE

(

1

3

4

2

2

1

+

6

7

5

3

*

)

TWE,LWY

INF-PSF(

)

( 2 1 + 3 * )

lista LWY

Rys.2.10 Przej

Ğcie z zapisu infiksowego na postfiksowy.

Wej

Ğcie algorytmu stanowi tablica TWE zawierająca pojedyncze znaki

zadanego wyra

Īenia infiksowego, a wynik (odwrotny zapis polski) jest

otrzymywany w postaci listy wyj

Ğciowej LWY. Algorytm w postaci

procedury INF-PSF z parametrami TWE i LWY zawiera kod K.2.10.

K.2.10

INF-PSF(TWE, LWY)
1

top[STOS]

m

0

2

head[LWY]

m

nil

3

i

m

1

4

powtarzaj

5

je

Ğli TWE[i] jest liczb

ą

6

to

{ key[x]

m

TWE[i]

7

LISTA-WSTAW(LWY, x) }

8

inaczej je

Ğli TWE[i]=”+” lub TWE[i]=”*”

9

to

PUSH(STOS, TWE[i])

10

inaczej je

Ğli TWE[i]=”)”

11

to

{ key[x]

m

POP(STOS)

12

LISTA-WSTAW(LWY, x) }

13

i

m

i+1

14

a

Ī_do i>length[TWE]

15

je

Ğli STOS-PUSTY(STOS)

16

to

LISTA-ODWR(LWY)

17

inaczej

{ key[x]

m

POP(STOS)

18

LISTA-WSTAW(LWY,x)

19 LISTA-ODWR(LWY) }

Algorytm analizuje kolejne elementy tablicy wej

Ğciowej TWE. JeĞli kolejny

element tej tablicy zawiera operand (liczb

Ċ), wówczas jest ona niezwáocznie

umieszczana w li

Ğcie wyjĞciowej. Operacja ta jest realizowana w liniach 6 i 7 i

- 43 -

wymaga u

Īycia zmiennej pomocniczej x, która staje siĊ wskaĨnikiem do

do

áączanego elementu listy. Znaki operacji są tymczasowo umieszczane na

stosie (linia 9). Lewe nawiasy s

ą ignorowane, a napotkanie prawego nawiasu

oznacza,

Īe oba operandy dla operacji wykonywanej na danym poziomie

zagnie

ĪdĪenia obliczeĔ juĪ wystąpiáy i naleĪy pobraü ze stosu odpowiadający

im znak operacji oraz do

áączyü go do listy wyjĞciowej (linie 11 i 12). Dla

uproszczenia zak

áada siĊ, Īe na danym poziomie zagnieĪdĪenia wystĊpują

dok

áadnie dwa operandy poáączone znakiem operacji. NaleĪy takĪe zaznaczyü,

Īe algorytm nie zajmuje siĊ ewentualnymi báĊdami w wyraĪeniach.

Linie od 15 do 19 zawieraj

ą polecenia generujące koĔcową postaü wyniku.

Warto zauwa

Īyü, Īe lista wynikowa jest odwracana za pomocą procedury

LISTA-ODWR(LWY), dzi

Ċki czemu operandy i znaki operacji w wyraĪeniu

postfiksowym pojawiaj

ą siĊ w naturalnym porządku „od lewej do prawej”.

Jak ju

Ī wspomniano, gáównym powodem, dla którego stosujemy zapis

postfiksowy jest to,

Īe wartoĞü tak zapisanego wyraĪenia moĪe byü áatwo

obliczona przy pomocy stosu. Algorytm wykonuj

ący takie obliczenie nie jest

zbyt skomplikowany, a przy jego opracowaniu pomocn

ą moĪe okazaü siĊ

analiza przyk

áadu obliczania wyraĪenia 5 9 8 + 4 6 * * 7 + * z rys.2.8.

2.5 Grafy

2.5.1

Grafy skierowane i nieskierowane

Zdefiniujemy podstawowe poj

Ċcia oraz sposób reprezentowania w pamiĊci dla

popularnej klasy struktur nazywanych grafami.

Definicja 2.1

Grafem nazywamy par

Ċ zbiorów





E

V ,

G

, gdzie V jest sko

Ĕczonym zbiorem

wierzcho

áków, a E jest zbiorem krawĊdzi. Przykáady grafów pokazano na

rys.2.11.

- 44 -

a)

b)

1

2

4

5

1

2

5

4

3

3

6

Rys.2.11 Przyk

áady grafów: a) graf skierowany, b) graf nieskierowany.

Na rys.2.11a przedstawiono graf okre

Ğlany jako nieskierowany, dla którego

^

`

5

,

4

,

3

,

2

,

1

V

, a

             

^

`

5

,

4

,

4

,

3

,

5

,

2

,

4

,

2

,

3

,

2

,

5

,

1

,

2

,

1

E

.

Zbiór kraw

Ċdzi E takiego grafu jest zatem zbiorem par





v

u,

, gdzie

u

.

Zauwa

Īmy, Īe pary

i

V

v



,





v

u,





v

u,

oznaczaj

ą tĊ samą krawĊdĨ, a ponadto

(nie wyst

Ċpują pĊtle, tj. krawĊdzie prowadzące do tego samego wierzchoáka).

Zbiór kraw

Ċdzi E w grafie nieskierowanym jest zbiorem nieuporządkowanych

par wierzcho

áków

. Kraw

ĊdĨ

v

u

z



v

u,







v

u,

jest okre

Ğlana jako incydentna z

wierzcho

ákami u i v.

Na rys.2.11b pokazano graf skierowany, w którym

^

`

6

,

5

,

4

,

3

,

2

,

1

V

, a

               

^

`

6

,

6

,

4

,

5

,

2

,

4

,

6

,

3

,

5

,

3

,

5

,

2

,

4

,

1

,

2

,

1

E

.

Zauwa

Īmy, Īe w grafie skierowanym mogą wystąpiü pĊtle do tego samego

wierzcho

áka, a krawĊdĨ





v

u,

jest tutaj okre

Ğlana, jako wychodząca

z wierzcho

áka u i wchodząca do wierzchoáka v.

Je

Ğli

jest kraw

Ċdzią grafu



v

u,







E

V ,

G

, to mówimy,

Īe wierzchoáek u jest

s

ąsiedni do wierzchoáka v. Fakt ten dla grafu skierowanego moĪna zapisaü jako

v

u

o

.

Liczb

Ċ wszystkich wierzchoáków grafu oznaczymy symbolem

V

, a liczb

Ċ

kraw

Ċdzi symbolem

E

.

- 45 -

Definicja 2.2

Stopniem wierzcho

áka w grafie nieskierowanym nazywamy liczbĊ incydentnych

z nim kraw

Ċdzi. W przypadku wierzchoáków grafu skierowanego operuje siĊ

poj

Ċciami stopnia wyjĞciowego (liczba krawĊdzi wychodzących) i stopnia

wej

Ğciowego (liczba krawĊdzi wchodzących).

Definicja 2.3

ĝcieĪką (drogą) dáugoĞci k z wierzchoáka

do wierzcho

áka

u

uc

w grafie

nazywamy ci

ąg wierzchoáków



E

V

G

,



k

v

v

v

,...,

,

1

0

, takich,

Īe

i

oraz

dla

0

v

u

k

v

u

c





E

v

v

i

i





,

1

k

i

,...,

1

.

Definicja 2.4

Cyklem w grafie skierowanym nazywamy

ĞcieĪkĊ

k

v

v

v

,...,

,

1

0

zawieraj

ącą co

najmniej jedn

ą krawĊdĨ, dla której

k

v

v

0

.

Definicja 2.5

Cyklem w grafie nieskierowanym nazywamy

ĞcieĪkĊ

k

v

v

v

,...,

,

1

0

, dla której

, wierzcho

áki

s

ą róĪne i

.

k

v

v

0

k

v

v

v

,...,

,

2

1

2

t

k

Graf nie zawieraj

ący cykli nazywamy acyklicznym.

Definicja 2.6

Graf nieskierowany jest spójny je

Ğli kaĪda para wierzchoáków jest poáączona

ĞcieĪką. W przypadku grafu skierowanego istnieje pojĊcie silnej spójnoĞci,
które oznacza,

Īe kaĪde dwa wierzchoáki są osiągalne jeden z drugiego.

2.5.2

Sposoby reprezentowania grafów

Istniej

ą dwa podstawowe sposoby reprezentowania grafów. Są to:

1. Listy s

ąsiedztwa

2. Macierze

s

ąsiedztwa.

Przedstawienie grafów za pomoc

ą list sąsiedztwa

- 46 -

Jako struktur

Ċ reprezentującą graf





E

V

G

,

rozwa

Īamy tablicĊ Adj rozmiaru

V

, której elementami s

ą listy odpowiadające wierzchoákom z V. Dla kaĪdego

wierzcho

áka

list

Ċ

V

u



> @

u

Adj

tworz

ą wszystkie wierzchoáki v takie, Īe

. Listy s

ąsiedztwa dla grafów z rys.2.11a i 2.11b przedstawiono

odpowiednio na rys.2.12a i 2.12b.





E

v



u,

a)

b)

1

2

3

4

2

1

2

2

3

2

nil

5

5

4

5

5

4

1

3

nil

4

nil

1

2

3

4

2

5

6

2

5

4

4

nil

5

nil

nil

nil

nil

6

6

nil

nil

nil

Rys.2.12 Listy s

ąsiedztwa.

Zalet

ą reprezentacji listowej jest to, Īe umoĪliwia ona przedstawienie w zwarty

sposób grafów rzadkich, dla których

2

V

E



. Przy takiej reprezentacji

rozmiar wymaganej pami

Ċci wynosi













E

V

O

E

V

O



,

max

.

Przedstawienie grafów za pomoc

ą macierzy sąsiedztwa

Graf

G

mo

Īe byü reprezentowany takĪe przez tablicĊ dwuwymiarową,

sk

áadającą siĊ wyáącznie z zer i jedynek, nazywaną macierzą sąsiedztwa.

Zak

áadamy wtedy, Īe wierzchoáki grafu są ponumerowane od 1 do



E

V ,



V

. Macierz

s

ąsiedztwa jest tablicą dwuwymiarową

 

ij

a

A





V

j

V

i

d

d

d

d

1

,

1

, gdzie

 

¯

®

­



razie.

przeciwnym

w

0

E,

,

jesli

1

j

i

a

ij

Macierze reprezentuj

ące grafy z rys.2.11a i 2.11b przedstawiono odpowiednio

na rys.2.13a i 2.13b.

- 47 -

a)

b)

1

2

3

4

1

2 3

4

0

0

0

1

1

1

1

1

1

0

1

1 0

0

0

0

5

5

1

1

0

1

1

0 1

1

0

1

2

3

4

1

2 3

4

0

1

0

1

0

0

0

0

0

0

1

0 0

0

0

0

5

5

0

1

1

0

0

0 1

0

0

0

0 0

0

0

0

0

1

0

0

1

6

6

Rys.2.13 Macierze s

ąsiedztwa.

Taka reprezentacja jest korzystna wówczas, gdy graf jest „g

Ċsty” tzn,

E

jest

bliskie

2

V

lub gdy wyst

Ċpuje potrzeba szybkiego stwierdzania, czy istnieje

kraw

ĊdĨ áącząca dwa zadane wierzchoáki. Rozmiar wymaganej pamiĊci wynosi

 

2

V

O

. Dla grafu nieskierowanego

pami

Ċü moĪna zaoszczĊdziü,

wykorzystuj

ąc symetrycznoĞü macierzy sąsiedztwa.

2.6 Drzewa

2.6.1 Definicje

Zdefiniujemy podstawowe poj

Ċcia odnoszące siĊ obszernej klasy struktur

danych okre

Ğlanych jako drzewa.

Definicja 2.7

Drzewem zorientowanym (skierowanym) nazywamy skierowany graf acykliczny
spe

ániający nastĊpujące trzy warunki:

1. Istnieje dok

áadnie jeden wierzchoáek, do którego nie dochodzi Īadna

kraw

ĊdĨ. Wierzchoáek ten nazywamy korzeniem drzewa.

2. Dla dowolnego wierzcho

áka v w drzewie istnieje droga prowadząca od

korzenia do tego wierzcho

áka i jest to droga jedyna.

3. Ka

Īdy wierzchoáek nie bĊdący korzeniem ma dokáadnie jedną krawĊdĨ

wchodz

ącą do niego.

- 48 -

Dla drzewa zorientowanego z rys.2.14 zbiorem wierzcho

áków jest

, a zbiorem kraw

Ċdzi

^

7

,

6

,

5

,

4

,

3

,

2

,

1

V

`

          

^

`

7

,

3

6

,

2

,

5

,

2

,

4

,

2

,

3

,

1

,

2

,

1

E

.

Korzeniem jest wierzcho

áek 1.

Cz

Ċsto rozwaĪa siĊ drzewa niezorientowane, tj. takie, w których istnieje droga

nie tylko od korzenia do pewnego w

Ċzáa lecz droga w obu kierunkach.

Definicja 2.8

Drzewem niezorientowanym nazywamy graf nieskierowany, który jest:

1. Spójny tj. istnieje droga pomi

Ċdzy dwoma dowolnymi wierzchoákami.

2. Acykliczny.
3. Posiada

wyró

Īniony wierzchoáek nazywany korzeniem

Drzewa niezorientowane b

Ċdziemy przedstawiaü graficznie w sposób pokazany

na rys. 2.15.

1

2

6

4

3

7

5

1

2

6

4

3

7

5

Rys.2.14 Drzewo zorientowane.

Rys.2.15 Drzewo niezorientowane.

W przypadku drzew wierzcho

áki czĊsto nazywa siĊ wĊzáami.

Definicja 2.9

Je

Ğli rozwaĪyü krawĊdĨ





E

w

v



,

w drzewie zorientowanym, to w

Ċzeá v jest

nazywany rodzicem wierzcho

áka w, a wĊzeá w jest nazywany synem

wierzcho

áka v. PojĊcie rodzica i syna ma zastosowanie takĪe dla drzew

niezorientowanych. W tym przypadku tak

Īe rozwaĪa siĊ krawĊdĨ

, z

tym,

Īe wĊzeá v jest wĊzáem poáoĪonym o jeden poziom wyĪej w strukturze

drzewa ni

Ī wĊzeá w.





E

w

v



,

Definicja 2.10

Je

Īeli w drzewie zorientowanym istnieje droga prowadząca od wĊzáa v do wĊzáa

w, to w

Ċzeá w nazywamy potomkiem wĊzáa v, a wĊzeá v nazywamy przodkiem

w

Ċzáa w. Dla drzewa niezorientowanego naleĪy zaznaczyü, Īe wĊzeá v jest

po

áoĪony wyĪej w strukturze drzewa niĪ wĊzeá w.

- 49 -

Definicja 2.11

Pewien w

Ċzeá v wraz ze wszystkimi jego potomkami nazywamy poddrzewem.

W

Ċzeá v jest wtedy okreĞlany jako korzeĔ tego poddrzewa.

Definicja 2.12

W

Ċzeá nie posiadający potomków nazywamy liĞciem.

Definicja 2.13

G

áĊbokoĞcią wĊzáa nazywamy dáugoĞü drogi od korzenia do tego wĊzáa.

Definicja 2.14

Wysoko

Ğü wĊzáa oznacza maksymalną dáugoĞü drogi od tego wĊzáa do liĞcia.

Wysoko

Ğcią drzewa jest zatem wysokoĞü jego korzenia.

W wielu zastosowaniach przydatne s

ą tzw. drzewa uporządkowane.

Definicja 2.15

Drzewem uporz

ądkowanym nazywamy drzewo, w którym zbiór synów kaĪdego

w

Ċzáa jest uporządkowany. W graficznej reprezentacji drzew uporządkowanych

b

Ċdziemy zakáadaü, Īe synowie kaĪdego wĊzáa są uporządkowani od lewej

strony do prawej.

2.6.2 Drzewa binarne

Wa

Īną klasĊ drzew uporządkowanych stanowią drzewa binarne.

Definicja 2.16

Drzewem binarnym nazywamy drzewo spe

ániające dwa warunki:

i. Ka

Īdy wĊzeá posiada co najwyĪej dwóch synów

ii. W

Ğród synów kaĪdego wĊzáa da siĊ wyróĪniü lewy i prawy.

Przyk

áad drzewa binarnego przedstawia rys. 2.16a, a prosty sposób

reprezentowania tego drzewa za pomoc

ą tablic pokazano na rys. 2.16b.

- 50 -

1

2

4

3

6

7

8

9

5

a)

b)

LS

2

RS

1

2

6

3

4

0

3

0

0

4

5

0

5

0

7

6

8

0

7

0

0

8

9

0

9

0

Rys.2.16 Reprezentowanie drzewa binarnego za pomoc

ą tablic.

W

proponowanym tutaj sposobie reprezentowania drzewa binarnego

wykorzystuje si

Ċ dwie tablice jednowymiarowe LS i RS. Dla pewnego indeksu

i elementy tablic LS[i] i RS[i] s

áuĪą do pamiĊtania indeksów odpowiednio

lewego i prawego syna w

Ċzáa i.

Ze wzgl

Ċdów praktycznych związanych z zastosowaniem drzew binarnych

w algorytmach istotny jest sposób (kolejno

Ğü) przechodzenia wĊzáów takiego

drzewa. Drzewo pokazane na rys.2.17, które pos

áuĪy jako przykáadowe podczas

prezentowania ró

Īnych metod przechodzenia drzewa binarnego.

1

2

5

4

3

6

8

7

Rys.2.17 Przyk

áad drzewa binarnego.

Zdefiniowane zostan

ą trzy metody przechodzenia (odwiedzania) wĊzáów

drzewa binarnego.

Przechodzenie drzewa metod

ą preorder

Odwiedzanie kolejnych w

Ċzáów drzewa binarnego metodą preorder odbywa siĊ

wed

áug algorytmu:

1. Odwied

Ĩ pewien wĊzeá.

2. Przejd

Ĩ metodą preorder kolejno poddrzewa: lewe i prawe, których

korzeniami s

ą synowie rozwaĪanego wĊzáa.

- 51 -

Ogólny schemat metody preorder przedstawiono na rys.2.18a, a kolejno

Ğü

przechodzenia w

Ċzáów drzewa binarnego z rys.2.17 zaznaczono na rys.2.18b.

Przechodzenie rozpocz

Ċto od korzenia.

1

2

3

a)

1

2

5

4

3

6

8

7

1

8

6

7

2

5

4

3

b)

Rys.2.18 Ilustracja metody preorder.

Do okre

Ğlenia metody preorder uĪyto samego definiowanego pojĊcia (metoda

preorder). Taki sposób definiowania nazywa si

Ċ rekurencyjnym i bĊdzie

zastosowany tak

Īe przy definiowaniu dwóch pozostaáych metod.

Przechodzenie drzewa metod

ą postorder

Odwiedzanie kolejnych w

Ċzáów drzewa binarnego metodą postorder odbywa

si

Ċ wedáug algorytmu:

1. Przejd

Ĩ metodą postorder kolejne poddrzewa: lewe i prawe, których

korzeniami s

ą synowie rozwaĪanego wĊzáa.

2. Odwied

Ĩ rozwaĪany wĊzeá.

Ogólny schemat metody postorder przedstawiono na rys.2.19a, a kolejno

Ğü

przechodzenia w

Ċzáów drzewa binarnego z rys.2.17 zaznaczono na rys.2.19b.

3

1

2

a)

1

2

5

4

3

6

8

7

8

5

7

6

4

3

1

2

b)

Rys.2.19 Ilustracja metody postorder.

Przechodzenie drzewa metod

ą inorder

Odwiedzanie kolejnych w

Ċzáów drzewa binarnego metodą inorder odbywa siĊ

wed

áug algorytmu:

- 52 -

1. Przejd

Ĩ metodą inorder lewe poddrzewo potomków rozwaĪanego wĊzáa.

2. Odwied

Ĩ rozwaĪany wĊzeá.

3. Przejd

Ĩ metodą inorder prawe poddrzewo potomków rozwaĪanego wĊzáa.

Ogólny schemat metody inorder przedstawiono na rys.2.20a, a kolejno

Ğü

przechodzenia w

Ċzáów drzewa binarnego z rys.2.17 zaznaczono na rys.2.20b.

2

1

3

a)

1

2

5

4

3

6

8

7

5

7

8

6

3

4

2

1

b)

Rys.2.20 Ilustracja metody inorder.

Drzewa regularne i pe

áne

Zdefiniujemy jeszcze dwie podklasy drzew binarnych tj. drzewa regularne i
drzewa pe

áne.

Definicja 2.17

Regularnym drzewem binarnym nazywamy drzewo, w którym ka

Īdy z wĊzáów

jest albo li

Ğciem, albo posiada jednoczeĞnie lewego i prawego syna.

a)

b)

Rys.2.21 Drzewa binarne: regularne (a) i nieregularne (b).

Zgodnie z definicj

ą 2.17 drzewo na rys.2.21a jest regularne, podczas gdy

drzewo na rys.2.21b nie jest.

Definicja 2.18

Drzewo binarne nazywamy pe

ánym gdy istnieje liczba k taka, Īe dla kaĪdego

w

Ċzáa o gáĊbokoĞci mniejszej niĪ k wystĊpują oba wĊzáy bĊdące jego synami, a

ka

Īdy wĊzeá o gáĊbokoĞci k jest liĞciem.

- 53 -

a)

b)

Rys.2.22 Drzewa binarne: pe

áne (a) i niepeáne (b).

Zatem pe

áne drzewo binarne to takie drzewo, w którym dla wszystkich wĊzáów

wewn

Ċtrznych (tj. nie bĊdących liĞümi) wystĊpują jednoczeĞnie obaj synowie, a

g

áĊbokoĞü wszystkich liĞci jest jednakowa. Zgodnie z definicją 2.18 drzewo na

rys.2.22a jest pe

áne, podczas gdy drzewo na rys.2.22b nie jest.

2.6.3 U

Īycie struktur wskaĨnikowych

Podobnie jak listy, drzewa cz

Ċsto są reprezentowane przy uĪyciu struktur ze

wska

Ĩnikami. Analogicznie do elementów listy, wĊzáy drzewa są wtedy

strukturami o kilku polach, wsród których wyst

Ċpuje pole klucza oraz

dodatkowe pola przeznaczone do pami

Ċtania wskaĨników do innych wĊzáów

(rys.2.23). Liczba i sposób interpretacji tych wska

Ĩników na ogóá zaleĪy od

rodzaju drzewa.

key

...

Rys.2.23 W

Ċzeá drzewa reprezentowanego za pomocą struktur ze wskaĨnikami.

Drzewa binarne

Struktura pojedynczego w

Ċzáa drzewa binarnego jest pokazana na rys.2.24.

key

p

left right

Rys.2.24 W

Ċzeá drzewa binarnego jako struktura ze wskaĨnikami.

W ka

Īdym wĊĨle drzewa binarnego jest pamiĊtana czĊĞü informacyjna wĊzáa

(pole key) oraz wska

Ĩniki p - do wĊzáa rodzica, left – do lewego syna i right –

do prawego syna tego w

Ċzáa. W pseudokodzie dla pewnego wĊzáa x operowaü

- 54 -

b

Ċdziemy odpowiednio atrybutami key[x], p[x], left[x] oraz right[x]. JeĞli

p[x]=nil, to w

Ċzeá x jest korzeniem. JeĞli natomiast left[x]=nil lub right[x]=nil to

w

Ċzeá x nie ma odpowiednio lewego lub prawego syna. Atrybut root[T] drzewa

T oznacza wska

Ĩnik na korzeĔ drzewa. JeĞli root[T]=nil to drzewo jest puste.

Przyk

áad reprezentowania drzewa binarnego z rys.2.25a przy uĪyciu

wska

Ĩników pokazano na rys.2.25b.

a)

1

3

2

5

4

6

1

nil

3

2

4

5

6

root[ ]

T

b)

nil

nil

nil

nil

nil

nil

nil

Rys.2.25 Proste drzewo binarne jako struktura ze wska

Ĩnikami.

Drzewa o dowolnej strukturze

W przypadku je

Ğli na strukturĊ drzewa nie nakáada siĊ wstĊpnych ograniczeĔ,

tzn. liczba synów ka

Īdego wĊzáa nie jest z góry ustalona, bardziej odpowiednia

dla pojedynczego w

Ċzáa jest struktura pokazana na rys.2.26. UmoĪliwia ona

reprezentacj

Ċ dowolnego drzewa o n wĊzáach w pamiĊci

 

n

O

.

key

p

leftchild rightsibling

Rys.2.26 W

Ċzeá drzewa dowolnego jako struktura ze wskaĨnikami.

W ka

Īdym wĊĨle drzewa wystĊpują teraz nastĊpujące pola:

p[x]

- wska

Ĩnik na wĊzeá-rodzic,

key[x] -

zawarto

Ğü informacyjna wĊzáa,

leftchild[x]

- wska

Īnik na wĊzeá-syn poáoĪony najbardziej z lewej,

rightsibling[x] - wska

Īnik na prawego „brata” tj. prawy sąsiedni wĊzeá

b

Ċdący synem tego samego wĊzáa-rodzica.

- 55 -

W pseudokodzie dla pewnego w

Ċzáa x operowaü bĊdziemy odpowiednio

atrybutami p[x], key[x], leftchild[x] oraz rightsibling[x]. Je

Ğli wĊzeá x nie ma

synów, to leftchild[x]=nil. Je

Ğli natomiast jest on najbardziej na prawo

po

áoĪonym synem pewnego wĊzáa to rightsibling[x]=nil. Przykáad

reprezentowania drzewa z rys.2.27 przy u

Īyciu wskaĨników pokazano na

rys.2.28.

A

D

B

F

E

C

I

G

H

J

L

M

N

K

Rys.2.27 Drzewo o strukturze dowolnej.

C

B

K

E

F

D

nil

nil

nil

nil

A

nil

root[ ]

T

nil

nil

I

J

nil

G

H

nil

nil

M

N

nil

nil

nil

L

nil

nil

nil

Rys.2.28 Drzewo z rys.2.27 jako struktura ze wska

Ĩnikami.

2.7 Rekursja

Rekursj

Ċ nazywaną takĪe rekurencją zastosowaliĞmy juĪ, definiując metody

przechodzenia w

Ċzáów drzewa binarnego.

- 56 -

Zastosowanie rekurencji cz

Ċsto prowadzi do bardziej przejrzystych i

zrozumia

áych definicji i algorytmów. Przykáadami są m.in. takĪe rekurencyjne

definicje listy i drzewa binarnego.

Definicja 2.19 (Rekurencyjna definicja listy)

List

ą nazywamy strukturĊ zdefiniowaną na skoĔczonym zbiorze elementów,

która:
x albo nie zawiera Īadnych elementów i jest nazywana listą pustą,
x albo jest konkatenacją (poáączeniem) elementu i listy.

Definicja 2.20 (Rekurencyjna definicja drzewa binarnego)

Drzewo binarne jest struktur

ą zdefiniowaną na skoĔczonym zbiorze wĊzáów w

ten sposób,

Īe:

x albo nie zawiera Īadnych wĊzáów i jest nazywane drzewem pustym,
x albo skáada siĊ z trzech rozáącznych zbiorów wĊzáów: korzenia, drzewa

binarnego nazywanego lewym poddrzewem oraz drzewa binarnego
nazywanego prawym poddrzewem.

Rekurencj

Ċ stosuje siĊ powszechnie takĪe jako metodĊ organizacji obliczeĔ.

Definicja 2.21

Procedur

Ċ, która bezpoĞrednio lub poĞrednio wywoáuje samą siebie nazywamy

rekurencyjn

ą.

Przyk

áady algorytmów rekurencyjnych

Przyk

áad 2.1

Typowym zadaniem, gdzie mo

Īna zastosowaü rekurencjĊ jest obliczanie potĊgi

dodatniej liczby m wed

áug zaleĪnoĞci:

¯

®

­

t

u



0

dla

1

dla

1

1

n

n

m

m

m

n

n

.

(2.1)

Zak

áadamy, Īe wykáadnik potĊgi n przyjmuje wartoĞci caákowite nieujemne. Jak

wynika z zale

ĪnoĞci (2.1) w celu obliczenia n-tej potĊgi liczby m naleĪy

obliczy

ü (n-1)-szą potĊgĊ m i pomnoĪyü otrzymaną wartoĞü przez m.

- 57 -

Przypadkiem szczególnym jest n=0, kiedy warto

Ğü potĊgi wynosi 1. Algorytm

taki realizuje procedura rekurencyjna K.2.12.

K.2.12

POT

ĉGA-M-DO-N(m,n)

1

je

Ğli n=0

2

to zwró

ü 1

3

inaczej zwró

ü (m * POT

ĉGA-M-DO-N(m,n-1))

W kolejnym wywo

áaniu procedura POTĉGA-M-DO-N sprawdza wartoĞü

wyk

áadnika potĊgi n. JeĞli wartoĞü ta wynosi 0, wówczas jako wynikiem tego

wywo

áania procedury jest wartoĞü 1. W przeciwnym razie procedura wywoáuje

sam

ą siebie w celu obliczenia

m

, obliczona warto

Ğü jest mnoĪona przez m,

po czym obliczony iloczyn jest zwracany jako efekt bie

Īącego wywoáania

procedury.

1



n

Dzia

áanie procedury rekurencyjnej áatwiej jest Ğledziü przy pomocy prostej

symulacji graficznej, przedstawiaj

ącej kolejne wywoáania oraz zwracane

warto

Ğci [8]. Na rys.2.29 pokazano w ten sposób porządek wywoáaĔ

rekrencyjnych oraz zwracane warto

Ğci podczas obliczania wartoĞci

3

.

4

Wywoáanie: 1

Warto

Ğü: 81

m: 3
n: 4

Wywoáanie: 2

Warto

Ğü: 27

m: 3
n: 3

Wywoáanie: 3

Warto

Ğü: 9

m: 3
n: 2

Wywoáanie: 4

Warto

Ğü: 3

m: 3
n: 1

Wywoáanie: 5

Warto

Ğü: 1

m: 3
n: 0

Rys.2.29 Ilustracja wywo

áaĔ w procedurze rekurencyjnej obliczania potegi.

Pierwsze wywo

áanie procedury ma postaü, POTĉGA-M-DO-N(3,4), zatem

najbardziej po

áoĪony na lewo prostokąt pokazuje wartoĞci parametrów m i n

jako równe odpowiednio 3 i 4. W kolejnych wywo

áaniach wartoĞü n zmniejsza

si

Ċ kaĪdorazowo o 1, aĪ do osiągniĊcia wartoĞci 0, co koĔczy dalsze wywoáania.

Wówczas s

ą obliczane wartoĞci kolejnych potĊg i zwracane na coraz wyĪsze

poziomy wywo

áaĔ, przy czym na najwyĪszy poziom jest zwracany wynik

ko

Ĕcowy wynoszący 81.

Przyk

áad 2.2

Jako drugi przyk

áad rozwaĪymy przedstawiony w [1] algorytm przechodzenia

metod

ą inorder drzewa binarnego reprezentowanego za pomocą tablic LS i RS

(zob.rys.2.16). Procedura przechodzenia jest przedstawiona jako kod K.2.13.

- 58 -

K.2.13

DRZB-INORDER(w

Ċzeá)

1

je

Ğli LS[w

Ċzeá]z0

2

to

DRZB-INORDER(LS[w

Ċzeá])

3

NUMER[w

Ċzeá]

m

licznik

4

licznik

m

licznik+1

5

je

Ğli RS[w

Ċzeá]z0

6

to

DRZB-INORDER(RS[w

Ċzeá])

W algorytmie przyj

Ċto, Īe istnieje pewna zmienna globalna licznik, na początku

równa 1. Przy pierwszym wywo

áaniu procedury parametr wejĞciowy wĊzeá

powinien mie

ü takĪe wartoĞü 1. Wynikiem koĔcowym jest wypeánienie tablicy

NUMER okre

Ğlającej kolejnoĞü przechodzenia wĊzáów drzewa w ten sposób, Īe

element NUMER[i] zawiera liczb

Ċ naturalną pokazującą jako który z kolei jest

odwiedzany w

Ċzeá i.

Pytania kontrolne

1. Omówi

ü listĊ dwukierunkową i jej reprezentacjĊ przy uĪyciu wskaĨników.

2. Przedstawi

ü podstawowe operacje na listach:

a) przeszukiwanie listy;
b) w

áączanie nowego elementu;

c) usuwanie z listy;
d) odwracanie kolejno

Ğci elementów.

3.

Omówi

ü stos i jego reprezentacjĊ tablicową. Przedstawiü podstawowe

operacje na stosie.

4.

Omówi

ü kolejkĊ i jej reprezentacjĊ tablicową. Przedstawiü podstawowe

operacje dla kolejki.

5.

Przedstawi

ü algorytm przejĞcia od zapisu infiksowego na zapis

postfiksowy dla prostych wyra

ĪeĔ.

6. Omówi

ü sposoby przedstawienia listy za pomocą:

a) kilku tablic;

- 59 -

b) jednej tablicy.

7. Poda

ü definicjĊ i sposoby reprezentacji grafów.

8. Poda

ü definicjĊ i sposoby reprezentacji drzew.

9. Poda

ü rekurencyjną definicjĊ listy i drzewa.

Zadania

1. Zaproponowa

ü sposób przedstawienia stosu za pomocą listy. Napisaü

procedury POP i PUSH dla reprezentacji listowej.

2. Zaproponowa

ü sposób przedstawienia kolejki za pomocą listy. Napisaü

procedury ENQUEUE i DEQUEUE dla reprezentacji listowej.

3. Napisa

ü w pseudokodzie algorytm wyznaczania wartoĞci prostych wyraĪeĔ

zapisanych w notacji postfiksowej. Zak

áada siĊ, Īe wyraĪenia zawierają

tylko pojedyncze cyfry oraz znaki operacji + i *. Nale

Īy wykorzystaü stos.

4. Napisa

ü algorytm zliczania elementów w podanej liĞcie:

a) bez wykorzystania rekursji;
b) z wykorzystaniem rekursji.

5. Rozwa

Īyü listy zagnieĪdĪone, tj. takie, których elementy mogą same byü

listami. Stosuj

ąc rekursjĊ napisaü algorytm wyznaczający ogólną liczbĊ

elementów w listach o dowolnym stopniu zagnie

ĪdĪenia.

6.

Wie

Īe Hanoi. Stosując rekursjĊ naleĪy zaprogramowaü przeniesienie n

dysków z pr

Ċta A na prĊt B, wykorzystując przy tym prĊt C jako

pomocniczy. Funkcja powinna zwraca

ü iloĞü ruchów potrzebnych do

wykonania takiej operacji. Wej

Ğciem jest liczba dysków n.

Powinny przy tym by

ü speánione nastĊpujące warunki:

- tylko jeden dysk moĪe byü przenoszony równoczeĞnie,
- wszystkie dyski mają róĪne Ğrednice i nigdy dysk wiĊkszy nie moĪe byü

po

áoĪony na mniejszym,

- wyjĞciowym poáoĪeniem jest sytuacja na rysunku.

- 60 -

3

Zastosowanie drzew i algorytmy przeszukiwania

3.1 Drzewa przeszukiwa

Ĕ binarnych

Drzewa przeszukiwa

Ĕ binarnych okreĞlane takĪe jako drzewa BST (binary

search trees) stanowi

ą specjalną klasĊ drzew binarnych, dla których moĪna

stosunkowo

áatwo skonstruowaü podstawowe algorytmy jak: wyszukiwanie,

minimum, maksimum, do

áączanie itd. Podstawowe operacje na drzewach BST

wymagaj

ą czasu proporcjonalnego do wysokoĞci drzewa.

Definicja 3.1

Drzewem przeszukiwa

Ĕ binarnych (BST) nazywamy drzewo binarne, w którym

warto

Ğci kluczy są przechowywane w taki sposób, aby speániaáy tzw. wáasnoĞü

drzewa BST, zgodnie z któr

ą dla dowolnego wĊzáa x zachodzi:

x jeĞli y jest wĊzáem lewego poddrzewa wĊzáa x, to

> @

>

x

key

y

key

@

d

oraz

x jeĞli y jest wĊzáem prawego poddrzewa wĊzáa x, to

> @

>

x

key

y

key

t

@

.

Przyk

áady drzew BST przedstawia rys. 3.1.

a)

5

3

5

2

7

8

b)

2

5

8

5

3

7

Rys.3.1 Przyk

áady drzew BST.

W drzewach BST z rys.3.1a i 3.1b wyst

Ċpują dokáadnie te same wartoĞci

kluczy, lecz ze wzgl

Ċdu na wiĊkszą wysokoĞü drzewo z rys.3.1b jest mniej

efektywne podczas wykonywania typowych operacji.

- 61 -

Podana w

áasnoĞü drzewa BST pozwala w prosty sposób posortowaü rosnąco

(wypisa

ü w porządku rosnącym) klucze wszystkich wĊzáów drzewa. W tym

celu wystarczy wykorzysta

ü metodĊ przechodzenia inorder, jak uczyniono to w

algorytmie przedstawionym jako kod K.3.1.

K.3.1

DRZB-INORDER1(x)
1

je

Ğli x

z

nil

2

to

{ DRZB-INORDER1(left[x])

3

wypisz key[x]

4

DRZB-INORDER1(right[x]) }

W algorytmie za

áoĪono, Īe drzewo BST jest reprezentowane za pomocą

struktury ze wska

Ĩnikami. Parametrem procedury przy pierwszym jej

wywo

áaniu jest wskaĨnik na wĊzeá-korzeĔ. Procedura sprawdza, czy rozwaĪany

w

Ċzeá istnieje (linia 1), po czym realizuje kolejno nastĊpujące czynnoĞci:

wywo

áuje przechodzenie lewego poddrzewa, wypisuje wartoĞü klucza w wĊĨle

oraz wywo

áuje przechodzenie prawego poddrzewa. W ten sposób dla drzewa z

rys.3.1 zostanie wypisany ci

ąg kluczy: 2 3 5 5 7 8.

3.1.1

Przeszukiwanie w drzewach BST

Przeszukiwanie w drzewie BST jest realizowane przy pomocy rekursywnej
funkcji BST-POSZ(x,k) (kod K.3.2).

K.3.2

BST-POSZ(x,k)
1

je

Ğli x=nil lub k= key[x]

2

to zwró

ü x

3

je

Ğli k<key[x]

4

to zwró

ü BST-POSZ(left[x],k)

5

inaczej zwró

ü BST-POSZ(right[x],k)

Parametr x jest wska

Ĩnikiem do pewnego wĊzáa (w szczególnoĞci moĪe byü

wska

Ĩnikiem do korzenia drzewa), a k wartoĞcią poszukiwanego klucza.

Przeszukiwanie odbywa si

Ċ w poddrzewie, którego korzeniem jest x. Funkcja

zwraca wska

Ĩnik do znalezionego wĊzáa lub nil jeĞli wĊzeá o podanym kluczu

nie istnieje. Przeszukiwanie rozpoczyna si

Ċ od wĊzáa początkowego i jest

kontynuowane w dó

á drzewa. Dla kaĪdego wĊzáa x, który nie jest pusty,

- 62 -

algorytm porównuje warto

Ğü klucza dla tego wĊzáa z wartoĞcią poszukiwaną k.

Je

Ğli wartoĞci te są równe, to przeszukiwanie zostaje przerwane (wĊzeá zostaá

znaleziony). Je

Ğli x ma wartoĞü nil to przeszukiwanie takĪe zostaje przerwane

(w

Ċzeá nie zostaá znaleziony). JeĞli natomiast sprawdzany wĊzeá ma wartoĞü

klucza inn

ą od poszukiwanej, wówczas korzystamy z wáasnoĞci drzewa BST w

nast

Ċpujący sposób:

x poszukujemy dalej tylko w lewym poddrzewie, jeĞli wartoĞü

poszukiwanego klucza by

áa mniejsza od napotkanego,

x poszukujemy dalej tylko w prawym poddrzewie, jeĞli wartoĞü

poszukiwanego klucza by

áa niemniejsza od napotkanego.

Algorytm przeszukiwania w drzewie BST mo

Īna takĪe napisaü nie stosując

rekursji. Wersj

Ċ bez rekursji okreĞlaną takĪe jako wersja iteracyjna przedstawia

kod K.3.3.

K.3.3

BST-POSZ-ITER(x,k)
1

dopóki

x

znil i kzkey[x]

2

wykonuj je

Ğli k<key[x]

3

to

x

mleft[x]

4

inaczej

x

mright[x]

5

zwró

ü x

3.1.2

Inne operacje na drzewach BST

Poszukiwanie w

Ċzáa o minimalnym kluczu

Algorytm poszukiwania w

Ċzáa o minimalnym kluczu w drzewie BST realizuje

funkcja BST-MIN(x) (kod K.3.4).

K.3.4

BST-MIN(x)
1

dopóki

left[x]

znil

2

wykonuj

x

mleft[x]

3

zwró

ü x

Przeszukiwanie rozpoczyna si

Ċ od dowolnego wĊzáa x i odbywa siĊ w

poddrzewie, którego korzeniem jest w

Ċzeá x. WĊzeá o minimalnym kluczu jest

poszukiwany wed

áug prostej strategii „podąĪania” za wskaĨnikiem left

- 63 -

kolejnych w

Ċzáów, aĪ do napotkania wĊzáa, dla którego wskaĨnik left[x] jest

pusty. W

Ċzeá o minimalnym kluczu jest zatem lewym skrajnym wĊzáem w

przeszukiwanym poddrzewie.

W analogiczny sposób mo

Īna napisaü funkcjĊ wyszukiwania wĊzáa o

maksymalnym kluczu.

àatwo zauwaĪyü, Īe obie funkcje dziaáają w czasie O(h),

gdzie h jest wysoko

Ğcią drzewa BST.

Nast

Ċpniki i poprzedniki

Problem poszukiwania nast

Ċpnika pewnego wĊzáa x w drzewie BST polega na

udzieleniu odpowiedzi na pytanie: który w

Ċzeá bĊdzie odwiedzany jako

nast

Ċpny po x podczas przechodzenia drzewa w porządku inorder. JeĞli

wszystkie klucze s

ą róĪne, to nastĊpnikiem wĊzáa x jest wĊzeá o najmniejszym

kluczu, wi

Ċkszym niĪ key[x]. Drzewo BST zapewnia wyznaczenie nastĊpnika

bez wykonywania operacji porównania. Skonstruujemy funkcj

Ċ BST-NAST(x)

(kod K.3.5), gdzie parametr x jest wska

Ĩnikiem na rozwaĪany wĊzeá, a w

wyniku jest zwracany wska

Ĩnik na nastĊpnik wĊzáa x. JeĞli x nie posiada

nast

Ċpnika, wówczas jest zwracany wskaĨnik pusty nil.

K.3.5

BST-NAST(x)
1

je

Ğli right[x]

znil

2

to zwró

ü DRZB-MIN(right[x])

3

y

mp[x]

4

dopóki

x

znil i x=right[y]

5

wykonuj

{ x

my

6

y

mp[y] }

7

zwró

ü y

W algorytmie K.3.5 rozwa

Īono dwa przypadki. JeĞli wĊzeá x posiada prawe

poddrzewo, to nast

Ċpnik wyznacza siĊ áatwo, gdyĪ jest to najmniejszy wĊzeá

prawego poddrzewa. W przypadku, gdy w

Ċzeá x nie ma prawego poddrzewa

(ale ma nast

Ċpnik y), to y jest najniĪszym przodkiem wĊzáa x, takim, Īe jego

lewy syn jest tak

Īe przodkiem x.

W drzewie BST na rys.3.2 nast

Ċpnikiem wĊzáa 13 jest wĊzeá 15. Aby go

wyznaczy

ü, wystarczy przejĞü w górĊ drzewa do napotkania wĊzáa, który jest

lewym w

Ċzáem-synem swojego rodzica. Przeszukiwanie takiego wĊzáa odbywa

- 64 -

si

Ċ w wierszach 3-6 algorytmu K.3.5. Znaleziona wartoĞü y jest zwracana w

wierszu 7.

15

5

7

3

18

20

17

4

2

13

9

Rys.3.2 Drzewo BST, w którym nast

Ċpnikiem wĊzáa 13 jest wĊzeá 15.

Dla drzewa o wysoko

Ğci h algorytm wyznaczania nastĊpnika, podobnie jak

analogiczny algorytm wyznaczania poprzednika, dzia

áają w czasie O(h).

Operacje wstawiania i usuwania

Operacje wstawiania i usuwania w drzewie BST tym ró

Īnią siĊ od dotychczas

omówionych operacji,

Īe modyfikują (zmieniają) one dynamiczną strukturĊ

drzewa. W ogólnym przypadku dynamiczna struktura drzewa musi by

ü wtedy

przeorganizowana tak, aby zachowa

ü wáasnoĞü drzewa BST. Omówimy

procedur

Ċ wstawiania nowego wĊzáa z do drzewa przeszukiwaĔ binarnych T

(kod K.3.6).

K.3.6

BST-WSTAW(T,z)
1

y

mnil

2

x

mroot[T]

3

dopóki

x

znil

4

wykonuj

{ y

mx

5

je

Ğli key[z]<key[x]

6

to

x

mleft[x]

7

inaczej

x

mright[x] }

8

p[z]

my

9

je

Ğli y=nil

10

to

root[T]

mz

11

inaczej je

Ğli key[z]<key[y]

12

to

left[y]

mz

13

inaczej

right[y]

mz

- 65 -

Zak

áada siĊ, Īe wstawiany wĊzeá przygotowano w ten sposób Īe key[z]=v,

left[z]=nil oraz right[z]=nil. W wyniku wykonania procedury wstawiania,
drzewo wej

Ğciowe T oraz pole p[z] są modyfikowane tak, Īe z staje siĊ wĊzáem

drzewa T.

Podobnie jak w przypadku procedury wyszukiwania, przegl

ądanie, drzewa

rozpoczyna si

Ċ w korzeniu i przebiega w dóá drzewa. WskaĨnik x postĊpuje po

pewnej

ĞcieĪce w drzewie, a zmienna y zawiera wskazanie na rodzica wĊzáa x.

W wierszach od 3 do 7 wska

Ĩniki x i y są przesuwane w dóá drzewa w kierunku

prawym lub lewym, w zale

ĪnoĞci od wyniku porównania kluczy elementów

wstawianego i napotkanego. Proces ten trwa a

Ī do chwili, gdy x przyjmie

warto

Ğü nil i w tym wáaĞnie miejscu jest wstawiany nowy wĊzeá. Wstawianie

odbywa si

Ċ w wierszach od 8 do 13.

3.2 Kopce

3.2.1

Definicja i w

áasnoĞü kopca

Definicja 3.2

Kopiec (heap) to struktura, która mo

Īe byü rozpatrywana jako rodzaj „prawie

pe

ánego” drzewa binarnego (rys.3.3a). Drzewo to jest peáne w tym sensie, Īe

jest wype

ánione na wszystkich poziomach z wyjątkiem byü moĪe najniĪszego,

który jest wype

ániony od lewej do prawej do pewnego miejsca. JednoczeĞnie

rozwa

Īa siĊ tablicĊ A, której elementy odpowiadają wĊzáom drzewa w sposób

wynikaj

ący z porównania rysunków 3.3a i 3.3b.

Tablica A reprezentuj

ąca kopiec posiada dwa nastĊpujące atrybuty:

length[A]

- liczba elementów w A,

heap-size[A]

- liczba elementów kopca,

dla których zachodzi nierówno

Ğü:

heap-size[A]

d length[A].

- 66 -

a)

16

14

7

8

10

9

3

1

7

3

6

2

5

4

4

2

9

8

1

10

b)

A

3

1

2

3

4

5

6

7

8

9

10

11

2

4

1

14

16

10

8

7

9

Rys.3.3 Reprezentowanie kopca przy pomocy drzewa binarnego i tablicy.

Zak

áada siĊ, Īe korzeniem drzewa jest A[1], a wszystkie elementy z indeksem

wi

Ċkszym od heap-size[A] nie zawierają elementów kopca. Przy takim sposobie

reprezentowania kopca, mo

Īna na podstawie danego indeksu i pewnego wĊzáa

obliczy

ü indeks jego rodzica, a takĪe indeksy lewego i prawego syna. Realizują

to proste funkcje PARENT(i) (kod.3.7), LEFT(i) (kod.3.8) oraz RIGHT(i)
(kod.3.9).

K.3.7

K.3.8

K.3.9

PARENT(i)
1

zwró

ü

¬i/2¼

LEFT(i)
1 zwró

ü 2i

RIGHT(i)
1

zwró

ü 2i+1

W

áasnoĞü kopca

Kopiec posiada specjaln

ą wáasnoĞü, która mówi, Īe dla kaĪdego wĊzáa i, który

nie jest korzeniem zachodzi

A[PARENT(i)]

t A[i].

Z w

áasnoĞci kopca wynika, Īe najwiĊkszy element kopca znajduje siĊ w

korzeniu, a poddrzewa ka

Īdego wĊzáa zawierają wartoĞci mniejsze niĪ wartoĞü

umieszczona w tym w

ĊĨle. PoniewaĪ kopiec jest budowany jako peáne drzewo

binarne, st

ąd jego wysokoĞü dla n wĊzáów wynosi 4(lgn). Jest to takĪe istotna

cecha kopca, z której wynika,

Īe podstawowe algorytmy na kopcach dziaáają w

czasie O(lgn).

- 67 -

3.2.2

Algorytmy na kopcach

Przywracanie w

áasnoĞci kopca

Dzia

áania na kopcu mogą prowadziü do zaburzenia jego wáasnoĞci, stąd

podstawow

ą operacją jest procedura przywracania wáasnoĞci kopca. W

algorytmie K.3.10 za

áoĪono, Īe kopiec jest reprezentowany przy pomocy

tablicy A, dla której w w

ĊĨle A[i] naleĪy przywróciü wáasnoĞü kopca.

K.3.10

KOPIEC-PRZYWR(A,i)
1

l

m LEFT(i)

2

r

m RIGHT(i)

3

je

Ğli l

dheap-size[A] i A[l]>A[i]

4

to

najwi

Ċkszyml

5

inaczej

najwi

Ċkszymi

6

je

Ğli r

dheap-size[A] i A[r]>A[najwiĊkszy]

7

to

najwi

Ċkszymr

8

je

Ğli najwi

Ċkszyzi

9

to

{ zamie

Ĕ A[i]lA[najwiĊkszy]

10

KOPIEC-PRZYWR(A,najwi

Ċkszy)}

W ka

Īdym kroku procedury jest wybierany najwiĊkszy spoĞród elementów A[i],

A[LEFT(i)] i A[RIGHT(i)], a jego indeks zostaje zapami

Ċtany w zmiennej

najwi

Ċkszy. JeĞli najwiĊkszym okazaá siĊ A[i], to wáasnoĞü kopca w wĊĨle A[i]

jest spe

ániona i procedura koĔczy pracĊ. W przeciwnym razie, tj. gdy

najwi

Ċkszym okazaá siĊ jeden z synów wĊzáa A[i], nastĊpuje zamiana miejscami

w

Ċzáów A[i] oraz A[najwiĊkszy]. W wyniku wĊzeá A[i] oraz jego synowie

spe

ániają wáasnoĞü kopca. WĊzeá A[najwiĊkszy] ma teraz poprzednią wartoĞü

w

Ċzáa A[i], dlatego poddrzewo zaczepione w wĊĨle A[najwiĊkszy] moĪe nie

spe

ániaü juĪ wáasnoĞci kopca. W takim przypadku procedurĊ przywracania

nale

Īy wywoáaü rekurencyjnie dla poddrzewa z korzeniem A[najwiĊkszy].

Przyk

áadem zastosowania procedury K.3.10 jest przywrócenie wáasnoĞci kopca

strukturze z rys.3.4a. W wyniku otrzymujemy kopiec pokazany na rys.3.4b.

- 68 -

a)

16

4

7

14

10

9

3

1

7

3

6

2

5

4

8

2

9

8

1

10

b)

16

14

7

8

10

9

3

1

7

3

6

2

5

4

4

2

9

8

1

10

Rys. 3.4 Efekt dzia

áania procedury przywracania wáasnoĞci kopca.

Jak wynika z rys.3.4a w

áasnoĞü kopca nie jest speániona dla wĊzáa o wartoĞci

klucza 4, tj. w

Ċzáa A[2], zatem pierwsze wywoáanie procedury przywracania

w

áasnoĞci kopca ma postaü KOPIEC-PRZYWR(A,2). Prowadzi ono do zamiany

miejscami w

Ċzáów A[2] i A[4], z kluczami odpowiednio 4 i 14. Taka zamiana

powoduje jednak zaburzenie w

áasnoĞci kopca w wĊĨle A[4], który ma teraz

warto

Ğü klucza 4, podczas gdy jego synami są wĊzáy A[8] i A[9], z kluczami

odpowiednio 2 i 8. Niezb

Ċdne jest zatem rekursywne wywoáanie KOPIEC-

PRZYWR(A,4), które prowadzi do zamiany miejscami w

Ċzáów A[4] i A[9], z

kluczami odpowiednio 4 i 8 oraz przywrócenia w

áasnoĞci kopca w caáym

poddrzewie, którego korzeniem jest w

Ċzeá A[2] (rys.3.4b).

Budowanie kopca

Za pomoc

ą procedury przywracania wáasnoĞci kopca moĪna z elementów

zadanej tablicy A[1..n] zbudowa

ü kopiec taki, Īe heap-size[A]=n. NaleĪy przy

tym zauwa

Īyü, Īe kaĪdy element podtablicy A[¬n/2¼+1..n] jest liĞciem w

drzewie binarnym reprezentuj

ącym kopiec. Elementy te zatem moĪna traktowaü

jako jednoelementowe kopce, w których w

áasnoĞü kopca na pewno jest

spe

ániona. Na przykáad dla tablicy wyjĞciowej A[1..10], pokazanej na rys. 3.5a

podtablic

ą liĞci jest A[6..10] (por.rys.3.5b).

Procedur

Ċ budowania kopca przedstawiono jako kod K.3.11.

K.3.11

KOPIEC-BUDUJ(A)
1

heap-size[A]

m length[A]

2

dla

i

m ¬length[A]/2¼ w_dóá_do 1

3

wykonuj

KOPIEC-PRZYWR(A,i)

- 69 -

a)

A

10

1

2

3

4

5

6

7

8

9

10

11

14 8

7

1

4

3

2

16

9

A [6..10]

b)

4

1

16

2

3

9

10

1

7

3

6

2

5

4

8

14

9

8

7

10

Rys.3.5 Zakres podtablicy li

Ğci (a) dla drzewa (b).

W algorytmie wykorzystano fakt,

Īe w wĊzáach podtablicy A[¬n/2¼+1..n]

w

áasnoĞü kopca jest juĪ speániona. NastĊpnie procedura przechodzi przez

pozosta

áe wĊzáy, tzn. wĊzáy podtablicy A[1..¬n/2¼] i wywoáuje w kaĪdym z nich

procedur

Ċ przywracania wáasnoĞci kopca. WĊzáy są przy tym odwiedzane

w kolejno

Ğci malejących numerów od ¬n/2¼ do 1. W kaĪdym z wĊzáów zostaje

wywo

áana procedura KOPIEC-PRZYWR, w efekcie czego poddrzewa

zaczepione w tych w

Ċzáach stają siĊ prawidáowymi kopcami.

Przyk

áadem uĪycia procedury KOPIEC-BUDUJ są pokazane na rys.3.7-3.11

kolejne kroki budowania kopca na podstawie tablicy z rys.3.5a. Drzewo
wyj

Ğciowe przedstawia rys.3.6.

4

1

16

2

3

9

10

1

7

3

6

2

5

4

8

14

9

8

7

10

Rys.3.6 Stan wyj

Ğciowy do budowania kopca z elementów tablicy z rys.3.5a.

- 70 -

4

1

16

2

3

9

10

1

7

3

6

2

5

4

8

14

9

8

7

10

Rys.3.7 Stan po wywo

áaniu KOPIEC-PRZYWR(A,5).

4

1

16

14

3

9

10

1

7

3

6

2

5

4

8

2

9

8

7

10

Rys.3.8 Stan po wywo

áaniu KOPIEC-PRZYWR(A,4).

4

1

16

14

10

9

3

1

7

3

6

2

5

4

8

2

9

8

7

10

Rys.3.9 Stan po wywo

áaniu KOPIEC-PRZYWR(A,3).

4

16

7

14

10

9

3

1

7

3

6

2

5

4

8

2

9

8

1

10

Rys.3.10 Stan po wywo

áaniu KOPIEC-PRZYWR(A,2).

16

14

7

8

10

9

3

1

7

3

6

2

5

4

4

2

9

8

1

10

Rys.3.11 Stan po wywo

áaniu KOPIEC-PRZYWR(A,1).

- 71 -

3.2.3 Kolejki

priorytetowe

Kolejka priorytetowa to struktura przechowuj

ąca S elementów, z których kaĪdy

ma przyporz

ądkowaną wartoĞü klucza. Typowymi operacjami są wtedy:

wstawianie nowego, a tak

Īe wyszukiwanie oraz usuwanie elementu

o maksymalnym kluczu. Przyk

áadem zastosowania takiej kolejki jest

przydzielanie zasobów w komputerze pracuj

ącym wspóábieĪnie, tzn.

wykonuj

ącym wiĊcej niĪ jedno zadanie. Zadania do wykonania posiadają

priorytety i s

ą ustawiane w kolejce. Kiedy pewne zadanie koĔczy siĊ lub zostaje

przerwane, spo

Ğród oczekujących jest wybierane zadanie o najwyĪszym

priorytecie, co oznacza usuni

Ċcie go z kolejki. Okazuje siĊ, Īe kolejkĊ

priorytetow

ą oraz podstawowe operacje w takiej kolejce wygodnie jest

zrealizowa

ü przy pomocy kopca.

Usuwanie maksymalnego elementu

Usuwanie maksymalnego elementu z kolejki priorytetowej jest równoznaczne
z usuni

Ċciem maksymalnego elementu z kopca reprezentującego tĊ kolejkĊ.

Realizuje to algorytm K.3.12.

K.3.12

KOPIEC-USU

ē-MAX(A)

1

je

Ğli heap-size[A] < 1

2

to

b

áąd „kopiec pusty”

3

max

m A[1]

4

A[1]

m A[heap-size[A]]

5

heap-size[A]

m heap-size[A]-1

6 KOPIEC-PRZYWR(A,1)
7

zwró

ü max

Linie 1 i 2 w funkcji K.3.12 zabezpieczaj

ą przed usuwaniem z pustej kolejki.

Elementem usuwanym jest zawsze korze

Ĕ kopca reprezentującego kolejkĊ

priorytetow

ą, tj. element A[1]. WartoĞü tego elementu jest zwracana w linii 7

jako wynik dzia

áania funkcji. Linie od 4 do 6 sáuĪą do zmodyfikowania kopca

(w tym przywrócenia w

áasnoĞci kopca) po usuniĊciu z niego maksymalnego

elementu.

Na rys.3.13-3.15 zilustrowano kolejne etapy usuwania maksymalnego elementu
z kolejki reprezentowanej przez kopiec z rys.3.12.

- 72 -

16

14

7

8

10

9

3

1

7

3

6

2

5

4

4

2

9

8

1

10

Rys.3.12 Kopiec przed usuni

Ċciem maksymalnego elementu.

1

14

7

8

10

9

3

1

7

3

6

2

5

4

4

2

9

8

1

10

Rys.3.13 Kopiec po wykonaniu polecenia z linii 4 w procedurze K.3.12.

1

14

7

8

10

9

3

1

7

3

6

2

5

4

4

2

9

8

Rys.3.14 Kopiec po wykonaniu polecenia z linii 5 w procedurze K.3.12.

14

8

7

4

10

9

3

1

7

3

6

2

5

4

1

2

9

8

Rys.3.15 Kopiec po wywo

áaniu procedury KOPIEC-PRZYWR(A,1).

- 73 -

Dodawanie nowego elementu

Dodanie nowego elementu do kolejki priorytetowej polega na powi

Ċkszeniu

kopca o nowy w

Ċzeá tak, aby zostaá on wstawiony na wáaĞciwe miejsce.

Operacj

Ċ taką realizuje algorytm K.3.13.

K.3.13

KOPIEC-WSTAW(A,key)
1

heap-size[A]

m heap-size[A]+1

2

i

m heap-size[A]

3

dopóki

i > 1 i A[PARENT(i)] < key

4

wykonuj

{ A[i]

m A[PARENT(i)]

5

i

m PARENT(i) }

6

A[i]

m key

Parametrami procedury wstawiania s

ą: kopiec reprezentujący kolejkĊ

priorytetow

ą oraz klucz dodawanego elementu. Algorytm dziaáa w ten sposób,

Īe powiĊksza najpierw kopiec dodając nowy liĞü (linia 1). NastĊpnie w sposób
podobny jak procedura sortowania przez wstawianie, przechodzi

ĞcieĪkĊ od

nowego li

Ğcia do korzenia celem okreĞlenia wáaĞciwego miejsca dla

wstawianego elementu.

Na rys.3.17-3.20 zilustrowano kolejne etapy dodawania elementu z kluczem 15
do kolejki reprezentowanej przez kopiec z rys.3.16.

16

14

7

8

10

9

3

1

7

3

6

2

5

4

4

2

9

8

1

10

Rys.3.16 Kopiec przed dodaniem elementu z kluczem 15.

- 74 -

16

14

7

8

10

9

3

1

7

3

6

2

5

4

4

2

9

8

1

10

11

Rys.3.17 Kopiec po wykonaniu polecenia z linii 1 w procedurze K.3.13.

16

14

7

8

10

9

3

1

7

3

6

2

5

4

4

2

9

8

1

10

11

7

Rys.3.18 Kopiec po 1-szym wykonaniu p

Ċtli w liniach 3y5 procedury K.3.13.

16

14

14

8

10

9

3

1

7

3

6

2

5

4

4

2

9

8

1

10

11

7

Rys.3.19 Kopiec po 2-gim wykonaniu p

Ċtli w liniach 3y5 procedury K.3.13.

16

15

14

8

10

9

3

1

7

3

6

2

5

4

4

2

9

8

1

10

11

7

Rys.3.20 Kopiec po wykonaniu polecenia z linii 6 w procedurze K.3.13.

Czas dzia

áania procedury KOPIEC-WSTAW(A,key) na n elementowym kopcu

wynosi O(lgn), poniewa

Ī jest równy dáugoĞci ĞcieĪki poprowadzonej od

nowego li

Ğcia do korzenia.

- 75 -

3.3 Przeszukiwanie w drzewach

3.3.1 Typy

zada

Ĕ przeszukiwania

Opracowanie

efektywnych procedur przeszukiwania jest kluczowym

zagadnieniem w dziedzinie algorytmów. Na rys.3.21 wyodr

Ċbniono dwie

podstawowe klasy problemów, które mog

ą byü rozwiązywane przy pomocy

przeszukiwania.

PRZESZUKIWANIE

Pozyskiwanie

informacji

z gotowych struktur

Generowanie

planów

rozwi

ązaĔ

Rys.3.21 Klasy zada

Ĕ przeszukiwania w drzewach.

Pierwsza grupa zada

Ĕ dotyczy przypadków, kiedy z istniejącej struktury naleĪy

uzyska

ü okreĞlone informacje, np. wyszukaü konkretny element w zadanym

drzewie binarnym. Inne przyk

áady moĪna podaü rozwaĪając drzewo na rys.3.22.

Henryk

Bogdan

Joanna

Franciszek

Zuzanna

Julia

Danuta

Józef

Jan

Rys.3.22 Drzewo zale

ĪnoĞci przodek-potomek.

Jest to struktura pokazuj

ąca zaleĪnoĞci przodek-potomek dla czáonków pewnej

rodziny. Przeszukiwanie w takim drzewie jest podstaw

ą do udzielania

odpowiedzi m.in. na nast

Ċpujące pytania:

x czy Zofia naleĪy do rodziny?
x czy Zuzanna jest potomkiem Bogdana?
itp.

- 76 -

Druga grupa zada

Ĕ przeszukiwania dotyczy generowania planów rozwiązaĔ

i mo

Īe byü

zilustrowana przy pomocy prostej zabawki-uk

áadanki

przedstawionej na rys.3.23 [2].

Rys.3.23 Uk

áadanka.

8

1

2

6

7

5

3

4

1

2

3

5

4

8

6

7

stan pocz

ątkowy

stan docelowy

Uk

áadanka skáada siĊ z 8-miu segmentów, które mogą byü przemieszczane

w obr

Ċbie 9-ciu pól. Przyjmując za punkt wyjĞcia pewien stan początkowy,

nale

Īy tak przesuwaü segmenty, aby otrzymaü nowy ukáad przyjĊty jako stan

docelowy. Zadanie przeszukiwania w tym przypadku polega na automatycznym
wygenerowaniu takiego ci

ągu przesuniĊü segmentów, który prowadzi do stanu

docelowego. Powstaje w ten sposób drzewo przeszukiwa

Ĕ, którego wĊzáy

reprezentuj

ą bieĪące stany ukáadanki tj. chwilowe ukáady segmentów. Dla

pewnego w

Ċzáa w drzewie przeszukiwaĔ jego synami są stany osiągalne z tego

w

Ċzáa po wykonaniu pojedynczego przesuniĊcia (rys.3.24).

8

1

2

6

3

5

7

4

8

1

2

3

7

5

6

4

8

1

2

6

7

5

3

4

8

1

3

6

2

5

7

4

8

1

2

6

7

5

3

4

8

1

2

3

6

5

7

4

8

1

2

6

7

5

3

4

8

3

1

6

2

5

7

4

8

1

2

5

7

6

3

4

8

1

2

3

6

5

7

4

8

1

2

6

7

4

3

5

8

1

2

3

6

5

7

4

8

6

2

1

7

5

3

4

8

3

2

1

6

5

7

4

8

1

2

7

6

5

3

4

Rys.3.24 Drzewo stanów uk

áadanki.

Nale

Īy zwróciü uwagĊ na fakt, Īe w odróĪnieniu od zadaĔ pozyskiwania

informacji z gotowych struktur, w zadaniach generowania planów rozwi

ązaĔ

- 77 -

przeszukiwana struktura istnieje tylko konceptualnie, tzn. nie musi by

ü

wcze

Ğniej zbudowana w caáoĞci. Budowane są tylko jej niezbĊdne czĊĞci,

w miar

Ċ jak postĊpuje proces przeszukiwania.

Dla obu wymienionych klas zada

Ĕ przeszukiwania konieczne jest rozwiązanie

nast

Ċpujących problemów:

1. Dost

Ċp do wĊzáów

2. Systematyczne si

Ċganie do wĊzáów

3. Sprawdzanie

w

Ċzáów.

Dost

Ċp do wĊzáów

W przypadku przeszukiwania w gotowej strukturze dost

Ċp do wĊzáów jest

rozumiany jako mo

ĪliwoĞü odczytania wszystkich synów dowolnego wĊzáa.

Drzewa s

ą zazwyczaj reprezentowane tak, Īe operacja ta jest bardzo prosta (np.

wska

Ĩniki do synów wĊzáa x drzewa binarnego reprezentowanego za pomocą

struktury ze wska

Ĩnikami, odczytujemy za pomocą atrybutów left[x] i right[x], a

dla drzew dowolnych nale

Īy wykorzystaü atrybuty leftchild[x] oraz

rightsibling[x]).

W zadaniach generowania planów rozwi

ązaĔ dostĊp do wĊzáów polega na

otrzymaniu (wygenerowaniu) w

Ċzáów-synów dowolnego wĊzáa, przy czym

sposób otrzymania tych w

Ċzáów jest, ogólnie biorąc, zaleĪny od typu zadania.

W przypadku uk

áadanki konieczna jest procedura, która dla dowolnego ukáadu

segmentów generuje zbiór stanów „s

ąsiednich” otrzymywanych z bieĪącego

przez wykonanie pojedynczego przesuni

Ċcia.

Systematyczne si

Ċganie do wĊzáów

Problem dost

Ċpu do wĊzáów jest waĪnym, ale nie jedynym w zadaniach

przeszukiwania. Za

áóĪmy, Īe dla drzewa zaleĪnoĞci przodek-potomek (rys.3.22)

mamy odpowiedzie

ü na pytanie: czy wĊzeá Zuzanna wystĊpuje w tym drzewie?

Potrzebna jest wtedy okre

Ğlona strategia, wedáug której naleĪy siĊgaü do

kolejnych w

Ċzáów drzewa w trakcie przeszukiwania. Na ogóá stosuje siĊ dwie

podstawowe strategie przeszukiwania:
x strategia wszerz (BFS – Breadth First Search) oraz
x strategia w gáąb – (DFS - Depth First Search).

- 78 -

Sprawdzanie w

Ċzáów

Operacja sprawdzania w

Ċzáów ma na celu ustalenie, czy wĊzeá osiągniĊty

w wyniku systematycznego si

Ċgania jest wĊzáem poszukiwanym.

3.3.2

Strategie wszerz i w g

áąb

Jak ju

Ī wspomniano systematyczne siĊganie do wĊzáów odbywa siĊ zwykle

wed

áug strategii wszerz lub wedáug strategii w gáąb. StrategiĊ siĊgania wszerz

pokazano schematycznie na rys.3.25. Zak

áada ona przeglądanie kolejno

wszystkich w

Ċzáów danego poziomu, a dopiero po ich wyczerpaniu przejĞcie do

nast

Ċpnego poziomu.

A

D

B

F

E

C

I

G

H

J

L

M

N

K

Rys.3.25 Przeszukiwanie wszerz.

Inaczej odbywa si

Ċ przeglądanie wĊzáów wedáug strategii w gáąb (rys.3.26).

W tym przypadku „odwiedzaj

ąc” wĊzáy naleĪy poruszaü siĊ maksymalnie w

dó

á, a dopiero gdy przestaje to byü moĪliwe, powróciü do wĊzáa wyĪszego

poziomu.

A

D

B

F

E

C

I

G

H

J

L

M

N

K

Rys.3.26 Przeszukiwanie w g

áąb.

- 79 -

Inaczej odbywa si

Ċ przeglądanie wĊzáów wedáug strategii w gáąb (rys.3.26).

W tym przypadku „odwiedzaj

ąc” wĊzáy naleĪy poruszaü siĊ maksymalnie w

dó

á, a dopiero gdy przestaje to byü moĪliwe, powróciü do wĊzáa wyĪszego

poziomu.

Postawimy teraz zadanie opracowania algorytmu przegl

ądającego wĊzáy

dowolnego drzewa wed

áug strategii wszerz. Zakáada siĊ przy tym, Īe drzewo

jest reprezentowane przy pomocy struktury ze wska

Ĩnikami. Algorytm

przegl

ądania realizuje funkcja DRZEWO-WSZERZ(W1,W2) (kod K.3.13).

Funkcja ta sprawdza, czy w

Ċzeá W2 jest wĊzáem potomnym wĊzáa W1, tzn. czy

W2 wyst

Ċpuje w poddrzewie, którego korzeniem jest W1.

K.3.13

DRZEWO-WSZERZ(W1, W2)
1 do_sprawdzenia

m nil

2

SYNOWIE(W1, do_sprawdzenia)

3 dopóki do_sprawdzenia

z nil

4

wykonuj

{ pierwszy

m PIERWSZY(do_sprawdzenia)

5 je

Ğli key[pierwszy] = key[W2] to zwróü W2

6 SYNOWIE(pierwszy, nowe_w

Ċzáy)

7 RESZTA(do_sprawdzenia)
8 NOWE-NA-KONIEC(do_sprawdzenia, nowe_w

Ċzáy) }

9 wypisz „w

Ċzáa nie znaleziono”

W

algorytmie wykorzystano dwie struktury listowe: do_sprawdzenia

i nowe_w

Ċzáy, zawierające odpowiednio wĊzáy oczekujące aktualnie na

sprawdzenie oraz w

Ċzáy, które są synami bieĪącego wĊzáa. UĪyto takĪe

nast

Ċpujących pomocniczych procedur i funkcji:

SYNOWIE(w, lista_s)

dla w

Ċzáa w generuje listĊ lista_s

w

Ċzáów-synów tego wĊzáa,

PIERWSZY(lista_w)

dla niepustej listy w

Ċzáów lista_w

zwraca wska

Ĩnik na pierwszy wĊzeá,

RESZTA(lista_w)

w li

Ğcie wĊzáów lista_w usuwa

pierwszy w

Ċzeá,

NOWE-NA-KONIEC(lista_w1, lista_w2)

na koniec listy w

Ċzáów lista_w1

dodaje list

Ċ wĊzáów lista_w2.

Ich opracowanie pozostawia si

Ċ Czytelnikowi.

- 80 -

Algorytm przeszukiwania w g

áąb moĪna otrzymaü dokonując niewielkiej

modyfikacji funkcji DRZEWO-WSZERZ. Podstawowa zmiana dotyczy linii 8,
gdzie wywo

áanie procedury NOWE-NA-KONIEC naleĪy zastąpiü wywoáaniem

analogicznej procedury NOWE-NA-POCZ

ĄTEK, która doáączy nowe wĊzáy,

b

Ċdące synami bieĪącego wĊzáa nie na koniec, lecz na początek listy

do_sprawdzenia.

3.3.3

Przeszukiwanie sterowane i niesterowane

Strategie wszerz i w g

áąb są przykáadami przeszukiwania niesterowanego w tym

sensie,

Īe porządek wedáug którego są sprawdzane wĊzáy drzewa jest z góry

okre

Ğlony, a aktualna zawartoĞü informacyjna drzewa nie ma na niego wpáywu.

W niektórych zastosowaniach zachodzi potrzeba sterowania przeszukiwaniem
w celu osi

ągniĊcia lepszego rozwiązania. W takim przypadku metoda nie

ogranicza si

Ċ wyborem pierwszego wĊzáa z listy do_sprawdzenia, lecz

wybierany jest taki w

Ċzeá, który wedáug pewnego kryterium jest najbardziej

odpowiedni, aby przeszukiwanie by

áo kontynuowane w kierunku tego wáaĞnie

w

Ċzáa. MoĪna np. zastosowaü kryterium polegające na wyborze wĊzáa

„najbardziej podobnego“ do poszukiwanego. Taki sposób post

Ċpowania jest

nazywany przeszukiwaniem sterowanym, a zastosowana strategia nosi nazw

Ċ

najpierw najlepszy (BF - best first).

Wybór „najbardziej podobnego“ w

Ċzáa w drzewie przeszukiwaĔ moĪna

przedstawi

ü na przykáadzie ukáadanki z rys.3.23. RozwaĪymy dwa stany

uk

áadanki pokazane na rys.3.27.

2

8

1

6

3

4

5

7

1

2

3

5

4

8

6

7

stan aktualny

stan docelowy

Rys.3.27 Aktualny i docelowy stan

uk

áadanki.

Aby oceni

ü podobieĔstwo stanów aktualnego i docelowego wprowadzimy

miar

Ċ podobieĔstwa (odlegáoĞci) pomiĊdzy stanami. Przyjmuje siĊ nastĊpujące

ustalenia:
1. Dla ka

Īdego segmentu ukáadanki wprowadza siĊ wagĊ równą liczbie

pozycji o jak

ą jest on odlegáy od swojej pozycji docelowej.

- 81 -

2. Do wagi segmentu z pkt.1 dodaje si

Ċ 3, jeĞli segment jest w pozycji

Ğrodkowej oraz 6, jeĞli jest on na obrzeĪach i nie poprzedza segmentu, który
docelowo po nim nast

Ċpuje.

Stosuj

ąc te ustalenia moĪna okreĞliü odlegáoĞü stanów aktualnego od

docelowego z rys.3.27. Wyniki zamieszczono w tab.3.1.

Segment

Naliczona waga

1

2+6=8

Tab.3.1 Tabela naliczania odleg

áoĞci

stanów uk

áadanki z rys.3.27.

2

1+6=7

3

1+6=7

4

2+6=8

5

0+6=6

6

1+3=4

7

0+6=6

.

8

2+0=2

Odleg

áoĞü stanów

(suma)

48

Podobne oceny odleg

áoĞci stanu aktualnego od docelowego mogą posáuĪyü jako

kryterium wyboru drogi w drzewie przeszukiwa

Ĕ i tym samym stanowiü

podstaw

Ċ przeszukiwania sterowanego.

3.3.4 Przeszukiwanie pe

áne

Omawiane dotychczas algorytmy by

áy tak skonstruowane, Īe przeszukiwanie

ko

Ĕczyáo siĊ z chwilą napotkania pierwszego wĊzáa, który speániaá zadane

kryterium. Mo

Īna jednak postawiü wymóg wyszukania wszystkich wĊzáów

spe

ániających to kryterium, a zatem kontynuowaü przeszukiwanie w caáej

strukturze. Taki sposób post

Ċpowania okreĞlimy jako przeszukiwanie peáne,

a jego wynikiem jest w przypadku ogólnym lista wyszukanych w

Ċzáów.

Realizacja przeszukiwania pe

ánego wymagaáaby niewielkiej modyfikacji

algorytmu DRZEWO-WSZERZ, polegaj

ącej na wprowadzeniu listy wynik, do

której po kolei by

áyby dodawane wĊzáy speániające kryterium przeszukiwania.

Przeszukiwanie ko

Ĕczyáoby siĊ dopiero z chwilą wyczerpania listy wĊzáów

do_sprawdzenia.

- 82 -

3.3.5

Generowanie dróg rozwi

ązaĔ

Rozwa

Īymy teraz problem poszukiwania drogi pomiĊdzy dwoma zadanymi

w

Ċzáami, tzn. otrzymania peánej listy wĊzáów wystĊpujących podczas

przechodzenia od jednego w

Ċzáa do drugiego. Na przykáad drogĊ pomiĊdzy

w

Ċzáami A i J w drzewie na rys.3.28 moĪna zapisaü w postaci listy wĊzáów

(A B F J).

A

D

B

F

E

C

H

G

I

J

K

L

Rys.3.28 Drzewo z zaznaczon

ą drogą od wĊzáa A do wĊzáa J.

Szczególne znaczenie ma poszukiwanie drogi w drzewach, w których korze

Ĕ

reprezentuje pewien stan pocz

ątkowy a synowie dowolnego wĊzáa moĪliwe

stany osi

ągane z wĊzáa-rodzica w wyniku wykonania elementarnej operacji.

Za

áóĪmy, Īe poszukujemy w drzewie wĊzáa reprezentującego pewien stan

docelowy okre

Ğlany jako rozwiązanie. W takim przypadku nie wystarcza tylko

stwierdzenie, czy poszukiwane rozwi

ązanie istnieje, lecz naleĪy podaü drogĊ

w drzewie przeszukiwa

Ĕ od stanu początkowego (korzenia) do rozwiązania.

Droga ta wyznacza list

Ċ elementarnych operacji potrzebnych do przejĞcia od

stanu pocz

ątkowego do rozwiązania. Ten rodzaj przeszukiwania okreĞlimy jako

generowanie dróg rozwi

ązaĔ.

W przypadku uk

áadanki elementarną operacją jest dozwolone, pojedyncze

przesuni

Ċcie segmentu. Algorytm, który automatycznie generuje rozwiązanie

dla uk

áadanki powinien zwracaü w wyniku listĊ kolejnych konfiguracji

segmentów, z których pierwsza jest stanem pocz

ątkowym, ostatnia stanem

docelowym, a ka

Īde dwie sąsiednie powinny byü osiągalne jedna z drugiej przy

pomocy elementarnej operacji. Za

áóĪmy, Īe naleĪy znaleĨü rozwiązanie dla

uk

áadanki w sytuacji pokazanej na rys.3.29.

- 83 -

8

1

2

6

7

5

3

4

8

1

2

3

7

5

6

4

stan pocz

ątkowy

stan docelowy

Rys.3.29 Aktualny i docelowy stan

uk

áadanki w zadaniu poszukiwania

drogi rozwi

ązania.

Przyk

áadem drogi rozwiązania otrzymanej na podstawie drzewa z rys.3.24. jest

sekwencja stanów uk

áadanki pokazana na rys.3.30.

8

1

2

3

7

5

6

4

8

1

2

6

7

5

3

4

8

1

2

6

7

5

3

4

8

6

2

1

7

5

3

4

Rys.3.30 Droga rozwi

ązania dla sytuacji z rys.3.29.

Pytania kontrolne

1. Poda

ü definicjĊ:

a) drzewa skierowanego;
b) drzewa nieskierowanego.

2. Wyja

Ğniü nastĊpujące pojĊcia:

a) rodzic i syn w

Ċzáa;

b) przodek i potomek w

Ċzáa;

c) korze

Ĕ, poddrzewo, liĞü;

d) g

áĊbokoĞü i wysokoĞü wĊzáa oraz wysokoĞü drzewa;

e) drzewo uporz

ądkowane i drzewo binarne;

f) regularne drzewo binarne;
g) pe

áne drzewo binarne.

3. Omówi

ü tablicową reprezentacjĊ drzew binarnych.

4. Omówi

ü sposoby odwiedzania wierzchoáków drzewa binarnego.

- 84 -

5.

Przedstawi

ü sposoby reprezentacji drzew za pomocą struktur

wska

Ĩnikowych.

6.

Poda

ü definicjĊ drzewa przeszukiwaĔ binarnych oraz omówiü podstawowe

operacje w drzewach BST.

7. Poda

ü sposób reprezentowania oraz podstawową wáasnoĞü kopca.

8. Omówi

ü procedury:

a) przywracania w

áasnoĞci kopca;

b) budowania kopca.

9.

Omówi

ü kolejkĊ priorytetową oraz operacje:

a) usuwania maksymalnego elementu;
b) wstawiania nowego elementu.

10. Scharakteryzowa

ü dwa podstawowe typy zadaĔ przeszukiwania w

drzewach.

11. Omówi

ü strategie przeszukiwania:

a) wszerz (breadth-first),
b) w g

áąb (depth-first),

c) najpierw najlepszy (best-first).

Zadania

1. Napisa

ü rekursywne procedury przechodzenia drzewa binarnego w

porz

ądkach:

a) preorder; b) postorder; c) inorder.

Dla ka

Īdego z punktów a), b) i c) rozwaĪyü dwa warianty: i) drzewo jest

reprezentowane tablicowo; ii) drzewo jest reprezentowane za pomoc

ą

struktur wska

Ĩnikowych.

2. Wprowadzimy nast

Ċpujące pojĊcia:

W

Ċzáem wewnĊtrznym nazywamy dowolny wĊzeá drzewa nie bĊdący

li

Ğciem. StopieĔ wĊzáa to liczba jego synów. Rząd drzewa wynosi k, jeĞli

stopie

Ĕ dowolnego wĊzáa nie przekracza k. Peáne drzewo rzĊdu k, to

- 85 -

drzewo rz

Ċdu k, w którym wszystkie liĞcie mają tĊ samą gáĊbokoĞü, a

wszystkie w

Ċzáy wewnĊtrzne mają stopieĔ k.

Wyprowadzi

ü wzór na liczbĊ wĊzáów peánego drzewa rzĊdu k, jeĞli jego

wysoko

Ğü wynosi h.

3. Napisa

ü procedury wykonania nastĊpujących operacji na drzewach BST:

a)

wyszukiwanie maksymalnego elementu;

b)

wyszukiwanie poprzednika zadanego w

Ċzáa;

c)

usuwanie zadanego w

Ċzáa.

4. Napisa

ü procedurĊ przeszukiwania drzewa w gáąb.

5. Napisa

ü procedurĊ budowania drzewa przeszukiwaĔ binarnych z elementów

uporz

ądkowanej tablicy jednowymiarowej.

- 86 -

4 Sortowanie

4.1 Wprowadzenie

Sortowanie polega na zmianie kolejno

Ğci elementów pewnego ciągu tak, aby

zosta

áy one ustawione w porządku niemalejącym lub nierosnącym. W zbiorze,

do którego nale

Īą elementy ciągu, powinien byü okreĞlony porządek.

Definicja 4.1

Cz

ĊĞciowym porządkiem na zbiorze S nazywamy relacjĊ R, która posiada

nast

Ċpujące wáaĞciwoĞci:

x ZwrotnoĞü. Dla dowolnego

S

a



, zachodzi

.

aRa

x PrzechodnioĞü. Dla dowolnych

S

c

b

a



,

,

, zachodzi: je

Ğli

i

to

.

aRb

bRc

aRc

x AntysymetrycznoĞü. JeĞli

i

bRa

to

aRb

b

a

.

Przyk

áadami czĊĞciowych porządków są: relacja d w zbiorze liczb caákowitych

oraz relacja

Ž dla zbiorów.

Definicja 4.2

Ca

ákowitym (liniowym) porządkiem na zbiorze S nazywamy czĊĞciowy

porz

ądek R na S, taki, Īe dla dowolnych

S

b

a



,

, zachodzi

aRb

albo

.

bRa

Relacja

d jest przykáadem liniowego porządku w zbiorze liczb caákowitych,

natomiast relacja

Ž dla zbiorów nie jest liniowym porządkiem.

Definicja 4.3

Niech S b

Ċdzie zbiorem, w którym jest okreĞlony liniowy porządek d, a

n

a

a

a

,...,

,

2

1

ci

ągiem elementów z S. Zadaniem sortowania jest wyznaczenie

permutacji, tj. pewnej kolejno

Ğci

'

'

2

'

1

,...,

,

n

a

a

a

, zadanych n elementów takiej,

Īe

- 87 -

'

'

2

'

1

...

n

a

a

a

d

d

d

.

Rozwa

Īymy dwie nastĊpujące klasy algorytmów sortowania (rys.4.1):

1.

Algorytmy oparte wy

áącznie na porównywaniu sortowanych elementów.

Dla takich algorytmów wyka

Īemy, Īe do posortowania ciągu záoĪonego z n

elementów potrzeba co najmniej nlgn porówna

Ĕ.

2. Algorytmy korzystaj

ące z pewnych wáasnoĞci sortowanych elementów (np.

z faktu,

Īe sortowane liczby są jednostajnie rozáoĪone w przedziale

>

.

Dla takich algorytmów nie obowi

ązuje dolna granica



1

,

0





n

n lg

:

.

Algorytmy sortowania

Oparte wy

áącznie

na porównywaniu

sortowanych elementów

Wykorzystuj

ące

w

áaĞciwoĞci

sortowanych elementów

Rys.4.1 Klasy algorytmów

sortowania.

Inny podzia

á algorytmów sortowania moĪe byü dokonany ze wzglĊdu na uĪycie

pami

Ċci. WyróĪniamy wtedy:

x

x

algorytmy wewn

Ċtrzne, gdy dane są przechowywane wyáącznie w pamiĊci

wewn

Ċtrznej,

algorytmy zewn

Ċtrzne, gdy w przewaĪającej czĊĞci dane znajdują siĊ poza

pami

Ċcią wewnĊtrzną.

Je

Ğli sortowanie jest czĊĞcią innego algorytmu, wówczas liczba sortowanych

elementów nie jest zwykle du

Īa, co pozwala je zmieĞciü w pamiĊci

wewn

Ċtrznej. Z kolei sortowanie zewnĊtrzne dotyczy gáównie takich

zastosowa

Ĕ, jak operacje w systemach ksiĊgowych, gdzie danych jest zwykle

znacznie wi

Ċcej, niĪ moĪe pomieĞciü pamiĊü wewnĊtrzna.

- 88 -

4.2 Algorytmy oparte na porównaniach

4.2.1 Drzewa decyzyjne

Rozwa

Īymy ponownie algorytm sortowania przez wstawianie (kod K.4.1).

K.4.1

SORT-WSTAW(A)
1

dla

j

m2 do length[A]

2

wykonuj

{ key

m A[j]

3

 Wstaw A[j] do posortowanego ci

ągu A[1..j-1]

4

i

m j-1

5

dopóki

i>0 i A[i]>key

6

wykonuj

{ A[i+1]

m A[i]

7

i

m i-1 }

8

A[i+1]

m key }

Jest to efektywny algorytm w przypadku sortowania niewielkiej liczby
elementów, a jego dzia

áanie moĪna porównaü do ukáadania talii kart w rĊku.

Zaczynaj

ąc od „pustej” rĊki dokáadamy kolejne karty do juĪ uporządkowanej

talii w r

Ċku tak, aby po dodaniu karty byáy nadal uporządkowane. Elementy

tablicy A[1..j-1] reprezentuj

ą (uporządkowane) karty trzymane w rĊce, a

elementy A[j+1..n] reprezentuj

ą nieuporządkowany stos kart na stole. Indeks j

wskazuje na kart

Ċ aktualnie wstawianą do talii. Indeks ten, począwszy od

warto

Ğci 2, przesuwa siĊ w tablicy w stronĊ rosnących indeksów. W kaĪdej

iteracji p

Ċtli zewnĊtrznej (linie 1-8) pobierany jest z tablicy element A[j].

Nast

Ċpnie w pĊtli wewnĊtrznej (linie 5-7) jest poszukiwane wáaĞciwe miejsce

dla elementu A[j] w ju

Ī uporządkowanej czĊĞci tablicy. W tym celu, począwszy

od pozycji j-1, elementy tablicy s

ą przemieszczane w stronĊ rosnących

indeksów dopóty, a

Ī nie „zwolni” siĊ miejsce, w którym powinien byü

umieszczony element A[j]. Sortowanie tablicy

3

,

1

,

6

,

4

,

2

,

5

A

za pomoc

ą

opisywanego algorytmu przedstawiono na rys.4.2.

- 89 -

5

2

4

6

1

3

2

5

4

6

1

3

2

4

5

6

1

3

2

4

5

6

1

3

1

2

4

5

6

3

1

2

3

4

5

6

P o s o r t o w a n e

A[1] A[2] A[3] A[4] A[5] A[6]

Rys.4.2 Sortowanie przez wstawianie.

Sortowanie przez wstawianie jest przyk

áadem sortowania wewnĊtrznego, a

algorytm jest oparty wy

áącznie na porównaniach sortowanych elementów. W

takich algorytmach ustalenie wzgl

Ċdnego poáoĪenia elementów

oraz

jest

mo

Īliwe za poĞrednictwem porównania

i

a

j

a

j

i

a

a

d

, a do ilustracji wykonywanych

porówna

Ĕ wygodnie jest uĪyü struktury nazywanej drzewem decyzyjnym. Na

rysunku 4.3 przedstawiono drzewo decyzyjne odpowiadaj

ące algorytmowi

sortowania ci

ągu

3

2

1

,

,

a

a

a

.

a

1

: a

2

a

2

: a

3

a

1

: a

3

a

1

: a

3

²

¢ a

1

a

2

,

, a

3

²

¢ a

2

a

1

,

, a

3

a

2

: a

3

²

¢ a

1

a

3

,

, a

2

²

¢ a

3

a

1

,

, a

2

²

¢ a

2

a

3

,

, a

1

²

¢ a

3

a

2

,

, a

1

d

!

d

d

d

d

!

!

!

!

Rys.4.3 Drzewo decyzyjne dla sortowanie 3-ch elementów.

Drzewo decyzyjne pokazuje zatem porównania wykonywane przez algorytm
sortuj

ący dla ustalonego rozmiaru danych wejĞciowych. Inne aspekty

algorytmu, jak sterowanie i przep

áyw danych nie są tutaj uwzglĊdniane.

- 90 -

Ka

Īdy wĊzeá wewnĊtrzny odpowiada porównaniu elementów

oraz

. Z ka

Īdym liĞciem drzewa jest natomiast związana pojedyncza

permutacja ci

ągu wejĞciowego. Wykonanie algorytmu polega na przejĞciu od

korzenia do jednego z li

Ğci, a dojĞcie do liĞcia oznacza, Īe algorytm znalazá juĪ

uporz

ądkowanie (permutacjĊ) elementów. Sortowanie na podstawie drzewa

decyzyjnego z rys.4.3 mo

Īna przeĞledziü zakáadając

i

a

j

a



3

,

1

d

d

j

i



.

0

,

2

,

1

3

2

1



a

a

a

W tym przypadku algorytm wykona si

Ċ „wzdáuĪ” ĞcieĪki:

2

3

1

3

1

3

2

2

1

,

,

:

:

:

a

a

a

a

a

a

a

a

a

o

o

o

.

4.2.2

Dolne ograniczenie na czas sortowania

Jak wynika z rys.4.3, d

áugoĞü najdáuĪszej ĞcieĪki od korzenia drzewa

decyzyjnego do li

Ğcia odpowiada liczbie porównaĔ dokonywanej przez

algorytm sortuj

ący w przypadku pesymistycznym. JeĞli zatem uda siĊ okreĞliü

dolne

ograniczenie na wysoko

Ğü drzew decyzyjnych, to bĊdzie ono

jednocze

Ğnie dolnym ograniczeniem na czas dziaáania algorytmów sortujących

wy

áącznie za pomocą porównaĔ. Oceny dolnego ograniczenia moĪna dokonaü

korzystaj

ąc ze sformuáowanego i udowodnionego dalej twierdzenia [5].

Twierdzenie 4.1

Ka

Īde drzewo decyzyjne odpowiadające algorytmowi poprawnie sortującemu n

elementów ma wysoko

Ğü





n

n lg

:

.

Dowód

Rozwa

Īymy drzewo decyzyjne o wysokoĞci h odpowiadające algorytmowi

sortuj

ącemu n elementów. Liczba permutacji dla ciągu záoĪonego z n

elementów wynosi n!, drzewo to ma zatem n! li

Ğci. PoniewaĪ drzewo binarne o

wysoko

Ğci h nie moĪe mieü wiĊcej niĪ

li

Ğci stąd

h

2

.

h

n

2

!

d

Logarytmuj

ąc obustronnie ostatnią nierównoĞü otrzymujemy

(4.1)

 

!

lg n

h

t

- 91 -

Dalej skorzystamy z nast

Ċpującego wzoru Stirlinga

¸¸

¹

·

¨¨

©

§

¸

¹

·

¨

©

§

4



¸

¹

·

¨

©

§

n

e

n

n

n

n

1

1

2

!

S

,

z którego wynika,

Īe

n

e

n

n

¸

¹

·

¨

©

§

!

!

(4.2)

gdzie

jest podstaw

ą logarytmu naturalnego. UwzglĊdniając

nierówno

Ğü (4.2) otrzymujemy na podstawie (4.1):

...

71828

,

2

e





n

n

e

n

n

n

e

n

h

n

lg

lg

lg

lg

:



¸

¹

·

¨

©

§

t

.

Uwaga

W wyniku dokonanej wcze

Ğniej analizy algorytmu sortowania przez wstawianie

otrzymano z

áoĪonoĞü pesymistyczną

 

2

n

O

. Oznacza to,

Īe górne

ograniczenie na czas dzia

áania tego algorytmu nie jest równe dolnej granicy

z naszego twierdzenia. Mówimy,

Īe nie jest to asymptotycznie

optymalny algorytm sortuj

ący wyáącznie za pomocą porównaĔ.



n

n lg

:



4.2.3

Algorytmy asymptotycznie optymalne

Rozwa

Īymy dwa przykáady algorytmów asymptotycznie optymalnych:

sortowanie przez kopcowanie i sortowanie przez scalanie.

Sortowanie przez kopcowanie (heapsort)

Algorytm sortowania przez kopcowanie (kod K.4.2) u

Īywa kopca

zbudowanego z elementów sortowanej tablicy A.

K.4.2

SORT-KOPCOW(A)
1 KOPIEC-BUDUJ(A)
2

dla

i

m length[A] w_dóá_do 2

3

wykonuj

{ zamie

Ĕ A[1]lA[i]

- 92 -

4

heap-size[A]

m heap-size[A]-1

5

KOPIEC-PRZYWR(A,1) }

A

3

1

2

3

4

5

6

7

8

9

10

11

2

4

1

14

16

10

8

7

9

Rys.4.4 Tablica elementów do posortowania.

a)

16

14

7

8

10

9

3

4

2

1

b)

14

8

7

4

10

9

3

1

2

16

c)

10

8

7

4

9

1

3

14

2

16

d)

9

8

7

4

3

1

2

14

10

16

e)

8

7

2

4

3

1

9

14

10

16

f)

7

4

2

1

3

8

9

14

10

16

g)

4

2

7

1

3

8

9

14

10

16

h)

3

2

7

4

1

8

9

14

10

16

i)

2

1

7

4

3

8

9

14

10

16

j)

1

2

7

4

3

8

9

14

10

16

- 93 -

Rys.4.5 Sortowanie przez kopcowanie tablicy z rys.4.4.

Algorytm ten rozpoczyna dzia

áanie uĪywając podanej wczeĞniej procedury

budowania kopca z n-elementowej tablicy A. Poniewa

Ī najwiĊkszy element

znajduje si

Ċ w korzeniu A[1], stąd moĪe on zostaü umieszczony na swoim

miejscu, tj. na ko

Ĕcu tablicy A przez zamianĊ miejscami z A[n]. Po tej zamianie

odrzucamy element A[n] zmniejszaj

ąc rozmiar kopca o 1 i przywracamy

w

áasnoĞü kopca dla pozostaáych elementów. Taka operacja jest nastĊpnie

powtarzana dla kopca o rozmiarze n-1, n-2, itd., a

Ī otrzymamy kopiec o

rozmiarze 2.

Dzia

áanie algorytmu sortowania przez kopcowanie zilustrowano na przykáadzie

sortowania tablicy A zawieraj

ącej 10 liczb (rys.4.4). Rysunki 4.5ay4.5j

pokazuj

ą postaü kopca oraz fragment posortowanej tablicy na początku

kolejnych iteracji p

Ċtli dla w linii 2.

Algorytm ten wykonuje funkcj

Ċ budowania kopca dziaáającą w czasie

, a

nast

Ċpnie dokonuje n-1 wywoáaĔ funkcji przywracania wáaĞciwoĞci kopca, z

których ka

Īde zajmuje czas

 

n

O





n

O lg

. St

ąd ogólny czas dziaáania caáej

procedury sortowania przez kopcowanie wynosi





n

n

O

lg

.

Metoda „dziel i zwyci

ĊĪaj” i sortowanie przez scalanie

Stosowanie rekurencji sprzyja zwi

Ċzáemu i eleganckiemu zapisowi algorytmów,

lecz samo w sobie nie zwi

Ċksza ich efektywnoĞci (np. w sensie skrócenia czasu

oblicze

Ĕ). JeĞli jednak rekurencjĊ dopeániü pewnymi dodatkowymi zabiegami,

jak równowa

Īenie oraz zastosowanie metody okreĞlanej jako „dziel i

zwyci

ĊĪaj” moĪna uzyskaü bardziej efektywne algorytmy.

W podej

Ğciu „dziel i zwyciĊĪaj” wystĊpuje rekursja, przy czym kaĪdy poziom

rekursji ma nast

Ċpującą strukturĊ:

dziel

-

dzielimy problem na podproblemy;

zwyci

ĊĪaj

-

na tym etapie rozwi

ązujemy podproblemy rekurencyjnie

wykorzystuj

ąc metodĊ „dziel i zwyciĊĪaj”, chyba, Īe są one

tak ma

áych rozmiarów, Īe nie wymagają zastosowania

- 94 -

rekursji;

po

áącz

-

áączymy rozwiązania podproblemów, aby otrzymaü
rozwi

ązanie caáego problemu.

Metod

Ċ „dziel i zwyciĊĪaj” zaprezentujemy na przykáadzie algorytmu

sortowania przez scalanie dzia

áającego w czasie





n

n lg

4

. Dla uproszczenia

b

Ċdziemy zakáadaü, Īe sortowanym ciągiem jest

n

x

x

x

,...,

,

2

1

,

,

k

n

2

N

k



a poszukuje si

Ċ permutacji

n

x

x

x

c

c

c

,...,

,

2

1

elementów ci

ągu początkowego takich, Īe

n

x

x

x

c

d

d

c

d

c

...

2

1

.

Etapy algorytmu s

ą nastĊpujące:

1. Dziel

Dzielimy n-elementowy ci

ąg na dwa podciągi po n/2

elementów ka

Īdy.

2. Zwyci

ĊĪaj

Sortujemy otrzymane podci

ągi, uĪywając rekurencyjnie

sortowania przez scalanie. Je

Ğli na którymĞ poziomie rekursji

otrzymujemy do posortowania ci

ąg jednoelementowy, wówczas

nie nast

Ċpuje dalsze zagáĊbianie wywoáaĔ rekursywnych.

3. Po

áącz

àączymy ciągi posortowane na niĪszych poziomach rekursji w
jeden posortowany ci

ąg.

G

áówna procedura sortowania zostaáa przedstawiona jako kod K.4.3.

K.4.3

SORT-SCALANIE(A, p, r)
1 je

Ğli p<r

2 to { q

m ¬(p+r)/2¼

3 SORT-SCALANIE(A, p, q)
4 SORT-SCALANIE(A, q+1, r)
5 SCALAJ(A, p, q, r) }

- 95 -

Procedura SORT-SCALANIE(A,p,r) sortuje podtablic

Ċ A[p..r] záoĪoną z m

elementów (m=r-p+1). Je

Ğli

r

p

t

, to tablica jest ju

Ī posortowana i nie

nast

Ċpuje dalsze zagáĊbianie wywoáaĔ rekursywnych. W przeciwnym razie

dzieli si

Ċ tablicĊ

na dwie podtablice:

>

r

p

A ..

@

>

@

q

p

A ..

zawieraj

ącą

elementów oraz

zawieraj

ącą

ª

º

2

/

m

> @

r

q..

A

¬

¼

2

/

m

elementów. Dla tak otrzymanych

tablic wywo

áuje siĊ procedurĊ sortowania przez scalanie (linie 3 i 4). NastĊpnie

posortowane „po

áówki“ powinny zostaü poáączone (scalone) tak, aby w wyniku

otrzyma

ü takĪe posortowaną tablicĊ (linia 5). Opracowanie procedury scalającej

pozostawia si

Ċ czytelnikowi (zob zad.2 na koĔcu rozdziaáu). Aby zatem

posortowa

ü tablicĊ

> @ > @ > @

> @

>

@

A

length

,

1

A

,...,

3

A

A

,

2

A

A

, procedur

Ċ sortowania

wywo

áuje siĊ nastĊpująco: SORT-SCALANIE(A,1,length[A]).

Schemat sortowania przez scalanie dla

6

,

2

,

3

,

1

,

6

,

4

,

2

,

5

A

pokazano na

rys.4.6.

1 2 2 3 4 5 6 6

scal

2 4 5 6

1 2 3 6

2 5

4 6

1 3

2 6

scal

scal

scal

scal

scal

scal

5

2

4

6

1

3

2

6

Rys.4.6 Sortowanie przez scalanie.

Ocenimy teraz z

áoĪonoĞü czasową algorytmu sortowania przez scalanie. Jest to

algorytm rekurencyjny, który wykorzystuje metod

Ċ „dziel i zwyciĊĪaj”. Czas

dzia

áania

T(n) takich algorytmów mo

Īna opisaü zaleĪnoĞcią rekurencyjną

postaci:

 

 





 

 

¯

®

­

!





d

4

s

n

n

C

n

D

b

n

aT

s

n

n

T

,

/

,

1

(4.3)

Zapis ten oznacza,

Īe jeĞli problem jest dostatecznie maáy (rozmiar zadania nie

przekracza pewnej sta

áej s), wówczas jego rozwiązanie zajmuje staáy czas

.

Je

Ğli natomiast dzielimy problem na a podproblemów i kaĪdy z nich jest

 

1

4

- 96 -

rozmiaru n/b, to czas rozwi

ązania tych podproblemów wyniesie

. Do

tej wielko

Ğci naleĪy dodaü czas



b

n

aT

/



 

n

D

przeznaczony na dzielenie problemu na

podproblemy oraz czas scalania

 

n

!1

n

!1

n

C

.

c

n lg

W przypadku sortowania przez scalanie zale

ĪnoĞü rekurencyjna (4.3) ma

posta

ü:

(4.4)

 

 





 

¯

®

­

4



4

,

2

/

2

1

,

1

n

n

T

n

n

T

gdzie sk

áadnik

oznacza czas scalania, a czas dzielenia, jako sta

áy

pomini

Ċto. ZáoĪonoĞü obliczeniową algorytmu sortowania przez scalanie moĪna

otrzyma

ü rozwiązując równanie rekurencyjne (4.4). Rozwiązanie to moĪna

otrzyma

ü wprost, jeĞli skorzystaü z podanego niĪej twierdzenia [5].

 

n

4

Twierdzenie 4.2

Niech a,b,c b

Ċdą nieujemnymi staáymi. Rozwiązanie równania rekurencyjnego

 





¯

®

­



,

/

1

,

bn

c

n

aT

n

b

n

T

dla n b

Ċdących potĊgą liczby c ma postaü

 

 








°

¯

°

®

­

!



,

,

lg

,

log

c

a

n

O

a

n

n

O

c

a

n

O

n

T

a

c

.

Z powy

Īszego twierdzenia, którego dowód pominiemy, wynika, Īe záoĪonoĞü

obliczeniowa

algorytmu sortowania przez scalanie wynosi

O

.

Uwzgl

Ċdniając wczeĞniej udowodnione twierdzenie 4.1 otrzymujemy, Īe

z

áoĪonoĞü ta wynosi

.





n





n

n lg

4

4.3 Sortowanie w czasie liniowym

Przedstawimy dwa algorytmy, dla których nie obowi

ązuje dolna granica na czas

sortowania



n

n lg



:

, jak to ma miejsce w przypadku algorytmów opartych

wy

áącznie na porównaniach. Prezentowane tutaj algorytmy oprócz porównaĔ

- 97 -

wykorzystuj

ą pewne specyficzne wáaĞciwoĞci sortowanych elementów, przy

czym mo

Īe siĊ zdarzyü, Īe porównania nie są w ogóle konieczne.

4.3.1

Sortowanie przez zliczanie

W algorytmie sortowania przez zliczanie zak

áadamy, Īe kaĪdy z n sortowanych

elementów jest liczb

ą caákowitą z przedziaáu

. Je

Ğli

k

..

1

 

n

O

k

, to wtedy

sortowanie dzia

áa w czasie

 

n

O

. Idea algorytmu polega na okre

Ğleniu dla

ka

Īdego elementu x, ile elementów jest mniejszych lub równych x. Mając tĊ

liczb

Ċ, moĪemy okreĞliü dokáadną pozycjĊ x w posortowanym ciągu. ProcedurĊ

sortowania przez zliczanie przedstawia kod K.4.4.

K.4.4

SORT-ZLICZANIE(A, B, k)

1

dla

i

m1 do k

2

wykonuj

C[i]

m 0

3

dla

j

m1 do length[A]

4

wykonuj

C[A[j]]

m C[A[j]] + 1

5

 C[i] zawiera teraz liczb

Ċ elementów równych i

6

dla

i

m2 do k

7

wykonuj

C[i]

m C[i] + C[i-1]

8

 C[i] zawiera teraz liczb

Ċ elementów mniejszych lub równych i

9

dla

j

m length[A] w_dóá_do 1

10

wykonuj

{ B[C[A[j]]]

m A[j]

11

C[A[j]]

m C[A[j]] – 1 }

W procedurze SORT-ZLICZANIE przyj

Ċto, Īe dane wejĞciowe są elementami

tablicy

,

. Tablica

> @

n

A ..

1

> @





A

length

n

> @

n

B ..

1

jest tablic

ą wyjĞciową, gdzie

zostan

ą umieszczone posortowane elementy, a tablica

> @

k

..

1

C

jest tablic

ą

pomocnicz

ą. W liniach 1-2 tablica C jest zerowana, natomiast operacje w

liniach 3-4 prowadz

ą do zapisu w kaĪdym elemencie

> @

i

C

liczby ca

ákowitej

odpowiadaj

ącej iloĞci elementów tablicy wejĞciowej równych i. NastĊpnie w

liniach 6-7 jest wyznaczana i zapisywana w

> @

i

C

liczba elementów tablicy

wej

Ğciowej mniejszych lub równych i. Ostatecznie w liniach 9-11 wszystkie

elementy zostaj

ą rozmieszczone na wáaĞciwych miejscach w tablicy

.

B

Dzia

áanie algorytmu K.4.4 zilustrujemy na przykáadzie sortowania tablicy

4

,

1

,

4

,

3

,

1

,

4

,

6

,

3

A

,

- 98 -

dla której

8

n

oraz

.

6

k

Po wykonaniu linii 4 tablice A i C maj

ą postaü pokazaną na rys.4.7a, natomiast

po wykonaniu linii 7 tablica C zostaje wype

ániona w sposób przedstawiony na

rys.4.7b. Rysunki 4.7c-4.7j pokazuj

ą postaü tablic B i C po kolejnych iteracjach

wykonywanych w liniach 9-11.

a)

3 6 4 1 3 4 1 4

1

3 4 5 6 7 8

2

A

C

2 0 2 3 0 1

1

3 4 5 6

2

b)

C

2 2 4 7 7 8

1

3

4 5 6

2

c)

j=8

4

1

3

4 5 6 7

2

B

C

8

2 2 4 6 7 8

1

3

4 5 6

2

d)

j=7

4

1

3

4 5 6 7

2

B

C

8

1 2 4 6 7 8

1

3

4 5 6

2

1

e)

j=6

4

1

3

4 5 6 7

2

B

C

8

1 2 4 5 7 8

1

3

4 5 6

2

1

4

f)

j=5

4

1

3

4 5 6 7

2

B

C

8

1 2 3 5 7 8

1

3

4 5 6

2

1

4

3

g)

j=4

4

1

3

4 5 6 7 8

2

B

C

0 2 3 5 7 8

1

3

4 5 6

2

1

4

3

1

h)

j=3

4

1

3

4 5 6 7 8

2

B

C

0 2 3 4 7 8

1

3

4 5 6

2

1

4

3

1

4

i)

j=2

4

1

3

4 5 6 7

2

B

C

8

0 2 3 4 7 7

1

3

4 5 6

2

1

4

3

1

4

6

j)

j=1

4

1

3

4 5 6 7 8

2

B

C

0 2 2 4 7 7

1

3

4 5 6

2

1

4

3

1

4

3

6

Rys.4.7 Ilustracja algorytmu sortowania przez zliczanie dla tablicy

¢3,6,4,1,3,4,1,4².

- 99 -

Ocenimy czas dzia

áania algorytmu sortowania przez zliczanie. PĊtle w liniach

1-2 oraz 3-4 wymagaj

ą odpowiednio czasów

 

k

O

oraz

 

n

O

. Poniewa

Ī

analogiczne wymogi maj

ą pĊtle w liniach 6-7 oraz 9-11, stąd caákowity czas

dzia

áania procedury K.4.4 moĪna zapisaü jako





n

k

O



. Z za

áoĪenia

wynika dalej,

Īe czas ten wynosi

 

n

O

k

 

n

O

, a zatem jest ograniczony funkcj

ą

liniow

ą wzglĊdem liczby sortowanych elementów n. Ocena ta Ğwiadczy o duĪej

efektywno

Ğci algorytmu sortowania przez zliczanie.

4.3.2 Sortowanie

kube

ákowe

Algorytm sortowania kube

ákowego równieĪ naleĪy do algorytmów szybkich, tj.

sortuj

ących w czasie liniowym. Podobnie jak w przypadku sortowania przez

zliczanie, tutaj tak

Īe nakáada siĊ ograniczenie na dane wejĞciowe. Polega ono

na za

áoĪeniu, Īe sortowane są liczby wybrane losowo (z rozkáadem

jednostajnym) z przedzia

áu

>



1

..

0

. Procedur

Ċ sortowania kubeákowego

przedstawiono w postaci kodu K.4.5.

K.4.5

SORT-KUBE

àKOWE(A)

1

n

m length[A]

2

dla

i

m1 do n

3

wykonuj

wstaw A[i] do listy B[

¬n A[i]¼]

4

dla

i

m0 do n-1

5

wykonuj

posortuj list

Ċ B[i] przez wstawianie

6 po

áącz listy B[0], B[1],..., B[n-1] w tej kolejnoĞci

Parametrem wej

Ğciowym jest n-elementowa tablica A, której elementy speániają

zale

ĪnoĞü

. Algorytm sortowania zak

áada podziaá przedziaáu

na n podprzedzia

áów jednakowych rozmiarów nazywanych „kubeákami”, a

nast

Ċpnie rozrzucenie n liczb do tych podprzedziaáów. W tym celu jest

wykorzystana tablica list

> @

1

0



d

i

A

>



1

..

0

>

@

1

..

0



n

B

reprezentuj

ących kubeáki. Liczby w

podprzedzia

áach są nastĊpnie sortowane przez wstawianie, a posortowane listy z

ka

Īdego podprzedziaáu áączy siĊ ze sobą.

Dzia

áanie algorytmu zilustrujemy na przykáadzie 10-elementowej tablicy

0,68

;

23

,

0

;

12

,

0

;

21

,

0

;

94

,

0

;

72

,

0

;

26

,

0

;

0,39

;

17

,

0

;

78

,

0

A

.

- 100 -

Rysunek 4.8a przedstawia nieposortowan

ą tablicĊ A, natomiast rys.4.8b tablicĊ

B po wykonaniu p

Ċtli w liniach 4-5 procedury.

0
1
2
3
4

B

5
6

7

8

9

a)

b)

1
2
3
4
5

A

0,78

0,17
0,39
0,26
0,72
0,94

0,21

0,12

0,23

0,68

6
7

8

9

10

0,12

0,17

nil

0,21

0,23

0,39

0,68

0,26

nil

nil

0,72

0,78

nil

nil

0,94

nil

Rys.4.8 Sortowanie kube

ákowe.

Poprawno

Ğü sortowania kubeákowego

W celu wykazania,

Īe algorytm sortowania kubeákowego dziaáa poprawnie,

rozwa

Īa siĊ ([5]) dwa dowolne elementy

> @

i

A

i

> @

j

A

. Je

Ğli podczas sortowania

trafi

ą one do tego samego kubeáka, to w tablicy wynikowej na pewno wystąpią

w poprawnej kolejno

Ğci, poniewaĪ liczby w kaĪdym kubeáku są sortowane

przez wstawianie, a poprawno

Ğü tej metody zakáadamy. ZaáóĪmy zatem, Īe

elementy

> @

i

A

i

trafi

ą do róĪnych kubeáków o numerach odpowiednio

i

i

, a ponadto

i

. Po po

áączeniu kubeáków elementy listy

znajd

ą siĊ

przed elementami listy

> @

j

A

jc



c

c

jc

> @

i

B c

>

j

B

@

c

, a zatem element

> @

i

A

poprzedzi

w ci

ągu

wynikowym. Musi wtedy zachodzi

ü

>

j

A

@

> @

> @

j

A

i

A

d

, co wyka

Īemy metodą „nie

wprost”, zak

áadając, Īe jest przeciwnie. Otrzymujemy wówczas

> @

¬

¼

> @

¬

¼

j

j

nA

i

nA

i

c

t

c

co jest sprzeczne z wcze

Ğniejszym zaáoĪeniem, Īe

i

jc



c

.

Z

áoĪonoĞü sortowania kubeákowego

Mo

Īna równieĪ wykazaü ([5]), Īe czas dziaáania algorytmu sortowania

kube

ákowego jest liniowy wzglĊdem liczby sortowanych elementów. PoniewaĪ

pesymistyczny czas wykonania operacji we wszystkich liniach oprócz linii 5

- 101 -

wynosi

, pozostaje dokona

ü analizy sortowania wszystkich list

zawieraj

ących elementy w kubeákach. Oznaczymy przez

n

zmienn

ą losową odpowiadającą liczbie elementów w kubeáku

.

Pesymistyczny czas sortowania przez wstawianie wynosi

 

n

O

,...

1

,

0

n

> @

1

,



i

i

B

i

> @

i

B

 

2

n

O

, a zatem

oczekiwany czas posortowania elementów listy

> @

i

B

wynosi

 

>

@

2

E

n

O

> @





2

E

i

i

n

O

.

Ocenimy teraz ca

ákowity oczekiwany czas posortowania elementów we

wszystkich kube

ákach, tzn.

.

(4.5)

> @





> @

¸

¹

·

¨

©

§

¦

¦





1

0

2

1

0

2

E

E

n

i

i

n

i

i

n

O

n

O

Mamy n elementów i n list. Poniewa

Ī do kaĪdej listy trafiają elementy z

n

1

cz

ĊĞci caáego przedziaáu

, to prawdopodobie

Ĕstwo tego, Īe dany element

trafi do listy

, jest jednakowe dla wszystkich list i wynosi

> 

1

,

0

> @

i

B

n

1

p

.

Zmienna losowa

n

ma zatem rozk

áad dwumianowy z wartoĞcią oczekiwaną

i

> @

1

E

np

n

i

i wariancj

ą

> @





n

p

np

n

i

1

1

1

Var





.

Na podstawie znanej zale

ĪnoĞci dla wartoĞci oczekiwanej i wariancji zmiennej

losowej otrzymujemy

> @

> @

> @

 

1

1

2

1

1

1

E

Var

E

2

2

2

4









n

n

n

n

n

i

i

i

.

Wynik ten, w po

áączeniu z (4.5), pozwala stwierdziü, Īe czas posortowania

elementów we wszystkich kube

ákach jest liniowy, a zatem oczekiwany czas

sortowania kube

ákowego jest takĪe liniowy.

Pytania kontrolne

1. Poda

ü definicjĊ oraz przykáady porządku czĊĞciowego i porządku

liniowego.

- 102 -

2. Sformu

áowaü ogólnie zadanie sortowania oraz scharakteryzowaü dwie klasy

algorytmów sortowania.

3. Wyja

Ğniü pojĊcia sortowania wewnĊtrznego i zewnĊtrznego.

4. Omówi

ü na przykáadzie uĪycie drzewa decyzyjnego do prezentacji

algorytmu sortowania za pomoc

ą porównaĔ.

5. Poda

ü dolne ograniczenie na pesymistyczny czas sortowania w algorytmach

wykorzystuj

ących tylko porównania i udowodniü jego poprawnoĞü.

6. Przedstawi

ü algorytm sortowania przez wstawianie i oszacowaü jego

z

áoĪonoĞü czasową.

7. Przedstawi

ü algorytm sortowania przez kopcowanie i oszacowaü jego

z

áoĪonoĞü czasową.

8. Na

przyk

áadzie algorytmu sortowania przez scalanie przedstawiü istotĊ

metody „dziel i zwyci

ĊĪaj“.

9. Dla algorytmu sortowania przez scalanie pokaza

ü zastosowanie zaleĪnoĞci

rekurencyjnej do oszacowania czasu dzia

áania algorytmu.

10. Omówi

ü algorytm sortowania przez zliczanie dziaáający w czasie liniowym

i wyja

Ğniü fakt, Īe dla tego algorytmu nie obowiązuje granica

:

.





n

n lg

11. Omówi

ü algorytm sortowania kubeákowego i wykazaü jego poprawnoĞü.

Jaka cecha

áączy algorytmy sortowania przez zliczanie i sortowania

kube

ákowego?

Zadania

1. Skonstruowa

ü drzewo decyzyjne odpowiadające algorytmowi sortowania

przez wstawianie dla ci

ągu

.

4

3

2

1

,

,

,

a

a

a

a

2. Napisa

ü procedurĊ SCALAJ(A,p,q,r) realizującą scalanie posortowanych

tablic

>

@

q

p

A ..

i

w jedn

ą posortowaną tablicĊ

>

r

q

A

..

1



@

>

@

r

p

A ..

, tak, aby

mog

áa ona byü wykorzystana w algorytmie sortowania przez scalanie.

3. Zilustrowa

ü dziaáanie procedury sortowania przez zliczanie dla tablicy

3

,

4

,

2

,

7

,

5

,

4

,

2

,

1

,

3

,

1

,

7

A

.

4. Zilustrowa

ü dziaáanie procedury sortowania kubeákowego dla tablicy

42

,

0

,

0,71

,

53

,

0

,

89

,

0

,

20

,

0

,

39

,

0

,

0,64

,

16

,

0

,

0,13

,

79

,

0

A

.

- 103 -

5 Bibliografia

[1] Aho A.V., Hopcroft J.E., Ullman J.D.: Projektowanie i analiza

algorytmów komputerowych. PWN, 1983.

[2] Anderson J.R., Corbett A.T., Reiser B.J.: Essential LISP.

Addison-Wesley Publishing Company, 1987.

[3] Banachowski L., Diks K., Rytter W.: Algorytmy i struktury

danych. Wydawnictwa Naukowo-Techniczne, 1996.

[4] Banachowski L., Kreczmar A.: Elementy analizy algorytmów.

Wydawnictwa Naukowo-Techniczne, 1982.

[5] Cormen T.H., Leiserson C.E,, Rivest R.L.: Wprowadzenie do

algorytmów. Wydawnictwa Naukowo-Techniczne, 1997.

[6] Drozdek A., Simon D.L.: Struktury danych w j

Ċzyku C.

Wydawnictwa Naukowo-Techniczne, 1996.

[7] Knuth D.E.: Sztuka programowania. Tom 1. Algorytmy

podstawowe. Wydawnictwa Naukowo-Techniczne, 2002.

[8] Winston P.H., Horn B.K.P.: LISP. Third Edition. Addison-Wesley

Publishing Company, 1989.

- 104 -

DODATEK

Zadania na egzaminy i kolokwia

W uzupe

ánieniu zostaną podane przykáadowe zestawy zadaĔ, jakie pojawiaáy

si

Ċ w ostatnich latach na egzaminach i kolokwiach. Przy kaĪdym zadaniu w

nawiasach podano maksymaln

ą liczbĊ punktów, na którą moĪe byü oceniona

prawid

áowa odpowiedĨ. Czas rowiązywania w przeliczeniu na 1 punkt wynosiá

Ğrednio 2 minuty. MoĪliwe jest wystąpienie w róĪnych zestawach podobnych, a
nawet identycznych zada

Ĕ. Pozostawiono je celowo, aby Czytelnik mógá

zmierzy

ü siĊ z „oryginalnymi” zestawami obejmującymi z reguáy odpowiednio

dobrany zakres materia

áu.

Zestaw 1

1. Zdefiniowa

ü jednym zdaniem nastĊpujące pojĊcia:

a) g

áĊbokoĞü wierzchoáka drzewa; (1)

b) operand typu i w j

Ċzyku maszyny RAM; (1)

c) silnie spójny graf skierowany; (1)
d) procedura rekurencyjna; (1)
e) algorytm sortuj

ący w czasie liniowym; (1)

f) asymptotycznie optymalny algorytm sortuj

ący wyáącznie za pomocą

porówna

Ĕ. (1)

2. Napisa

ü rekurencyjną procedurĊ obliczającą n-tą potĊgĊ liczby m (m>0). (2)

3. Rozwa

Īyü nastĊpujący program w jĊzyku maszyny RAM:

LOAD =0
STORE 1
LOAD =1
STORE 2

ET1: LOAD =5

SUB 2
JGTZ Et2
JUMP Et3

Et2: LOAD 1

ADD 2
STORE 1
LOAD 2
ADD =1
STORE 2
JUMP ET1

Et3: WRITE 1

HALT

- 105 -

a) Jaka jest waga logarytmiczna operandu w pierwszej komendzie LOAD? (1)
b) Jaka jest warto

Ğü operandu w komendzie z etykietą Et1? (1)

c) Jakiego typu adres wyst

Ċpuje w komendzie JGTZ? (1)

d) Ile razy wykona si

Ċ komenda ADD 2 ? (1)

e) Poda

ü wynik dziaáania programu (1)

f) Ile rejestrów wykorzystano w obliczeniach ? (1)
g) Jakie zadanie pe

áni tutaj rejestr 0 ? (1)

4. Rozwa

Īyü wyraĪenie: (((2-1)*3)+1).

a) Poda

ü odwrotny zapis polski tego wyraĪenia. (1)

b) Przedstawi

ü ciąg operacji na stosie wykonywanych w trakcie otrzymania

zapisu postfiksowego. (2)

c) Przedstawi

ü ciąg operacji na stosie wykonywanych w trakcie obliczania

warto

Ğci otrzymanego wyraĪenia postfiksowego. (2)

5.

Zak

áadamy Īe liczby: 1, 3, 5, 7, 9, 0 są odpowiednio elementami

A[1],..., A[6] tablicy A.

a) Sporz

ądziü rysunek pokazujący rozmieszczenie tych liczb w wĊzáach

odpowiedniego drzewa binarnego reprezentuj

ącego kopiec zbudowany w

wyniku wywo

áania procedury KOPIEC-BUDUJ(A). (2)

b) Przedstawi

ü rysunek pokazujący stan po usuniĊciu maksymalnego elementu

z kolejki priorytetowej reprezentowanej przez kopiec z p. a). (2)

c) Jak b

Ċdzie wyglądaáa kolejka priorytetowa reprezentowana przez kopiec z p.

a) po wykonaniu operacji dodawania elementu o warto

Ğci 8? (2)

6.

Zak

áada siĊ, Īe tablica A=¢3,4,1,4² jest sortowana przez zliczanie wedáug

nast

Ċpującego algorytmu:

SORT-ZLICZANIE(A, B, k)

1

dla

i

m1 do k

2

wykonuj

C[i]

m 0

3

dla

j

m1 do length[A]

4

wykonuj

C[A[j]]

m C[A[j]] + 1

5

dla

i

m2 do k

6

wykonuj

C[i]

m C[i] + C[i-1]

7

dla

j

m length[A] w_dóá_do 1

8

wykonuj

{ B[C[A[j]]]

m A[j]

9

C[A[j]]

m C[A[j]] – 1 }

a) Jaka jest zawarto

Ğü tablicy C przed wejĞciem do pĊtli w liniach 7-9? (1)

b) Jaka jest zawarto

Ğü tablicy C po wykonaniu procedury? (1)

c) Jaka jest zawarto

Ğü tablicy B po wykonaniu procedury? (1)

d) Jaka jest zawarto

Ğü tablicy A po wykonaniu procedury? (1)

- 106 -

Zestaw 2

1.

Zdefiniowa

ü jednym zdaniem nastĊpujące pojĊcia:

a) z

áoĪonoĞü pamiĊciowa; (1)

b) lista (definicja rekurencyjna); (1)
c) stopie

Ĕ wĊzáa w drzewie; (1)

d) rz

ąd drzewa; (1)

e) procedura rekurencyjna; (1)
f) algorytm sortuj

ący w czasie liniowym. (1)

2.

Napisa

ü w pseudokodzie procedurĊ , która dla i-tego elementu kopca

wypisuje po kolei elementy tworz

ące drogĊ od tego elementu do korzenia

kopca. (2)

3.

Rozwa

Īyü program:

LOAD =1
STORE 1
LOAD =1
STORE 2

ET1: LOAD =4

SUB 2
JGTZ Et2
JUMP Et3

Et2: LOAD 1

MULT 2
STORE 1
LOAD 2
ADD =1
STORE 2
JUMP ET1

Et3: WRITE 1

HALT

a)

Jaka jest waga logarytmiczna drugiej komendy STORE? (1)

b)

Jaka jest warto

Ğü operandu w komendzie z etykietą Et1? (1)

c)

Jakiego typu adres wyst

Ċpuje w komendzie JGTZ? (1)

d)

Ile razy wykona si

Ċ komenda MULT 2 ? (1)

e) Poda

ü wynik dziaáania programu. (1)

f)

Ile rejestrów wykorzystano w obliczeniach? (1)

g) Poda

ü wagĊ logarytmiczną operandu komendy MULT podczas jej ostatniego

wykonania. (1)

4.

Zak

áadamy Īe liczby: 1, 3, 5, 7, 9, 0 są odpowiednio elementami

A[1],..., A[6] tablicy A.

a) Sporz

ądziü rysunek pokazujący rozmieszczenie tych liczb w wĊzáach

odpowiedniego drzewa binarnego reprezentuj

ącego kopiec zbudowany w

wyniku wywo

áania procedury KOPIEC-BUDUJ(A). (2)

- 107 -

b) Przedstawi

ü rysunek pokazujący stan po usuniĊciu maksymalnego elementu

z kolejki priorytetowej reprezentowanej przez kopiec z p. a). (2)

c) Jak b

Ċdzie wyglądaáa kolejka priorytetowa reprezentowana przez kopiec z p.

a) po wykonaniu operacji dodawania elementu o warto

Ğci 8 ? (2)

5. Rozwa

Īyü nastĊpujące drzewo binarne:

4

3

0

-1

2

1

a) Poda

ü kolejnoĞü odwiedzania wierzchoáków tego drzewa metodą preorder. (1)

b) Poda

ü kolejnoĞü odwiedzania wierzchoáków tego drzewa metodą postorder. (1)

c) Poda

ü kolejnoĞü odwiedzania wierzchoáków tego drzewa metodą inorder. (1)

6.

Poda

ü definicjĊ porządku czĊĞciowego. (2)

7.

Zak

áada siĊ, Īe tablica A=¢3,4,1,4² jest sortowana przez zliczanie wedáug

nast

Ċpującego algorytmu:

SORT-ZLICZANIE(A, B, k)

1

dla

i

m1 do k

2

wykonuj

C[i]

m 0

3

dla

j

m1 do length[A]

4

wykonuj

C[A[j]]

m C[A[j]] + 1

5

dla

i

m2 do k

6

wykonuj

C[i]

m C[i] + C[i-1]

7

dla

j

m length[A] w_dóá_do 1

8

wykonuj

{ B[C[A[j]]]

m A[j]

9

C[A[j]]

m C[A[j]] – 1 }

Przedstawi

ü, jak zmienia siĊ zawartoĞü tablic B i C po wykonaniu

kolejnych iteracji w wierszach 7-9. Przed wej

Ğciem do pĊtli w liniach 7-9

C=

¢1,1,2,4². (4)

Zestaw 3

1.

Zdefiniowa

ü jednym zdaniem nastĊpujące pojĊcia:

a)

rozmiar zadania; (1)

b)

notacja

f

; (1)

 

 



n

g

n

:



c)

operand typu *i w j

Ċzyku maszyny RAM; (1)

d) z

áoĪonoĞü pesymistyczna; (1)

e)

lista dwukierunkowa; (1)

f)

struktury z ograniczonym dost

Ċpem; (1)

g)

cykl w grafie nieskierowanym. (1)

- 108 -

2.

Zapisa

ü w pseudojĊzyku algorytm wypisujący elementy listy L

reprezentowanej przy pomocy wska

Ĩników. (3)

3. Rozwa

Īyü program:

LOAD =10

STORE 2

Et1: READ 1
LOAD 1
JZERO Et3
LOAD 1
SUB 2
JGTZ Et2
JUMP Et1
Et2: LOAD 1
STORE 2
JUMP ET1
Et3: WRITE 2
HALT

a) Jaka jest warto

Ğü operandu w pierwszej komendzie LOAD? (1)

b) Jaka jest warto

Ğü operandu w komendzie z etykietą Et1? (1)

c) Jakiego typu adres wyst

Ċpuje w komendzie JZERO? (1)

d) (1) Poda

ü wynik dziaáania programu po wprowadzeniu liczb: 1 2 3 4 0.

e) (1) Poda

ü wynik dziaáania programu po wprowadzeniu liczb: 10 20 30 40 0.

4. Rozwa

Īyü graf nieskierowany G={V, E}, gdzie:

V={a, b, c, d},
E={(a,b), (a,c), (b,c), (b,d),(c,d)}.

a) Narysowa

ü ten graf. (1)

b) Naszkicowa

ü reprezentacjĊ grafu G z uĪyciem list sąsiedztwa. (2)

c) Naszkicowa

ü reprezentacjĊ grafu G z uĪyciem macierzy sąsiedztwa. (2)

5. Rozwa

Īyü wyraĪenie: (2-(1*(3+1))).

a) Poda

ü odwrotny zapis polski tego wyraĪenia. (1)

b) Przedstawi

ü ciąg operacji na stosie wykonywanych w trakcie otrzymywania

zapisu postfiksowego. (2)

c) Przedstawi

ü ciąg operacji na stosie wykonywanych w trakcie obliczania

warto

Ğci otrzymanego w p. b) wyraĪenia postfiksowego. (2)

6. Zak

áadamy Īe liczby: 1, 3, 6, –1, 0, 4, 2 są odpowiednio elementami

A[1],..., A[7] tablicy A.

a) Przedstawi

ü rysunki pokazujące ukáad tych liczb w tablicy A oraz w

w

Ċzáach odpowiedniego drzewa binarnego po zbudowaniu kopca. (2)

b) Jak b

Ċdzie wyglądaáa kolejka priorytetowa reprezentowana przez kopiec z

rys a) po wykonaniu operacji usuwania maksymalnego elementu? (2)

c) Rozmie

Ğciü liczby (pierwotnej) tablicy A w wĊzáach drzewa binarnego, tak,

aby powsta

áo drzewo BST o minimalnej gáĊbokoĞci. (1)

- 109 -

Zestaw 4

1.

Zdefiniowa

ü jednym zdaniem nastĊpujące pojĊcia:

a) g

áĊbokoĞü wierzchoáka drzewa; (1)

b) drzewo niezorientowane; (1)
c) operand typu i w j

Ċzyku maszyny RAM; (1)

d) silnie spójny graf skierowany; (1)
e) lista dwukierunkowa; (1)
f) sortowanie wewn

Ċtrzne; (1)

g) cykl w grafie skierowanym. (1)

2. Zapisa

ü w pseudojĊzyku procedurĊ MAX wyznaczającą maksymalną

spo

Ğród czytanych kolejno liczb. Procedura ta koĔczy pracĊ z chwilą

napotkania zera, wypisuj

ąc maksymalną liczbĊ. (3)

3.

Rozwa

Īyü program:

LOAD =10
STORE 2
Et1: READ 1
LOAD 1
JZERO Et3
LOAD 1
SUB 2
JGTZ Et2
JUMP Et1
Et2: LOAD 1
STORE 2
JUMP ET1
Et3: WRITE 2
HALT

a) Jaka jest warto

Ğü operandu w pierwszej komendzie LOAD? (1)

b) Jaka jest warto

Ğü operandu w komendzie z etykietą Et1? (1)

c) Jakiego typu adres wyst

Ċpuje w komendzie JZERO? (1)

d) (1) Poda

ü wynik dziaáania programu po wprowadzeniu liczb: 1 2 3 4 0.

e) (1) Poda

ü wynik dziaáania programu po wprowadzeniu liczb: 10 20 30 40 0.

4.

Rozwa

Īyü graf skierowany G={V, E}, gdzie:

V={a, b, c, d},
E={(a,b), (a,c), (b,d), (c,b),(d,c), (d,d)}.

a) Narysowa

ü ten graf. (1)

b) Naszkicowa

ü reprezentacjĊ grafu G z uĪyciem list sąsiedztwa. (2)

c) Naszkicowa

ü reprezentacjĊ grafu G z uĪyciem macierzy sąsiedztwa. (2)

5.

Rozwa

Īyü wyraĪenie: (((2-1)*3)+1).

a) Poda

ü odwrotny zapis polski tego wyraĪenia. (1)

b) Przedstawi

ü ciąg operacji na stosie wykonywanych w trakcie otrzymywania

zapisu postfiksowego. (2)

- 110 -

c) Przedstawi

ü ciąg operacji na stosie wykonywanych w trakcie obliczania

warto

Ğci otrzymanego w p. b) wyraĪenia postfiksowego. (2)

6. Rozwa

Īyü nastĊpujące drzewo binarne:

4

3

0

-1

2

1

a) Poda

ü kolejnoĞü odwiedzania wierzchoáków tego drzewa metodą preorder. (1)

b) Poda

ü kolejnoĞü odwiedzania wierzchoáków tego drzewa metodą postorder. (1)

c) Poda

ü kolejnoĞü odwiedzania wierzchoáków tego drzewa metodą inorder. (1)

d) Czy drzewo to ma w

áasnoĞü drzewa BST? (1)

e) Czy drzewo to ma w

áasnooĞü kopca? (1)

Zestaw 5

1.

Zdefiniowa

ü jednym zdaniem nastĊpujące pojĊcia:

a) rozmiar zadania; (1)
b) równomierne kryterium wagowe; (1)
c) operand typu i w j

Ċzyku maszyny RAM; (1)

d) spójny graf nieskierowany; (1)
e) procedura rekurencyjna. (1)

2.

Zapisa

ü w pseudojĊzyku procedurĊ, która wypisuje minimalny element

tablicy jednowymiarowej A zadanej jako parametr. (3)

3.

Rozwa

Īyü program:

LOAD =0
STORE 1
LOAD =1
STORE 2
ET1: LOAD =5
SUB 2
JGTZ Et2
JUMP Et3
Et2: LOAD 1
ADD 2
STORE 1
LOAD 2
ADD =1
STORE 2
JUMP ET1
Et3: WRITE 1
HALT

a) Jaka jest waga logarytmiczna operandu w pierwszej komendzie STORE? (1)

- 111 -

- 112 -

b) Jaka jest warto

Ğü operandu w komendzie z etykietą Et1? (1)

c) Jakiego typu adres wyst

Ċpuje w komendzie JGTZ? (1)

d) Ile razy wykona si

Ċ komenda ADD 2 ? (1)

e) Poda

ü wynik dziaáania programu. (1)

f) Ile rejestrów wykorzystano w obliczeniach? (1)
g) Jakie zadanie pe

áni tutaj rejestr 0 ? (1)

4. Zdefiniowa

ü jednym zdaniem nastĊpujące pojĊcia:

a) regularne drzewo binarne; (1)
b) podstawowa w

áasnoĞü kopca; (1)

c) w

Ċzeá wewnĊtrzny drzewa; (1)

d) drzewo poszukiwa

Ĕ binarnych; (1)

e) asymptotycznie optymalny algorytm sortuj

ący wyáącznie za pomocą

porówna

Ĕ. (1)

5. Napisa

ü iteracyjną wersjĊ algorytmu poszukiwania w drzewie BST

elementu o podanym kluczu. (3)

6. Poda

ü istotĊ metody „dziel i zwyciĊĪaj”. (2)

7. Zak

áadamy Īe liczby: 1, 2, 3, 4, 5, 6 są odpowiednio elementami A[1],...,

A[6] tablicy A.

a) Sporz

ądziü rysunki pokazujące rozmieszczenie tych liczb w tablicy A oraz

w w

Ċzáach odpowiedniego drzewa binarnego tak, aby byá to stan wyjĞciowy

dla procedury budowania kopca. (1)

b) Przedstawi

ü rysunki podobne jak w p. a), ale po zbudowaniu kopca. (2)

c) Jak b

Ċdzie wyglądaáa kolejka priorytetowa reprezentowana przez kopiec z

rys. b) po wykonaniu operacji usuwania maksymalnego elementu? (2)