Algorytmy Almanach algalm

[ Pobierz całość w formacie PDF ]
Algorytmy. Almanach
Autorzy: George Heineman, Gary Pollice, Stanley Selkow
T³umaczenie: Zdzis³aw P³oski
ISBN: 978-83-246-2209-2
Tytu³ orygina³
Format: 168
×
237, stron: 352
Ca³a wiedza o algorytmach w jednym podrêczniku!
Jaki wp³yw na ró¿ne algorytmy wywieraj¹ podobne decyzje projektowe?
Jak rozwi¹zywaæ problemy dotycz¹ce kodowania?
Jak wykorzystaæ zaawansowane struktury danych do usprawnienia algorytmów?
Tworzenie niezawodnego oprogramowania wymaga stosowania sprawnych algorytmów.
Jednak programiœci rzadko poœwiêcaj¹ im uwagê, dopóki nie pojawi¹ siê k³opoty.
Aby ich unikn¹æ, powinieneœ wiedzieæ, w jaki sposób poprawianie efektywnoœci
najwa¿niejszych algorytmów przes¹dza o sukcesie Twoich aplikacji. W tej ksi¹¿ce
znajdziesz przetestowane i wypróbowane metody wykorzystywania oraz poprawiania
skutecznoœci algorytmów – do u¿ycia w celu wdro¿enia sprawnych rozwi¹zañ
programistycznych.
Ksi¹¿ka „Algorytmy. Almanach” to ca³a wiedza o algorytmach, potrzebna ambitnemu
programiœcie, zebrana w jeden kompletny podrêcznik. Ksi¹¿ka zawiera opisy algorytmów
do rozwi¹zywania rozmaitych problemów, pomaga w wyborze i realizacji algorytmów
odpowiednich do Twoich potrzeb, a tak¿e dostarcza wydajnych rozwi¹zañ zakodowanych
w kilku jêzykach programowania, które ³atwo mo¿na zaadaptowaæ w konkretnych
zadaniach. Dziêki temu podrêcznikowi nauczysz siê projektowaæ struktury danych,
a tak¿e dowiesz siê, na czym polega przeszukiwanie drzewa binarnego oraz jak
korzystaæ z informacji heurystycznych. Poznasz zaawansowane struktury danych,
przydatne do usprawniania algorytmów, a jednoczeœnie niezbêdne dla
zagwarantowania pe³nego sukcesu Twoich rozwi¹zañ programistycznych.
Algorytmy w ujêciu matematycznym
Wzorce i dziedziny
Algorytmy sortowania
Wyszukiwanie sekwencyjne
Przeszukiwanie drzewa binarnego
Algorytmy grafowe
Drzewa poszukiwañ
Korzystanie z informacji heurystycznych
Algorytmy przep³ywu w sieciach
Geometria obliczeniowa
Zapytania przedzia³owe
Ca³a wiedza o algorytmach, potrzebna ka¿demu programiœcie!
Spis treści
Przedmowa ............................................................................................................................... 7
Zasada: oddziel algorytm od rozwiązywanego problemu
8
Zasada: wprowadzaj tylko tyle matematyki, ile trzeba
9
Zasada: analizę matematyczną stosuj doświadczalnie
9
Odbiorcy
10
Treść książki
11
Konwencje stosowane w tej książce
11
Zastosowanie przykładów w kodzie
12
Podziękowania
13
Literatura
13
Część I ............................................................................................................... 15
1. Algorytmy są ważne .....................................................................................................17
Postaraj się zrozumieć problem
18
Jeśli to konieczne, eksperymentuj
19
Kwestia uboczna
23
Nauka płynąca z opowiedzianej historii
23
Literatura
25
2. Algorytmy w ujęciu matematycznym ......................................................................... 27
Rozmiar konkretnego problemu
27
Tempo rośnięcia funkcji
29
Analiza przypadku najlepszego, średniego i najgorszego
33
Rodziny efektywności
37
Mieszanka działań
49
Operacje do pomiarów wzorcowych
50
Uwaga końcowa
52
Literatura
52
3
 3. Wzorce i dziedziny ...................................................................................................... 53
Wzorce — język komunikacji
53
Forma wzorca pseudokodu
55
Forma projektowa
57
Forma oceny doświadczalnej
59
Dziedziny a algorytmy
59
Obliczenia zmiennopozycyjne
60
Ręczne przydzielanie pamięci
64
Wybór języka programowania
66
Część II ............................................................................................................. 69
4. Algorytmy sortowania .................................................................................................71
Przegląd
71
Sortowanie przez wstawianie
77
Sortowanie medianowe
81
Sortowanie szybkie
91
Sortowanie przez wybieranie
98
Sortowanie przez kopcowanie
99
Sortowanie przez zliczanie
104
Sortowanie kubełkowe
106
Kryteria wyboru algorytmu sortowania
111
Literatura
115
5. Wyszukiwanie ............................................................................................................ 117
Przegląd
117
Wyszukiwanie sekwencyjne
118
Wyszukiwanie z haszowaniem
128
Przeszukiwanie drzewa binarnego
140
Literatura
146
6. Algorytmy grafowe ................................................................................................... 147
Przegląd
147
Przeszukiwania w głąb
153
Przeszukiwanie wszerz
160
Najkrótsza ścieżka z jednym źródłem
163
Najkrótsza ścieżka między wszystkimi parami
174
Algorytmy minimalnego drzewa rozpinającego
177
Literatura
180
4
|
Spis treści
7. Znajdowanie dróg w AI ..............................................................................................181
Przegląd
181
Przeszukiwania wszerz
198
A
*
SEARCH
201
Porównanie
211
Algorytm minimaks
214
Algorytm AlfaBeta
222
8. Algorytmy przepływu w sieciach ............................................................................. 231
Przegląd
231
Przepływ maksymalny
234
Dopasowanie obustronne
243
Uwagi na temat ścieżek powiększających
246
Przepływ o minimalnym koszcie
249
Przeładunek
250
Przydział zadań
252
Programowanie liniowe
253
Literatura
254
9. Geometria obliczeniowa ........................................................................................... 255
Przegląd
255
Skanowanie otoczki wypukłej
263
Zamiatanie prostą
272
Pytanie o najbliższych sąsiadów
283
Zapytania przedziałowe
294
Literatura
300
Część III ...........................................................................................................301
10. Gdywszystkoinne zawodzi ......................................................................................303
Wariacje na temat
303
Algorytmy aproksymacyjne
304
Algorytmy offline
304
Algorytmy równoległe
305
Algorytmy losowe
305
Algorytmy, które mogą być złe, lecz z malejącym prawdopodobieństwem
312
Literatura
315
Spis treści
|
5
11. Epilog...........................................................................................................................317
Przegląd
317
Zasada: znaj swoje dane
317
Zasada: podziel problem na mniejsze problemy
318
Zasada: wybierz właściwą strukturę
319
Zasada: dodaj pamięci, aby zwiększyć efektywność
319
Zasada: jeśli nie widać rozwiązania, skonstruuj przeszukanie
321
Zasada: jeśli nie widać rozwiązania, zredukuj problem do takiego,
który ma rozwiązanie
321
Zasada: pisanie algorytmów jest trudne, testowanie — trudniejsze
322
Część IV ......................................................................................................... 325
Dodatek. Testy wzorcowe ......................................................................................... 327
Podstawy statystyczne
327
Sprzęt
328
Przykład
329
Raportowanie
335
Dokładność
337
Skorowidz ..................................................................................................................339
6
|
Spis treści
[ Pobierz całość w formacie PDF ]