Algorytmy dla bystrzaków - ebook
Algorytmy dla bystrzaków - 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
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
Kategoria: | Programowanie |
Zabezpieczenie: |
Watermark
|
ISBN: | 978-83-283-6077-8 |
Rozmiar pliku: | 4,4 MB |