Zanurz się w algorytmach. Przygoda dla początkujących odkrywców Pythona - ebook

Bez znajomości algorytmów nie można się nauczyć programowania. Algorytmy są też przydatne w pracy naukowców i inżynierów. Właściwie każdy z nas codziennie z nich korzysta: gotując, wypełniając urzędowe formularze czy przeprowadzając mniej lub bardziej złożone procedury. Co więcej, ludzki organizm również wykonuje skomplikowane działania bez udziału świadomości, ale zgodnie z ukrytymi algorytmami. Łatwo się przekonać, że dzięki umiejętności zastosowania odpowiedniego algorytmu albo nawet zaprojektowania nowego można rozwiązać bardzo złożone problemy.

Ta książka jest praktycznym wprowadzeniem do algorytmów i ich implementacji w Pythonie. Omówiono w niej wiele najciekawszych algorytmów służących do przeszukiwania, sortowania i optymalizacji. Zaprezentowano także te bazujące na... ludzkiej podświadomości. Nie zabrakło dość zaawansowanych tematów, takich jak algorytmy służące do uczenia maszynowego, przetwarzania języka naturalnego i wdrażania technik sztucznej inteligencji. Omówiono też algorytmy znane od starożytności, służące do mnożenia liczb, obliczania największego wspólnego dzielnika czy generowania kwadratów magicznych. Pokazano ponadto, w jaki sposób zaimplementować poszczególne algorytmy w Pythonie, aby uzyskać możliwie najwyższą wydajność kodu.

Dzięki książce dowiesz się, jak:

• generować i wykorzystywać diagramy Woronoja
• wykorzystywać algorytmy podczas pisania chatbota
• stosować algorytm wyżarzania do optymalizacji globalnej
• tworzyć drzewa decyzyjne
• projektować algorytmy przydatne w pisaniu programów
• mierzyć wydajność i prędkość działania algorytmów

Zanurz się w algorytmach: łagodnie i z zaciekawieniem!

O autorze

O korektorze merytorycznym

Podziękowania

Wstęp

• Dla kogo jest ta książka?
• Co znajdziesz w tej książce
• Konfigurowanie środowiska
  • Instalacja Pythona w systemie Windows
  • Instalacja Pythona w systemie macOS
  • Instalacja Pythona w systemie Linux
  • Instalacja bibliotek firm trzecich
• Podsumowanie

1. Rozwiązywanie problemów z użyciem algorytmów

• Podejście analityczne
  • Model Galileusza
  • Metoda rozwiązywania równań z jedną niewiadomą
  • Wewnętrzny fizyk
• Podejście algorytmiczne
  • Myślenie za pomocą karku
  • Zastosowanie algorytmu Chapmana
  • Rozwiązywanie problemów z użyciem algorytmów
• Podsumowanie

2. Algorytmy na przestrzeni wieków

• Mnożenie rosyjskich chłopów
  • Ręczne obliczanie algorytmu mnożenia rosyjskich chłopów
  • Implementacja algorytmu mnożenia rosyjskich chłopów z użyciem Pythona
• Algorytm Euklidesa
  • Ręczne obliczanie algorytmu Euklidesa
  • Implementacja algorytmu Euklidesa z użyciem Pythona
• Japońskie kwadraty magiczne
  • Implementacja kwadratu Lo Shu z użyciem Pythona
  • Implementacja algorytmu Kurushimy z użyciem Pythona
• Podsumowanie

3. Znajdowanie maksimum i minimum

• Ustalanie stóp podatkowych
  • Kroki we właściwym kierunku
  • Zmiana pojedynczych kroków na algorytm
• Zastrzeżenia do metody bazującej na gradiencie
• Problem ekstremum lokalnego
  • Edukacja i zarobki z całego życia
  • Wspinanie się na wzgórza edukacji - właściwe podejście
• Od znajdowania maksimum do znajdowania minimum
• Optymalizacja w ujęciu ogólnym
• Kiedy nie używać algorytmów
• Podsumowanie

4. Sortowanie i wyszukiwanie

• Sortowanie przez wstawianie
  • Sortowanie przez wstawianie - wstawianie
  • Sortowanie przez wstawianie - sortowanie
