Markowe wykłady z matematyki Matematyka dyskretna

Opis

Markowe wykłady z matematyki Matematyka dyskretna

Wydawnictwo: GIS

Autorzy: Marek Zakrzewski

 

Jest to II wydanie drugiego tomu z autorskiej serii ,,Markowe wykłady z matematyki’’. Książka została pomyślana, jako podstawowy podręcznik dla studentów wydziałów matematyki i informatyki. Może także stanowić interesującą lekturę dla ambitniejszych uczniów szkół średnich. Tom zawiera standardowy kurs kombinatoryki i teorii grafów, wzbogacony o elementy teorii prawdopodobieństwa i złożoności obliczeniowej.

 

Spis treści

Wstęp

I Kombinatoryka 1

1 Permutacje i kombinacje, czyli sztuka mnożenia 5

1.1 Permutacje i kombinacje . . . . . . . . . . . . . . . . . . . . . . 5

1.2 Ciągi skończone i kombinacje z powtórzeniami . . . . . . . . . 10

1.3 Teoria liczb, gry i geometria . . . . . . . . . . . . . . . . . . . . 13

2 Współczynniki Newtona 17

2.1 Współczynniki Newtona i trójkąt Pascala . . . . . . . . . . . . 17

2.2 Tożsamości kombinatoryczne . . . . . . . . . . . . . . . . . . . 19

2.3 Pascal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

3 Wzór włączeń i wyłączeń, czyli sztuka dodawania 25

3.1 Wzór włączeń i wyłączeń i jego zastosowania . . . . . . . . . . 25

3.2 Nieporządki i punkty stałe permutacji . . . . . . . . . . . . . . 28

4 Permutacje, piętnastka i tasowanie kart 31

4.1 Działania na permutacjach . . . . . . . . . . . . . . . . . . . . 31

4.2 Parzystość permutacji i piętnastka . . . . . . . . . . . . . . . . 34

4.3 O tasowaniu kart* . . . . . . . . . . . . . . . . . . . . . . . . . 36

5 Grupy symetrii i lemat CFB 39

5.1 Grupy permutacji i symetria figur . . . . . . . . . . . . . . . . . 39

5.2 Lemat Cauchy’ego-Frobeniusa-Burnside’a i jego zastosowania . 42

5.3 Kolorowanie sześcianu . . . . . . . . . . . . . . . . . . . . . . . 47

5.4 Dygresja: równoważności i porządki . . . . . . . . . . . . . . . . 49

6 Indukcja i rekurencja 51

6.1 Zasada indukcji matematycznej . . . . . . . . . . . . . . . . . . 51

6.2 Zadanie o wieży z Hanoi . . . . . . . . . . . . . . . . . . . . . . 55

6.3 Liczby Fibonacciego . . . . . . . . . . . . . . . . . . . . . . . . 56

7 Rekurencje liniowe 59

7.1 Rekurencje liniowe i wzór na liczby Fibonacciego . . . . . . . . 59

7.2 Między kombinatoryką a geometrią . . . . . . . . . . . . . . . . 62

7.3 Fibonacci i de Moivre . . . . . . . . . . . . . . . . . . . . . . . 64

8 Funkcje tworzące 65

8.1 Wprowadzenie . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

8.2 Operacje na ciągach i funkcjach tworzących* . . . . . . . . . . 68

8.3 Splot i zadania o podziale* . . . . . . . . . . . . . . . . . . . . 72

8.4 Liczby Catalana* . . . . . . . . . . . . . . . . . . . . . . . . . . 75

II Teoria grafów i geometria kombinatoryczna 79

9 Problemy i metody teorii grafów 83

9.1 Język teorii grafów . . . . . . . . . . . . . . . . . . . . . . . . . 83

9.2 Mosty królewieckie i grafy eulerowskie . . . . . . . . . . . . . . 85

9.3 Grafy hamiltonowskie i dwudzielność . . . . . . . . . . . . . . . 87

9.4 Drzewa i związki acykliczne . . . . . . . . . . . . . . . . . . . . 91

10 Zliczanie drzew i twierdzenie Cayleya 93

10.1 Izomorfizm i zliczanie grafów . . . . . . . . . . . . . . . . . . . 93

10.2 Kody Pr¨ufera i twierdzenie Cayleya . . . . . . . . . . . . . . . . 96

10.3 Macierz grafu i twierdzenie Kirchoffa . . . . . . . . . . . . . . . 100

10.4 Cayley . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102

11 Skojarzenia, twierdzenie Halla i kwadraty łacińskie 103

11.1 Twierdzenie Halla o małżeństwach i kwadraty łacińskie . . . . 103

