ALGORYTMY DLA BYSTRZAKÓW

SPIS TREŚCI

O autorach 15

Podziękowania od autorów 17

Wprowadzenie 19

CZĘŚĆ I: ZACZYNAMY 25

Rozdział 1: Wprowadzenie do algorytmów 27

• Co to jest algorytm? 28
  • Zastosowania algorytmów 30
  • Algorytmy są wszędzie 32
• Stosowanie komputerów do rozwiązywania problemów 33
  • Wykorzystanie nowoczesnych procesorów i procesorów graficznych 34
  • Wykorzystanie układów specjalnych 35
  • Wykorzystanie sieci 36
  • Wykorzystywanie dostępnych danych 37
• Odróżnianie problemów od rozwiązań 38
  • Poprawność a skuteczność 38
  • Nie ma nic za darmo! 39
  • Dostosowanie strategii do problemu 39
  • Zrozumiały opis algorytmów 39
  • Stawianie czoła trudnym problemom 40
• Strukturyzacja danych w celu uzyskania rozwiązania 40
  • Zrozumienie punktu widzenia komputera 41
  • Układ danych robi różnicę 41

Rozdział 2: Projekt algorytmu 43

• Rozpoczęcie rozwiązywania problemu 44
  • Modelowanie rzeczywistych problemów 45
  • Znajdowanie rozwiązań i kontrprzykładów 47
  • Na ramionach olbrzymów 48
• Dziel i zwyciężaj 48
  • Unikanie rozwiązań siłowych 49
  • Zacznij od uproszczenia 50
  • Rozwiązanie składowych problemu zwykle jest łatwiejsze niż rozwiązanie całego problemu 50
• Zachłanność może być dobra 51
  • Stosowanie zachłannego wnioskowania 51
  • Osiąganie dobrego rozwiązania 52
• Koszty obliczeniowe i korzystanie z heurystyk 53
  • Reprezentowanie problemu jako przestrzeni 54
  • Wykonywanie losowych ruchów i liczenie na szczęście 54
  • Używanie heurystyki i funkcji kosztu 55
• Ocena algorytmów 56
  • Symulacje z wykorzystaniem maszyn abstrakcyjnych 57
  • Więcej abstrakcji 58
  • Wykorzystanie funkcji 59

Rozdział 3: Wykorzystanie Pythona do pracy z algorytmami 63

• Zalety Pythona 65
  • Dlaczego w tej książce korzystamy z Pythona? 65
  • Korzystanie z MATLAB-a 67
  • Inne środowiska testowania algorytmów 68
• Dystrybucje Pythona 68
  • Pobieranie środowiska Anaconda Analytics 69
  • Enthought Canopy Express 70
  • Środowisko pythonxy 70
  • WinPython 71
• Instalowanie Pythona w systemie Linux 71
• Instalowanie Pythona w systemie MacOS 72
• Instalowanie Pythona w systemie Windows 74
• Pobieranie zestawów danych i przykładowego kodu 77
  • Korzystanie ze środowiska Jupyter Notebook 77
  • Definiowanie repozytorium kodu 79
  • Zestawy danych wykorzystywane w tej książce 84

Rozdział 4: Wprowadzenie do Pythona jako narzędzia do programowania algorytmów 87

• Działania na liczbach i operacje logiczne 89
  • Przypisywanie wartości do zmiennych 90
  • Wykonywanie działań arytmetycznych 91
  • Porównywanie danych za pomocą wyrażeń boolowskich 92
• Tworzenie ciągów znaków i posługiwanie się nimi 95
• Działania na datach 97
• Tworzenie i stosowanie funkcji 98
  • Tworzenie funkcji wielokrotnego użytku 98
  • Wywoływanie funkcji 99
• Stosowanie instrukcji warunkowych i pętli 102
  • Podejmowanie decyzji za pomocą instrukcji if 102
  • Wybór pomiędzy wieloma opcjami z wykorzystaniem decyzji zagnieżdżonych 103
  • Wykonywanie powtarzających się zadań za pomocą pętli for 104
  • Korzystanie z instrukcji while 105
