Helion


Szczegóły ebooka

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

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


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