• Mierzenie wydajności algorytmu
  • Dlaczego dbamy o wydajność?
  • Precyzyjny pomiar czasu
  • Zliczanie kroków
  • Porównywanie z dobrze znanymi funkcjami
  • Jeszcze więcej precyzji
  • Notacja dużego O
• Sortowanie przez scalanie
  • Scalanie
  • Od scalania do sortowania
• Sortowanie przez spanie
• Od sortowania do wyszukiwania
  • Wyszukiwanie binarne
  • Zastosowania wyszukiwania binarnego
• Podsumowanie

5. Czysta matematyka

• Ułamki łańcuchowe
  • Jak wyrazić liczbę fi
  • Więcej o ułamkach łańcuchowych
  • Algorytm generowania ułamka łańcuchowego
  • Od ułamków dziesiętnych do ułamków łańcuchowych
  • Od ułamków do pierwiastków
• Pierwiastki kwadratowe
  • Metoda babilońska
  • Pierwiastki kwadratowe w Pythonie
• Generatory liczb losowych
  • Umożliwienie losowości
  • Liniowe generatory kongruentne
  • Ocena generatora liczb pseudolosowych
  • Testy Diehard do oceny losowości w sekwencji wyjściowej generatora
  • Rejestr przesuwający z liniowym sprzężeniem zwrotnym
• Podsumowanie

6. Zaawansowana optymalizacja

• Życie komiwojażera
  • Sformułowanie problemu
  • Mózg kontra mięśnie
  • Algorytm najbliższego sąsiada
  • Implementacja algorytmu najbliższego sąsiada
  • Poszukiwanie dalszych ulepszeń
  • Algorytmy zachłanne
  • Funkcja temperatury
• Symulowane wyżarzanie
  • Strojenie naszego algorytmu
  • Unikanie zbyt dużego pogarszania
  • Umożliwienie powrotu do wcześniejszego rozwiązania
  • Testowanie wydajności
• Podsumowanie

7. Geometria

• Problem dyrektora poczty
• Trójkąty
  • Podstawy
  • Środek trójkąta
  • Zwiększenie naszych możliwości rysowania
• Triangulacja Delone
  • Inkrementacyjne generowanie triangulacji Delone
  • Implementacja triangulacji Delone
• Od Delone do Woronoja
• Podsumowanie

8. Analiza języka

• Dlaczego algorytmy przetwarzające język są skomplikowane
• Dodawanie spacji
  • Definiowanie listy słów i wyszukiwanie słów
  • Radzenie sobie ze słowami złożonymi
  • Poszukiwanie potencjalnych słów pomiędzy następującymi po sobie spacjami
  • Wykorzystanie korpusu do sprawdzania poprawności słów
  • Odszukiwanie pierwszej i drugiej części potencjalnego słowa
• Dokańczanie fraz
  • Tokenizacja i tworzenie n-gramów
  • Nasza strategia
  • Znajdowanie potencjalnych n+1-gramów
  • Wybieranie frazy na podstawie częstości występowania
• Podsumowanie

9. Uczenie maszynowe

• Drzewa decyzyjne
• Tworzenie drzewa decyzyjnego
  • Pobranie zbioru danych
  • Przeglądanie zbioru danych
  • Dzielenie zbioru danych
  • Sprytne dzielenie
  • Wybieranie zmiennych do dzielenia
  • Zwiększanie głębokości
• Ocena jakości drzewa decyzyjnego
  • Problem nadmiernego dopasowania
  • Ulepszenia i udoskonalenia
• Losowy las decyzyjny
• Podsumowanie

10. Sztuczna inteligencja

• Gra w kreski
• Rysowanie planszy
• Zapis rozgrywki
• Podliczanie punktów
• Drzewa gry i sposób na wygraną
  • Tworzenie drzewa gry
  • Wygrywanie gry
  • Dodawanie ulepszeń
• Podsumowanie

11. Ruszamy w dal

• Odkrywanie dalszych możliwości algorytmów
• Tworzenie chatbota
  • Zamiana słów na wektory liczbowe
  • Podobieństwo wektorów
• Zwiększanie wydajności i prędkości działania
• Algorytmy dla ambitnych
• Rozwiązywanie największych tajemnic

Skorowidz