11.2 Pokrycia dominami, zliczanie skojarzeń i permanent . . . . . . 108

12 Wzór Eulera 111

12.1 Planarność i wzór Eulera . . . . . . . . . . . . . . . . . . . . . 111

12.2 Kombinatoryka, geometria i gra* . . . . . . . . . . . . . . . . . 115

12.3 Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

13 Twierdzenie o czterech barwach i kolorowanie grafów 119

13.1 Kolorowanie wierzchołków i twierdzenie o 4 barwach . . . . . . 119

13.2 Kolorowanie krawędzi . . . . . . . . . . . . . . . . . . . . . . . 122

14 Parkietaże, wielościany i czwarty wymiar 125

14.1 Parkietaże . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

14.2 Wielościany platońskie i archimedesowe . . . . . . . . . . . . . 127

14.3 Czwarty wymiar i jeszcze dalej . . . . . . . . . . . . . . . . . . 131

15 Być albo nie być, czyli kwestie istnienia 133

15.1 Zasada szufladkowa . . . . . . . . . . . . . . . . . . . . . . . . . 134

15.2 Kolorowanie i parzystość . . . . . . . . . . . . . . . . . . . . . . 137

15.3 Proste twierdzenie o prostych . . . . . . . . . . . . . . . . . . . 139

15.4 Żołnierze Conwaya . . . . . . . . . . . . . . . . . . . . . . . . . 140

16 Twierdzenia ramseyowskie 143

16.1 Gra w trójkąty i liczby Ramseya . . . . . . . . . . . . . . . . . 143

16.2 Twierdzenie van der Waerdena* . . . . . . . . . . . . . . . . . . 147

16.3 Erd˝os . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

III Teoria prawdopodobieństwa 151

17 Prawdopodobieństwo 155

17.1 Przestrzeń zdarzeń i rozkład prawdopodobieństwa . . . . . . . 155

17.2 Prawdopodobieństwo warunkowe i niezależność . . . . . . . . . 158

18 Trzy zadania z nieoczekiwaną odpowiedzią 161

18.1 Paradoksy nietranzytywności . . . . . . . . . . . . . . . . . . . 161

18.2 Paradoks urodzinowy . . . . . . . . . . . . . . . . . . . . . . . . 163

18.3 Problem sekretarki* . . . . . . . . . . . . . . . . . . . . . . . . 165

19 Zmienna losowa i problem kolekcjonera 169

19.1 Zmienna losowa i jej rozkład . . . . . . . . . . . . . . . . . . . 169

19.2 Czekanie na sukces i problem kolekcjonera . . . . . . . . . . . . 172

20 Nierówność Czebyszewa i Prawo Wielkich Liczb 175

20.1 Miary rozproszenia: wariancja i odchylenie standardowe . . . . 175

20.2 Nierówność Czebyszewa . . . . . . . . . . . . . . . . . . . . . . 178

20.3 Rozkład dwumianowy i Prawo Wielkich Liczb . . . . . . . . . . 180

20.4 Laplace i Czebyszew . . . . . . . . . . . . . . . . . . . . . . . . 183

21 Aproksymacje rozkładu dwumianowego 185

21.1 Aproksymacja poissonowska . . . . . . . . . . . . . . . . . . . . 186

21.2 Rozkład normalny i aproksymacja gaussowska . . . . . . . . . . 190

21.3 Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192

22 Prawdopodobieństwo i funkcje tworzące 193

22.1 Nowe spojrzenie na wartość średnią i wariancję . . . . . . . . . 193

22.2 Błądzenie losowe** . . . . . . . . . . . . . . . . . . . . . . . . . 196

IV Złożoność, obliczalność i twierdzenie G¨odla 199

23 Złożoność algorytmów i zagadnienie P-NP 203

23.1 Algorytmy sortowania i złożoność problemów . . . . . . . . . . 203

23.2 Hierarchia funkcji i zagadnienie P-NP . . . . . . . . . . . . . . 209

24 Granice obliczalności i problem stopu 211

24.1 Obliczalność i rozstrzygalność . . . . . . . . . . . . . . . . . . . 211

24.2 Funkcja Rado i problem stopu . . . . . . . . . . . . . . . . . . . 215

24.3 Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218

25 Arytmetyka Peano i twierdzenie G¨odla 219

25.1 Arytmetyka jako system formalny . . . . . . . . . . . . . . . . . 220

25.2 Twierdzenie G¨odla . . . . . . . . . . . . . . . . . . . . . . . . . 222

25.3 G¨odel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224

Odpowiedzi i wskazówki 225

Indeks 234