Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00298 008578 11062418 na godz. na dobę w sumie
Algorytmy i struktury danych - książka
Algorytmy i struktury danych - książka
Autor: , , Liczba stron: 448
Wydawca: Helion Język publikacji: polski
ISBN: 83-7361-177-0 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> algorytmy - programowanie
Porównaj ceny (książka, ebook, audiobook).
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.:

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ą.
Znajdź podobne książki Ostatnio czytane w tej kategorii

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*XCTPGYENT5 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 ]_HQTXTGRTGGPVWLæE[MCľF[PKGRQMQNQTQYCP[LGUEGYKGTEJQđGMY) FQ ]_KHXPKGLGUVRQđæ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*XCTPGYENT5 6  ]ITGGF[CRKUWLGYPGYENTDKÎTYKGTEJQđMÎYMVÎT[OPCNGľ[ RT[RQTæFMQYCèVGPUCOMQNQT_ DGIKP ]_PGYENT∅ ]_HQTXTGRTGGPVWLæE[MCľF[PKGRQMQNQTYCP[LGUEGYKGTEJQđGMY) FQDGIKP ]_HQWPFHCNUG ]_HQTYTGRTGGPVWLæEGIQMCľF[YKGTEJQđGMYDKQTGPGYENT FQ ]_KHKUVPKGLGYITCHKG)MTCYúFļđæEæECYKGTEJQđMKXKY VJGP ]_HQWPFVTWG ]_KHHQWPFHCNUGVJGPDGIKP ]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 HQWPFDQQNGCP XYKPVGIGT DGIKP PGYENT XRKGTYU[PKGRQMQNQTQYCP[YKGTEJQđGMYITCHKG)  YJKNGX PWNNFQDGIKP HQWPFHCNUG YRKGTYU[YKGTEJQđGMGDKQTWPGYENT  YJKNGY PWNNFQDGIKP KHKUVPKGLGYITCHKG)MTCYúFļđæEæECYKGTEJQđMKXKY VJGP HQWPFVTWG YPCUVúRP[YKGTEJQđGMGDKQTWPGYENT  GPF KHHQWPFHCNUGFQDGIKP QPCEXLCMQRQMQNQTQYCP[ FQFCLXFQPGYENT GPF XPCUVú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) Y0 :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: PCOGCTTC[=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 TGENKUVCTTC[=?QHTGEQTF FCVCTGCN PGZVKPVGIGT 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[RGTGEQTF EWTUQTKPVGIGT 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)

Gdzie kupić całą publikację:

Algorytmy i struktury danych
Autor:
, ,

Opinie na temat publikacji:


Inne popularne pozycje z tej kategorii:


Czytaj również:


Prowadzisz stronę lub blog? Wstaw link do fragmentu tej książki i współpracuj z Cyfroteką: