Matematyka dyskretna dla praktyków. Algorytmy i uczenie maszynowe w Pythonie - ebook

Mimo że osiągnięcia matematyczne stały się podwalinami algorytmiki, wielu inżynierów nie w pełni rozumie reguły matematyki dyskretnej. Nawet jeśli nie stanowi to szczególnego problemu w codziennej pracy, w końcu okazuje się, że matematyka dyskretna jest niezbędna do osiągnięcia prawdziwej biegłości w operowaniu algorytmami i w pracy na danych. Co więcej, znajomość tej dziedziny bardzo ułatwia rozwiązywanie problemów z zakresu uczenia maszynowego. W ten sposób praktyczna biegłość w matematyce zauważalnie poprawia wyniki pracy inżynierów.

Ta książka jest kompleksowym wprowadzeniem do matematyki dyskretnej, przydatnym dla każdego, kto chce pogłębić i ugruntować swoje umiejętności informatyczne. W zrozumiały sposób przedstawiono tu metody matematyki dyskretnej i ich zastosowanie w algorytmach i analizie danych, włączając w to techniki uczenia maszynowego. Zaprezentowano również zasady oceny złożoności obliczeniowej algorytmów i używania wyników tej oceny do zarządzania pracą procesora. Omówiono także sposoby przechowywania struktur grafowych, ich przeszukiwania i znajdywania ścieżek między wierzchołkami. Pokazano też, jak wykorzystać przedstawione informacje podczas posługiwania się bibliotekami Pythona, takimi jak scikit-learn i NumPy.

W książce między innymi:

• terminologia i metody matematyki dyskretnej
• zastosowanie metod matematyki dyskretnej w algorytmach i analizie danych
• algebra Boole'a i kombinatoryka w podstawowych strukturach algorytmów
• rozwiązywanie problemów z dziedziny teorii grafów
• zadania związane z uczeniem maszynowym a matematyka dyskretna

Matematyka dyskretna - poznaj, zrozum, zastosuj!

• O autorach
• O recenzencie
• Wprowadzenie
  • Dla kogo jest ta książka?
  • O czym jest ta książka?
    • Część I. Podstawowe pojęcia z obszaru matematyki dyskretnej
    • Część II. Zastosowania matematyki dyskretnej w analizie danych i informatyce
    • Część III. Praktyczne zastosowania matematyki dyskretnej
  • Co zrobić, aby jak najlepiej wykorzystać tę książkę
  • Kody źródłowe
  • Konwencje typograficzne przyjęte w tej książce
• I. Podstawowe pojęcia z obszaru matematyki dyskretnej
• 1. Podstawowe pojęcia, notacja, teoria mnogości, relacje i funkcje
  • Czym jest matematyka dyskretna?
  • Podstawowa teoria mnogości
    • Definicja zbiory i ich notacja
    • Definicja elementy zbiorów
    • Definicja zbiór pusty
    • Przykład kilka przykładowych zbiorów
    • Definicja podzbiory i nadzbiory
    • Definicja notacja konstrukcji zbiorów
    • Przykład użycie notacji konstrukcji zbiorów
    • Definicja podstawowe operacje na zbiorach
    • Definicja zbiory rozłączne
    • Przykład liczby parzyste i nieparzyste
    • Twierdzenie prawa De Morgana
      • Dowód
    • Przykład prawo De Morgana
    • Definicja moc zbioru
    • Przykład moce zbiorów
  • Funkcje i relacje
    • Definicja relacje, dziedziny i przeciwdziedziny
    • Definicja funkcje
    • Przykłady relacje kontra funkcje
    • Przykład funkcje w algebrze elementarnej
    • Przykład funkcje w Pythonie i funkcje matematyczne
  • Podsumowanie
