Darmowy fragment publikacji:
IDZ DO
IDZ DO
PRZYK£ADOWY ROZDZIA£
PRZYK£ADOWY ROZDZIA£
SPIS TREĎCI
SPIS TREĎCI
KATALOG KSI¥¯EK
KATALOG KSI¥¯EK
KATALOG ONLINE
KATALOG ONLINE
ZAMÓW DRUKOWANY KATALOG
ZAMÓW DRUKOWANY KATALOG
TWÓJ KOSZYK
TWÓJ KOSZYK
DODAJ DO KOSZYKA
DODAJ DO KOSZYKA
CENNIK I INFORMACJE
CENNIK I INFORMACJE
ZAMÓW INFORMACJE
ZAMÓW INFORMACJE
O NOWOĎCIACH
O NOWOĎCIACH
ZAMÓW CENNIK
ZAMÓW CENNIK
CZYTELNIA
CZYTELNIA
FRAGMENTY KSI¥¯EK ONLINE
FRAGMENTY KSI¥¯EK ONLINE
Wydawnictwo Helion
ul. Chopina 6
44-100 Gliwice
tel. (32)230-98-63
e-mail: helion@helion.pl
Algorytmy i struktury
danych
Autorzy: Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman
T³umaczenie: Andrzej Gra¿yñski
ISBN: 83-7361-177-0
Tytu³ orygina³u: Data Structures and Algorithms
Format: B5, stron: 442
W niniejszej ksi¹¿ce przedstawiono struktury danych i algorytmy stanowi¹ce podstawê
wspó³czesnego programowania komputerów. Algorytmy s¹ niczym przepis na
rozwi¹zanie postawionego przed programistê problemu. S¹ one nierozerwalnie
zwi¹zane ze strukturami danych — listami, rekordami, tablicami, kolejkami, drzewami…
podstawowymi elementami wiedzy ka¿dego programisty.
Ksi¹¿ka obejmuje szeroki zakres materia³u, a do jej lektury wystarczy znajomoġæ
dowolnego jêzyka programowania strukturalnego (np. Pascala). Opis klasycznych
algorytmów uzupe³niono o algorytmy zwi¹zane z zarz¹dzaniem pamiêci¹ operacyjn¹
i pamiêciami zewnêtrznymi.
Ksi¹¿ka przedstawia algorytmy i struktury danych w kontekġcie rozwi¹zywania
problemów za pomoc¹ komputera. Z tematyk¹ rozwi¹zywania problemów powi¹zano
zagadnienie zliczania kroków oraz z³o¿onoġci czasowej — wynika to z g³êbokiego
przekonania autorów tej ksi¹¿ki, i¿ wraz z pojawianiem siê coraz szybszych
komputerów, pojawiaæ siê bêd¹ tak¿e coraz bardziej z³o¿one problemy
do rozwi¹zywania i — paradoksalnie — z³o¿onoġæ obliczeniowa u¿ywanych
algorytmów zyskiwaæ bêdzie na znaczeniu.
W ksi¹¿ce omówiono m.in.:
• Tradycyjne struktury danych: listy, kolejki, stosy
• Drzewa i operacje na strukturach drzew
• Typy danych oparte na zbiorach, s³owniki i kolejki priorytetowe wraz
ze sposobami ich implementacji
• Grafy zorientowane i niezorientowane
• Algorytmy sortowania i poszukiwania mediany
• Asymptotyczne zachowanie siê procedur rekurencyjnych
• Techniki projektowania algorytmów: „dziel i rz¹dĥ”, wyszukiwanie lokalne
i programowanie dynamiczne
• Zarz¹dzanie pamiêci¹, B-drzewa i struktury indeksowe
Ka¿demu rozdzia³owi towarzyszy zestaw æwiczeñ, o zró¿nicowanym stopniu trudnoġci,
pomagaj¹cych sprawdziæ swoj¹ wiedzê. „Algorytmy i struktury danych” to doskona³y
podrêcznik dla studentów informatyki i pokrewnych kierunków, a tak¿e dla wszystkich
zainteresowanych t¹ tematyk¹.
Spis treści
Od tłumacza ...................................................z...................................................z.......7
Wstęp ...................................................z...................................................z...............11
1
Projektowanie i analiza algorytmów...................................................z...................15
1.1. Od problemu do programu ...................................................l...................................................................... 15
1.2. Abstrakcyjne typy danych...................................................l....................................................................... 23
1.3. Typy danych, struktury danych i ADT ...................................................l................................................... 25
1.4. Czas wykonywania programu ...................................................l................................................................. 28
1.5. Obliczanie czasu wykonywania programu...................................................l.............................................. 33
1.6. Dobre praktyki programowania ...................................................l.............................................................. 39
1.7. Super Pascal ...................................................l...................................................l......................................... 41
Ćwiczenia...................................................l...................................................l.................................................... 44
Uwagi bibliograficzne...................................................l...................................................l................................. 48
2
Podstawowe abstrakcyjne typy danych ...................................................z..............49
2.1. Lista jako abstrakcyjny typ danych...................................................l......................................................... 49
2.2. Implementacje list ...................................................l...................................................l................................ 52
2.3. Stosy...................................................l...................................................l..................................................... 64
2.4. Kolejki...................................................l...................................................l.................................................. 68
2.5. Mapowania...................................................l...................................................l........................................... 73
2.6. Stosy a procedury rekurencyjne ...................................................l.............................................................. 75
Ćwiczenia...................................................l...................................................l.................................................... 80
Uwagi bibliograficzne...................................................l...................................................l................................. 84
3
Drzewa ...................................................z...................................................z.............85
3.1. Podstawowa terminologia ...................................................l....................................................................... 85
3.2. Drzewa jako abstrakcyjne obiekty danych...................................................l.............................................. 92
4
SPIS TREŚCI
3.3. Implementacje drzew ...................................................l...................................................l........................... 95
3.4. Drzewa binarne ...................................................l...................................................l.................................. 102
Ćwiczenia...................................................l...................................................l.................................................. 113
Uwagi bibliograficzne...................................................l...................................................l............................... 116
4
Podstawowe operacje na zbiorach ...................................................z....................117
4.1. Wprowadzenie do zbiorów............................l...................................................l........................................ 117
4.2. Słowniki ...................................................l...................................................l............................................. 129
4.3. Tablice haszowane ...................................................l...................................................l............................. 132
4.4. Implementacja abstrakcyjnego typu danych MAPPING ...................................................l...................... 146
4.5. Kolejki priorytetowe ...................................................l...................................................l.......................... 148
4.6. Przykłady złożonych struktur zbiorowych...................................................l............................................ 156
Ćwiczenia...................................................l...................................................l.................................................. 163
Uwagi bibliograficzne...................................................l...................................................l............................... 165
5
Zaawansowane metody reprezentowania zbiorów ..............................................167
5.1. Binarne drzewa wyszukiwawcze ...................................................l.......................................................... 167
5.2. Analiza złożoności operacji wykonywanych na binarnym drzewie wyszukiwawczym.......................... 171
5.3. Drzewa trie ...................................................l...................................................l......................................... 175
5.4. Implementacja zbiorów w postaci drzew wyważonych — 2-3-drzewa...................................................l 181
5.5. Operacje MERGE i FIND...................................................l..................................................................... 193
5.6. Abstrakcyjny typ danych z operacjami MERGE i SPLIT ...................................................l.................... 202
Ćwiczenia...................................................l...................................................l.................................................. 207
Uwagi bibliograficzne...................................................l...................................................l............................... 209
6
Grafy skierowane ...................................................z..............................................211
6.1. Podstawowe pojęcia ...................................................l...................................................l........................... 211
6.2. Reprezentacje grafów skierowanych...................................................l..................................................... 213
6.3. Graf skierowany jako abstrakcyjny typ danych ...................................................l.................................... 215
6.4. Znajdowanie najkrótszych ścieżek o wspólnym początku...................................................l.................... 217
6.5. Znajdowanie najkrótszych ścieżek między każdą parą wierzchołków ...................................................l. 221
6.6. Przechodzenie przez grafy skierowane — przeszukiwanie zstępujące...................................................l. 229
6.7. Silna spójność i silnie spójne składowe digrafu...................................................l.................................... 237
Ćwiczenia...................................................l...................................................l.................................................. 240
Uwagi bibliograficzne...................................................l...................................................l............................... 242
7
Grafy nieskierowane ...................................................z.........................................243
7.1. Definicje...................................................l...................................................l............................................. 243
7.2. Metody reprezentowania grafów...................................................l........................................................... 245
7.3. Drzewa rozpinające o najmniejszym koszcie..........l...................................................l.............................. 246
7.4. Przechodzenie przez graf ...................................................l...................................................................... 253
7.5. Wierzchołki rozdzielające i składowe dwuspójne grafu ...................................................l....................... 256
SPIS TREŚCI
5
7.6. Reprezentowanie skojarzeń przez grafy...................................................l................................................ 259
Ćwiczenia...................................................l...................................................l.................................................. 262
Uwagi bibliograficzne...................................................l...................................................l............................... 264
8
Sortowanie ...................................................z...................................................z.....265
8.1. Model sortowania wewnętrznego......................l...................................................l.................................... 265
8.2. Proste algorytmy sortowania wewnętrznego...........l...................................................l.............................. 266
8.3. Sortowanie szybkie (quicksort)...................................................l............................................................. 273
8.4. Sortowanie stogowe ...................................................l...................................................l........................... 283
8.5. Sortowanie rozrzutowe...................................................l.......................................................................... 287
8.6. Dolne ograniczenie dla sortowania za pomocą porównań ...................................................l.................... 294
8.7. Szukanie k-tej wartości (statystyki pozycyjne)...................................................l..................................... 298
Ćwiczenia...................................................l...................................................l.................................................. 302
Uwagi bibliograficzne...................................................l...................................................l............................... 304
9
Techniki analizy algorytmów ...................................................z...........................305
9.1. Efektywność algorytmów...................................................l...................................................................... 305
9.2. Analiza programów zawierających wywołania rekurencyjne...................................................l............... 306
9.3. Rozwiązywanie równań rekurencyjnych ...................................................l.............................................. 308
9.4. Rozwiązanie ogólne dla pewnej klasy rekurencji ...................................................l................................. 311
Ćwiczenia...................................................l...................................................l.................................................. 316
Uwagi bibliograficzne...................................................l...................................................l............................... 319
10
Techniki projektowania algorytmów ...................................................z................321
10.1. Zasada „dziel i zwyciężaj” ...................................................l.................................................................. 321
10.2. Programowanie dynamiczne ...................................................l............................................................... 327
10.3. Algorytmy zachłanne ...................................................l...................................................l....................... 335
10.4. Algorytmy z nawrotami ...................................................l...................................................................... 339
10.5. Przeszukiwanie lokalne...................................................l....................................................................... 349
Ćwiczenia...................................................l...................................................l.................................................. 355
Uwagi bibliograficzne...................................................l...................................................l............................... 358
11
Struktury danych i algorytmy obróbki danych zewnętrznych .............................359
11.1. Model danych zewnętrznych...................................................l............................................................... 359
11.2. Sortowanie zewnętrzne ...................................................l....................................................................... 362
11.3. Przechowywanie informacji w plikach pamięci zewnętrznych ...................................................l.......... 373
11.4. Zewnętrzne drzewa wyszukiwawcze ...................................................l.................................................. 381
Ćwiczenia...................................................l...................................................l.................................................. 387
Uwagi bibliograficzne...................................................l...................................................l............................... 390
6
12
SPIS TREŚCI
Zarządzanie pamięcią ...................................................z.......................................391
12.1. Podstawowe aspekty zarządzania pamięcią ...................................................l........................................ 391
12.2. Zarządzanie blokami o ustalonej wielkości ...................................................l........................................ 395
12.3. Algorytm odśmiecania dla bloków o ustalonej wielkości...................................................l................... 397
12.4. Przydział pamięci dla obiektów o zróżnicowanych rozmiarach ...................................................l......... 405
12.5. Systemy partnerskie ...................................................l...................................................l......................... 412
12.6. Upakowywanie pamięci ...................................................l...................................................................... 416
Ćwiczenia...................................................l...................................................l.................................................. 419
Uwagi bibliograficzne...................................................l...................................................l............................... 421
Bibliografia ...................................................z...................................................z....423
Skorowidz ...................................................z...................................................z......429
1
Projektowanie i analiza algorytmów
Stworzenie programu rozwiązującego konkretny problem jest procesem wieloetapowym. Proces ten
rozpoczyna się od sformułowania problemu i jego specyfikacji, po czym następuje projektowanie
rozwiązania, które musi zostać następnie zapisane w postaci konkretnego programu, czyli zaim-
plementowane. Konieczne jest udokumentowanie oraz przetestowanie implementacji, a rozwiąza-
nie wyprodukowane przez działający program musi zostać ocenione i zinterpretowane. W niniej-
szym rozdziale zaprezentowaliśmy nasze podejście do wymienionych kroków, następne rozdziały
poświęcone są natomiast algorytmom i strukturom danych, składającym się na większość progra-
mów komputerowych.
1.1. Od problemu do programu
Wiedzieć, jaki problem tak naprawdę się rozwiązuje — to już połowa sukcesu. Większość pro-
blemów, w swym oryginalnym sformułowaniu, nie ma klarownej specyfikacji. Faktycznie, niektó-
re (wydawałoby się) oczywiste problemy, jak „sporządzenie smakowitego deseru” czy też „za-
chowanie pokoju na świecie” wydają się niemożliwe do sformułowania w takiej postaci, która
przynajmniej otwierałaby drogę do ich rozwiązania za pomocą komputerów. Nawet jednak, gdy
dany problem wydaje się (w sposób mniej lub bardziej oczywisty) możliwy do rozwiązania przy
użyciu komputera, pozostaje jeszcze trudna zazwyczaj kwestia jego parametryzacji. Niekiedy by-
wa i tak, że rozsądne wartości parametrów mogą być ok reślone jedynie w drodze eksperymentu.
Jeżeli niektóre aspekty rozwiązywanego problemu dają się wyrazić w kategoriach jakiegoś
formalnego modelu, okazuje się to zwykle wielce pomocne, gdyż również w tych kategoriach po-
szukuje się rozwiązania, a dysponując konkretnym programem można określić (lub przynajmniej
spróbować określić), czy faktycznie rozwiązuje on dany problem. Także — abstrahując od kon-
kretnego programu — mając określoną wiedzę o modelu i jego właściwościach, można na tej pod-
stawie podjąć próbę znalezienia dobrego rozwiązania .
Na szczęście, każda niemal dyscyplina naukowa daje się ująć w ramy modelu (modeli) z jakiejś
dziedziny (dziedzin). Możliwe jest modelowanie wielu problemów natury wybitnie numerycznej
w postaci układów równań liniowych (w ten sposób oblicza się m.in. natężenia prądu w poszcze-
gólnych gałęziach obwodu elektrycznego czy naprężenia w układzie połączonych belek) bądź
równań różniczkowych (tak prognozuje się wzrost populacji i tak znajduje się stosunki ilościowe,
w jakich łączą się substraty reakcji chemicznych). Rozwiązywanie problemów natury tekstowej czy
symbolicznej odbywa się zazwyczaj na podstawie rozm aitych gramatyk wspomaganych zazwyczaj
16
1. PROJEKTOWANIE I ANALIZA ALGORYTMÓW
obfitym repertuarem procedur wykonujących różne operacje na łańcuchach znaków (w taki sposób
dokonuje się przecież kompilacja programu w języku wysokiego poziomu, tak również dokonuje
się wyszukiwania konkretnych fraz tekstowych w obsze rnych bibliotekach).
Algorytmy
Kiedy już dysponujemy odpowiednim modelem matematycznym dla naszego problemu, możemy
spróbować znaleźć rozwiązanie wyrażające się w kategoriach tegoż modelu. Naszym głównym
celem jest poszukiwanie rozwiązania w postaci algorytmu — pod tym pojęciem rozumiemy skoń-
czoną sekwencję instrukcji, z których każda ma klarowne znaczenie i może być wykonana w skoń-
czonym czasie przy użyciu skończonego wysiłku. Dobrym przykładem klarownej instrukcji, wyko-
nywalnej „w skończonym czasie i skończonym wysiłkiem”, jest instrukcja przypisania w rodzaju
Z [
. Oczywiście, poszczególne instrukcje algorytmu mogą być wykonywane wielokrotnie
i niekoniecznie w kolejności, w której zostały zapisane. Wynika stąd kolejne wymaganie stawiane
algorytmowi — musi się on zatrzymywać po wykonaniu skończonej liczby instrukcji, niezależnie
od danych wejściowych. Nasz program zasługuje więc na miano „algorytmu” tylko wtedy, gdy jego
wykonywanie nigdy (czyli dla żadnych danych wejściowych) nie prowadzi do „ugrzęźnięcia” ste-
rowania w nieskończonej pętli.
Co najmniej jeden aspekt powyższych rozważań nie jest do końca oczywisty. Określenie
„klarowne znaczenie” ma mianowicie charakter na wskroś relatywny, ponieważ to, co jest oczywiste
dla jednej osoby, może być wątpliwe dla innej. Ponadto wykonywanie się każdej z instrukcji w skoń-
czonym czasie może nie wystarczyć do tego, by „algorytm kończył swe działanie po wykonaniu
skończonej liczby instrukcji”. Za pomocą serii argumentów i kontrargumentów można jednak w więk-
szości przypadków osiągnąć porozumienie odnośnie tego, czy dana sekwencja instrukcji faktycznie
może być uważana za algorytm. Zazwyczaj ostateczne wyjaśnienie wątpliwości w tym względzie
jest powinnością osoby, która uważa się za autora algorytmu. W jednym z kolejnych punktów niniej-
szego rozdziału przedstawiliśmy sposób szacowania czasu wykonywania konstrukcji powszechnie
spotykanych w językach programowania, dowodząc tym s amym ich „skończoności czasowej”.
Do zapisu algorytmów używać będziemy języka Pascal „wzbogaconego” jednakże o niefor-
malne opisy w języku naturalnym — programy zapisywane w powstałym w ten sposób „pseudoję-
zyku” nie nadają się co prawda do wykonania przez komputer, lecz powinny być intuicyjnie zro-
zumiałe dla Czytelnika, a to jest przecież w tej książce najważniejsze. Takie podejście umożliwia
również ewentualne zastąpienie Pascala innym językiem, bardziej wygodnym dla Czytelnika, na
etapie tworzenia „prawdziwych” programów. Pora teraz na pierwszy przykład, w którym zilustro-
waliśmy większość etapów naszego podejścia do tworzeni a programów komputerowych.
Przykład 1.1. Stworzymy model matematyczny, opisujący funkcjonowanie sygnalizacji świetlnej
na skomplikowanym skrzyżowaniu. Ruch na takim skrzyżowaniu opisać można przez rozłożenie go
na poszczególne „zakręty” z konkretnej ulicy w inną (dla przejrzystości przejazd na wprost rów-
nież uważany jest za „zakręt”). Jeden cykl obsługi takiego skrzyżowania obejmuje pewną liczbę
faz, w każdej fazie mogą być równocześnie wykonywane te zakręty (i tylko te), które ze sobą nie
kolidują. Problem polega więc na określeniu poszczególnych faz ruchu i przyporządkowaniu każ-
dego z możliwych zakrętów do konkretnej fazy w taki sposób, by w każdej fazie każda para za-
krętów byłą parą niekolidującą. Oczywiście, rozwiązanie optymalne powinno wyznaczać najmniejszą
możliwą liczbę faz.
Rozpatrzmy konkretne skrzyżowanie, którego schemat przedstawiono na rysunku 1.1. Skrzy-
żowanie to znajduje się niedaleko Uniwersytetu Princeton i znane jest z trudności manewrowania,
1.1. OD PROBLEMU DO PROGRAMU
17
RYSUNEK 1.1.
Przykładowe
skrzyżowanie
zwłaszcza przy zawracaniu. Ulice C i E są jednokierunkowe, pozostałe są ulicami dwukierunko-
wymi. Na skrzyżowaniu tym można wykonać 13 różnych „zakrętów”; niektóre z nich, jak AB
(czyli z ulicy A w ulicę B) i EC, mogą być wykonywane równocześnie, inne natomiast, jak AD i EB,
kolidują ze sobą i mogą być wykonane tylko w różnych fazach.
Opisany problem daje się łatwo ująć („modelować”) w postaci struktury zwanej grafem. Każ-
dy graf składa się ze zbioru wierzchołków i zbioru linii łączących wierzchołki w pary — linie te
nazywane są krawędziami. W naszym grafie modelującym sterowanie ruchem na skrzyżowaniu
wierzchołki reprezentować będą poszczególne zakręty, a połączenie dwóch wierzchołków krawę-
dzią oznaczać będzie, że zakręty reprezentowane przez te wierzchołki kolidują ze sobą. Graf od-
powiadający skrzyżowaniu pokazanemu na rysunku 1.1 przedstawiony jest na rysunku 1.2, nato-
miast w tabeli 1.1 widoczna jest jego reprezentacja macierzowa — każdy wiersz i każda kolumna
reprezentuje konkretny wierzchołek; jedynka na przecięciu danego wiersza i danej kolumny wska-
zuje, że odpowiednie wierzchołki połączone są krawęd zią.
RYSUNEK 1.2.
Graf reprezentujący
skrzyżowanie pokazane
na rysunku 1.1
Rozwiązanie naszego problemu bazuje na koncepcji zwanej kolorowaniem grafu. Polega ona
na przyporządkowaniu każdemu wierzchołkowi konkretnego koloru w taki sposób, by wierzchołki
połączone krawędzią miały różne kolory. Nietrudno się domyślić, że optymalne rozwiązanie naszego
problemu sprowadza się do znalezienia takiego kolorowania grafu z rysunku 1.2, które wykorzystuje
jak najmniejszą liczbę kolorów.
18
1. PROJEKTOWANIE I ANALIZA ALGORYTMÓW
TABELA 1.1.
Macierzowa reprezentacja grafu z rysunku 1.2
AB
AC
AD
BA
BC
BD
DA
DB
DC
EA
EB
EC
ED
AB
AC
AD
BA
BC
BD
DA
DB
DC
EA
EB
EC
ED
Zagadnienie kolorowania grafu studiowane było przez dziesięciolecia i obecna wiedza na temat
algorytmów zawiera wiele propozycji w tym względzie. Niestety, problem kolorowania dowolnego
grafu przy użyciu najmniejszej możliwej liczby kolorów zalicza się do ogromnej klasy tzw. pro-
blemów NP-zupełnych, dla których jedynymi znanymi rozwiązaniami są rozwiązania typu „sprawdź
wszystkie możliwości”. W przełożeniu na kolorowanie grafu oznacza to sukcesywne próby wyko-
rzystania jednego koloru, potem dwóch, trzech itd. tak długo, aż w końcu liczba użytych kolorów
okaże się wystarczająca (czego stwierdzenie również wymaga „sprawdzenia wszystkich możliwo-
ści”). Co prawda wykorzystanie specyfiki konkretnego grafu może ten proces nieco przyspieszyć,
jednakże w ogólnym wypadku nie istnieje alternatywa dla oczywistego „sprawdzania wszystkich
możliwości”.
Okazuje się więc, że znalezienie optymalnego pokolorowania grafu jest w ogólnym przypadku
procesem bardzo kosztownym i dla dużych grafów może okazać się zupełnie nie do przyjęcia, nie-
zależnie od tego, jak efektywnie skonstruowany byłby program rozwiązujący zagadnienie. Zasto-
sujemy w związku z tym trzy możliwe podejścia. Po pierwsze, dla małych grafów duży koszt cza-
sowy nie będzie zbytnią przeszkodą i „sprawdzenie wszystkich możliwości” będzie zadaniem
wykonalnym w rozsądnym czasie. Drugie podejście polegać będzie na wykorzystaniu specjalnych
własności grafu, pozwalających na rezygnację a priori z dość dużej liczby sprawdzeń. Trzecie po-
dejście odwoływać się będzie natomiast do znanej prawdy, że rozwiązanie problemu można znacznie
przyspieszyć, rezygnując z poszukiwania rozwiązania optymalnego i zadowalając się rozwiąza-
niem dobrym, możliwym do zaakceptowania w konkretnych warunkach i często niewiele gorszym
od optymalnego — tym bardziej, że wiele rzeczywistych skrzyżowań nie jest aż tak skomplikowa-
nych, jak pokazane na rysunku 1.1. Takie algorytmy, szybko dostarczające dobrych, lecz nieko-
niecznie optymalnych rozwiązań, nazywane są algorytm ami heurystycznymi.
Jednym z heurystycznych algorytmów kolorowania grafu jest tzw. algorytm „zachłanny”
(ang. greedy). Kolorujemy pierwszym kolorem tyle wierzchołków, ile tylko możemy. Następnie
wybieramy kolejny kolor i wykonać należy kolejno następujące czynności:
(1) Wybierz dowolny niepokolorowany jeszcze wierzchołek i przyporządkuj mu aktualnie uży-
wany kolor.
1.1. OD PROBLEMU DO PROGRAMU
19
(2) Przejrzyj listę wszystkich niepokolorowanych jeszcze wierzchołków i dla każdego z nich
sprawdź, czy jest połączony krawędzią z jakimś wierzchołkiem mającym aktualnie używany
kolor. Jeżeli nie jest, opatrz go tym kolorem.
„Zachłanność” algorytmu wynika stąd, że w każdym kroku (tj. przy każdym z używanych
kolorów) stara się on pokolorować jak największą liczbę wierzchołków, niezależnie od ewentualnych
negatywnych konsekwencji tego faktu. Nietrudno wskazać przypadek, w którym mniejsza zachłan-
ność prowadzi do zastosowania mniejszej liczby kolorów. Graf przedstawiony na rysunku 1.3 można
pokolorować przy użyciu tylko dwóch kolorów; jednego dla wierzchołków 1, 3 i 4, drugiego dla
pozostałych. Algorytm zachłanny, analizujący wierzchołki w kolejności wzrastającej numeracji,
rozpocząłby natomiast od przypisania pierwszego kol oru wierzchołkom 1 i 2, po czym wierzchołki
3 i 4 otrzymałyby drugi kolor, a dla wierzchołka 5 konieczne byłoby użycie trzeciego koloru.
RYSUNEK 1.3.
Przykładowy graf,
dla którego nie popłaca
zachłanność algorytmu
kolorowania
Zastosujmy teraz „zachłanne” kolorowanie do grafu z rysunku 1.2. Rozpoczynamy od wierz-
1
chołka AB, nadając mu pierwszy z kolorów — niebieski; kolorem tym możemy także opatrzyć
wierzchołki AC, AD i BA, ponieważ są one „osamotnione”. Nie możemy nadać koloru niebieskiego
wierzchołkowi BC, gdyż jest on połączony z (niebieskim) wierzchołkiem AB; z podobnych wzglę-
dów nie możemy także pokolorować na niebiesko wierzchołków BD, DA i DB, możemy to jednak
zrobić z wierzchołkiem DC. Wierzchołkom EA, EB i EC nie można przyporządkować koloru nie-
bieskiego — w przeciwieństwie do „osamotnionego” wierz chołka ED.
Weźmy kolejny kolor — czerwony. Przyporządkowujemy go wierzchołkom BC i BD; wierz-
chołek DA łączy się krawędzią z BD, więc nie może mieć koloru czerwonego, podobnie jak wierz-
chołek DB łączący się z BC. Spośród niepokolorowanych jeszcze wierzchołków tylko EA można
nadać kolor czerwony.
Pozostały cztery niepokolorowane wierzchołki: DA, DB, EB i EC. Jeżeli przypiszemy DA
kolor zielony, możemy go także przyporządkować DB, jednakże dla EB i EC musimy wtedy użyć
kolejnego (żółtego) koloru. Ostateczny wynik kolorowania przedstawiamy w tabeli 1.2. Dla każ-
dego koloru w kolumnie Ekstra prezentujemy te wierzchołki, które nie są połączone z żadnym
wierzchołkiem w tym kolorze i przy innej kolejności przechodzenia zachłannego algorytmu przez
wierzchołki mogłyby ten właśnie kolor uzyskać.
Zgodnie z wcześniejszymi założeniami, wszystkie wierzchołki w danym kolorze (kolumna
Wierzchołki) odpowiadają zakrętom „uruchamianym” w danej fazie. Oprócz nich można także uru-
chomić inne zakręty, które z nimi nie kolidują (mimo że reprezentujące je wierzchołki mają inny
kolor), są one wyszczególnione w kolumnie Ekstra.
Tak więc wedle otrzymanego rozwiązania, sygnalizacja sterująca ruchem na skrzyżowaniu
pokazanym na rysunku 1.1 powinna być sygnalizacją czterofazową. Po doświadczeniach z grafem
przedstawionym na rysunku 1.3 nie można nie zastanawiać się, czy jest rozwiązanie optymalne,
tzn. czy nie byłoby możliwe rozwiązanie problemu przy użyciu sygnalizacji trój- czy dwufazowej.
1 Zgodnie z kolejnością przyjętą w tabeli na rysunku 1.3 — przyp. tłum.
20
1. PROJEKTOWANIE I ANALIZA ALGORYTMÓW
TABELA 1.2.
Jeden ze sposobów pokolorowania grafu z rysunku 1.2
za pomocą „zachłannego” algorytmu
Kolor
Wierzchołki
Ekstra
niebieski
czerwony
zielony
żółty
AB, AC, AD, BA, DC, ED
BC, BD, EA
DA, DB
EB, EC
—
BA, DC, ED
AD, BA, DC, ED
BA, DC, EA, ED
Rozstrzygniemy tę wątpliwość za pomocą elementarnych wiadomości z teorii grafów. Nazwijmy
k-kliką zbiór k wierzchołków, w których każde dwa połączone są krawędziami. Jest oczywiste, że
nie da się pokolorować k-kliki przy użyciu mniej niż k kolorów. Gdy spojrzymy uważnie na rysu-
nek 1.2 spostrzeżemy, że wierzchołki AC, DA, BD i EB tworzą 4-klikę, wykluczone jest zatem po-
kolorowanie grafu wykorzystując mniej niż 4 kolory, zatem nasze rozwiązanie jest optymalne pod
względem liczby faz.
Pseudojęzyki i stopniowe precyzowanie
Gdy tylko znajdziemy odpowiedni model matematyczny dla rozwiązywanego problemu, możemy
przystąpić do formułowania algorytmu w kategoriach tego modelu. Początkowa wersja takiego algo-
rytmu składa się zazwyczaj z bardzo ogólnych instrukcji, które w kolejnych krokach należy uściślić,
czyli zastąpić instrukcjami bardziej precyzyjnymi. Przykładowo, sformułowanie „wybierz dowolny
niepokolorowany jeszcze wierzchołek” jest intuicyjnie zrozumiałe dla osoby studiującej algorytm,
lecz aby z algorytmu tego stworzyć program możliwy do wykonania przez komputer, sformułowa-
nia takie muszą zostać poddane stopniowej formalizacji. Postępowanie takie nazywa się stopniowym
precyzowaniem (ang. stepwise refinement) i prowadzi do uzyskania programu w pełni zgodnego ze
składnią konkretnego języka programowania.
Przykład 1.2. Poddajmy więc stopniowemu precyzowaniu „zachłanny” algorytm kolorowania grafu,
a dokładniej jego część związaną z konkretnym kolorem. Zakładamy wstępnie, że mamy do czy-
nienia z grafem G, którego niektóre wierzchołki mogą być pokolorowane. Poniższa procedura tworzy
zbiór wierzchołków newclr, którym należy przyporządkować odnośny kolor. Procedura ta wywo-
ływana jest cyklicznie tak długo, aż wszystkim węzłom grafu przyporządkowane zostaną kolory.
Pierwsze, najbardziej ogólne sformułowanie wspomnianej procedury może wyglądać tak, jak na
listingu 1.1.
LISTING 1.1.
Początkowa wersja procedury greedy
RTQEGFWTGITGGF[
XCT) )4#2* XCTPGYENT 5 6
]ITGGF[CRKUWLGYPGYENTDKÎTYKGTEJQđMÎYMVÎT[OPCNGľ[
RT[RQTæFMQYCèVGPUCOMQNQT_
DGIKP
]_PGYENT ∅
2 Symbol ∅ oznacza zbiór pusty.
1.1. OD PROBLEMU DO PROGRAMU
21
]_HQT XTGRTGGPVWLæE[MCľF[PKGRQMQNQTQYCP[LGUEGYKGTEJQđGMY) FQ
]_KH XPKGLGUVRQđæEQP[MTCYúFKæľCFP[OYKGTEJQđMKGOYEJQFæE[O
YUMđCFPGYENT VJGPDGIKP
]_QPCEXLCMQRQMQNQTQYCP[
]_FQFCLXFQPGYENT
GPF
GPF ]ITGGF[_
Na listingu 1.1 widoczne są podstawowe elementy zapisu algorytmu w pseudojęzyku. Po
pierwsze, widzimy zapisane tłustym drukiem i małymi literami słowa kluczowe, które odpowia-
dają zastrzeżonym słowom języka Pascal. Po drugie, słowa pisane w całości wielkimi literami —
)4#2* i 5 63
są nazwami abstrakcyjnych typów danych. W procesie stopniowego precyzowania
typy te muszą zostać zdefiniowane w postaci typów danych pascalowych oraz procedur wykonu-
jących na tych danych określone operacje. Abstrakcyjnymi typami danych zajmiemy się szczegó-
łowo w dwóch następnych punktach.
Konstrukcje strukturalne Pascala, jak: if, for i while są użyte w naszym pseudojęzyku w ory-
ginalnej postaci, jednakże już np. warunek w instrukcji if (w wierszu {3}) zapisany jest w sposób
zupełnie nieformalny, podobnie zresztą jak wyrażenie stojące po prawej stronie instrukcji przypi-
sania w wierszu {1}. Nieformalnie został także zapisany zbiór, po którym iterację przeprowadza
instrukcja for w wierszu {2}.
Nie będziemy szczegółowo opisywać procesu przekształcania przedstawionej procedury do
poprawnego programu pascalowego, zaprezentujemy jedynie transformację instrukcji if z wiersza
{3} do bardziej precyzyjnej postaci.
Aby określić, czy dany wierzchołek X połączony jest krawędzią z którymś z wierzchołków
należących do zbioru PGYENT, rozpatrzymy każdy element Y tego zbioru i będziemy sprawdzać, czy
w grafie ) istnieje krawędź łącząca wierzchołki X oraz Y. Wynik sprawdzenia zapisywać będziemy
w zmiennej boolowskiej HQWPF — jeśli rzeczona krawędź istnieje, zmiennej tej nadana zostanie
wartość VTWG.
Zmieniona wersja procedury przedstawiona została na listingu 1.2.
LISTING 1.2.
Rezultat częściowego sprecyzowania procedury greedy
RTQEGFWTGITGGF[
XCT) )4#2* XCTPGYENT 5 6
]ITGGF[CRKUWLGYPGYENTDKÎTYKGTEJQđMÎYMVÎT[OPCNGľ[
RT[RQTæFMQYCèVGPUCOMQNQT_
DGIKP
]_PGYENT ∅
]_HQT XTGRTGGPVWLæE[MCľF[PKGRQMQNQTYCP[LGUEGYKGTEJQđGMY)
FQDGIKP
]_HQWPF HCNUG
]_HQT YTGRTGGPVWLæEGIQMCľF[YKGTEJQđGMYDKQTGPGYENT FQ
]_KH KUVPKGLGYITCHKG)MTCYúFļđæEæECYKGTEJQđMKXKY VJGP
]_HQWPF VTWG
]_KHHQWPF HCNUGVJGPDGIKP
]XPKGđæE[UKúľCFP[OYKGTEJQđMKGOGDKQTWPGYENT_
]_QPCEXLCMQRQMQNQTQYCP[
]_FQFCLXFQPGYENT
3 Odróżniamy tu abstrakcyjny typ danych 5 6 od typu zbiorowego UGV języka Pascal.
22
1. PROJEKTOWANIE I ANALIZA ALGORYTMÓW
]_GPF
GPF
GPF ]ITGGF[_
Zredukowaliśmy tym samym nasz algorytm do zbioru operacji wykonywanych na dwóch
zbiorach wierzchołków. Pętla zewnętrzna (wiersze od {2} do {5}) stanowi iterację po niepokolo-
rowanych wierzchołkach grafu ); pętla wewnętrzna (wiersze od {3.2} do {3.4}) iteruje natomiast
po wierzchołkach znajdujących się aktualnie w zbiorze PGYENT. Instrukcja w wierszu {5} dodaje
nowy wierzchołek do zbioru PGYENT.
Język Pascal oferuje wiele możliwości reprezentowania zbiorów danych — niektórymi z nich
zajmiemy się dokładniej w rozdziałach 4. i 5. Na potrzeby reprezentowania zbioru wierzchołków
w naszym przykładzie wykorzystamy inny abstrakcyjny typ danych, .+56, który może być zaim-
plementowany jako lista liczb całkowitych (KPVGIGT), zakończona specjalną wartością PWNN (która
może być reprezentowana przez wartość ). Lista ta może mieć postać tablicy, lecz — jak zoba-
czymy w rozdziale 2. — istnieje wiele innych sposobów jej reprezentowania.
Zastąpmy instrukcję for w wierszu 3.2 na listingu 1.2 przez pętlę, w której zmienna Y repre-
zentuje kolejne wierzchołki zbioru PGYENT (w kolejnych obrotach pętli). Identycznemu zabiegowi
poddamy pętlę rozpoczynającą się w wierszu {2}. W rezultacie otrzymamy nową, bardziej precy-
zyjną wersję procedury, która zaprezentowana jest n a listingu 1.3.
LISTING 1.3.
Kolejny etap sprecyzowania procedury ITGGF[
RTQEGFWTGITGGF[
XCT) )4#2* XCTPGYENT .+56
]ITGGF[CRKUWLGYPGYENTDKÎTYKGTEJQđMÎYMVÎT[OPCNGľ[
RT[RQTæFMQYCèVGPUCOMQNQT_
XCT
HQWPF DQQNGCP
XY KPVGIGT
DGIKP
PGYENT
X RKGTYU[PKGRQMQNQTQYCP[YKGTEJQđGMYITCHKG)
YJKNGX PWNNFQDGIKP
HQWPF HCNUG
Y RKGTYU[YKGTEJQđGMGDKQTWPGYENT
YJKNGY PWNNFQDGIKP
KH KUVPKGLGYITCHKG)MTCYúFļđæEæECYKGTEJQđMKXKY VJGP
HQWPF VTWG
Y PCUVúRP[YKGTEJQđGMGDKQTWPGYENT
GPF
KHHQWPF HCNUGFQDGIKP
QPCEXLCMQRQMQNQTQYCP[
FQFCLXFQPGYENT
GPF
X PCUVúRP[PKGRQMQNQTQYCP[YKGTEJQđGMYITCHKG)
GPF
GPF ]ITGGF[_
Procedurze pokazanej na listingu 1.3 sporo jeszcze brakuje do tego, by została zaakceptowa-
na przez kompilator Pascala. Poprzestaniemy jednak na tym etapie jej precyzowania, gdyż chodzi
nam raczej o prezentację określonego sposobu postęp owania niż ostateczny wynik.
1.2. ABSTRAKCYJNE TYPY DANYCH
23
Podsumowanie
Na rysunku 1.4 przedstawiamy schemat procesu tworzenia programu, zgodnie z ujęciem w niniej-
szej książce. Proces ten rozpoczyna się etapem modelowania, na którym wybrany zostaje odpo-
wiedni model matematyczny dla danego problemu (np. graf). Na tym etapie opis algorytmu ma
zazwyczaj postać wybitnie nieformalną.
RYSUNEK 1.4.
Proces rozwiązywania
problemu za pomocą
komputera
Kolejnym krokiem jest zapisanie algorytmu w pseudojęzyku stanowiącym mieszankę instrukcji
pascalowych i nieformalnych opisów wyrażonych w języku naturalnym. Realizacja tego etapu polega
na stopniowym precyzowaniu ogólnych, nieformalnych opisów do bardziej szczegółowej postaci.
Niektóre fragmenty zapisu algorytmu mogą mieć już wystarczająco szczegółową postać do tego,
by można było wyrazić je w kategoriach konkretnych operacji wykonywanych na konkretnych danych,
w związku z czym nie muszą być już bardziej precyzowane. Po odpowiednim sprecyzowaniu in-
strukcji algorytmu, definiujemy abstrakcyjne typy danych dla wszystkich struktur używanych przez
algorytm (z wyjątkiem być może struktur skrajnie elementarnych, jak: liczby całkowite, liczby rzeczy-
wiste czy łańcuchy znaków). Z każdym abstrakcyjnym typem danych wiążemy zestaw odpowiednio
nazwanych procedur, z których każda wykonuje konkretną operację na danych tego typu. Każda
nieformalnie zapisana operacja zostaje następnie za stąpiona wywołaniem odpowiedniej procedury.
W trzecim kroku wybieramy odpowiednią implementację dla każdego typu danych, w szczegól-
ności dla związanych z tym typem procedur wykonujących konkretne operacje. Zastępujemy także
istniejące jeszcze nieformalne zapisy „prawdziwymi” instrukcjami języka Pascal. W efekcie otrzy-
mujemy program, który można skompilować i uruchomić. Po cyklu testowania i usuwania błędów
(mamy nadzieję — krótkiego) otrzymamy poprawny program dostarczający upragnione rozwiązanie.
1.2. Abstrakcyjne typy danych
Większość omawianych dotychczas zagadnień powinna być znana nawet początkującym progra-
mistom. Jedynym istotnym novum mogą być abstrakcyjne typy danych, celowe więc będzie uświa-
domienie sobie ich roli w szeroko rozumianym procesie projektowania programów. W tym celu
posłużymy się analogią — dokonamy mianowicie wyszczególnienia wspólnych cech abstrakcyjnych
typów danych i procedur pascalowych.
Procedury, jako podstawowe narzędzie każdego języka algorytmicznego, stanowią tak naprawdę
uogólnienie operatorów. Uwalniają one od kłopotliwego ograniczenia do podstawowych operacji
(w rodzaju dodawania czy mnożenia liczb), pozwalając na dokonywanie operacji bardziej zaawan-
sowanych, jak np. mnożenie macierzy.
Inną użyteczną cechą procedur jest enkapsulacja niektórych fragmentów kodu. Określony frag-
ment programu, związany ściśle z pewnym aspektem funkcjonalnym programu, zamykany jest
w ramach ściśle zlokalizowanej sekcji. Jako przykład posłuży procedura dokonująca wczytywania
i weryfikacji danych. Jeżeli w pewnym momencie okaże się, że program powinien (powiedzmy)
24
1. PROJEKTOWANIE I ANALIZA ALGORYTMÓW
oprócz liczb dziesiętnych honorować także liczby w postaci szesnastkowej, niezbędne zmiany
trzeba będzie wprowadzić jedynie w ściśle określonym fragmencie kodu, bez ingerowania w inne
fragmenty programu.
Definiowanie abstrakcyjnych typów danych
Abstrakcyjne typy danych, często dla prostoty oznaczane skrótem ADT (ang. Abstract Data Types),
mogą być traktowane jak model matematyczny, z którym związano określoną kolekcję operacji.
Przykładem prostego ADT może być zbiór liczb całkowitych, w stosunku do którego określono
operacje sumy, iloczynu i różnicy (w rozumieniu teorii mnogości). Argumentami operacji związa-
nych z określonym ADT mogą być także dane innych typów, dotyczy to także wyniku operacji.
Przykładowo, wśród operacji związanych z ADT reprezentującym zbiór liczb całkowitych znaj-
dować się mogą procedury badające przynależność określonego elementu do zbioru, zwracające
liczbę elementów czy też tworzące nowy zbiór złożony z podanych parametrów. Tak czy inaczej,
macierzysty ADT wystąpić musi jednak co najmniej raz jako argument którejś ze swych procedur.
Dwie wspomniane wcześniej cechy procedur — uogólnienie i enkapsulacja — stosują się jako
żywo do abstrakcyjnych typów danych. Tak jak procedury stanowią uogólnienie elementarnych
operatorów (
, Ō, , itd.), tak abstrakcyjne typy danych są uogólnieniem elementarnych typów danych
(KPVGIGT, TGCN, DQQNGCP itd.). Odpowiednikiem enkapsulacji kodu przez procedury jest natomiast enka-
psulacja typu danych — w tym sensie, że definicja struktury konkretnego ADT wraz z towarzyszą-
cymi tej strukturze operacjami zamknięta zostaje w ściśle zlokalizowanym fragmencie programu.
Każda zmiana postaci czy zachowania ADT uskuteczniana jest wyłącznie w jego definicji, natomiast
przez pozostałe fragmenty ów ADT traktowany jest — to ważne — jako elementarny typ danych.
Pewnym odstępstwem od tej reguły jest sytuacja, w której dwa różne ADT są ze sobą powiązane,
czyli procedury jednego ADT uzależnione są od pewnych szczegółów drugiego. Enkapsulacja nie
jest wówczas całkowita i niektórych zmian dokonać tr zeba na ogół w definicjach obydwu ADT.
By dokładniej zrozumieć podstawowe idee tkwiące u podstaw koncepcji abstrakcyjnych typów
danych, przyjrzyjmy się dokładniej typowi .+56 wykorzystywanemu w procedurze ITGGF[ na listingu
1.3. Reprezentuje on listę liczb całkowitych (KPVGIGT) o nazwie PGYENT, a podstawowe operacje
wykonywane w kontekście tej listy są następujące:
(1) Usuń wszystkie elementy z listy.
(2) Udostępnij pierwszy element listy lub wartość PWNN, jeżeli lista jest pusta.
(3) Udostępnij kolejny element listy lub wartość PWNN, jeżeli wyczerpano zbiór elementów.
(4) Wstaw do listy nowy element (liczbę całkowitą).
Istnieje wiele struktur danych, które mogłyby posłużyć do efektywnej implementacji typu
.+56 — zajmiemy się nimi dokładniej w rozdziale 2. Gdybyśmy w zapisie algorytmu na listingu 1.3,
używającym powyższych opisów, zastąpili je wywołaniam i procedur:
(1) /#- 07..
PGYENT ;
(2) Y (+456
PGYENT ;
(3) Y 0 :6
PGYENT ;
(4) +05 46
XPGYENT);
od razu widoczna stałaby się podstawowa zaleta abstrakcyjnych typów danych. Otóż program ko-
rzystający z ADT ogranicza się tylko do wywoływania związanych z nim procedur — ich imple-
mentacja jest dla niego obojętna. Dokonując zmian w tej implementacji nie musimy ingerować
w wywołania procedur.
1.3. TYPY DANYCH, STRUKTURY DANYCH I ADT
25
Drugim abstrakcyjnym typem danych, używanym przez procedurę ITGGF[, jest )4#2* repre-
zentujący graf, z następującymi operacjami podstawo wymi:
(1) Udostępnij pierwszy niepokolorowany wierzchołek.
(2) Sprawdź, czy dwa podane wierzchołki połączone są kra wędzią.
(3) Przyporządkuj kolor wierzchołkowi.
(4) Udostępnij kolejny niepokolorowany wierzchołek.
Wymienione cztery operacje są co prawda wystarczające w procedurze ITGGF[, lecz oczywiście zestaw
podstawowych operacji na grafie powinien być nieco bogatszy i powinien obejmować na przykład:
dodanie krawędzi między podanymi wierzchołkami, usunięcie konkretnej krawędzi, usunięcie kolo-
rowania z wszystkich wierzchołków itp. Istnieje wiele struktur danych zdolnych do reprezentowania
grafu w tej postaci — przedstawimy je dokładniej w rozdziałach 6. i 7.
Należy wyraźnie zaznaczyć, że nie istnieje ograniczenie liczby operacji podstawowych zwią-
zanych z danym modelem matematycznym. Każdy zbiór tych operacji definiuje odrębny ADT.
Przykładowo, zestaw operacji podstawowych dla abstrakcyjnego typu danych 5 6 mógłby być na-
stępujący:
(1) /#- 07..
# — procedura usuwająca wszystkie elementy ze zbioru A,
(2) 70+10
#$ — procedura przypisująca zbiorowi C sumę zbiorów A i B,
(3) 5+
# — funkcja zwracająca liczbę elementów w zbiorze A.
Implementacja abstrakcyjnego typu danych polega na zdefiniowaniu jego odpowiednika (jako
typu) w kategoriach konkretnego języka programowania oraz zapisaniu (również w tym języku) pro-
cedur implementujących jego podstawowe operacje. „Typ” w języku programowania stanowi za-
zwyczaj kombinację typów elementarnych tego języka oraz obecnych w tym języku mechanizmów
agregujących. Najważniejszymi mechanizmami agregującymi języka Pascal są tablice i rekordy.
Na przykład abstrakcyjny zbiór 5 6 zawierający liczby całkowite może być zaimplementowany
jako tablica liczb całkowitych.
Należy także podkreślić jeden istotny fakt. Abstrakcyjny typ danych jest kombinacją modelu
matematycznego i zbioru operacji, jakie można na tym modelu wykonywać, dlatego dwa iden-
tyczne modele, połączone z różnymi zbiorami operacji, określają różne ADT. Większość materiału
zawartego w niniejszej książce poświęcona jest badaniu podstawowych modeli matematycznych, jak
zbiory i grafy, i znajdowaniu najodpowiedniejszych (w konkretnych sytuacjach) zestawów operacji
dla tych modeli.
Byłoby wspaniale, gdybyśmy mogli tworzyć programy w językach, których elementarne typy
danych i operacje są jak najbliższe używanym przez nas modelom i operacjom abstrakcyjnych typów
danych. Język Pascal (pod wieloma względami) nie jest najlepiej przystosowany do odzwiercie-
dlania najczęściej używanych ADT, w dodatku nieliczne języki, w których abstrakcyjne typy danych
deklarować można bezpośrednio, nie są powszechnie znane (o niektórych z nich wspominamy w notce
bibliograficznej).
1.3. Typy danych, struktury danych i ADT
Mimo że określenia „typ danych” (lub po prostu „typ”), „struktura danych” i „abstrakcyjny typ danych”
brzmią podobnie, ich znaczenie jest całkowicie odmienne. W terminologii języka programowania
„typem danych” nazywamy zbiór wartości, jakie przyjmować mogą zmienne tego typu. Na przykład
zmienna typu DQQNGCP przyjmować może tylko dwie wartości: VTWG i HCNUG. Poszczególne języki
26
1. PROJEKTOWANIE I ANALIZA ALGORYTMÓW
programowania różnią się od siebie zestawem elementarnych typów danych; elementarnymi typami
danych języka Pascal są: liczby całkowite (KPVGIGT), liczby rzeczywiste (TGCN), wartości boolow-
skie (DQQNGCP) i znaki (EJCT). Także mechanizmy agregacyjne, za pomocą których tworzy się typy
złożone z typów elementarnych, różne są w różnych językach — niebawem zajmiemy się mecha-
nizmami agregacyjnymi Pascala.
Abstrakcyjnym typem danych (ADT) jest model, z którym skojarzono zestaw operacji podsta-
wowych. Jak już wspominaliśmy, możemy formułować algory tmy w kategoriach ADT, chcąc jednak
zaimplementować dany algorytm w konkretnym języku programowania, musimy znaleźć sposób
reprezentowania tych ADT w kategoriach typów danych i operatorów właściwych temu językowi.
Do reprezentowania modeli matematycznych składających się na poszczególne ADT służą struk-
tury danych, które stanowią kolekcje zmiennych (być może różnych typów) połączonych ze sobą
na różne sposoby.
Podstawowymi blokami tworzącymi struktury danych są komórki (ang. cells). Komórkę można
obrazowo opisać jako skrzynkę, w której można przechowywać pojedynczą wartość należącą do
danego typu (elementarnego lub złożonego). Struktury danych tworzy się przez nadanie nazwy agre-
gatom takich komórek i (opcjonalnie) przez zinterpretowanie zawartości niektórych komórek jako
połączenia (czyli wskaźnika) między komórkami.
Najprostszym mechanizmem agregującym, obecnym w Pascalu i większości innych języków
programowania, jest (jednowymiarowa) tablica (ang. array) stanowiąca sekwencję komórek zawie-
rających wartości określonego typu, zwanego często typem bazowym. Pod względem matematycznym
można postrzegać tablicę jako odwzorowanie zbioru indeksów (którymi mogą być liczby całkowite)
w typ bazowy. Konkretna komórka w ramach konkretnej tablicy może być identyfikowana w postaci
nazwy, której towarzyszy konkretna wartość indeksu. W języku Pascal indeksami mogą być m.in.
liczby całkowite z określonego przedziału (noszącego nazwę typu okrojonego) oraz wartości typu
wyliczeniowego, jak np. typ (czarny, niebieski, czerwony, zielony). Typ bazowy tablicy może być
w zasadzie dowolnym typem, tak więc deklaracja:
PCOG CTTC[=KPFGZV[RG?QHEGNNV[RG
określa tablicę o nazwie PCOG, złożoną z elementów typu bazowego EGNNV[RG, indeksowanych warto-
ściami typu KPFGZV[RG.
Język Pascal jest skądinąd niezwykle bogaty pod względem możliwości wyboru typu indek-
sowego. Niektóre inne języki, jak Fortran, dopuszczają w tej roli jedynie liczby całkowite (z okre-
ślonego przedziału). Chcąc w takiej sytuacji użyć np. znaków w roli typu indeksowego, musieliby-
śmy uciec się do jakiegoś ich odwzorowania w liczby c ałkowite, np. bazując na ich kodach ASCII.
Innym powszechnie używanym mechanizmem agregującym są rekordy. Rekord jest komórką
składającą się z innych komórek zwanych polami, mających na ogół różne typy. Rekordy często łączone
są w tablice — typ rekordowy staje się wówczas type m bazowym tablicy. Deklaracja pascalowa:
XCT
TGENKUV CTTC[=?QHTGEQTF
FCVC TGCN
PGZV KPVGIGT
GPF
określa czteroelementową tablicę, której komórka je st rekordem zawierającym dwa pola: FCVC i PGZV.
Trzecim mechanizmem agregującym, dostępnym w Pascalu i niektórych innych językach, są
pliki. Plik, podobnie jak jednowymiarowa tablica, stanowi sekwencję elementów określonego typu.
W przeciwieństwie jednak do tablicy, plik nie podlega indeksowaniu; elementy dostępne są tylko
w takiej kolejności w jakiej fizycznie występują w pliku. Poszczególne elementy tablicy (i poszczególne
1.3. TYPY DANYCH, STRUKTURY DANYCH I ADT
27
pola rekordu) są natomiast dostępne w sposób bezpośredni, czyli szybciej niż w pliku. Plik odróż-
nia jednak od tablicy istotna zaleta — jego wielkość (liczba zawartych w nim elementów) może
zmieniać się w czasie i jest potencjalnie nieograni czona.
Wskaźniki i kursory
Oprócz mechanizmów agregujących istnieją jeszcze inne sposoby ustanawiania relacji między komór-
kami — służą do tego wskaźniki i kursory. Wskaźnik jest komórką, której zawartość jednoznaczni e
identyfikuje inną komórkę. Fakt, że komórka A jest wskaźnikiem komórki B, zaznaczamy na sche-
macie struktury danych rysując strzałkę od A do B.
W języku Pascal to, że zmienna RVT może wskazywać komórkę o typie EGNNV[RG, zaznaczamy
w następujący sposób:
XCT
RVT ↑EGNNV[RG
Strzałka poprzedzająca nazwę typu bazowego oznacza typ wskaźnikowy (czyli zbiór wartości sta-
nowiących wskazania na komórkę o typie EGNNV[RG). Odwołanie do komórki wskazywanej przez
zmienną RVT (zwane także dereferencją wskaźnika) ma postać RVT↑ — strzałka występuje za na-
zwą zmiennej.
Kursor tym różni się od wskaźnika, że identyfikuje komórkę w ramach konkretnej tablicy —
wartością kursora jest indeks odnośnego elementu. W samym zamyśle nie różni się on od wskaź-
nika — jego zadaniem jest także identyfikowanie komórki — jednak, w przeciwieństwie do niego,
nie można za pomocą kursora identyfikować komórek „samodzielnych”, które nie wchodzą w skład
tablicy. W niektórych językach, jak np. Fortran i Algol, wskaźniki po prostu nie istnieją i jedyną
metodą identyfikowania komórek są właśnie kursory. Należy także zauważyć, że w Pascalu nie jest
możliwe utworzenie wskaźnika do konkretnej komórki tablicy, więc jedynie kursory umożliwiają
identyfikowanie poszczególnych komórek. Niektóre języki, jak PL/I i C, są pod tym względem
bardziej elastyczne i dopuszczają wskazywanie eleme ntów tablic przez „prawdziwe” wskaźniki.
Na schemacie struktury danych kursory zaznaczane są podobnie jak wskaźniki, czyli za po-
dla za-
mocą strzałek, a dodatkowo w komórkę będącą kursorem może być wpisana jej zawartość
znaczenia, iż nie mamy do czynienia z „typowym” wskaźn ikiem.
4
Przykład 1.3. Na rysunku 1.5 pokazano strukturę danych składającą się z dwóch części: tablicy
TGENKUV (zdefiniowanej wcześniej w tym rozdziale) i kursorów do elementów tej tablicy; kursory
te połączone są w listę łańcuchową. Elementy tablicy TGENKUV są rekordami. Pole PGZV każdego z tych
rekordów jest kursorem do „następnego” rekordu i zgodnie z tą konwencją, na rysunku 1.5 rekordy
tablicy uporządkowane są w kolejności 4, 1, 3, 2. Zwróć uwagę, że pole PGZV rekordu 2 zawiera
wartość 0, oznaczającą kursor pusty, czyli nie identyfikujący żadnej komórki, konwencja taka ma
sens jedynie wtedy, gdy komórki tablicy indeksowane są począwszy od 1, nie od zera.
4 Wynika to z jeszcze jednej, fundamentalnej różnicy między wskaźnikiem a kursorem. Otóż implementa-
cja wskaźników w Pascalu (i wszystkich niemal językach, w których wskaźniki są obecne) bazuje na adresie
komórki w przestrzeni adresowej procesu. Adres ten (a więc i konkretna wartość wskaźnika) ma sens jedynie
w czasie wykonywania programu — nie istnieje więc jakakolwiek wartość wskaźnika, którą można by umie-
ścić na schemacie. Kursor natomiast jest wielkością absolutną, pozostającą bez związku z konkretnymi adre-
sami komórek — przyp. tłum.
28
1. PROJEKTOWANIE I ANALIZA ALGORYTMÓW
Każda komórka łańcucha (w górnej części rysunku) jest re kordem o następującej definicji:
RYSUNEK 1.5.
Przykładowa
struktura danych
V[RG
TGEQTFV[RG TGEQTF
EWTUQT KPVGIGT
RVT ↑TGEQTFV[RG
GPF
Pole EWTUQT tego rekordu jest kursorem do jakiegoś elementu tablicy TGENKUV, pole RVT zawiera
natomiast wskaźnik do następnej komórki w łańcuchu. Wszystkie rekordy łańcucha są rekordami
anonimowymi, nie mają nazw, gdyż każdy z nich utworzony został dynamicznie, w wyniku wywoła-
nia funkcji PGY. Pierwszy rekord łańcucha wskazywany jest natomiast przez zmienną JGCFGT:
XCT
JGCFGT ↑TGEQTFV[RG
Pole FCVC pierwszego rekordu w łańcuchu zawiera kursor do czwartego elementu tablicy TGENKUV,
pole RVT jest natomiast wskaźnikiem do drugiego rekordu. W drugim rekordzie pole data ma war-
tość 2, co oznacza kursor do drugiego elementu tablicy TGENKUV; pole RVT jest natomiast pustym
wskaźnikiem oznaczającym po prostu brak wskazania na cokolwiek. W języku Pascal „puste”
wskazanie oznaczane jest słowem kluczowym nil.
1.4. Czas wykonywania programu
Programista przystępujący do rozwiązywania jakiegoś problemu staje często przed wyborem jed-
nego spośród wielu możliwych algorytmów. Jakimi kryteriami powinien się wówczas kierować?
Otóż istnieją pod tym względem dwa, sprzeczne ze sob ą, kryteria oceny:
(1) Najlepszy algorytm jest łatwy do zrozumienia, kodow ania i weryfikacji.
(2) Najlepszy algorytm prowadzi do efektywnego wykorzystania zasobów komputera i jest jed-
nocześnie tak szybki, jak to tylko możliwe.
1.4. CZAS WYKONYWANIA PROGRAMU
29
Jeżeli tworzony program ma być uruchamiany tylko od czasu do czasu, wiążące będzie z pew-
nością pierwsze kryterium. Koszty związane z wytworzeniem programu są wówczas znacznie wyższe
od kosztów wynikających z jego uruchamiania, należy więc dążyć do jak najefektywniejszego
wykorzystania czasu programistów, bez szczególnej troski o obciążenie zasobów systemu. Jeżeli
jednak program ma być uruchamiany często, koszty związane z jego wykonywaniem szybko się
zwielokrotnią. Wówczas górę biorą względy natury efektywnościowej, gdzie liczy się szybki algo-
rytm, bez względu na jego stopień komplikacji. Warto niekiedy wypróbować kilka różnych algo-
rytmów i wybrać najbardziej opłacalny w konkretnych warunkach. W przypadku dużych złożo-
nych systemów może okazać się także celowe przeprowadzanie pewnych symulacji badających
zachowania konkretnych algorytmów. Wynika stąd, że programiści powinni nie tylko wykazać się
umiejętnością optymalizowania programów, lecz także powinni umieć określić, czy w danej sytu-
acji zabiegi optymalizacyjne są w ogóle uzasadnione .
Pomiar czasu wykonywania programu
Czas wykonywania konkretnego programu zależy od szer egu czynników, w szczególności:
(1) danych wejściowych,
(2) jakości kodu wynikowego generowanego przez kompilat or,
(3) architektury i szybkości komputera, na którym progra m jest wykonywany,
(4) złożoności czasowej algorytmu użytego do konstrukcji programu.
To, że czas wykonywania programu zależeć może od danych wejściowych, prowadzi do wnio-
sku, iż czas ten powinien być możliwy do wyrażenia w postaci pewnej funkcji wybranego aspektu
tych danych — owym „aspektem” jest najczęściej rozmiar danych. Znakomitym przykładem wpływu
danych wejściowych na czas wykonania programu jest proces sortowania danych w rozmaitych
odmianach, którymi zajmiemy się szczegółowo w rozdziale 8. Jak wiadomo, dane wejściowe pro-
gramu sortującego mają postać listy elementów. Rezultatem wykonania programu jest lista złożona
z tych samych elementów, lecz uporządkowana według określonego kryterium. Przykładowo, lista
2, 1, 3, 1, 5, 8 po uporządkowaniu w kolejności rosnącej będzie mieć postać 1, 1, 2, 3, 5, 8. Naj-
bardziej intuicyjną miarą rozmiaru danych wejściowych jest liczba elementów w liście, czyli dłu-
gość listy wejściowej. Kryterium długości listy wejściowej jako ro
Pobierz darmowy fragment (pdf)
