Helion - Algorytmy. Almanach.pdf

(10160 KB) Pobierz
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
Dodatki . ......................................................................................................... 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