Algorytmy_Almanach_algalm.pdf

(708 KB) Pobierz
Algorytmy. Almanach
Autorzy: George Heineman, Gary Pollice, Stanley Selkow
T³umaczenie: Zdzis³aw P³oski
ISBN: 978-83-246-2209-2
Tytu³ orygina³u:
Algorithms in a Nutshell
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
Zasada: wprowadzaj tylko tyle matematyki, ile trzeba
Zasada: analizę matematyczną stosuj doświadczalnie
Odbiorcy
Treść książki
Konwencje stosowane w tej książce
Zastosowanie przykładów w kodzie
Podziękowania
Literatura
8
9
9
10
11
11
12
13
13
Część I ...............................................................................................................15
1. Algorytmy są ważne .....................................................................................................17
Postaraj się zrozumieć problem
Jeśli to konieczne, eksperymentuj
Kwestia uboczna
Nauka płynąca z opowiedzianej historii
Literatura
18
19
23
23
25
2. Algorytmy w ujęciu matematycznym ......................................................................... 27
Rozmiar konkretnego problemu
Tempo rośnięcia funkcji
Analiza przypadku najlepszego,
średniego
i najgorszego
Rodziny efektywności
Mieszanka działań
Operacje do pomiarów wzorcowych
Uwaga końcowa
Literatura
27
29
33
37
49
50
52
52
3
3. Wzorce i dziedziny ......................................................................................................53
Wzorce — język komunikacji
Forma wzorca pseudokodu
Forma projektowa
Forma oceny doświadczalnej
Dziedziny a algorytmy
Obliczenia zmiennopozycyjne
Ręczne przydzielanie pamięci
Wybór języka programowania
53
55
57
59
59
60
64
66
Część II ............................................................................................................. 69
4. Algorytmy sortowania .................................................................................................71
Przegląd
Sortowanie przez wstawianie
Sortowanie medianowe
Sortowanie szybkie
Sortowanie przez wybieranie
Sortowanie przez kopcowanie
Sortowanie przez zliczanie
Sortowanie kubełkowe
Kryteria wyboru algorytmu sortowania
Literatura
71
77
81
91
98
99
104
106
111
115
5. Wyszukiwanie ............................................................................................................ 117
Przegląd
Wyszukiwanie sekwencyjne
Wyszukiwanie z haszowaniem
Przeszukiwanie drzewa binarnego
Literatura
117
118
128
140
146
6. Algorytmy grafowe ................................................................................................... 147
Przegląd
Przeszukiwania w głąb
Przeszukiwanie wszerz
Najkrótsza
ścieżka
z jednym
źródłem
Najkrótsza
ścieżka
między wszystkimi parami
Algorytmy minimalnego drzewa rozpinającego
Literatura
147
153
160
163
174
177
180
4
|
Spis treści
7. Znajdowanie dróg w AI ..............................................................................................181
Przegląd
Przeszukiwania wszerz
A
*
SEARCH
Porównanie
Algorytm minimaks
Algorytm AlfaBeta
181
198
201
211
214
222
8. Algorytmy przepływu w sieciach ............................................................................. 231
Przegląd
Przepływ maksymalny
Dopasowanie obustronne
Uwagi na temat
ścieżek
powiększających
Przepływ o minimalnym koszcie
Przeładunek
Przydział zadań
Programowanie liniowe
Literatura
231
234
243
246
249
250
252
253
254
9. Geometria obliczeniowa ...........................................................................................255
Przegląd
Skanowanie otoczki wypukłej
Zamiatanie prostą
Pytanie o najbliższych sąsiadów
Zapytania przedziałowe
Literatura
255
263
272
283
294
300
Część III ...........................................................................................................301
10. Gdy wszystko inne zawodzi ......................................................................................303
Wariacje na temat
Algorytmy aproksymacyjne
Algorytmy offline
Algorytmy równoległe
Algorytmy losowe
Algorytmy, które mogą być złe, lecz z malejącym prawdopodobieństwem
Literatura
303
304
304
305
305
312
315
Spis treści
|
5
11. Epilog ...........................................................................................................................317
Przegląd
Zasada: znaj swoje dane
Zasada: podziel problem na mniejsze problemy
Zasada: wybierz właściwą strukturę
Zasada: dodaj pamięci, aby zwiększyć efektywność
Zasada: jeśli nie widać rozwiązania, skonstruuj przeszukanie
Zasada: jeśli nie widać rozwiązania, zredukuj problem do takiego,
który ma rozwiązanie
Zasada: pisanie algorytmów jest trudne, testowanie — trudniejsze
317
317
318
319
319
321
321
322
Część IV ......................................................................................................... 325
Dodatek. Testy wzorcowe ......................................................................................... 327
Podstawy statystyczne
Sprzęt
Przykład
Raportowanie
Dokładność
327
328
329
335
337
Skorowidz ..................................................................................................................339
6
|
Spis treści

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin