George Heineman
George Heineman, mojeksiążki
[ Pobierz całość w formacie PDF ]
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. Gdy wszystko inne 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
ROZDZIAŁ 2.
Algorytmy
w ujęciu matematycznym
Wybierając algorytm do rozwiązania problemu, próbujesz przewidzieć, który będzie najszybszy
dla konkretnego zbioru danych na konkretnej platformie (lub rodzinie platform). Określenie
oczekiwanego czasu działania danego algorytmu jest procesem z natury matematycznym. W tym
rozdziale przedstawiamy narzędzia matematyczne pomagające w takich przewidywaniach. Po
przeczytaniu tego rozdziału Czytelnicy będą rozumieć różne pojęcia matematyczne występujące
w tej książce.
Wspólnym motywem tego rozdziału (w istocie — przyjętym w całej książce) jest założenie, że
wszystkie hipotezy i przybliżenia mogą się różnić o pewną stałą, przy czym w naszych uogól-
nieniach stałe takie możemy pomijać. Dla wszystkich algorytmów ujętych w tej książce stałe te
są małe w przypadku niemal wszystkich platform.
Rozmiar konkretnego problemu
Przez egzemplarz (ukonkretnienie) problemu rozumie się określony zbiór danych, na którym
działa program. W większości problemów czas wykonania programu wzrasta z rozmiarem ko-
dowania rozwiązywanego egzemplarza. Z drugiej strony reprezentacje nazbyt zwarte (np. po-
wstałe z użyciem technik kompresji) mogą niepotrzebnie spowalniać wykonanie programu.
Zdefiniowanie optymalnego sposobu zakodowania konkretnego problemu jest zaskakująco trudne,
ponieważ problemy występują w świecie rzeczywistym i trzeba je tłumaczyć na odpowiednią
reprezentację maszynową, aby można było je rozwiązać na komputerze. Rozważmy dwa zako-
dowania liczby
x
, pokazane nieco dalej w ramce „Konkrety są kodowane”.
O ile to tylko możliwe, chcemy w ocenie algorytmów korzystać z założenia, że zakodowanie
konkretnego problemu nie ma decydującego wpływu na możliwość uzyskania sprawnej realizacji
algorytmu. Choć rozmiary obu kodowań (w ramce) są niemal identyczne, wiąże się z nimi różna
sprawność podstawowej operacji, zależna od tego, czy
x
ma w reprezentacji dwójkowej parzystą,
czy nieparzystą liczbę bitów o wartości 1.
Wybór reprezentacji konkretnego problemu zależy od typu i rozmaitości operacji, które mają być
wykonywane. Projektowanie efektywnych algorytmów często zaczyna się od wyboru odpowied-
nich struktur danych, za pomocą których można przedstawić problem wymagający rozwiązania,
co pokazano na rysunku 2.1.
27
[ Pobierz całość w formacie PDF ]