• Przechowywanie danych z wykorzystaniem zbiorów, list i krotek 106
  • Tworzenie zbiorów 106
  • Tworzenie list 107
  • Tworzenie i używanie krotek 108
• Definiowanie przydatnych iteratorów 110
• Indeksowanie danych z wykorzystaniem słowników 111

Rozdział 5: Wykonywanie podstawowych operacji na danych za pomocą Pythona 113

• Wykonywanie obliczeń za pomocą wektorów i macierzy 114
  • Operacje na wartościach skalarnych i na wektorach 115
  • Mnożenie wektorów 117
  • Najlepiej rozpocząć od utworzenia macierzy 118
  • Mnożenie macierzy 119
  • Definiowanie zaawansowanych operacji na macierzach 120
• Właściwe tworzenie kombinacji 122
  • Rozróżnianie permutacji 122
  • Tasowanie kombinacji 123
  • Obsługa powtórzeń 124
• Uzyskiwanie pożądanych wyników za pomocą rekurencji 125
  • Co to jest rekurencja? 125
  • Eliminowanie rekurencji wywołań ogonowych 128
• Szybsze wykonywanie zadań 129
  • Dziel i zwyciężaj 129
  • Rozróżnianie możliwych rozwiązań 132

CZĘŚĆ II: ZNACZENIE SORTOWANIA I WYSZUKIWANIA 135

Rozdział 6: Strukturyzowanie danych 137

• Niezbędność struktury 138
  • Łatwiejsze oglądanie treści 138
  • Dopasowywanie danych z różnych źródeł 139
  • Korygowanie danych 140
• Układanie danych w stos 143
  • Porządkowanie z wykorzystaniem stosów 143
  • Korzystanie z kolejek 145
  • Wyszukiwanie danych z wykorzystaniem słowników 146
• Drzewa 147
  • Podstawowe wiadomości o drzewach 147
  • Budowanie drzewa 148
• Reprezentowanie relacji za pomocą grafu 150
  • Więcej niż drzewa 150
  • Budowanie grafów 151

Rozdział 7: Organizowanie i wyszukiwanie danych 155

• Sortowanie z wykorzystaniem algorytmów MergeSort i QuickSort 156
  • Dlaczego ważne jest sortowanie danych? 156
  • Naiwne sortowanie danych 158
  • Lepsze techniki sortowania 160
• Korzystanie z drzew wyszukiwania i stert 164
  • Potrzeba skutecznego wyszukiwania 165
  • Budowanie drzewa wyszukiwania binarnego 167
  • Wyspecjalizowane wyszukiwania za pomocą sterty binarnej 168
• Korzystanie z tablic asocjacyjnych 169
  • Pojemniki na dane 169
  • Zapobieganie kolizjom 171
  • Tworzenie własnej funkcji haszującej 173

CZĘŚĆ III: ŚWIAT GRAFÓW 175

Rozdział 8: Podstawowe informacje o grafach 177

• Znaczenie sieci 178
  • Istota grafu 178
  • Grafy są wszędzie 180
  • Społecznościowa strona grafów 181
  • Podgrafy 182
• Definiowanie sposobu rysowania grafu 183
  • Rozróżnianie kluczowych atrybutów 183
  • Rysowanie grafu 185
• Pomiar funkcjonalności grafu 186
  • Zliczanie krawędzi i wierzchołków 186
  • Obliczanie centralności 188
• Liczbowa reprezentacja grafu 190
  • Dodawanie grafu do macierzy 191
  • Używanie reprezentacji rzadkich 192
  • Korzystanie z list do przechowywania grafu 192

Rozdział 9: Połącz kropki 195

• Efektywne przechodzenie przez graf 196
  • Tworzenie grafu 197
  • Przeszukiwanie najpierw wszerz 198
  • Przeszukiwanie najpierw w głąb 199
  • Określanie, której aplikacji użyć 202
