40 algorytmów, które powinien znać

40 algorytmów, które powinien znać - Opis

Wiedza o algorytmach jest niezbędna każdemu, kto rozwiązuje problemy programistyczne. Algorytmy są również ważne w teorii i praktyce obliczeń. Każdy programista powinien znać możliwie szeroki ich zakres. Powinien też umieć z nich korzystać przy rozwiązywaniu rzeczywistych problemów, w tym przy projektowaniu algorytmów, ich modyfikacji i implementacji. Niezależnie od tego, czy zajmujesz się sztuczną inteligencją, zabezpieczaniem systemów informatycznych lub inżynierią danych, musisz dobrze zrozumieć, czym właściwie są i jak działają algorytmy.

Ta książka jest praktycznym wprowadzeniem do algorytmów i ich zastosowania. Znalazły się w niej podstawowe informacje i pojęcia dotyczące algorytmów, ich działania, a także ograniczeń, jakim podlegają. Opisano też techniki ich projektowania z uwzględnieniem wymagań dotyczących struktur danych. Zaprezentowano klasyczne algorytmy sortowania i wyszukiwania, algorytmy grafowe, jak również wiele zagadnień związanych ze sztuczną inteligencją: algorytmy uczenia maszynowego, sieci neuronowych i przetwarzania języka naturalnego. Ważną częścią publikacji są rozdziały poświęcone przetwarzaniu danych i kryptografii oraz algorytmom powiązanym z tymi zagadnieniami. Wartościowym podsumowaniem prezentowanych treści jest omówienie technik pracy z problemami NP-trudnymi.

W książce między innymi:

struktury danych i algorytmy w bibliotekach Pythona
algorytm grafowy służący do wykrywania oszustw w procesie analizy sieciowej
przewidywanie pogody przy użyciu algorytmów uczenia nadzorowanego
rozpoznawanie obrazu za (...) więcej pomocą syjamskich sieci neuronowych
tworzenie systemu rekomendacji filmów
szyfrowanie symetryczne i asymetryczne podczas wdrażania modelu uczenia maszynowego

Oto algorytm: poznaj, zaimplementuj, zastosuj!
Spis treści:

O autorze 11

O recenzencie 13

Przedmowa 15

WSTĘP I PODSTAWOWE ALGORYTMY 21

Rozdział 1. Wprowadzenie do algorytmów 23

Co to jest algorytm? 24

Fazy algorytmu 24

Określenie logiki algorytmu 26

Zrozumienie pseudokodu 26
Korzystanie z fragmentów kodu (snippetów) 28
Stworzenie planu wykonania 28

Wprowadzenie do pakietów w Pythonie 29

Pakiety w Pythonie 30
Programowanie w Pythonie z Jupyter Notebook 31

Techniki projektowania algorytmów 31

Wymiar danych 33
Wymiar obliczeniowy 33

Analiza efektywności 35

Analiza pamięciowej złożoności obliczeniowej 35
Czasowa złożoność obliczeniowa 36
Szacowanie efektywności 37
Wybór algorytmu 37
Notacja dużego O 38

Walidacja algorytmu 41

Algorytmy dokładne, aproksymacyjne i randomizowane 41
Możliwość wyjaśnienia 43

Podsumowanie 43

Rozdział 2. Struktury danych w algorytmach 45

Struktury danych w Pythonie 46

Lista 46
Krotka 50
Słownik 51
Zbiór 52
Ramka danych 54
Macierz 56

Abstrakcyjne typy danych 57

Wektor 57
Stos 58
Kolejka 60
Kiedy używać stosów i kolejek? 62
Drzewo 62

Podsumowanie 65

Rozdział 3. Algorytmy sortowania wyszukiwania 67

Wprowadzenie do algorytmów sortowania 68

Zamiana wartości zmiennych w Pythonie 68
Sortowanie bąbelkowe 68
Sortowanie przez wstawianie 71
Sortowanie przez scalanie 72
Sortowanie Shella 74
Sortowanie przez wymianę 76

Wprowadzenie do algorytmów wyszukiwania 78

Wyszukiwanie liniowe 78
Wyszukiwanie binarne 79
Wyszukiwanie interpolacyjne 79

Praktyczne przykłady 80
Podsumowanie 83

Rozdział 4. Projektowanie algorytmów 85

Wprowadzenie do projektowania algorytmów 86

