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
Projektowanie i analiza
algorytmów
Autorzy: Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman
T³umaczenie: Wojciech Derechowski
ISBN: 83-7197-770-0
Tytu³ orygina³u: The Design and Analysis
of Computer Algorithms
Format: B5, stron: 488
Badanie algorytmów le¿y w samym sercu nauk komputerowych. W ostatnich latach
dokonano znacz¹cych postêpów w tej dziedzinie. Opracowano m.in. wiele
efektywniejszych algorytmów (szybkie przekszta³cenie Fouriera), odkryto tak¿e
istnienie pewnych naturalnych zadañ, dla których wszystkie algorytmy s¹ nieefektywne.
Wyniki te powoduj¹ wzrost zainteresowania badaniami algorytmów, co przyczynia siê
do intensywnego rozwoju tej dziedziny wiedzy.
Ksi¹¿ka jest podrêcznikiem wstêpnego kursu projektowania i analizy algorytmów.
Autorzy po³o¿yli nacisk raczej na prezentacji najwa¿niejszych idei i przystêpnoġci
wyk³adu, ni¿ na szczegó³ach realizacji i sztuczkach programistycznych. Autorzy
przedstawiaj¹ na ogó³ nieformalne, intuicyjne objaġnienia zamiast d³ugich
i pracoch³onnych dowodów. Ksi¹¿ka nie wymaga ¿adnego szczególnego przygotowania
z zakresu matematyki, czy jêzyków programowania. Po¿¹dana jest jednak pewna
dojrza³oġæ w stosowaniu pojêæ matematycznych, ogólne obycie w jêzykach
programowania wysokiego poziomu, takich jak FORTRAN lub ALGOL, a tak¿e
podstawowa znajomoġæ algebry liniowej.
W ksi¹¿ce omówiono m.in.:
• Podstawowe pojêcia i modele (w tym maszynê Turniga)
• Najwa¿niejsze struktury danych, rekurencjê, programowanie dynamiczne
• Algorytmy sortowania, operacje na zbiorach, drzewach i grafach
• Szybkie przekszta³cenie Fouriera z zastosowaniami
• Algorytmy arytmetyczne, operacje na wielomianach
• Algorytmy dopasowania wzorców
• Problemy NP-zupe³ne
• Dolne ograniczenia z³o¿onoġci obliczeniowej
Wa¿nym uzupe³nieniem treġci ksi¹¿ki s¹ æwiczenia o zró¿nicowanych poziomach
trudnoġci. „Projektowanie i analiza algorytmów” to doskona³y podrêcznik dla studentów
informatyki i kierunków pokrewnych, a tak¿e wspania³a pomoc dla osób prowadz¹cych
wyk³ady i æwiczenia na tych kierunkach.
Spis treści
Przedmowa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
7
1. Modele obliczania . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.1 Algorytmy i ich złożoność . . . . . . . . . . . . . . . . . . . . . . . . 11
1.2 Maszyny o dostępie swobodnym . . . . . . . . . . . . . . . . . . . . . 14
1.3 Złożoność obliczeniowa programów RAM . . . . . . . . . . . . . . . 20
1.4 Model z zapamiętanym programem . . . . . . . . . . . . . . . . . . . 23
1.5 Abstrakcje RAM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
1.6 Pierwotny model obliczania: maszyna Turinga . . . . . . . . . . . . . 34
1.7 Związek pomiędzy maszyną Turinga i modelem RAM . . . . . . . . 39
1.8 Pidgin ALGOL — język wysokiego poziomu . . . . . . . . . . . . . . 41
2. Projektowanie efektywnych algorytmów . . . . . . . . . . . . . . . 51
2.1 Struktury danych: listy, kolejki i stosy . . . . . . . . . . . . . . . . . 52
2.2 Reprezentacje zbioru . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
2.3 Grafy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
2.4 Drzewa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
2.5 Rekurencja . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
2.6 Dziel i zwyciężaj
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
2.7 Zrównoważenie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
2.8 Programowanie dynamiczne . . . . . . . . . . . . . . . . . . . . . . . 74
2.9 Zakończenie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
3. Sortowanie i statystyka pozycyjna . . . . . . . . . . . . . . . . . . . 85
3.1 Problem sortowania . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
3.2 Sortowanie pozycyjne
. . . . . . . . . . . . . . . . . . . . . . . . . . 87
3.3 Sortowanie przez porównania . . . . . . . . . . . . . . . . . . . . . . 95
3.4 Heapsort — algorytm sortowania przez O(n log n) porównań . . . . 96
3.5 Quicksort — algorytm sortowania w czasie oczekiwanym O(n log n) 101
3.6 Statystyka pozycyjna . . . . . . . . . . . . . . . . . . . . . . . . . . . 106
3.7 Czas oczekiwany dla statystyki pozycyjnej . . . . . . . . . . . . . . . 108
4. Struktury danych dla zadań operujących na zbiorach . . . . . . . 117
4.1 Operacje pierwotne na zbiorach . . . . . . . . . . . . . . . . . . . . . 117
4.2 Haszowanie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120
4.3 Poszukiwanie binarne
. . . . . . . . . . . . . . . . . . . . . . . . . . 122
4.4 Drzewa poszukiwań binarnych . . . . . . . . . . . . . . . . . . . . . . 124
4.5 Optymalne drzewa poszukiwań binarnych . . . . . . . . . . . . . . . 128
4
Spis treści
4.6 Prosty algorytm sumy zbiorów rozłącznych . . . . . . . . . . . . . . 132
4.7 Struktury drzew dla problemu UNION-FIND . . . . . . . . . . . . . 136
4.8 Zastosowania i rozszerzenia algorytmu UNION-FIND . . . . . . . . . 146
4.9 Schematy z drzewami zrównoważonymi . . . . . . . . . . . . . . . . . 152
4.10 Słowniki i kolejki priorytetowe
. . . . . . . . . . . . . . . . . . . . . 155
4.11 Kopce złączane . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159
4.12 Kolejki konkatenowane . . . . . . . . . . . . . . . . . . . . . . . . . . 162
4.13 Podział
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
4.14 Podsumowanie rozdziału . . . . . . . . . . . . . . . . . . . . . . . . . 169
5. Algorytmy na grafach . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
5.1 Drzewa rozpinające o minimalnym koszcie . . . . . . . . . . . . . . . 179
5.2 Przeszukiwanie w głąb . . . . . . . . . . . . . . . . . . . . . . . . . . 183
5.3 Dwuspójność . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187
5.4 Przeszukiwanie w głąb grafu skierowanego . . . . . . . . . . . . . . . 195
5.5 Spójność silna . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 197
5.6 Problemy znajdowania ścieżek . . . . . . . . . . . . . . . . . . . . . . 203
5.7 Algorytm przechodniego domknięcia . . . . . . . . . . . . . . . . . . 207
5.8 Algorytm najkrótszych ścieżek . . . . . . . . . . . . . . . . . . . . . 208
5.9 Problemy ścieżek i mnożenie macierzy . . . . . . . . . . . . . . . . . 210
5.10 Problemy jednego źródła . . . . . . . . . . . . . . . . . . . . . . . . . 215
5.11 Dominatory w acyklicznym grafie skierowanym . . . . . . . . . . . . 218
6. Mnożenie macierzy i pokrewne operacje . . . . . . . . . . . . . . . 235
6.1 Podstawy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 235
6.2 Algorytm Strassena mnożenia macierzy . . . . . . . . . . . . . . . . 239
6.3 Odwracanie macierzy . . . . . . . . . . . . . . . . . . . . . . . . . . . 241
6.4 Rozkład LUP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 242
6.5 Zastosowania rozkładu LUP . . . . . . . . . . . . . . . . . . . . . . . 250
6.6 Mnożenie macierzy zero-jedynkowych . . . . . . . . . . . . . . . . . . 252
7. Szybkie przekształcenie Fouriera z zastosowaniami
. . . . . . . . 263
7.1 Dyskretna transformata Fouriera i transformata odwrotna . . . . . . 264
7.2 Algorytm szybkiego przekształcenia Fouriera . . . . . . . . . . . . . 268
7.3 FFT z operacjami na bitach . . . . . . . . . . . . . . . . . . . . . . . 276
7.4
Iloczyny wielomianów . . . . . . . . . . . . . . . . . . . . . . . . . . 281
7.5 Mnożenie liczb całkowitych według algorytm Sch¨onhagego–Strassena 282
8. Arytmetyka na liczbach całkowitych i wielomianach . . . . . . . . 289
8.1 Podobieństwo między liczbami całkowitymi i wielomianami
. . . . . 290
8.2 Mnożenie i dzielenie liczb całkowitych . . . . . . . . . . . . . . . . . 291
8.3 Mnożenie i dzielenie wielomianów . . . . . . . . . . . . . . . . . . . . 298
8.4 Arytmetyka modularna . . . . . . . . . . . . . . . . . . . . . . . . . 300
8.5 Arytmetyka modularna na wielomianach i wartości wielomianów . . 304
8.6 Chińskie zliczanie reszt . . . . . . . . . . . . . . . . . . . . . . . . . . 306
8.7 Chińskie zliczanie reszt i interpolacja wielomianów . . . . . . . . . . 310
8.8 Największy wspólny dzielnik i algorytm Euklidesa . . . . . . . . . . 312
Spis treści
5
8.9 Asympotycznie szybki algorytm GCD dla wielomianów . . . . . . . . 315
8.10 Największy wspólny dzielnik liczb całkowitych . . . . . . . . . . . . . 320
8.11 Chińskie zliczanie reszt — raz jeszcze . . . . . . . . . . . . . . . . . . 322
. . . . . . . . . . . . . . . . . . . . . . . . . . . 323
8.12 Wielomiany rzadkie
9. Algorytmy dopasowania wzorców . . . . . . . . . . . . . . . . . . . . 329
. . . . . . . . . . . . . . 329
9.1 Automaty skończone i wyrażenia regularne
9.2 Rozpoznawanie wzorców przez wyrażenia regularne . . . . . . . . . . 338
9.3 Rozpoznawanie podnapisów . . . . . . . . . . . . . . . . . . . . . . . 341
9.4 Dwukierunkowe deterministyczne automaty ze stosem . . . . . . . . 347
9.5 Drzewa pozycji i indentyfikatory podnapisowe . . . . . . . . . . . . . 358
10. Problemy NP-zupełne . . . . . . . . . . . . . . . . . . . . . . . . . . . 375
10.1 Niedeterministyczne maszyny Turinga . . . . . . . . . . . . . . . . . 376
10.2 Klasy P i N P . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383
10.3 Języki i problemy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385
10.4 NP-zupełność problemu spełnialności . . . . . . . . . . . . . . . . . . 388
. . . . . . . . . . . . . . . . . . . . . . . 395
10.5 Inne problemy NP-zupełne
10.6 Problemy o wielomianowej złożoności pamięciowej
. . . . . . . . . . 406
11. Problemy niełatwe na podstawie dowodu . . . . . . . . . . . . . . . 417
11.1 Hierarchie złożoności . . . . . . . . . . . . . . . . . . . . . . . . . . . 417
11.2 Hierarchia pamięciowa dla deterministycznych maszyn Turinga . . . 418
11.3 Problem wymagający wykładniczego czasu i pamięci
. . . . . . . . . 421
11.4 Problem nieelementarny . . . . . . . . . . . . . . . . . . . . . . . . . 430
12. Ograniczenia dolne liczby operacji arytmetycznych . . . . . . . . 439
12.1 Ciała . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 439
12.2 Kod liniowy — raz jeszcze . . . . . . . . . . . . . . . . . . . . . . . . 440
12.3 Macierzowe formułowanie problemów . . . . . . . . . . . . . . . . . . 443
12.4 Ograniczenie dolne liczby mnożeń zależne od liczby wierszy . . . . . 443
12.5 Ograniczenie dolne liczby mnożeń zależne od liczby kolumn . . . . . 445
12.6 Ograniczenie dolne liczby mnożeń zależne od liczby wierszy i kolumn 450
12.7 Nastawianie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 452
Bibliografia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463
Indeks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 477
Rozdział 1.
Modele obliczania
Jak, mając dany problem, znajdziemy efektywny algorytm rozwiązania? Gdy zna-
leźliśmy algorytm, jak mamy porównać ten algorytm z innymi algorytmami, które
rozwiązują ten sam problem? Jak powinniśmy oceniać jakość algorytmu? Pytania
tego rodzaju są ciekawe zarówno dla programisty, jak i dla uczonego o teoretycz-
nym nastawieniu do nauk komputerowych. W książce rozpatrujemy różne kierunki
badań, które usiłują odpowiedzieć na takie pytania.
W tym rozdziale rozważamy kilka modeli komputera — maszynę o dostępie swo-
bodnym, maszynę z zapamiętanym programem i maszynę Turinga. Porównujemy
je co do tego, jak odzwierciedają złożoność algorytmu i wyprowadzamy z nich kilka
wyspecjalizowanych modeli obliczeń: liniowe programy arytmetyczne, obliczenia na
bitach, obliczenia na wektorach bitów i drzewa decyzji. Wreszcie, w ostatnim punk-
cie rozdziału wprowadzamy język do opisu algorytmów, zwany „Pidgin ALGOL”.
1.1. Algorytmy i ich złożoność
Algorytmy mogą być oceniane na podstawie rozmaitych kryteriów. Najczęściej in-
teresuje nas szybkość z jaką wzrastają czas lub pamięć potrzebne, by rozwiązać
zadanie w coraz bardziej wymagających przypadkach. Zawsze będziemy przypisy-
wać zadaniu liczbę całkowitą, zwaną rozmiarem zadania, która jest miarą wielkości
danych. Na przykład rozmiarem zadania w przypadku mnożenia macierzy może być
największy wymiar macierzy, które mamy pomnożyć. Rozmiarem zadania z grafem
może być liczba krawędzi grafu.
Wymagany przez algorytm czas wyrażony jako funkcja rozmiaru zadania zwany
jest złożonością czasową algorytmu. Zachowanie się tej złożoności w granicy, gdy
rozmiar zadania wzrasta, nazywa się asymptotyczną złożonością czasową. Podobnie
można zdefiniować złożoność pamięciową i asymptotyczną złożoność pamięciową.
Asymptotyczna złożoność algorytmu jest tym, co ostatecznie rozstrzyga o rozmia-
rze zadań, które mogą być rozwiązane przez ten algorytm. Jeżeli algorytm prze-
twarza dane o rozmiarze n w czasie cn2 dla pewnej stałej c, to mówimy, że czasowa
złożoność tego algorytmu jest O(n2), czytaj „rzędu n2”. Ściślej, funkcja g(n) jest
12
Rozdział 1. Modele obliczania
Algorytm
Złożoność
czasowa
A1
A2
A3
A4
A5
n
n log n
n2
n3
2n
Maksymalny rozmiar zadania
1 sek.
1000
140
31
10
9
1 min.
6 × 104
4893
244
39
15
1 godz.
3.6 × 106
2.0 × 105
1897
153
21
Rys. 1.1. Ograniczenia rozmiaru zadania spowodowane szybkoś-
cią wzrostu złożoności
O(f(n)), jeżeli istnieje stała c taka, że g(n) (cid:2) cf(n) dla wszystkich nieujemnych
wartości n prócz pewnego skończonego (być może pustego) zbioru tych wartości.
Można by przypuszczać, że ogromny wzrost szybkości obliczeń dzięki powstaniu
maszyn cyfrowych obecnej generacji zmniejszy znaczenie efektywnych algorytmów.
Jest jednak odwrotnie. Skoro komputery stają się szybsze i możemy przetwarzać
coraz większe zadania, to o wzroście rozmiaru zadania, jaki można osiągnąć przez
wzrost szybkości komputera, rozstrzyga złożoność algorytmu.
Załóżmy, że mamy pięć algorytmów A1 − A5 o podanych złożonościach czasowych:
Algorytm
Złożoność czasowa
A1
A2
A3
A4
A5
n log n (1)
n
n2
n3
2n
Złożoność czasowa jest tu liczbą jednostek czasu potrzebnych do przetworzenia da-
nych rozmiaru n. Zakładając, że jednostka czasu jest równa jednej milisekundzie,
algorytm A1 może przetworzyć w ciągu jednej sekundy dane o rozmiarze 1000, na-
tomiast algorytm A5 dane o rozmiarze co najwyżej 9. Rysunek 1.1 podaje rozmiary
zadań, które mogą być rozwiązane przez każdy z tych pięciu algorytmów w ciągu
jednej sekundy, jednej minuty i jednej godziny.
Przypuśćmy, że następna generacja komputerów będzie dziesięć razy szybsza niż
obecna. Rysunek 1.2 pokazuje wzrost rozmiaru zadania, jakie można rozwiązać
dzięki temu wzrostowi prędkości. Zauważmy, że z algorytmem A5 dziesięciokrotny
wzrost prędkości zwiększa tylko o trzy rozmiar zadania, które można rozwiązać,
natomiast z algorytmem A3 ten rozmiar wzrasta więcej niż trzykrotnie.
Zamiast wzrostu szybkości rozważmy skutek użycia bardziej efektywnego algoryt-
mu. Popatrzmy raz jeszcze na rys. 1.1. Biorąc jedną minutę za podstawę porów-
1O ile nie zaznaczono inaczej, wszystkie logarytmy w tej książce mają podstawę 2.
1.1. Algorytmy i ich złożoność
13
Algorytm
Złożoność
czasowa
Maksymalny
rozmiar zadania
przed przyspieszeniem
Maksymalny
rozmiar zadania
po przyspieszeniu
A1
A2
A3
A4
A5
n
n log n
n2
n3
2n
s1
s2
s3
s4
s5
10s1
około 10s2 dla dużych s2
3.16s3
2.15s4
s5 + 3.3
Rys. 1.2. Skutek dziesięciokrotnego przyspieszenia
nania, można przez zastąpienie algorytmu A4 algorytmem A3 rozwiązać zadanie
sześciokrotnie większe, a przez zastąpienie algorytmu A4 algorytmem A2, zada-
nie 125 razy większe. Wyniki te są znacznie bardziej przekonujące niż dwukrotna
poprawa osiągnięta przez dziesięciokrotny wzrost szybkości. Jeżeli za podstawę po-
równania weźniemy godzinę, rożnice są jeszcze bardziej istotne. Wnioskujemy, że
asymptotyczna złożoność algorytmu jest ważną miarą jakości algorytmu, miarą,
która stanie się jeszcze ważniejsza w przyszłości, gdy szybkość obliczeń wzrośnie.
Mimo uwagi, którą poświęcamy temu, jak rośnie rząd wielkości, powinniśmy zdawać
sobie sprawę, że algorytm o gwałtownym tempie wzrostu może mieć mniejszą stałą
proporcjonalności niż algorytm o niższym. W takim przypadku szybko rosnący
algorytm może być lepszy dla małych zadań, a może nawet dla wszystkich zadań,
które mają rozmiar, jaki nas interesuje. Przypuśćmy na przykład, że złożonościami
czasowymi algorytmów A1, A2, A3, A4 i A5 są 1000n, 100n log n, 10n2, n3 i 2n.
Wtedy A5 będzie najlepszy dla zadań o rozmiarze 2 (cid:2) n (cid:2) 9, A3 dla 10 (cid:2) n (cid:2) 58,
A2 dla 59 (cid:2) n (cid:2) 1024, a A1 dla zadań o rozmiarze większym niż 1024.
Nim w rozważaniu algorytmów i ich złożoności pójdziemy dalej, musimy opisać
model maszyny liczącej, która je wykonuje i określić, co rozumiemy przez krok
w obliczeniach. Niestety nie istnieje model obliczeń, który pasowałby do wszyst-
kich sytuacji. Jedną z głównych trudności jest długość słów maszynowych. Jeżeli
na przykład założy się, że w słowie maszynowym można umieścić liczbę całkowitą
dowolnej wielkości, całe zadanie można zakodować w postaci jednej liczby całkowi-
tej w jednym słowie. Jeżeli założy się, że słowo maszynowe jest skończone, trzeba
rozważyć trudność zapamiętania dowolnie dużych liczb i inne problemy pomija-
ne, gdy zadania mają umiarkowany rozmiar. Dla problemu musimy wybrać model,
który będzie odzwierciedlać czas obliczeń w rzeczywistym komputerze.
W następnych punktach tego rozdziału omówimy kilka podstawowych modeli ma-
szyn liczących, przede wszystkim maszynę o dostępie swobodnym, maszynę o do-
stępie swobodnym z zapamiętanym programem i maszynę Turinga. Te trzy modele
są równoważne pod względem mocy obliczeniowej, lecz nie szybkości.
14
Rozdział 1. Modele obliczania
Formalne modele obliczeń wzięły się głównie z pragnienia, by wydobyć na jaw
istotną trudność obliczeniową różnych problemów. Chcemy podać dowody dolnych
ograniczeń czasu obliczeń. Aby wykazać, że nie istnieje algorytm, który wykonuje
dane zadanie w czasie krótszym niż pewien czas, potrzebujemy ścisłej i w wie-
lu punktach bardzo sztywnej definicji tego, czym jest algorytm. Przykład takiej
definicji stanowią maszyny Turinga (p. 1.6.).
W opisach i objaśnieniach algorytmów przyda się nam zapis prostszy i bardziej
jasny niż program dla maszyny o dostępie swobodnym, maszyna z zapamiętanym
programem, czy maszyna Turinga. Z tego powodu wprowadzimy język wysokiego
poziomu, zwany Pidgin ALGOL. W całej książce opisujemy algorytmy w tym ję-
zyku. Ale żeby rozumieć złożoność obliczeniową algorytmu opisanego przez Pidgin
ALGOL, musimy pokazać, jak Pidgin ALGOL zależy od modeli bardziej formal-
nych. Zrobimy to w ostatnim punkcie tego rozdziału.
1.2. Maszyny o dostępie swobodnym
Maszyna (RAM, od random access machine) jest modelem komputera o jednym
akumulatorze i instrukcjach, którym nie wolno się modyfikować.
Maszyna RAM składa się z taśmy wejściowej tylko do czytania, taśmy wyjściowej
tylko do pisania, programu oraz pamięci (rys. 1.3). Taśma wejściowa jest ciągiem
klatek, z których każda zawiera liczbę całkowitą (być może ujemną). Ilekroć z ta-
śmy wejściowej czytany jest symbol, głowica taśmy wejściowej przesuwa się o jedną
klatkę w prawo. Wyjściem jest taśma tylko do pisania, podzielona na klatki, które
początkowo są puste. Gdy wykonywana jest instrukcja pisania, w klatce znajdującej
się na taśmie wyjściowej pod głowicą taśmy wyjściowej drukowana jest liczba całko-
wita i głowica taśmy wyjściowej przesuwana jest na prawo. Gdy symbol wyjściowy
zostanie zapisany, nie można go zmienić.
Pamięć składa się z ciągu rejestrów r0, r1, . . . , ri, . . . , z których każdy może prze-
chowywać liczbę całkowitą dowolnej wielkości. Na liczbę rejestrów, które mogą być
użyte, nie nakładamy żadnego ograniczenia górnego. Abstrakcja tego rodzaju jest
poprawna, w przypadkach gdy:
1. rozmiar zadania jest na tyle mały, że mieści się ono w pamięci komputera,
oraz
2. liczby całkowite, użyte do obliczeń, są na tyle małe, że mieszczą się w poje-
dynczych słowach maszynowych.
Program dla maszyny RAM nie jest przechowywany w pamięci. A więc zakładamy,
że program ten nie modyfikuje sam siebie. Program jest jedynie ciągiem instrukcji
z (nieobowiązkowymi) etykietami. Ścisłe określenie instrukcji używanych w pro-
gramie nie jest zbyt ważne, dopóki są podobne do instrukcji spotykanych w rze-
czywistych komputerach. Zakładamy instrukcje arytmetyczne, instrukcje wejścia-
wyjścia, instrukcje adresowania pośredniego (przykładowo w indeksowaniu do ta-
1.2. Maszyny o dostępie swobodnym
15
Rys. 1.3. Maszyna o dostępie swobodnym
blic) i instrukcje rozgałęzienia (branching).2 Wszelkie obliczenia wykonywane są
w rejestrze r0, zwanym akumulatorem, który, jak wszystkie pozostałe rejestry pa-
mięci, może pomieścić dowolną liczbę całkowitą. Przykład zbioru instrukcji dla
maszyny RAM przedstawia rysunek 1.4. Każda instrukcja składa się z dwóch czę-
ści — kodu operacji i adresu.
W zasadzie możemy uzupełnić ten zbiór o dowolne inne, znane z rzeczywistych
komputerów instrukcje, takie jak operacje logiczne czy operacje na znakach, nie
zmieniając przy tym rzędu złożoności zadań. Czytelnik wedle swego uznania mo-
że uważać zbiór instrukcji za uzupełniony w ten sposób. Operandum może mieć
postać:
1. = i, co oznacza samą liczbę całkowitą i,
2. nieujemnej liczby całkowitej i, co oznacza zawartość rejestru i,
3. ∗i, co oznacza adresowanie pośrednie. A mianowicie, operandum jest zawar-
tością rejestru j, gdzie j jest liczbą całkowitą, która znajduje się w rejestrze
i. Jeżeli j 0, to maszyna ulega zatrzymaniu.
2Oprócz instrukcji warunkowych (Jump on Greater than Zero, Jump on Zero, jak czytam JGTZ
i JZERO), repertuar zawiera JUMP; por. rys. 1.5 (str. 17) — przyp. tłum.
16
Rozdział 1. Modele obliczania
Kod operacji
1. LOAD
2.
STORE
3. ADD
4.
SUB
5. MULT
6. DIV
7. READ
8. WRITE
JUMP
9.
JGTZ
10.
11.
JZERO
12. HALT
Adres
operandum
operandum
operandum
operandum
operandum
operandum
operandum
operandum
etykieta
etykieta
etykieta
Rys. 1.4. Tablica instrukcji RAM
Instrukcje te powinny być dobrze znane każdemu, kto programował asembler. Może-
my teraz zdefiniować sens programu P za pomocą dwóch wielkości: przekształcenia
c określonego na zbiorze nieujemnych liczb całkowitych o wartościach w zbiorze
liczb całkowitych i „licznika lokalizacji”, który ustala następną instrukcję do wy-
konania. Funkcja c jest mapą pamięci; c(i) jest to liczba całkowita umieszczona
w rejestrze i (zawartość rejestru i).
Początkowo c(i) = 0 dla każdego i (cid:5) 0, licznik lokalizacji jest nastawiony na pierw-
szą instrukcję P , a taśma wyjściowa jest pusta. Po wykonaniu k-tej instrukcji P
licznik lokalizacji jest automatycznie nastawiany na k + 1 (tj. na następną instruk-
cję), chyba że k-tą instrukcją jest JUMP, HALT, JGTZ lub JZERO.
Aby określić sens instrukcji, definiujemy v(a), wartość operandum a następująco:
v(= i) = i,
v(i) = c(i),
v(∗i) = c(c(i)).
Tabela na rysuku 1.5 definiuje sens każdej instrukcji z rysunku 1.4. Instrukcje nie-
zdefiniowane, takie jak STORE = i, można uważać za równoważne HALT. Podobnie
zatrzymuje maszynę dzielenie przez zero.
Podczas wykonywania każdej z pierwszych ośmiu instrukcji licznik lokalizacji jest
zwiększany o 1. Instrukcje są wykonywane w porządku, w którym występują w pro-
gramie, aż do napotkania instrukcji JUMP, HALT, JGTZ przy zawartości akumu-
latora większej od zera, lub JZERO, przy zawartości akumulatora równej zero.
Ogólnie program RAM definiuje przekształcenie taśm wejściowych w taśmy wyj-
ściowe. Skoro nie dla wszystkich taśm wejściowych program może się zatrzymać,
przekształcenie jest częściowe (czyli może być nieokreślone dla pewnych danych
1.2. Maszyny o dostępie swobodnym
17
Instrukcja
1. LOAD a
2.
STORE i
STORE ∗i
3. ADD a
4.
SUB a
5. MULT a
6. DIV a
7. READ i
READ ∗i
8. WRITE a
9.
10.
JUMP b
JGTZ b
11.
JZERO b
Sens
c(0) ← v(a)
c(i) ← c(0)
c(c(i)) ← c(0)
c(0) ← c(0) + v(a)
c(0) ← c(0) − v(a)
c(0) ← c(0) × v(a)
c(0) ← (cid:7) c(0)/v(a)(cid:8) (3)
c(i) ← bieżący symbol na wejściu.
c(c(i)) ← bieżący symbol na wejściu. Głowica taśmy wejścio-
wej przesuwa się o jedną klatkę w prawo w obu przypadkach.
v(a) jest drukowane w klatce, która na taśmie wyjściowej jest
obecnie pod głowicą. Następnie głowica taśmy wyjściowej
przesuwana jest o jedną klatkę w prawo.
Licznik lokalizacji jest nastawiany na instrukcję z etykietą b.
Licznik lokalizacji jest nastawiany na instrukcję z etykietą
b, jeżeli c(0) 0; w przeciwnym razie licznik lokalizacji jest
nastawiany na następną instrukcję.
Licznik lokalizacji jest nastawiany na instrukcję z etykietą
b, jeżeli c(0) = 0; w przeciwnym razie licznik lokalizacji jest
nastawiany na następną instrukcję.
Wykonanie ustaje.
12. HALT
3W tej książce (cid:1) x(cid:2) (ceiling x ) oznacza najmniejszą liczbę całkowitą, większą lub równą x, zaś
(cid:3) x (cid:4) (floor lub część całkowita x ) oznacza największą liczbę całkowitą, mniejszą lub równą x.
Rys. 1.5. Sens instrukcji RAM. Operandum a jest tu = i, i, lub ∗i
wejściowych). Przekształcenie to można interpretować na różne sposoby. Dwiema
istotnymi interpretacjami są funkcja, bądź język.
Przypuśćmy, że program P zawsze czyta n liczb całkowitych z taśmy wejściowej
i pisze co najwyżej jedną liczbę całkowitą na taśmie wyjściowej. Jeżeli x1, x2, . . . , xn
są liczbami całkowitymi w pierwszych n klatkach taśmy wejściowej a P zapisuje y
w pierwszej klatce taśmy wyjściowej i zatrzymuje się, to mówimy, że P oblicza funk-
cję f(x1, x2, . . . , xn) = y. Łatwo udowodnić, że RAM, jak każdy inny realistyczny
model komputera, oblicza jedynie funkcje częściowo rekurencyjne. Otóż dla każdej
częściowo rekurencyjnej funkcji f możemy zdefiniować program RAM, który obli-
cza f, i dla każdego programu RAM, równoważną funkcję częściowo rekurencyjną
(patrz Davis [ 1958 ] lub Rogers [ 1967 ] odnośnie funkcji rekurencyjnych).
Program RAM można interpretować także jako akceptor języka. Alfabetem jest
skończony zbiór symboli, a językiem zbiór napisów nad pewnym alfabetem. Sym-
bole alfabetu mogą być reprezentowane przez liczby całkowite 1, 2, . . . , k dla pewne-
go k. Maszyna RAM może akceptować język w następujący sposób. Umieszczamy
18
Rozdział 1. Modele obliczania
begin
read r1;
if r1 (cid:2) 0 then write 0
else
begin
r2 ← r1;
r3 ← r1 − 1;
while r3 0 do
begin
r2 ← r2 ∗ r1;
r3 ← r3 − 1
end;
write r2
end
end
Rys. 1.6. Program dla nn w Pidgin ALGOLu
napis wejściowy s = a1a2 ··· an na taśmie wejściowej: symbol a1 w pierwszej klat-
ce, symbol a2 w drugiej, itd. Symbol 0, którego użyjemy jako znacznika końca,
umieszczamy w klatce (n + 1), by oznaczyć koniec napisu wejściowego.
Napis wejściowy s jest akceptowany przez program P maszyny RAM, jeżeli P czyta
cały napis s i znacznik końca, pisze 1 w pierwszej klatce taśmy wyjściowej i zatrzy-
muje się. Język akceptowany przez P jest zbiorem akceptowanych napisów wejścio-
wych. Dla napisów wejściowych, które nie należą do języka akceptowanego przez
P , P może drukować na taśmie wyjściowej symbol inny niż 1 i zatrzymywać się
albo nawet nie zatrzymywać się. Łatwo udowodnić, że język jest akceptowany przez
program RAM wtedy i tylko wtedy, gdy jest rekurencyjnie przeliczalny. Język jest
akceptowany przez zatrzymującą się dla wszystkich danych maszynę RAM wtedy
i tylko wtedy, gdy jest językiem rekurencyjnym (odnośnie języków rekurencyjnych
i rekurencyjnie przeliczalnych, patrz Hopcroft i Ullman [ 1969 ]).
Rozważmy dwa przykłady programów RAM. Pierwszy definiuje funkcję, drugi ak-
ceptuje język.
Przykład 1.1. Rozważmy funkcję f(n) daną wzorem:
nn, gdy liczba całkowita n (cid:5) 1,
w przeciwnym razie.
f(n) =
0
Napisany w języku Pidgin ALGOL program, który oblicza f(n) mnożąc n samo
przez siebie (n − 1) razy, podaje rys. 1.6.4 Odpowiedni program RAM to rys. 1.7.
Zmienne r1, r2 i r3 leżą w rejestrach 1, 2 i 3. Nie robimy pewnych oczywistych
(cid:1)
usprawnień, więc odpowiedniość między rysunkami 1.6 i 1.7 będzie jasna.
4Patrz punkt 1.8. w sprawie opisu języka Pidgin ALGOL.
1.2. Maszyny o dostępie swobodnym
19
pos:
while:
continue:
Program RAM
1
READ
1
LOAD
JGTZ
pos
WRITE =0
endif
JUMP
LOAD
1
STORE 2
1
LOAD
SUB
=1
STORE 3
3
LOAD
continue
JGTZ
JUMP
endwhile
2
LOAD
MULT
1
STORE 2
LOAD
3
SUB
=1
STORE 3
JUMP
while
endwhile: WRITE 2
endif:
HALT
Odpowiednie
instrukcje Pidgin ALGOLu
read r1
if r1 (cid:2) 0 then write 0
r2 ← r1
r3 ← r1 − 1
while r3 0 do
r2 ← r2 ∗ r1
r3 ← r3 − 1
write r2
Rys. 1.7. Program RAM dla nn
begin
d ← 0;
read x;
while x (cid:10)= 0 do
begin
if x (cid:10)= 1 then d ← d − 1 else d ← d + 1;
read x
end;
if d = 0 then write 1
end
Rys. 1.8. Rozpoznawanie napisów z równą liczbą jedynek i dwójek
Przykład 1.2. Rozważmy program RAM, który akceptuje złożony ze wszystkich
napisów o tej samej liczbie jedynek i dwójek język nad alfabetem wejściowym {1, 2}.
Program ten wczytuje każdy symbol wejściowy do rejestru 1, a w rejestrze 2 utrzy-
20
Rozdział 1. Modele obliczania
Program RAM
=0
while:
LOAD
STORE 2
1
READ
LOAD
1
JZERO endwhile
1
LOAD
SUB
=1
JZERO one
LOAD
SUB
STORE 2
JUMP
LOAD
ADD
STORE 2
1
READ
JUMP
while
2
endwhile: LOAD
endif
2
=1
2
=1
one:
endif:
output:
JZERO output
HALT
WRITE =1
HALT
Odpowiednie
instrukcje Pidgin ALGOLu
d ← 0
read x
while x (cid:10)= 0 do
if x (cid:10)= 1
then d ← d − 1
else d ← d + 1
read x
if d = 0 then write 1
Rys. 1.9. Program RAM odpowiadający algorytmowi z rysunku 1.8
muje różnicę d pomiędzy liczbą jedynek i dwójek widzianych dotychczas. Po na-
potkaniu znacznika końca 0 sprawdza, czy różnica d jest równa zero i jeżeli tak
jest, drukuje 1 i zatrzymuje się. Zakładamy, że 0, 1 i 2 są wszystkimi możliwymi
symbolami wejściowymi.
Program z rysunku 1.8 zawiera istotne szczegóły tego algorytmu. Równoważny
(cid:1)
program RAM podaje rys. 1.9; x leży w rejestrze 1, a d w rejestrze 2.
1.3. Złożoność obliczeniowa programów RAM
Dwie ważne miary algorytmu to jego złożoność czasowa i pamięciowa w funkcji roz-
miaru danych. Jeżeli za złożoność, dla pewnego rozmiaru danch, wziąć złożoność
maksymalną dla wszystkich danych tego rozmiaru, to złożoność tę nazywa się zło-
żonością najgorszego przypadku. Jeżeli za złożoność wziąć „średnią” złożoność dla
wszystkich danych pewnego rozmiaru, tę złożoność nazywana się złożonością ocze-
kiwaną. Złożoność oczekiwana algorytmu jest zwykle trudniejsza do oszacowania
1.3. Złożoność obliczeniowa programów RAM
21
niż złożoność najgorszego przypadku. Konieczne jest jakieś założenie o rozkładzie
danych, a założenia zgodne z rzeczywistością na ogół nie są łatwe (tractable) ma-
tematycznie. Położymy nacisk na złożoność najgorszego przypadku, ponieważ jest
łatwiejsza do potraktowania i ma uniwersalne zastosowanie. Jednakże należy pa-
miętać, że algorytm o najlepszej złożoności najgorszego przypadku niekoniecznie
musi mieć najlepszą złożoność oczekiwaną.
Złożoność czasowa najgorszego przypadku (bądź po prostu złożoność czasowa) pro-
gramu RAM jest funkcją f(n), która dla wszystkich danych rozmiaru n jest maksi-
mum sumy opisującej „czas” zużywany przez każdą wykonywaną instrukcję. Ocze-
kiwana złożoność czasowa jest średnią dla wszystkich danych rozmiaru n tej samej
sumy. Odnośnie pamięci definiujemy podobne terminy, gdy za „«czas» zużywa-
ny przez każdą wykonywaną instrukcję” podstawiamy „«pamięć» zużywaną przez
każdy wykorzystywany rejestr”.
Aby ściśle określić złożoność czasową i pamięciową, musimy określić czas wymagany
dla wykonania każdej instrukcji RAM i pamięć zajmowaną przez każdy rejestr.
Rozważymy dwa takie kryteria kosztu dla programów RAM. Według kryterium
kosztu zuniformizowanego każda instrukcja RAM wymaga jednej jednostki czasu,
a każdy rejestr, jednej jednostki pamięci. O ile nie zaznaczymy inaczej, złożoność
programu RAM będzie mierzona według kryterium kosztu zuniformizowanego.
Druga definicja, niejednokroć bardziej realistyczna, uwzględnia skończoną długość
rzeczywistego słowa pamięciowego i nazywana jest kryterium kosztu logarytmicz-
nego. Niech l(i) będzie następującą funkcją logarytmiczną dla liczb całkowitych:
(cid:7) log | i|(cid:8) + 1,
1,
i (cid:10)= 0
i = 0
l(i) =
Tabela na rysunku 1.10 przedstawia koszt logarytmiczny t(a) dla trzech możli-
wych postaci operandum a. Rysunek 1.11 przedstawia czas wymagany przez każdą
z instrukcji.
W tym koszcie uwzględniony jest fakt, że reprezentacja liczby całkowitej n w reje-
strze wymaga (cid:7) log n(cid:8) + 1 bitów. Rejestry, jak pamiętamy, mogą zawierać dowolnie
duże liczby całkowite.
Kryterium kosztu logarytmicznego opiera się na grubym założeniu, że koszt wyko-
nania instrukcji jest proporcjonalny do długości operandów tych instrukcji. Roz-
ważmy na przykład koszt instrukcji ADD ∗i. Po pierwsze musimy ustalić koszt
Operandum a
Koszt t(a)
= i
i
∗i
l(i)
l(i) + l(c(i))
l(i) + l(c(i)) + l(c(c(i)))
Rys. 1.10. Logarytmiczny koszt operandum
22
Rozdział 1. Modele obliczania
Instrukcja
1. LOAD a
2.
STORE i
STORE ∗i
3. ADD a
4.
SUB a
5. MULT a
6. DIV a
7. READ i
READ ∗i
8. WRITE a
9.
10.
11.
12. HALT
JUMP b
JGTZ b
JZERO b
Koszt
t(a)
l(c(0)) + l(i)
l(c(0)) + l(i) + l(c(i))
l(c(0)) + t(a)
l(c(0)) + t(a)
l(c(0)) + t(a)
l(c(0)) + t(a)
l(input) + l(i)
l(input) + l(i) + l(c(i))
t(a)
1
l(c(0))
l(c(0))
1
Rys. 1.11. Logarytmiczny koszt instrukcji RAM,
gdzie t(a) jest kosztem operandum a, zaś b ozna-
cza etykietę
dekodowania operandum reprezentowanego przez adres. Aby rozpoznać liczbę cał-
kowitą i, trzeba czasu l(i). Następnie, aby odczytać c(i), zawartość rejestru i, oraz
odszukać rejestr c(i) potrzeba czasu l(c(i)). Wreszcie, czytanie zawartości rejestru
c(i) kosztuje l(c(c(i))). Skoro instrukcja ADD ∗i dodaje liczbę całkowitą c(c(i))
do c(0), liczby całkowitej w akumulatorze, widzimy, że realistycznym kosztem, jaki
należy przypisać instrukcji ADD ∗i, jest l(c(0)) + l(i) + l(c(i)) + l(c(c(i))).
Logarytmiczną złożoność pamięciową programu RAM definiujemy jako sumę l(xi)
po wszystkich rejestrach z akumulatorem włącznie, gdzie xi jest liczbą całkowitą
o największej wielkości, umieszczoną w rejestrze i w dowolnej chwili obliczeń.
Jest rzeczą jasną, że dany program może mieć całkowicie różne złożoności czaso-
we zależnie od tego, czy użyje się kosztu zuniformizowanego, czy logarytmicznego.
Jeżeli założenie, że każdą liczbę napotkaną w czasie obliczeń można umieścić w jed-
nym słowie maszynowym, jest realistyczne, to właściwa jest funkcja kosztu zuni-
formizowanego. W przeciwnym razie dla realistycznej analizy złożoności bardziej
właściwy może być koszt logarytmiczny.
Obliczmy złożoność czasową i pamięciową programu RAM, który wylicza wartości
nn w przykładzie 1.1. Złożoność czasowa tego programu jest zdominowana przez
pętlę z instrukcją MULT. Za i-tym razem, gdy wykonywana jest istrukcja MULT,
akumulator zawiera ni, a rejestr 2 zawiera n. Wszystkich wykonywanych instrukcji
MULT jest n − 1. Zgodnie z kryterium kosztu zuniformizowanego każda z instruk-
cji MULT kosztuje jedną jednostkę czasu, stąd na wykonanie wszystkich instrukcji
MULT zużywany jest czas O(n). Zgodnie z kryterium kosztu logarytmicznego kosz-
1.4. Model z zapamiętanym programem
23
tem wykonania i-tej instrukcji MULT jest l(ni) + l(n) (cid:14) (i + 1) log n i wobec tego
kosztem wszystkich instrukcji MULT jest:
n−1(cid:8)
(i + 1) log n,
i=1
który jest O(n2 log n).
Złożoność pamięciową dyktują liczby całkowite, umieszczone w rejestrach od 0
do 3. Zgodnie z kosztem zuniformizowanym złożoność pamięciowa jest po prostu
O(1). Zgodnie z kosztem logarytmicznym złożoność pamięciowa jest O(n log n),
gdyż największą liczbą całkowitą umieszczoną w dowolnym z rejestrów jest nn,
a l(nn) (cid:14) n log n. Wobec tego dla programu z przykładu 1.1 mamy następujące
złożoności:
Koszt
zuniformizowany
Złożoność czasowa
Złożoność pamięciowa
O(n)
O(1)
Koszt
logarytmiczny
O(n2 log n)
O(n log n)
Koszt zuniformizowany jest dla tego programu realistyczny tylko wtedy, gdy poje-
dyncze słowo maszynowe może pomieścić liczbę całkowitą tak dużą, jak nn. Jeżeli
liczba nn jest większa od tego, co można pomieścić w jednym słowie maszynowym,
to nawet logarytmiczna złożoność czasowa jest nieco nierealistyczna, gdyż zakła-
da, że dwie liczby całkowite, i oraz j, mogą być pomnożone przez siebie w czasie
O(l(i)) + l(j)), a nie wiadomo dotychczas, czy tak jest.
Dla programu RAM z przykładu 1.2, przy założeniu, że n jest długością napisu
wejściowego, złożoności czasowe i pamięciowe są następujące:
Koszt
Koszt
zuniformizowany
logarytmiczny
Złożoność czasowa
Złożoność pamięciowa
O(n)
O(1)
O(n log n)
O(log n)
Jeżeli n jest większe od tego, co można pomieścić w jednym słowie maszynowym,
to koszt logarytmiczny dla tego programu jest dość realistyczny.
1.4. Model z zapamiętanym programem
Ponieważ program RAM nie jest przechowywany w pamięci maszyny, nie może
modyfikować sam siebie. Teraz rozważymy inny model komputera, tzw. maszynę
o dostępie swobodnym z zapamiętanym programem (RASP, od random access stored
program), która jest podobna do maszyny RAM z tym, że program jest w pamięci
i może modyfikować sam siebie.
24
Rozdział 1. Modele obliczania
Instrukcja
Kodowanie
Instrukcja
Kodowanie
LOAD
LOAD
STORE
ADD
ADD
SUB
SUB
MULT
MULT
i
= i
i
i
= i
i
= i
i
= i
1
2
3
4
5
6
7
8
9
DIV
i
= i
DIV
READ
i
WRITE
i
WRITE = i
JUMP
i
JGTZ
i
JZERO
i
HALT
10
11
12
13
14
15
16
17
18
Rys. 1.12. Kody dla instrukcji RASP
Zbiór instrukcji RASP jest identyczny ze zbiorem instrukcji RAM prócz tego, że
adresowanie pośrednie nie jest dozwolone, gdyż nie jest potrzebne. Jak zobaczymy,
RASP może symulować adresowanie pośrednie przez modyfikacje instrukcji w czasie
wykonania programu.
Ogólna struktura maszyny RASP jest także podobna do struktury RAM, ale za-
kłada się, że program RASP leży w rejestrach pamięci. Każda instrukcja RASP
zajmuje dwa kolejne rejestry. Pierwszy z nich zawiera kod operacji; drugi — ad-
res. Jeżeli adres jest w postaci = i, to pierwszy rejestr będzie kodować także fakt,
że operandum jest literałem, a drugi rejestr będzie zawierać i. Do kodowania in-
strukcji służą liczby całkowite. Rysunek 1.12 pokazuje jeden z możliwych sposobów
kodowania. Na przykład instrukcja LOAD=32 zostanie zapamiętana za pomocą 2
w jednym rejestrze i 32 w następnym.
Podobnie jak w przypadku RAM, stan RASP może być reprezentowany przez:
1. mapę pamięci c, gdzie c(i) dla i (cid:5) 0 jest zawartością rejestru i, oraz
2. licznik lokalizacji, wskazujący na pierwszy z dwóch kolejnych rejestrów pa-
mięci, z których ma być pobrana bieżąca instrukcja.
Licznik lokalizacji jest nastawiony początkowo na pewien zadany rejestr. Począt-
kowa zawartość rejestrów pamięci to z reguły nie wszędzie 0, gdyż na początku do
pamięci pobierany jest program. Na początku jednak wszystkie prócz skończonej
liczby rejestrów pamięci i akumulator muszą zawierać 0 Po wykonaniu każdej in-
strukcji licznik lokalizacji jest zwiększany o 2, z wyjątkiem przypadków JUMP i,
JGTZ i (gdy akumulator jest dodatni), lub JZERO i (gdy akumulator zawiera 0),
w których licznik lokalizacji jest nastawiany na i. Skutek każdej z instrukcji jest
taki sam jak odpowiedniej instrukcji RAM.
Złożoność czasową programu RASP można zdefiniować bardzo podobnie, jak złożo-
ność czasową programu RAM. Możemy użyć bądź kryterium kosztu zuniformizowa-
nego, bądź logarytmicznego. Kosztem w tym ostatnim przypadku musimy jednak
obciążyć nie tylko operandum, lecz także dostęp do samej instrukcji. Kosztem tego
1.4. Model z zapamiętanym programem
25
dostępu jest l(LC), gdzie LC oznacza zawartość licznika lokalizacji. Na przykład
kosztem wykonania instrukcji ADD = i, umieszczonej w rejestrach j oraz j + 1, jest
l(j) + l(c(0)) + l(i)5. Kosztem instrukcji ADD i, umieszczonej w rejestrach j oraz
j + 1, jest l(j) + l(c(0)) + l(i) + l(c(i)).
Ciekawe jest pytanie, co różni złożoność programu RAM i odpowiedniego programu
RASP. Odpowiedź nie jest zaskakująca. Dowolne przekształcenie wejścia na wyjście,
które może być wykonane w czasie T (n) przez jeden model, może być wykonane
przez drugi w czasie kT (n) dla pewnej stałej k, bez względu na to, czy weźmie się
koszt zuniformizowany, czy logarytmiczny. Podobnie pamięć wykorzystywana przez
te modele różni się tylko o stały czynnik przy obu miarach kosztu.
Dwa twierdzenia wyrażają te zależności w sposób formalny. Obydwu dowodzi się,
pokazując algorytmy, na mocy których RAM może symulować RASP i odwrotnie.
Twierdzenie 1.1. Jeżeli koszt instrukcji jest zuniformizowany lub logaryt-
miczny, to istnieje taka stała k, że dla każdego programu RAM o złożono-
ści czasowej T (n) istnieje równoważny program RASP o złożoności czasowej
kT (n).
Dowód. Pokazujemy, jak symulować program RAM P przez program RASP. Re-
jestr 1 RASP będzie służyć do tymczasowego przechowywania zawartości akumu-
latora RAM. Z programu P skonstruujemy program RASP PS, który będzie zaj-
mować następne r− 1 rejestrów RASP. Stała r jest zdeterminowana przez program
RAM P . Zawartość rejestru i RAM, i (cid:5) 1, będzie przechowywana w rejestrze r + i
RASP, więc w programie RASP wszystkie odniesienia do pamięci mają adresy o r
większe od odpowiednich odniesień w programie RAM.
Każda instrukcja RAM w P , niewymagająca adresowania pośredniego, jest kodowa-
na bezpośrednio w postaci identycznej instrukcji RASP (z odpowiednio zwiększo-
nymi adresami odniesień do pamięci). Każda instrukcja RAM w P , wymagajająca
adresowania pośredniego, jest przekształcana w sekwencję sześciu instrukcji RASP,
która symuluje adresowanie pośrednie przez modyfikację instrukcji.
Aby objaśnić symulację adresowania pośredniego powinien wystarczyć przykład.
By symulować instrukcję RAM SUB ∗i, gdzie i jest liczbą całkowitą dodatnią,
tworzymy sekwencję instrukcji RASP, która:
1. umieszcza tymczasowo zawartość akumulatora w rejestrze 1,
2. pobiera zawartość rejestru r+i do akumulatora (rejestr r+i RASP odpowiada
rejestrowi i RAM),
3. dodaje r do akumulatora,
4. umieszcza liczbę obliczoną w kroku 3. w polu adresu instrukcji SUB,
5. przywraca zawartość akumulatora z tymczasowego rejestru 1, i wreszcie
6. używa instrukcji SUB stworzonej w kroku 4., by wykonać odejmowanie.
5Można by doliczyć koszt czytania rejestru j + 1, ale ten koszt nie może różnić się bardzo od
l(j). W tym rozdziale mamy na uwadze nie czynniki stałe, lecz raczej szybkość wzrostu funkcji.
Zatem l(j) + l(j + 1) jest „w przybliżeniu” l(j) z dokładnością co najwyżej do czynnika 3.
26
Rozdział 1. Modele obliczania
Rejestr
100
101
102
103
104
105
106
107
108
109
110
111
Zawartość
3
1
1
r + i
5
r
3
111
1
1
6
−
Sens
STORE
1
LOAD r + i
ADD
= r
STORE 111
LOAD
SUB
1
b
gdzie b jest zawartością
rejestru i RAM
Rys. 1.13. Symulacja SUB ∗i przez RASP
Rejestr RASP
Instrukcja
j
j + 2
j + 4
j + 6
j + 8
j + 10
1
STORE
r + 1
LOAD
ADD
= r
STORE j + 11
LOAD
1
−
SUB
Koszt
l(j) + l(1) + l(c(0))
l(j + 2) + l(r + i) + l(c(i))
l(j + 4) + l(c(i)) + l(r)
l(j + 6) + l(j + 11) + l(c(i) + r)
l(j + 8) + l(1) + l(c(0))
l(j + 10) + l(c(i) + r) + l(c(0))
+l(c(c(i)))
Rys. 1.14. Koszt instrukcji RASP
Na przykład, stosując kodowanie instrukcji RASP podane na rysunku 1.12, i za-
kładając, że sekwencja instrukcji RASP zaczyna się w rejestrze 100, możemy sy-
mulować SUB ∗i za pomocą sekwencji pokazanej na rysunku 1.13. Przesunięcie r
można określić, gdy znana jest liczba instrukcji w programie RASP PS.
Stwierdzamy, że każda instrukcja RAM wymaga co najwyżej sześciu instrukcji
RASP, zatem według kryterium kosztu zuniformizowanego złożonością czasową
programu RASP jest co najwyżej 6T (n). (Zauważmy, że miara ta jest niezależ-
na od sposobu, w jaki określa się „wielkość” danych.)
Według kryterium kosztu logarytmicznego stwierdzamy, że każda instrukcja RAM
I należąca do P jest symulowana przez sekwencję S jednej lub sześciu instrukcji
RASP w PS. Możemy pokazać, iż istnieje taka stała k zależna od P , że koszt
instrukcji należących do S jest nie większy niż k razy koszt instrukcji I.
Na przykład instrukcja RAM SUB ∗i ma koszt:
M = l(c(0)) + l(i) + l(c(i)) + l(c(c(i))).
1.4. Model z zapamiętanym programem
27
Sekwencja S, która symuluje tę instrukcję RAM, jest pokazana na rysunku 1.14.
c(0), c(i), oraz c(c(i)) na rysunku 1.14 odnoszą się do zawartości rejestrów RAM.
Ponieważ PS zajmuje rejestry RASP od 2 do r, mamy j (cid:2) r−11. Ponadto l(x+y) (cid:2)
l(x) + l(y), więc koszt S jest na pewno mniejszy niż:
2l(1) + 4M + 11l(r) (6 + 11l(r))M.
Wobec tego wnioskujemy, że istnieje stała k = 6 + 11l(r) taka, że jeżeli P ma
(cid:1)
złożoność czasową T (n), to PS ma złożoność czasową co najwyżej kT (n).
Twierdzenie 1.2. Jeżeli koszt instrukcji jest zuniformizowany lub logaryt-
miczny, to istnieje taka stała k, że dla każdego programu RASP o złożoności
czasowej T (n) istnieje równoważny program RAM o złożoności czasowej co
najwyżej kT (n).
Dowód. Program RAM, który skonstruujemy, by symulować RASP, będzie używać
adresowania pośredniego, żeby dekodować i symulować instrukcje RASP umiesz-
czone w pamięci RAM. Pewne rejestry RAM będą mieć specjalne przeznaczenie:
rejestr 1 — używany w adresowaniu pośrednim,
rejestr 2 — licznik lokalizacji RASP,
rejestr 3 — pamięć do przechowywania akumulatora RASP.
Rejestr i RASP będzie umieszczony w rejestrze i + 3 RAM dla i (cid:5) 1.
RAM rozpoczyna pracę z programem RASP o skończonej długości, który jest
umieszczony w pamięci, poczynając od rejestru 4. Rejestr 2 — licznik lokaliza-
cji, zawiera 4; rejestry 1 i 3 zawierają 0. Program RAM tworzy pętla symulacji,
która zaczyna się od przeczytania (za pomocą instrukcji RAM LOAD ∗2) instruk-
cji RASP, dekodowania tej instrukcji i rozgałęzienia do jednego z 18 zestawów
instrukcji, z których każdy służy do obsługi jednego typu instrukcji RASP. W razie
niepoprawnego kodu operacji, RAM, jak i RASP zatrzymają się.
Operacje dekodowania i rozgałęzienia są jasne; jako model może służyć przykład
1.2 (chociaż tam dekodowany symbol był czytany z wejścia, a tu jest czytany z pa-
mięci). Podamy przykład instrukcji RAM, które symulują instrukcję 6 RASP, tj.
SUB i. Program ten, pokazany na rysunku 1.15, ulega wywołaniu, gdy c(c(2)) = 6,
a więc gdy licznik lokalizacji wskazuje na rejestr, który zawiera 6, czyli kod SUB.
Pomijamy dalsze szczegóły budowy programu RAM. Jako ćwiczenie pozostawiamy
dowód faktu, że według kryterium kosztu zuniformizowanego lub logarytmicznego,
złożoność czasowa programu RAM jest co najwyżej pewną stałą w iloczynie ze
(cid:1)
złożonością czasową RASP.
Z twierdzeń 1.1 i 1.2 wynika, że gdy chodzi o złożoność czasową (a także pa-
mięciową, co pozostawiamy jako ćwiczenie) modele RAM i RASP są równoważne
z dokładnością do czynnika stałego, tj. rząd ich złożoności jest ten sam dla tego
samego algorytmu. Spośród tych dwóch modeli na ogół wykorzystujemy w książce
model RAM, gdyż jest on nieco prostszy.
28
LOAD
ADD
STORE
LOAD
ADD
STORE
LOAD
SUB
STORE
LOAD
ADD
STORE
JUMP
2
=1
2
∗2
=3
1
3
∗1
3
2
=1
2
a
Rozdział 1. Modele obliczania
Zwiększ licznik lokalizacji o 1, tak aby wskazywał na rejestr,
który zawiera operandum i instrukcji SUB i.
Pobierz i do akumulatora, dodaj 3, wynik umieść w rejestrze
1.
Pobierz zawartość akumulatora RASP z rejestru 3. Odejmij
zawartość rejestru i+3, wynik umieść z powrotem w rejestrze
3.
Zwiększ licznik lokalizacji znów o 1, tak by wskazywał teraz
na następną instrukcję RASP.
Powróć na początek pętli symulacji (nazwany tutaj „a”).
Rys. 1.15. Symulacja SUB i przez RAM
1.5. Abstrakcje RAM
W wielu sytuacjach nie są potrzebne tak skomplikowane modele obliczeń jak RAM
i RASP. Wobec tego liczne modele definiuje się przez abstrakcję pewnych własności
RAM, zaniedbując inne. Uzasadnieniem dla takich modeli jest fakt, że zaniedby-
wane instrukcje stanowią co najwyżej stały ułamek kosztu każdego efektywnego
algorytu, rozwiązującego problemy, do których model jest stosowany.
i. Program liniowy
Pierwszym rozważanym przez nas modelem jest liniowy program (stright-line pro-
gram). W wielu problemach wystarczy skupić uwagę na klasie programów RAM,
gdzie instrukcje rozgałęzienia są używame tylko do powtarzania jakiejś sekwencji
instrukcji pewną ilość razy, proporcjonalną do n — rozmiaru danych. W tym przy-
padku dla każdego rozmiaru n można program „rozwinąć”, powielając odpowiednią
ilość razy instrukcje, które mają być powtarzane. Daje to sekwencję liniowych (wol-
nych od pętli) i zapewne coraz dłuższych programów, po jednym dla każdego n.
Przykład 1.3. Rozważmy mnożenie dwóch macierzy wymiaru n× n o elementach
ze zbioru liczb całkowitych. Zwykle można oczekiwać nie bez racji, że liczba powtó-
rzeń pętli w programie RAM będzie niezależna od wielkosci elementów macierzy.
Warto więc założyć dla uproszczenia, że dozwolone są tylko pętle z instrukcjami
testu, w których wchodzi w grę wyłącznie n, rozmiar zadania. Oczywisty algorytm
mnożenia macierzy zawiera pętle, które muszą być na przykład wykonane dokład-
nie n razy, gdyż wymaga instrukcji rozgałęzienia, które porównują indeks z n. (cid:1)
Dzięki rozwinięciu programu do postaci liniowej obywamy się bez instrukcji roz-
gałęzienia. Uzasadnienie czerpiemy stąd, że w wielu zadaniach nie więcej niż stały
1.5. Abstrakcje RAM
29
ułamek kosztu programu RAM jest przeznaczony na instrukcje rozgałęzienia, ste-
rujące pętlami. Podobnie często możemy założyć, że instrukcje wejścia tworzą tylko
stały ułamek kosztu programu i wykluczyć je, zakładając, że skończony zbiór wejść,
wymagany przy pewnym n, znajduje się w pamięci, gdy program rozpoczyna pracę.
Skutki adresowania pośredniego można oszacować przy ustalonym n, o ile rejestry,
służące do adresowania pośredniego, zawierają wartości zależne tylko od n, a nie
od wartości zmiennych wejściowych. Wobec tego zakładamy, że nasze programy
liniowe są pozbawione adresowania pośredniego.
Ponadto skoro każdy z programów liniowych może zawierać odniesienia tylko do
skończonej liczby rejestrów pamięci, wygodnie jest nazwać rejestry wykorzystywane
przez program. Rejestry podlegają wobec tego raczej odnosieniom przez adresy
symboliczne (symbole lub napisy złożone z liter), niż przez liczby całkowite.
Z repertuaru RAM po usunięciu wymagań co do READ, JUMP, JGTZ i JZE-
RO pozostają nam LOAD, STORE, WRITE, HALT i operacje arytmetyczne. Nie
potrzebujemy HALT, gdyż koniec programu musi oznaczać zatrzymanie. Możemy
obyć się bez WRITE, wyróżniając pewne adresy symboliczne jako zmienne wyjścio-
we; informacją wyjścia programu są wartości tych zmiennych w chwili zakończenia.
Możemy wreszcie włączyć LOAD i STORE do operacji arytmetycznych, zastępując
sekwencje, takie jak:
przez c ← a+b. Cały repertuar instrukcji programu liniowego jest więc następujący:
LOAD a
ADD b
STORE c
x ← y + z
x ← y − z
z ← y ∗ z
z ← y/z
x ← i
gdzie x, y i z są adresami symbolicznymi (czyli zmiennymi), a i jest stałą. Łatwo
zauważyć, że dowolna sekwencja LOAD, STORE i operacji arytmetycznych na
akumulatorze może być zastąpiona pewną sekwencją pięciu powyższych instrukcji.
Programowi liniowemu są przyporządkowane dwa wyróżnione zbiory zmiennych:
jego wejścia i wyjścia. Funkcja obliczana przez program liniowy jest zbiorem warto-
ści zmiennych wyjściowych (w zadanym porządku), wyrażanych względem wartości
zmiennych wejściowych.
Przykład 1.4. Rozważmy obliczanie wielomianu:
p(x) = anxn + an−1xn−1 + ··· + a1x + a0
Zmiennymi wejściowymi są współczynniki a0, a1, . . . , an i symbol x. Zmienną wyj-
ściową jest p. Według reguły Hornera p(x) obliczamy jako:
30
Rozdział 1. Modele obliczania
n = 1
t ← a1 ∗ x
p ← t + a0
n = 2
t ← a2 ∗ x
t ← t + a1
t ← t ∗ x
p ← t + a0
n = 3
t ← a3 ∗ x
t ← t + a2
t ← t ∗ x
t ← t + a1
t ← t ∗ x
p ← t + a0
Rys. 1.16. Programy liniowe, odpowiadające regule Hornera
1. a1x + a0
2. (a2x + a1)x + a0
3. ((a3x + a2)x + a1)x + a0
dla
dla
dla
n = 1,
n = 2,
n = 3.
Wyrażeniom tym odpowiadają programy liniowe z rysunku. 1.16. Reguła Hornera
dla dowolnego n powinna być jasna. Dla każdego n mamy program liniowy o 2n
krokach, który oblicza wielomian n-tego stopnia. W rozdziale 12. pokażemy, że
aby obliczyć wartość wielomianu n-tego stopnia, gdy współczynniki są dane jako
wejście, konieczne jest n mnożeń i n dodawań. Reguła Hornera jest optymalna
(cid:1)
według modelu programu liniowego.
Według modelu programu liniowego obliczeń złożonością czasową ciągu programów
jest liczba kroków n-tego programu jako funkcja n. Reguła Hornera na przykład
daje ciąg o złożoności czasowej 2n. Zauważmy, że mierzenie złożoności czasowej to
tyle, co mierzenie liczby operacji arytmetycznych. Złożonością pamięciową ciągu
programów jest liczba wymienionych zmiennych także jako funkcja n. Programy
z przykładu 1.4 mają złożoność pamięciową n + 4.
Definicja. Gdy chodzi o model programu liniowego, mówimy, że problem
ma złożoność czasową lub pamięciową OA(f(n)), jeżeli istnieje ciąg progra-
mów, którego złożoność czasowa lub pamięciowa sięga co najwyżej cf(n) dla
pewnej stałej c. (Zapis OA(f(n)) oznacza „rząd f(n) kroków, gdy modelem
jest programu liniowy”. Wskaźnik A oznacza „arytmetyczny”, co jest główną
cechą kodu liniowego.) Obliczanie wartości wielomianu ma złożoność czasową
OA(n), jak i pamięciową OA(n).
ii. Obliczenia na bitach
Model programu liniowego opiera się oczywiście na funkcji kosztu zuniformizowane-
go. Jak wspomnieliśmy, koszt ten jest właściwy, gdy wszystkie obliczane wielkości
są „rozsądne”. Istnieje prosta modyfikacja modelu programu liniowego, która jest
odbiciem funkcji kosztu logarytmicznego. Model ten, nazywamy przez nas oblicza-
niami na bitach, jest zasadniczo taki sam jak kod liniowy za wyjątkiem tego, że:
1. zakładamy, że wszystkie zmienne mają wartość 0 lub 1, tj. są bitami.
1.5. Abstrakcje RAM
31
Rys. 1.17. (a)Program dodawania na bitach, (b) równoważny układ logiczny
2. używamy operacji logicznych, a nie arytmetycznych.6 Piszemy ∧ dla i, ∨ dla
lub, ⊕ dla rozłącznego lub i ¬ dla nie.
Zgodnie z modelem bitowym operacje arytmetyczne na liczbach całkowitych i i j
wymagają przynajmniej l(i)+l(j) kroków, co jest odbiciem logarytmicznego kosztu
operandów. Faktycznie, mnożenie i dzielenie według najlepszych znanych algoryt-
mów wymaga wiecej niż l(i) + l(j) kroków, by pomnożyć lub podzielić i przez j.
Na oznaczenie rzędu wielkości w modelu obliczeń na bitach stosujemy OB. Model
bitowy przydaje się, gdy chcemy mówić o podstawowych operacjach, jak opera-
cje arytmetyczne, które są pierwotne w innych modelach. Na przykład w modelu
programu liniowego mnożenie dwóch n-bitowych liczb całkowitych jest do wyko-
nania w OA(1) kroku, natomiast w modelu bitowym najlepszy znany wynik to
OB(n log n log log n) kroków.
6Stąd zbiór instrukcji RAM musi zawierać te operacje.
32
Rozdział 1. Modele obliczania
Innym zastosowaniem modelu bitowego są układy logiczne. Programy liniowe z bi-
towymi wejściami i operacjami odpowiadają wzajemnie jednoznacznie logiczno-
kombinatorycznym układom do obliczania układów funkcji boolowskich. Liczba
kroków programu jest liczbą elemetów logicznych układu.
Przykład 1.5. Rysunek 1.17(a) przedstawia program dodawania dwóch dwubito-
wych liczb [ a1a0 ] i [ b1b0 ]. Zmiennymi wyjściowymi są c2, c1 i c0, takie że [ a1a0 ] +
[ b1b0 ] = [ c2c1c0 ]. Program liniowy z rysunku 1.17(a) oblicza:
c0 = a0 ⊕ b0,
c1 = ((a0 ∧ b0) ⊕ a1) ⊕ b1,
c2 = ((a0 ∧ b0) ∧ (a1 ∨ b1)) ∨ (a1 ∧ b1).
Rys. 1.17(b) przedstawia odpowiedni układ logiczny. Dowód, że dodawanie dwu
n-bitowych liczb można wykonać w OB(n) krokach zostawiamy jako ćwiczenie. (cid:1)
iii. Operacje na wektorach bitowych
Zamiast ograniczać wartość zmienej do 0 lub 1, można pójść w przeciwnym kie-
runku i pozwolić, by zmienne przybierały jako wartość dowolny wektor bitów. Fak-
tycznie, wektory bitów o danej długości odpowiadają w oczywisty sposób liczbom
całkowitym, więc nie wykraczamy istotnie poza model RAM, tj. w razie potrzeby
wciąż zakładamy nieograniczoną wielkość rejestrów.
Jednakże, jak zobaczymy w tych kilku algorytmach, w których stosowany jest mo-
del z wektorami bitów, długość używanych wektorów znacznie przewyższa liczbę
bitów potrzebnych do przedstawienia wielkości zadania. Wielkość liczb całkowitych
używanych w algorytmie będzie na ogół tego samego rzędu co wielkość zadania. Na
przykład, rozwiązując problemy dróg w grafie o 100 wierzchołkach, można by za-
stosować wektory bitów o długości 100 do wskazywania, czy istnieje droga z danego
wierzchołka v do każdego z wierzchołków grafu; tzn. w wektorze dla wierzchołka v
na i-tej pozycji jest 1 wtedy i tylko wtedy, gdy istnieje droga z v do vi. W przy-
padku tego samego problemu można używać także liczb całkowitych (przykładowo
do liczenia i indeksowania) i będą one mieć wielkość zapewne rzędu 100. Stąd dla
liczb całkowitych będzie potrzebne 7 bitów, podczas gdy dla wektorów 100.
Różnica nie musi być jednak aż tak znaczna, ponieważ większość komputerów wy-
konuje operacje logiczne na wektorach bitów o długości pełnego słowa w cyklu
jednej instrukcji. Zatem wektory bitów o długości 100 mogą podlegać manipula-
cjom w trzech lub czterech krokach, w porównaniu z jednym krokiem dla liczb
całkowitych. Niemniej wyniki na temat czasowej i pamięciowej złożoności algoryt-
mów dla modelu z wektorami bitów należy brać cum grano salis, gdyż wielkość
zadania, przy której model ten staje się nierealistyczny jest znacznie mniejsza, niż
dla modelu RAM i modelu kodu liniowego. Na oznaczenie rzędu wielkości w modelu
z wektorami bitowymi stosujemy OBV.
1.5. Abstrakcje RAM
33
iv. Drzewa decyzji
Rozważyliśmy trzy abstrakcje RAM, które zaniedbywały instrukcje rozgałęzienia
i obejmowały tylko kroki związane z obliczaniem. Istnieją pewne problemy, w któ-
rych można realistycznie uznać liczbę instrukcji rozgałęzienia za podstawową miarę
złożoności. W sortowaniu na przykład, wyjścia są identyczne z wejściami, wyjąwszy
uporządkowanie. Rozsądnie jest więc rozważyć model, w którym wszystkie kroki są
rozgałęzieniami od dwóch ramionach, i polegają na porównaniu dwóch wielkości.
Częstą reprezentacją programu z rozgałęzieniami jest drzewo binarne7, zwane drze-
wem decyzji. Każdy wewnętrzny wierzchołek reprezentuje decyzję. Test reprezen-
towany przez korzeń jest wykonywany jako pierwszy, po czym zależnie od wyniku
„sterowanie” przechodzi do jednego z synów. Ogólnie, sterowanie tak długo prze-
chodzi od wierzchołka do jednego z synów, przy czym wybór zależy zawsze od testu
na wierzchołku, aż dotrze do liścia. Wynik jest dostępny na tym liściu.
Przykład 1.6. Rys. 1.18 pokazuje drzewo decyzji dla programu, który sortuje trzy
liczby a, b i c. Testy wskazują owale wokół porównań na wierzchołkach; sterowanie
przechodzi na lewo, jeżeli test daje odpowiedź „tak”, i na prawo, jeżeli „nie”. (cid:1)
Złożonością czasową drzewa decyzji jest jego wysokość jako funkcja rozmiaru zada-
nia. Zwykle chcemy oszacować maksimum liczby porównań, które trzeba wykonać,
by dojść z korzenia do liścia. Zakładając model drzewa decyzji (porównań), ozna-
czamy rząd wielkości przez OC. Liczba wierzchołków może być znacznie większa
od wysokości drzewa. Na przykład drzewo decyzji, które sortuje n liczb, musi mieć
przynajmniej n! liści, lecz wystarczy, że ma wysokość około n log n.
Rys. 1.18. Drzewo decyzji
7W sprawie definicji dotyczących drzew patrz punkt 2.4.
34
Rozdział 1. Modele obliczania
1.6. Pierwotny model obliczania: maszyna Turinga
By udowodnić, że dana funkcja wymaga pewnego minimum czasu, potrzebujemy
modelu, który jest równie ogólny, lecz bardziej pierwotny od rozpatrzonych. Reper-
tuar instrukcji ma być jak najbardziej ograniczony, jednak model nie tylko musi
obliczać to wszystko, co oblicza RAM, lecz czynić to niemal równie szybko. Według
definicji, której użyjemy, „niemal” oznacza „równoważność wielomianową”.
Definicja. Mówimy, że funkcje f1(n) i f2(n) są równoważne wielomianowo,
jeżeli istnieją wielomiany p1(x) i p2(x) takie, że dla wszystkich wartości n,
f1(n) (cid:2) p1(f2(n)) i f2(n) (cid:2) p2(f1(n)).
Przykład 1.7. Funkcje f1(n) = 2n2 i f2(n) = n5 są równoważne wielomianowo;
niech na przykład p1(x) = 2x, skoro 2n2 (cid:2) 2n5, i p2(x) = x3, skoro n5 (cid:2) (2n2)3.
Natomiast n2 i 2n nie są równoważne wielomianowo, gdyż nie istnieje wielomian
p(x), taki że dla każdego n, p(n2) (cid:5) 2n.
(cid:1)
Obecnie jedynym zakresem, w którym do dowodu dolnych ograniczeń złożono-
ści obliczeniowej możemy użyć ogólnych modeli, takich jak maszyna Turinga, jest
„wyższy zakres”. Na przykład w rozdziale 11. pokażemy, że pewne problemy wy-
magają wykładniczego czasu i pamięci. (f(n) jest funkcją wykładniczą, jeżeli ist-
nieją stałe c1 0, k1 1, c2 0 i k2 1 takie, że c1kn
2 dla
1
wszystkich, prócz skończonej liczby wartości n.) W wykładniczym zakresie funkcje
wielomianowo równoważne są zasadniczo tożsame, gdyż dowolna funkcja, która jest
równoważna wielomianowo z funkcją wykładniczą, jest funkcją wykładniczą.
(cid:2) f(n) (cid:2) c2kn
Jest więc powód, by używać pierwotnego modelu, w którym złożoność czasowa
problemów jest równoważna wielomianowo ich złożoności w modelu RAM. Mo-
del, którego używamy — maszyna Turinga z wieloma taśmami — może wymagać
czasu8 ([ f(n) ]4), lecz nie więcej, aby wykonać to, co RAM z funkcją kosztu loga-
rytmicznego wykonuje w czasie f(n). Złożoność czasowa z użyciem modelu RAM
i maszyny Turinga będzie równoważna wielomianowo.
Definicja. Maszynę Turinga z wieloma taśmami (TM) przedstawia rys. 1.19.
Składa się ona z pewnej liczby k nieskończończonych w prawo taśm. Każda
taśma jest podzielona na komórki, a każda z nich zawiera jeden symbol spo-
śród skończonej liczby symboli taśm. Jedna komórka na każdej taśmie jest
czytana przez
Pobierz darmowy fragment (pdf)
