Projektowanie i analiza algorytmow.pdf

IDZ DO

PRZYK£ADOW Y ROZDZIA£

Projektowanie i analiza

SPIS TRECI

algorytmów

KATALOG KSI¥¯EK

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

KATALOG ONLINE

ZAMÓW DRUKOWANY KATALOG

TWÓJ KOSZYK

DODAJ DO KOSZYKA

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êpnoci

wyk³adu, ni¿ na szczegó³ach realizacji i sztuczkach programistycznych. Autorzy

przedstawiaj¹ na ogó³ nieformalne, intuicyjne objanienia 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¿onoci obliczeniowej

Wa¿nym uzupe³nieniem treci ksi¹¿ki s¹ æwiczenia o zró¿nicowanych poziomach

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

CENNIK I INFORMACJE

ZAMÓW INFORMACJE

O NOWOCIACH

ZAMÓW CENNIK

CZYTELNIA

FRAGMENTY KSI¥¯EK ONLINE

Wydawnictwo Helion

ul. Chopina 6

44-100 Gliwice

tel. (32)230-98-63

e-mail: helion@helion.pl

Spis treści

Przedmowa .................................... 7

1. Modele obliczania ............................. 11

1.1 Algorytmyiichzłożoność........................ 11

1.2 Maszynyodostępieswobodnym..................... 14

1.3 Złożoność obliczeniowa programów RAM . . . . . . . . . . . . . . . 20

1.4 Model z zapamiętanym programem . . . . . . . . . . . . . . . . . . . 23

1.5 AbstrakcjeRAM ............................. 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 Strukturydanych:listy,kolejkiistosy ................. 52

2.2 Reprezentacje zbioru . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

2.3 Grafy ................................... 57

2.4 Drzewa .................................. 60

2.5 Rekurencja ................................ 63

2.6 Dzielizwyciężaj ............................. 67

2.7 Zrównoważenie .............................. 73

2.8 Programowaniedynamiczne....................... 74

2.9 Zakończenie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

3. Sortowanie i statystyka pozycyjna ................... 85

3.1 Problemsortowania ........................... 86

3.2 Sortowaniepozycyjne .......................... 87

3.3 Sortowanieprzezporó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 Statystykapozycyjna...........................106

3.7 Czas oczekiwany dla statystyki pozycyjnej . . . . . . . . . . . . . . . 108

4. Struktury danych dla zadań operujących na zbiorach .......117

4.1 Operacjepierwotnenazbiorach.....................117

4.2 Haszowanie ................................120

4.3 Poszukiwaniebinarne ..........................122

4.4 Drzewaposzukiwańbinarnych......................124

4.5 Optymalne drzewa poszukiwań binarnych . . . . . . . . . . . . . . . 128

Spis treści

4.6 Prosty algorytm sumy zbiorów rozłącznych . . . . . . . . . . . . . . 132

4.7 StrukturydrzewdlaproblemuUNION-FIND .............136

4.8 Zastosowania i rozszerzenia algorytmu UNION-FIND . . . . . . . . . 146

4.9 Schematy z drzewami zrównoważonymi . . . . . . . . . . . . . . . . . 152

4.10Słownikiikolejkipriorytetowe .....................155

4.11Kopcezłączane..............................159

4.12Kolejkikonkatenowane..........................162

4.13Podział ..................................164

4.14Podsumowanierozdziału.........................169

5. Algorytmy na grafach ...........................179

5.1 Drzewarozpinająceominimalnymkoszcie...............179

5.2 Przeszukiwaniewgłą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 graﬁe skierowanym . . . . . . . . . . . . 218

6. Mnożenie macierzy i pokrewne operacje ...............235

6.1 Podstawy .................................235

6.2 AlgorytmStrassenamnożeniamacierzy ................239

6.3 Odwracaniemacierzy...........................241

6.4 RozkładLUP...............................242

6.5 ZastosowaniarozkładuLUP.......................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 FFTzoperacjaminabitach.......................276

7.4 Iloczynywielomianów ..........................281

7.5 Mnożenie liczb całkowitych według algorytm Schonhagego–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żenieidzieleniewielomianów....................298

8.4 Arytmetykamodularna .........................300

8.5 Arytmetyka modularna na wielomianach i wartości wielomianów . . 304

8.6 Chińskiezliczaniereszt..........................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

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

8.12Wielomianyrzadkie ...........................323

9. Algorytmy dopasowania wzorców ....................329

9.1 Automaty skończone i wyrażenia regularne . . . . . . . . . . . . . . 329

9.2 Rozpoznawanie wzorców przez wyrażenia regularne . . . . . . . . . . 338

9.3 Rozpoznawaniepodnapisów.......................341

9.4 Dwukierunkowe deterministyczne automaty ze stosem . . . . . . . . 347

9.5 Drzewa pozycji i indentyﬁkatory podnapisowe . . . . . . . . . . . . . 358

..............................383

10.3Językiiproblemy.............................385

10.4NP-zupełnośćproblemuspełnialności..................388

10.5InneproblemyNP-zupełne .......................395

10.6 Problemy o wielomianowej złożoności pamięciowej . . . . . . . . . . 406

11. Problemy niełatwe na podstawie dowodu ...............417

11.1Hierarchiezł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.4Problemnieelementarny.........................430

12. Ograniczenia dolne liczby operacji arytmetycznych ........439

12.1Ciała....................................439

12.2 Kod liniowy — raz jeszcze . . . . . . . . . . . . . . . . . . . . . . . . 440

12.3Macierzoweformułowanieproblemó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.7Nastawianie................................452

Bibliograﬁa ....................................463

Indeks .......................................477

10. Problemy NP-zupełne ...........................375

10.1 Niedeterministyczne maszyny Turinga . . . . . . . . . . . . . . . . . 376

10.2 Klasy

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 zdeﬁniować 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 cn 2 dla pewnej stałej c , to mówimy, że czasowa

złożoność tego algorytmu jest O ( n 2 ), czytaj „rzędu n 2 ”. Ściślej, funkcja g ( n )jest

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: