40 ALGORYTMÓW KTÓRE POWINIEN ZNAĆ KAŻDY PROGRAMISTA

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