• 2. Logika formalna i dowody matematyczne
  • Logika formalna i dowodzenie za pomocą tablic prawdy
    • Podstawy terminologii stosowanej w logice formalnej
    • Przykład niepoprawny argument
    • Przykład wszystkie pingwiny mieszkają w RPA!
    • Podstawowe idee logiki formalnej
    • Tablice prawdy
    • Przykład implikacja odwrotna
    • Przykład prawo przechodniości implikacji
    • Przykład prawa De Morgana
    • Przykład implikacja przeciwstawna
  • Dowody wprost
    • Przykład iloczyn parzystych i nieparzystych liczb całkowitych
    • Przykład pierwiastki liczb parzystych
    • Skrócenie dowodu za pomocą implikacji przeciwstawnej
  • Dowody nie wprost
    • Przykład czy istnieje najmniejsza dodatnia liczba wymierna?
    • Przykład dowód, że 2 jest liczbą niewymierną
    • Przykład ile jest liczb pierwszych?
  • Dowodzenie przez indukcję matematyczną
    • Przykład suma 1+2+...+n
    • Przykład kształty wypełniające przestrzeń
    • Przykład wzrost wykładniczy a wzrost w tempie silni
  • Podsumowanie
• 3. Obliczenia w systemach o podstawie n
  • Zrozumieć liczby o podstawie n
    • Przykład liczby dziesiętne
    • Definicja liczby o podstawie n
  • Konwersje między różnymi podstawami
    • Konwersja liczb o podstawie n na liczby dziesiętne
    • Przykład wartość dziesiętna liczby o podstawie 6
    • Konwersja z zapisu dziesiętnego na system o podstawie n
    • Przykład konwersja liczby dziesiętnej na liczbę binarną (podstawa 2)
    • Przykład konwersje z systemu dziesiętnego na binarny i szesnastkowy w Pythonie
  • Liczby binarne i ich zastosowania
    • Algebra Boolea
      • Operator AND
      • Operator OR
      • Operator NOT
    • Przykład użytkownicy Netfliksa
  • Liczby szesnastkowe i ich zastosowanie
    • Przykład położenie obiektów w pamięci komputera
    • Przykład wyświetlanie komunikatów o błędach
    • Przykład adresy MAC
    • Przykład kolory w sieci
  • Podsumowanie
• 4. Kombinatoryka z użyciem SciPy
  • Podstawy zliczania
    • Definicja iloczyn kartezjański
    • Twierdzenie moc iloczynów kartezjańskich zbiorów skończonych
    • Definicja iloczyn kartezjański n zbiorów
    • Twierdzenie reguła mnożenia
    • Przykład bajty
    • Przykład kolory w komputerze
  • Permutacje i kombinacje obiektów
    • Definicja permutacja
    • Przykład permutacje prostego zbioru
    • Twierdzenie permutacje zbioru
    • Przykład playlista
    • Wzrost w tempie silni
    • Twierdzenie wariacja bez powtórzeń
    • Definicja kombinacja
    • Przykład kombinacje kontra permutacje prostego zbioru
    • Twierdzenie kombinacje ze zbioru
    • Współczynniki dwumianowe
    • Przykład tworzenie zespołu
    • Przykład kombinacje kul
  • Alokacja pamięci
    • Przykład wstępne przydzielanie pamięci
  • Skuteczność algorytmów siłowych
    • Przykład szyfr Cezara
    • Przykład problem komiwojażera
  • Podsumowanie
