Algorytmy dla bystrzaków [Mueller John Paul, Massaron Luca] Bielsko-Biała

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