Алгоритмы для чайников Джон Пол Мюллер

Rok wydania: 2020

Oprawa:broszurowa

Ilość stron: 424

Format: 16,9 x23,5 cm

Algorytmy dla bystrzaków

John Paul Mueller, Luca Massaron

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.

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

John Paul Mueller jest wolnym strzelcem i redaktorem technicznym. Napisał 104 książki i ponad 600 artykułów o różnorodnej tematyce — od sieci po sztuczną inteligencję, od zarządzania bazami danych po inne obszary programowania. Jest konsultantem, przygotowuje różnego rodzaju egzaminy certyfikacyjne. Ma własną witrynę internetową pod adresem http://johnmuellerbooks.com

Luca Massaron specjalizuje się w statystycznych analizach wieloczynnikowych, uczeniu maszynowym, statystyce, eksploracji danych i algorytmice. Pasjonuje się potencjałem, jaki drzemie w nauce o danych.

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