Matematyka_dyskretna_dla_informatykow_madyin.pdf

(924 KB) Pobierz
•
Kup książkę
•
Poleć książkę
•
Oceń książkę
•
Księgarnia internetowa
•
Lubię to! » Nasza społeczność
Spis treści
Oznaczenia
Wstęp
1
3
I. Podstawy
1. Indukcja i rekurencja
1.1. Zasada indukcji matematycznej . . . . . . . . . . . . .
7
9
9
1.2. Zbiory częściowo uporządkowane . . . . . . . . . . . 11
1.3. Rekurencja . . . . . . . . . . . . . . . . . . . . . . . . 15
1.4. Zadania . . . . . . . . . . . . . . . . . . . . . . . . . 23
2. Rozmieszczenia i permutacje
2.1.
2.2.
2.3.
2.4.
27
Funkcje i rozmieszczenia . . . . . . . . . . . . . . . . 27
Permutacje . . . . . . . . . . . . . . . . . . . . . . . . 30
Liczby Stirlinga pierwszego rodzaju . . . . . . . . . . 38
Zadania . . . . . . . . . . . . . . . . . . . . . . . . . 41
44
3. Kombinacje
3.1.
3.2.
3.3.
3.4.
Współczynnik dwumianowy . . . . . . . . . . . . . . 44
Generowanie podzbiorów . . . . . . . . . . . . . . . . 48
Zbiory z powtórzeniami . . . . . . . . . . . . . . . . . 50
Zadania . . . . . . . . . . . . . . . . . . . . . . . . . 52
Kup książkę
Poleć książkę
iv
4. Podziały
Spis treści
54
4.1. Podziały zbioru . . . . . . . . . . . . . . . . . . . . . 54
4.2. Zasada szufladkowa Dirichleta . . . . . . . . . . . . . 55
4.3. Zasada włączania-wyłączania . . . . . . . . . . . . . . 58
4.4. Liczby Stirlinga drugiego rodzaju . . . . . . . . . . . . 63
4.5. Podziały liczb . . . . . . . . . . . . . . . . . . . . . . 67
4.6. Zadania . . . . . . . . . . . . . . . . . . . . . . . . . 69
5. Funkcje tworzące
72
5.1. Szeregi formalne . . . . . . . . . . . . . . . . . . . . 72
5.2. Rozwiązywanie rekurencji . . . . . . . . . . . . . . . 75
5.3. Zastosowania funkcji tworzących . . . . . . . . . . . . 77
5.4. Sploty . . . . . . . . . . . . . . . . . . . . . . . . . . 79
5.5. Zadania . . . . . . . . . . . . . . . . . . . . . . . . . 82
II. Grafy
6. Elementy teorii grafów
83
85
6.1. Podstawowe pojęcia . . . . . . . . . . . . . . . . . . . 85
6.2. Macierze grafów . . . . . . . . . . . . . . . . . . . . . 91
6.3. Izomorfizm, podstawowe własności i typy grafów . . . 102
6.4. Kolorowanie i wielomiany . . . . . . . . . . . . . . . 111
6.5. Zadania . . . . . . . . . . . . . . . . . . . . . . . . . 115
7. Cykle, drzewa, pokrycia
120
7.1. Grafy Eulera i Hamiltona, turnieje . . . . . . . . . . . 120
7.2. Spójność . . . . . . . . . . . . . . . . . . . . . . . . . 127
7.3. Drzewa . . . . . . . . . . . . . . . . . . . . . . . . . 129
7.4. Skojarzenia . . . . . . . . . . . . . . . . . . . . . . . 140
7.5. Zadania . . . . . . . . . . . . . . . . . . . . . . . . . 144
Kup książkę
Poleć książkę
Spis treści
8. Wybrane algorytmy grafowe
v
148
8.1. Algorytmy przeszukiwania . . . . . . . . . . . . . . . 148
8.2. Minimalne drzewa spinające i minimalne drogi . . . . 152
8.3. Przepływy w sieciach . . . . . . . . . . . . . . . . . . 157
8.4. Zadania . . . . . . . . . . . . . . . . . . . . . . . . . 164
III. Ogólne struktury kombinatoryczne
9. Ciała i przestrzenie wektorowe
167
169
9.1. Ciała skończone . . . . . . . . . . . . . . . . . . . . . 169
9.2. Skończone przestrzenie wektorowe . . . . . . . . . . . 171
9.3. Skończone geometrie rzutowe i afiniczne . . . . . . . . 175
9.4. Zadania . . . . . . . . . . . . . . . . . . . . . . . . . 179
10. Matroidy
181
10.1. Podstawy . . . . . . . . . . . . . . . . . . . . . . . . 181
10.2. Transwersale . . . . . . . . . . . . . . . . . . . . . . . 189
10.3. Matroidy dualne . . . . . . . . . . . . . . . . . . . . . 192
10.4. Wielomiany Tutte’a . . . . . . . . . . . . . . . . . . . 196
10.5. Zadania . . . . . . . . . . . . . . . . . . . . . . . . . 200
11. Systemy i algorytmy zachłanne
203
11.1. Systemy zachłanne . . . . . . . . . . . . . . . . . . . 203
11.2. Algorytmy zachłanne . . . . . . . . . . . . . . . . . . 207
11.3. Zadania . . . . . . . . . . . . . . . . . . . . . . . . . 212
Rozwiązania, odpowiedzi i wskazówki
215
Rozdział 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . 217
Rozdział 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . 223
Rozdział 3 . . . . . . . . . . . . . . . . . . . . . . . . . . . 227
Kup książkę
Poleć książkę

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika:

Zgłoś jeśli naruszono regulamin