Algorytmy i struktury danych ...

[ Pobierz całość w formacie PDF ]
IDZ DO
PRZYK£ADOW
Algorytmy i struktury
SPIS TRECI
danych
KATALOG KSI¥¯EK
Autorzy: Alfred V. Aho, John E. Hopcroft, Jeffrey D. Ullman
T³umaczenie: Andrzej Gra¿yñski
ISBN: 83-7361-177-0
Tytu³ orygina³
Format: B5, stron: 442
KATALOG ONLINE
ZAMÓW DRUKOWANY KATALOG
TWÓJ KOSZYK
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 kontekcie rozwi¹zywania
problemów za pomoc¹ komputera. Z tematyk¹ rozwi¹zywania problemów powi¹zano
zagadnienie zliczania kroków oraz z³o¿onoci 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 trudnoci,
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¹.
DODAJ DO KOSZYKA
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 treci
Od tłumacza.............................................................................................................7
Wstp .....................................................................................................................11
Projektowanie i analiza algorytmów......................................................................15
1.1. Od problemu do programu......................................................................................................................... 15
1.2. Abstrakcyjne typy danych.......................................................................................................................... 23
1.3. Typy danych, struktury danych i ADT ...................................................................................................... 25
1.4. Czas wykonywania programu.................................................................................................................... 28
1.5. Obliczanie czasu wykonywania programu................................................................................................. 33
1.6. Dobre praktyki programowania ................................................................................................................. 39
1.7. Super Pascal ............................................................................................................................................... 41
*wiczenia.......................................................................................................................................................... 44
Uwagi bibliograficzne....................................................................................................................................... 48
Podstawowe abstrakcyjne typy danych .................................................................49
2.1. Lista jako abstrakcyjny typ danych............................................................................................................ 49
2.2. Implementacje list...................................................................................................................................... 52
2.3. Stosy........................................................................................................................................................... 64
2.4. Kolejki........................................................................................................................................................ 68
2.5. Mapowania................................................................................................................................................. 73
2.6. Stosy a procedury rekurencyjne................................................................................................................. 75
*wiczenia.......................................................................................................................................................... 80
Uwagi bibliograficzne....................................................................................................................................... 84
Drzewa...................................................................................................................85
3.1. Podstawowa terminologia.......................................................................................................................... 85
3.2. Drzewa jako abstrakcyjne obiekty danych................................................................................................. 92
 4