Kwestia 1: Czy algorytm zwraca rezultat, jakiego oczekujemy? 87
Kwestia 2: Czy robi to w optymalny sposób? 87
Kwestia 3: Jak efektywny będzie ten algorytm zastosowany do większych zbiorów danych? 90

Strategie algorytmiczne 91

Strategia "dziel i rządź" 91
Strategia programowania dynamicznego 93
Strategia algorytmu zachłannego 93

Praktyczny przykład - rozwiązanie problemu komiwojażera 94

Metoda siłowa 95
Zastosowanie algorytmu zachłannego 98

Algorytm PageRank 99

Definicja problemu 100
Implementacja algorytmu PageRank 100

Programowanie liniowe 102

Definicja problemu w programowaniu liniowym 102

Praktyczny przykład - planowanie przepustowości za pomocą programowania liniowego 103
Podsumowanie 105

Rozdział 5. Algorytmy grafowe 107

Reprezentacja grafów 108

Rodzaje grafów 109
Specjalne rodzaje krawędzi 111
Sieci egocentryczne 112
Analiza sieciowa 112

Wprowadzenie do teorii analizy sieciowej 113

Najkrótsza ścieżka 113
Określanie sąsiedztwa 114
Wskaźnik centralności 115
Obliczanie wskaźników centralności w Pythonie 117

Trawersowanie grafu 119

Wyszukiwanie wszerz 119
Wyszukiwanie w głąb 121

Studium przypadku - analiza oszustw 125

Prosta analiza pod kątem oszustwa 127
Podejście strażnicy 128

Podsumowanie 130

ALGORYTMY UCZENIA MASZYNOWEGO 131

Rozdział 6. Algorytmy nienadzorowanego uczenia maszynowego 133

Wprowadzenie do nienadzorowanego uczenia maszynowego 134

Uczenie nienadzorowane w cyklu życia eksploracji danych 134
Trendy badawcze w zakresie uczenia nienadzorowanego 137
Praktyczne przykłady 137

Algorytmy klasteryzacji 138

Wyliczanie podobieństw 139
Grupowanie hierarchiczne 145
Ocena klastrów 147
Zastosowania klasteryzacji 148

Redukcja wymiarów 148

Analiza głównych składowych 149
Ograniczenia analizy głównych składowych 151

Reguły asocjacyjne 151

Przykłady użycia 151
Analiza koszykowa 152
Reguły asocjacyjne 153
Wskaźniki reguł 154
Algorytmy analizy asocjacyjnej 156

Praktyczny przykład - grupowanie podobnych tweetów 160

Modelowanie tematów 161
Klasteryzacja 162

Algorytmy wykrywania odchyleń 162

Wykorzystanie klastrów 162
Wykorzystanie wykrywania odchyleń opartego na gęstości 162
Wykorzystanie maszyny wektorów nośnych 163

Podsumowanie 163

Rozdział 7. Tradycyjne algorytmy uczenia nadzorowanego 165

Nadzorowane uczenie maszynowe 166

Żargon nadzorowanego uczenia maszynowego 166
Warunki konieczne 168
Rozróżnienie między klasyfikatorami a regresorami 169

Algorytmy klasyfikujące 169

Wyzwanie dla klasyfikatorów 170
Inżynieria cech w przetwarzaniu potokowym 171
Ocena klasyfikatorów 173
Określenie faz klasyfikacji 177
Algorytm drzewa decyzyjnego 178
Metody zespolone 181
Regresja logistyczna 185
Maszyna wektorów nośnych 187
Naiwny klasyfikator bayesowski 189
Zwycięzcą wśród algorytmów klasyfikacji jest... 192

Algorytmy regresji 193

Wyzwanie dla regresji 193
Regresja liniowa 195
Algorytm drzewa regresji 199
Regresyjny algorytm wzmocnienia gradientowego 199
Zwycięzcą wśród algorytmów regresji jest... 200

Praktyczny przykład, jak przewidywać pogodę 201
Podsumowanie 203

Rozdział 8. Algorytmy sieci neuronowych 205

Wprowadzenie do sieci neuronowych 206
Ewolucja sieci neuronowych 207
Trenowanie sieci neuronowej 209

Anatomia sieci neuronowej 209
Definicja gradientu prostego 210
Funkcje aktywacji 212

Narzędzia i modele 217

Keras 217
TensorFlow 220
Rodzaje sieci neuronowych 222

Uczenie transferowe 224
Studium przypadku - użycie uczenia głębokiego do wykrywania oszustw 225