• Sortowanie elementów grafu 202
  • Skierowane grafy acykliczne 203
  • Sortowanie topologiczne 204
• Redukcja do minimalnego drzewa rozpinającego 205
  • Wybór odpowiednich algorytmów 208
  • Kolejki z priorytetami 209
  • Wykorzystanie algorytmu Prima 210
  • Testowanie algorytmu Kruskala 211
  • Który algorytm działa najlepiej? 213
• Znalezienie najkrótszej trasy 214
  • Co to znaczy znaleźć najkrótszą ścieżkę? 214
  • Wyjaśnienie algorytmu Dijkstry 216

Rozdział 10: Odkrywanie tajemnic grafów 219

• Sieci społecznościowe jako grafy 220
  • Klasteryzacja sieci 220
  • Odkrywanie społeczności 223
• Poruszanie się po grafie 225
  • Zliczanie stopni separacji 225
  • Losowe poruszanie się po grafie 227

Rozdział 11: Pobieranie właściwej strony internetowej 229

• Odkrywanie świata za pomocą wyszukiwarki 230
  • Wyszukiwanie danych w internecie 230
  • Jak znaleźć właściwe dane? 230
• Czym jest algorytm PageRank? 232
  • Wnioskowanie w algorytmie PageRank 232
  • Szczegóły działania algorytmu PageRank 234
• Implementacja algorytmu PageRank 234
  • Implementacja skryptu Pythona 235
  • Rozwiązywanie problemów naiwnej implementacji 238
  • Nuda i teleportacja 240
  • Jak działa wyszukiwarka? 242
  • Inne zastosowania algorytmu PageRank 242
• Nie tylko paradygmat PageRank 243
  • Zapytania semantyczne 243
  • Stosowanie technik AI do tworzenia rankingu wyników wyszukiwania 244

CZĘŚĆ IV: ZMAGANIA Z BIG DATA 245

Rozdział 12: Zarządzanie obszernymi zbiorami danych 247

• Przekształcanie mocy obliczeniowej w dane 248
  • Implikacje prawa Moore’a 249
  • Dane są wszędzie 251
  • Zastosowanie algorytmów w biznesie 253
• Strumieniowy przepływ danych 255
  • Analiza strumieni z wykorzystaniem odpowiednich receptur 256
  • Rezerwowanie właściwych danych 257
• Szkicowanie odpowiedzi z danych strumienia 261
  • Filtrowanie elementów strumienia „na pamięć” 262
  • Przykład filtra Blooma 264
  • Znajdowanie liczby różnych elementów 267
  • Zliczanie obiektów w strumieniu 269

Rozdział 13: Współbieżne wykonywanie operacji 271

• Zarządzanie ogromnymi ilościami danych 272
  • Paradygmat przetwarzania równoległego 272
  • Dystrybucja plików i operacji 275
  • Zastosowanie rozwiązania MapReduce 277
• Algorytmy dla techniki MapReduce 280
  • Konfigurowanie symulacji MapReduce 281
  • Zapytanie przez mapowanie 283

Rozdział 14: Kompresja danych 287

• Zmniejszenie rozmiaru danych 288
  • Kodowanie 288
  • Efekty kompresji 290
  • Wybór rodzaju kompresji 291
  • Dobór kodowania 293
  • Kodowanie za pomocą kompresji Huffmana 295
  • Zapamiętywanie sekwencji za pomocą LZW 297

CZĘŚĆ V: TRUDNE PROBLEMY 303

Rozdział 15: Algorytmy zachłanne 305

• Kiedy lepiej jest być zachłannym? 306
  • Dlaczego zachłanność może być dobra? 307
  • Zarządzanie algorytmami zachłannymi 308
  • Problemy NP-zupełne 310
• Dlaczego zachłanność może być pożyteczna? 312
  • Organizacja danych z wykorzystaniem pamięci podręcznej komputera 312
  • Rywalizacja o zasoby 314
  • Kodowanie Huffmana raz jeszcze 316

