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

Opis

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.

Spis treści

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