SPIS TRECI
3.3. Implementacje drzew ................................................................................................................................. 95
3.4. Drzewa binarne ........................................................................................................................................ 102
*wiczenia........................................................................................................................................................ 113
Uwagi bibliograficzne..................................................................................................................................... 116
Podstawowe operacje na zbiorach.......................................................................117
4.1. Wprowadzenie do zbiorów....................................................................................................................... 117
4.2. Słowniki ................................................................................................................................................... 129
4.3. Tablice haszowane ................................................................................................................................... 132
4.4. Implementacja abstrakcyjnego typu danych MAPPING......................................................................... 146
4.5. Kolejki priorytetowe ................................................................................................................................ 148
4.6. Przykłady zło7onych struktur zbiorowych............................................................................................... 156
*wiczenia........................................................................................................................................................ 163
Uwagi bibliograficzne..................................................................................................................................... 165
Zaawansowane metody reprezentowania zbiorów ..............................................167
5.1. Binarne drzewa wyszukiwawcze ............................................................................................................. 167
5.2. Analiza zło7ono9ci operacji wykonywanych na binarnym drzewie wyszukiwawczym.......................... 171
5.3. Drzewa trie............................................................................................................................................... 175
5.4. Implementacja zbiorów w postaci drzew wywa7onych — 2-3-drzewa................................................... 181
5.5. Operacje MERGE i FIND........................................................................................................................ 193
5.6. Abstrakcyjny typ danych z operacjami MERGE i SPLIT ....................................................................... 202
*wiczenia........................................................................................................................................................ 207
Uwagi bibliograficzne..................................................................................................................................... 209
Grafy skierowane.................................................................................................211
6.1. Podstawowe poj?cia................................................................................................................................. 211
6.2. Reprezentacje grafów skierowanych........................................................................................................ 213
6.3. Graf skierowany jako abstrakcyjny typ danych....................................................................................... 215
6.4. Znajdowanie najkrótszych 9cie7ek o wspólnym poczAtku....................................................................... 217
6.5. Znajdowanie najkrótszych 9cie7ek mi?dzy ka7dA parA wierzchołków.................................................... 221
6.6. Przechodzenie przez grafy skierowane — przeszukiwanie zst?pujAce.................................................... 229
6.7. Silna spójno9B i silnie spójne składowe digrafu....................................................................................... 237
*wiczenia........................................................................................................................................................ 240
Uwagi bibliograficzne..................................................................................................................................... 242
Grafy nieskierowane............................................................................................243
7.1. Definicje................................................................................................................................................... 243
7.2. Metody reprezentowania grafów.............................................................................................................. 245
7.3. Drzewa rozpinajAce o najmniejszym koszcie........................................................................................... 246
7.4. Przechodzenie przez graf ......................................................................................................................... 253
7.5. Wierzchołki rozdzielajAce i składowe dwuspójne grafu.......................................................................... 256
SPIS TRECI
5
7.6. Reprezentowanie skojarzeC przez grafy................................................................................................... 259
*wiczenia........................................................................................................................................................ 262
Uwagi bibliograficzne..................................................................................................................................... 264
Sortowanie ...........................................................................................................265
8.1. Model sortowania wewn?trznego............................................................................................................. 265
8.2. Proste algorytmy sortowania wewn?trznego............................................................................................ 266
8.3. Sortowanie szybkie (quicksort)................................................................................................................ 273
8.4. Sortowanie stogowe ................................................................................................................................. 283
8.5. Sortowanie rozrzutowe............................................................................................................................. 287
8.6. Dolne ograniczenie dla sortowania za pomocA porównaC....................................................................... 294
8.7. Szukanie k-tej warto9ci (statystyki pozycyjne)........................................................................................ 298
*wiczenia........................................................................................................................................................ 302
Uwagi bibliograficzne..................................................................................................................................... 304
Techniki analizy algorytmów ..............................................................................305
9.1. Efektywno9B algorytmów......................................................................................................................... 305
9.2. Analiza programów zawierajAcych wywołania rekurencyjne.................................................................. 306
9.3. RozwiAzywanie równaC rekurencyjnych ................................................................................................. 308
9.4. RozwiAzanie ogólne dla pewnej klasy rekurencji .................................................................................... 311
*wiczenia........................................................................................................................................................ 316
Uwagi bibliograficzne..................................................................................................................................... 319
10
Techniki projektowania algorytmów...................................................................321
10.1. Zasada „dziel i zwyci?7aj”..................................................................................................................... 321
10.2. Programowanie dynamiczne.................................................................................................................. 327
10.3. Algorytmy zachłanne ............................................................................................................................. 335
10.4. Algorytmy z nawrotami ......................................................................................................................... 339
10.5. Przeszukiwanie lokalne.......................................................................................................................... 349
*wiczenia........................................................................................................................................................ 355
Uwagi bibliograficzne..................................................................................................................................... 358
11
Struktury danych i algorytmy obróbki danych zewntrznych.............................359
11.1. Model danych zewn?trznych.................................................................................................................. 359
11.2. Sortowanie zewn?trzne .......................................................................................................................... 362
11.3. Przechowywanie informacji w plikach pami?ci zewn?trznych ............................................................. 373
11.4. Zewn?trzne drzewa wyszukiwawcze ..................................................................................................... 381
*wiczenia........................................................................................................................................................ 387
Uwagi bibliograficzne..................................................................................................................................... 390
6
SPIS TRECI
12
Zarz/dzanie pamici/ ..........................................................................................391
12.1. Podstawowe aspekty zarzAdzania pami?ciA........................................................................................... 391
12.2. ZarzAdzanie blokami o ustalonej wielko9ci ........................................................................................... 395
12.3. Algorytm od9miecania dla bloków o ustalonej wielko9ci...................................................................... 397
12.4. Przydział pami?ci dla obiektów o zró7nicowanych rozmiarach............................................................ 405
12.5. Systemy partnerskie ............................................................................................................................... 412
12.6. Upakowywanie pami?ci......................................................................................................................... 416
*wiczenia........................................................................................................................................................ 419
Uwagi bibliograficzne..................................................................................................................................... 421
Bibliografia..........................................................................................................423
Skorowidz............................................................................................................429
[ Pobierz całość w formacie PDF ]