Metodologia 225

Podsumowanie 228

Rozdział 9. Algorytmy przetwarzania języka naturalnego 231

Wprowadzenie do przetwarzania języka naturalnego 232

Terminologia przetwarzania języka naturalnego 232
NLTK 234

Model bag-of-words 234
Wektorowe przedstawienie słów 237

Otoczenie słowa 237
Właściwości wektorowego przedstawienia słów 237

Użycie rekurencyjnych sieci neuronowych do przetwarzania języka naturalnego 238
Wykorzystanie przetwarzania języka naturalnego do analizy sentymentu 239
Studium przypadku - analiza sentymentu w recenzjach filmowych 241
Podsumowanie 243

Rozdział 10. Silniki poleceń 245

Wprowadzenie do silników poleceń 245
Rodzaje silników poleceń 246

Silniki poleceń oparte na treści 246
Silniki poleceń oparte na filtrowaniu kooperacyjnym 248
Hybrydowe silniki poleceń 250

Ograniczenia systemów poleceń 252

Zimny start 252
Wymagania dotyczące metadanych 252
Problem rzadkości danych 253
Tendencyjność ze względu na wpływ społeczny 253
Ograniczone dane 253

Obszary praktycznych zastosowań 253
Przykład praktyczny - stworzenie silnika poleceń 254
Podsumowanie 256

ZAGADNIENIA ZAAWANSOWANE 257

Rozdział 11. Algorytmy danych 259

Wprowadzenie do algorytmów danych 259

Klasyfikacja danych 260

Algorytmy przechowywania danych 261

Strategie przechowywania danych 261

Algorytmy strumieniowania danych 263

Zastosowania strumieniowania 264

Algorytmy kompresji danych 264

Algorytmy kompresji bezstratnej 264

Przykład praktyczny - analiza sentymentu na Twitterze 266
Podsumowanie 269

Rozdział 12. Kryptografia 271

Wprowadzenie do kryptografii 271

Waga najsłabszego ogniwa 272
Terminologia 272
Wymagania bezpieczeństwa 273
Podstawy projektowania szyfrów 275

Rodzaje technik kryptograficznych 278

Kryptograficzna funkcja skrótu 278
Szyfrowanie symetryczne 281
Szyfrowanie asymetryczne 283

Przykład - kwestie bezpieczeństwa we wdrażaniu modelu uczenia maszynowego 286

Atak man-in-the-middle 287
Obrona przed techniką masquerading 289
Szyfrowanie danych i modelu 289

Podsumowanie 291

Rozdział 13. Algorytmy przetwarzania danych w dużej skali 293

Wprowadzenie do algorytmów przetwarzania danych w dużej skali 294

Definicja dobrze zaprojektowanego algorytmu przetwarzania danych w dużej skali 294
Terminologia 294

Projektowanie algorytmów równoległych 295

Prawo Amdahla 295
Szczegółowość podprocesów 298
Równoważenie obciążenia 298
Przetwarzanie lokalne 299
Procesy współbieżne w Pythonie 299

Tworzenie strategii przetwarzania na puli zasobów 299

Architektura CUDA 300
Obliczenia w klastrze 303
Strategia hybrydowa 305

Podsumowanie 305

Rozdział 14. Uwagi praktyczne 307

Wprowadzenie do uwag praktycznych 308

Smutna historia bota sztucznej inteligencji na Twitterze 308

Transparentność algorytmu 309

Algorytmy uczenia maszynowego i transparentność 309

Etyka i algorytmy 313

Problemy z algorytmami uczącymi się 313
Znaczenie kwestii etycznych 313

Ograniczanie stronniczości modeli 315
Problemy NP-trudne 316

Uproszczenie problemu 316
Dopasowanie dobrze znanego rozwiązania podobnego problemu 316
Metoda probabilistyczna 317

Kiedy używać algorytmów 317

Praktyczny przykład - teoria czarnego łabędzia 318

Podsumowanie 320

O autorze: Imran Ahmad jest certyfikowanym instruktorem Google z wieloletnim doświadczeniem. Wykłada Pythona, uczenie maszynowe i głębokie, algorytmikę oraz zagadnienia big data. Przez ostatnie lata pracował w rządowym laboratorium Kanady nad projektem z zakresu uczenia maszynowego. Obecnie zajmuje się algorytmami używającymi GPU do optymalnego trenowania złożonych modeli uczenia maszynowego. mniej