• 5. Elementy prawdopodobieństwa dyskretnego
  • Definicja doświadczenie losowe
  • Definicje zdarzenia elementarne, zdarzenia losowe, przestrzenie prób
  • Przykład rzut monetą
  • Przykład rzut wieloma monetami
  • Definicja miara probabilistyczna
  • Twierdzenie podstawowe własności prawdopodobieństwa
    • Dowód
  • Przykład sport
  • Twierdzenie monotoniczność
    • Dowód
  • Twierdzenie zasada włączeń i wyłączeń
    • Dowód
  • Definicja rozkład jednostajny
  • Twierdzenie obliczanie prawdopodobieństwa
    • Dowód
  • Przykład rzut wieloma monetami
  • Definicja zdarzenia niezależne
  • Przykład rzucanie wieloma monetami
  • Prawdopodobieństwo warunkowe i twierdzenie Bayesa
    • Definicja prawdopodobieństwo warunkowe
    • Przykład temperatury i opady
    • Twierdzenie reguły mnożenia
      • Dowód
    • Twierdzenie twierdzenie o prawdopodobieństwie całkowitym
      • Dowód
    • Twierdzenie twierdzenie Bayesa
      • Dowód
  • Bayesowski filtr antyspamowy
  • Zmienne losowe, średnie i wariancja
    • Definicja zmienna losowa
    • Przykład błędy przesyłania danych
    • Przykład empiryczna zmienna losowa
    • Definicja wartość oczekiwana
    • Przykład empiryczna zmienna losowa
    • Definicja wariancja i odchylenie standardowe
    • Twierdzenie obliczanie wariancji w praktyce
      • Dowód
    • Przykład empiryczna zmienna losowa
  • Google PageRank (część I)
  • Podsumowanie
• II. Zastosowania matematyki dyskretnej w analizie danych i informatyce
• 6. Algorytmy algebry liniowej
  • Zrozumieć układy równań liniowych
    • Definicja równanie liniowe dwóch zmiennych
    • Definicja kartezjański układ współrzędnych
    • Przykład równanie liniowe
    • Definicja układ dwóch równań liniowych dwóch zmiennych
    • Przykład układ oznaczony
    • Przykład układ sprzeczny
    • Przykład układ nieoznaczony
    • Definicja układy równań liniowych i ich rozwiązania
    • Definicja układy oznaczone, sprzeczne i nieoznaczone
  • Macierze i macierzowe reprezentacje układów równań liniowych
    • Definicja macierze i wektory
    • Definicja dodawanie i odejmowanie macierzy
    • Definicja mnożenie przez skalar
    • Definicja transpozycja macierzy
    • Definicja iloczyn skalarny wektorów
    • Definicja mnożenie macierzy
    • Przykład ręczne mnożenie macierzy i mnożenie macierzy w NumPy
  • Rozwiązywanie małych układów równań liniowych za pomocą metody eliminacji Gaussa
    • Definicja współczynnik wiodący
    • Definicja zredukowana macierz schodkowa
    • Przykład układ oznaczony z macierzą schodkową
    • Przykład układ sprzeczny z macierzą schodkową
    • Przykład układ nieoznaczony z macierzą schodkową
    • Algorytm eliminacja Gaussa
    • Przykład układ 3 równań liniowych z 3 niewiadomymi
  • Rozwiązywanie dużych układów równań liniowych za pomocą NumPy
    • Przykład układ 3 równań z 3 niewiadomymi (NumPy)
    • Przykład sprzeczne i nieoznaczone układy równań w NumPy
    • Przykład układ 10 równań z 10 niewiadomymi (NumPy)
  • Podsumowanie
• 7. Złożoność algorytmów
  • Złożoność obliczeniowa algorytmów
  • Notacja dużego O
    • Kiedy stałe mają znaczenie?
  • Złożoność algorytmów zawierających podstawowe instrukcje sterujące
    • Przepływ sekwencyjny
    • Przepływ warunkowy
    • Pętla
  • Złożoność popularnych algorytmów wyszukiwania
    • Algorytm wyszukiwania liniowego
      • Czym jest funkcja w Pythonie?
    • Algorytm wyszukiwania binarnego
  • Popularne klasy złożoności obliczeniowej
  • Podsumowanie
  • Bibliografia
