Szczegóły ebooka

Algorytmy dla bystrzaków

Algorytmy dla bystrzaków

John Paul Mueller, Luca Massaron

Ebook

Zestaw algorytmy z ich zastosowaniami

Zdobądź umiejętności posługiwania się algorytmami

Naucz się wykorzystywać Pythona do testowania algorytmów

Myśl za pomocą algorytmów

Ten jasny i przystępny przewodnik pokazuje, w jaki sposób algorytmy wpływają na nasze codzienne życie - od interakcji online po osobistą komunikację. Są również niezwykle ważne, jeśli chodzi o podejmowanie różnego rodzaju decyzji. Jeśli chcesz wiedzieć, jak korzystać z procedur rozwiązywania problemów w prawdziwym świecie, książka Algorytmy dla bystrzaków zagwarantuje Ci doskonałe wprowadzenie do tej fascynującej, wszechobecnej dziedziny.

W książce:

  • Operacje na danych
  • Projektowanie algorytmów
  • Podstawy teorii grafów
  • Zarządzanie danymi o dużej objętości
  • Upraszczanie złożonych algorytmów

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
  • Tytuł: Algorytmy dla bystrzaków
  • Autor: John Paul Mueller, Luca Massaron
  • Tytuł oryginału: Algorithms For Dummies
  • Tłumaczenie: Radosław Meryk
  • ISBN: 978-83-283-6077-8, 9788328360778
  • Data wydania: 2020-01-31
  • Format: Ebook
  • Identyfikator pozycji: algoby
  • Wydawca: Dla bystrzaków