Rozdział 16: Programowanie dynamiczne 321

• Zasady programowania dynamicznego 322
  • Baza historyczna 322
  • Zmiana problemów na dynamiczne 323
  • Dynamiczne rzutowanie rekurencji 325
  • Wykorzystanie memoizacji 327
• Najlepsze procedury programowania dynamicznego 329
  • Co jest w plecaku? 330
  • Zwiedzanie miast 333
  • Przybliżone wyszukiwanie ciągów znaków 338

Rozdział 17: Korzystanie z algorytmów losowych 341

• Jak działa randomizacja? 342
  • Dlaczego randomizacja jest potrzebna? 343
  • Czym jest prawdopodobieństwo? 344
  • Rozkłady prawdopodobieństwa 345
  • Symulacja użycia metody Monte Carlo 348
• Wykorzystanie losowości w logice algorytmu 350
  • Obliczanie mediany za pomocą algorytmu Quickselect 350
  • Symulacja przy użyciu algorytmu Monte Carlo 353
  • Szybsze sortowanie dzięki algorytmowi Quicksort 355

Rozdział 18: Wyszukiwanie lokalne 357

• Co to jest wyszukiwanie lokalne? 358
  • Znajomość sąsiedztwa 358
• Sztuczki stosowane w wyszukiwaniu lokalnym 361
  • Problem wspinaczki z n-królowymi 362
  • Symulowane wyżarzanie 364
  • Unikanie powtórzeń przy użyciu przeszukiwania tabu 366
• Rozwiązywanie warunku spełnialności układów logicznych 367
  • Rozwiązywanie problemu 2-SAT z wykorzystaniem randomizacji 368
  • Implementacja kodu w Pythonie 369
  • Lepszy punkt wyjścia 371

Rozdział 19: Wykorzystanie programowania liniowego 375

• Stosowanie funkcji liniowych jako narzędzia 376
  • Podstawy matematyczne 377
  • Upraszczanie podczas planowania 379
  • Geometria w metodzie simplex 379
  • Ograniczenia 381
• Programowania liniowe w praktyce 382
  • Konfigurowanie modułu PuLP 383
  • Optymalizacja produkcji i przychodów 383

Rozdział 20: Heurystyka 389

• Klasyfikacja heurystyk 390
  • Cele heurystyki 390
  • Od genetyki do sztucznej inteligencji 391
• Sterowanie robotem za pomocą heurystyki 392
  • Skauting w nieznanym terenie 393
  • Wykorzystanie miar odległości jako heurystyki 394
• Algorytmy wyszukiwania ścieżki 395
  • Tworzenie labiryntu 396
  • Szybkie wyszukiwanie najlepszej trasy 398
  • Poruszanie się heurystyczne z wykorzystaniem algorytmu A* 402

CZĘŚĆ VI: DEKALOGI 407

Rozdział 21: Dziesięć algorytmów, które zmieniły świat 409

• Korzystanie z procedur sortowania 410
• Poszukiwanie informacji z wykorzystaniem procedur wyszukiwania 411
• Zmienianie sytuacji za pomocą liczb losowych 411
• Kompresja danych 412
• Zachowanie poufności danych 412
• Zmiana dziedziny danych 413
• Analiza powiązań w danych 413
• Wykrywanie wzorców w danych 414
• Automatyzacja i automatyczne odpowiedzi 415
• Tworzenie unikatowych identyfikatorów 415

Rozdział 22: Dziesięć problemów algorytmicznych do rozwiązania 417

• Obsługa wyszukiwania tekstu 418
• Rozróżnianie słów 418
• Ustalenie, czy aplikacja się zakończy 419
• Tworzenie i stosowanie funkcji jednokierunkowych 419
• Mnożenie bardzo dużych liczb 420
• Równy podział zasobów 420
• Skrócenie czasu obliczania odległości edycji 421
• Szybkie rozwiązywanie problemów 421
• Gra w grę parzystości 422
• Zrozumienie problemów przestrzennych 422