• 8. Przechowywanie i wyodrębnianie cech z grafów, drzew i sieci
  • Zrozumieć grafy, drzewa i sieci
    • Definicja graf
    • Definicja stopień wierzchołka
      • Przykład stopnie wierzchołków
      • Twierdzenie suma stopni wierzchołków
    • Definicja ścieżki
    • Definicja cykle
    • Definicja drzewa lub grafy acykliczne
    • Definicja sieci
    • Definicja grafy skierowane
    • Definicja sieci skierowane
      • Przykład sieć skierowana
    • Definicja wierzchołki sąsiednie
    • Definicja grafy i składowe spójne
  • Zastosowania grafów, drzew i sieci
  • Przechowywanie grafów i sieci
    • Definicja lista sąsiedztwa
    • Definicja macierz sąsiedztwa
      • Przykład lista sąsiedztwa i macierz sąsiedztwa
      • Przykład macierz sąsiedztwa niespójnego grafu
    • Definicja macierz sąsiedztwa dla grafu skierowanego
      • Przykład macierz sąsiedztwa dla grafu skierowanego
      • Przykład przechowywanie macierzy sąsiedztwa w Pythonie
    • Wydajne przechowywanie danych sąsiedztwa
    • Definicja macierz wag sieci
      • Przykład macierz wag sieci
    • Definicja macierz wag sieci skierowanej
      • Przykład macierz wag sieci skierowanej
      • Przykład przechowywanie macierzy wag w Pythonie
  • Wyodrębnianie cech z grafów
    • Stopnie wierzchołków w grafie
    • Liczba ścieżek o określonej długości między wierzchołkami
    • Twierdzenie potęgi macierzy sąsiedztwa
    • Potęgi macierzy w Pythonie
    • Twierdzenie najkrótsza (pod względem liczby krawędzi) ścieżka pomiędzy vi i vj
      • Przykład ścieżki między wierzchołkami grafu z rysunku 8.8
  • Podsumowanie
• 9. Przeszukiwanie struktur danych i znajdowanie najkrótszych ścieżek
  • Przeszukiwanie struktur grafowych i drzew
  • Algorytm przeszukiwania w głąb (DFS)
  • Implementacja algorytmu przeszukiwania w głąb w Pythonie
  • Problem najkrótszej ścieżki i jego warianty
    • Najkrótsze ścieżki w sieciach
    • Inne zastosowania najkrótszych ścieżek
    • Definicja problemu najkrótszej ścieżki
    • Sprawdzenie, czy istnieje rozwiązanie
  • Znajdowanie najkrótszych ścieżek metodą siłową
  • Algorytm Dijkstry znajdowania najkrótszych ścieżek
    • Algorytm Dijkstry
    • Algorytm Dijkstry zastosowany do małego problemu
  • Implementacja algorytmu Dijkstry w Pythonie
    • Przykład najkrótsze ścieżki
    • Przykład sieć bez połączenia
  • Podsumowanie
• III. Praktyczne zastosowania matematyki dyskretnej
• 10. Analiza regresji za pomocą NumPy i scikit-learn
  • Zbiór danych
  • Linie najlepszego dopasowania i metoda najmniejszych kwadratów
    • Zmienne
    • Zależność liniowa
    • Regresja
  • Linia najlepszego dopasowania
    • Metoda najmniejszych kwadratów i suma kwadratów błędów
  • Dopasowywanie prostej metodą najmniejszych kwadratów w NumPy
  • Dopasowywanie krzywych metodą najmniejszych kwadratów z użyciem NumPy i SciPy
  • Dopasowanie płaszczyzn metodą najmniejszych kwadratów z użyciem NumPy i SciPy
  • Podsumowanie
• 11. Wyszukiwanie w sieci za pomocą algorytmu PageRank
  • Rozwój wyszukiwarek na przestrzeni lat
  • Google PageRank (część II)
  • Implementacja algorytmu PageRank w Pythonie
  • Zastosowanie algorytmu na danych rzeczywistych
  • Podsumowanie
• 12. Analiza głównych składowych za pomocą scikit-learn
  • Wartości i wektory własne, bazy ortogonalne
  • Redukcja wymiarowości za pomocą analizy głównych składowych
  • Implementacja metody PCA z scikit-learn
  • Zastosowanie metody PCA na rzeczywistych danych
  • Podsumowanie