Mercurius Gliwice Sp. z o.o.
ul. Prymasa S. Wyszyńskiego 14 b
44-100 Gliwice
pn - pt 10.00 - 18.00
sb 10.00 - 14.00

e-mail:
[zasłonięte]@ksiegarniagliwice.pl
tel. 32 [zasłonięte] 19
fax. 32 [zasłonięte] 22

Bank PKO BP
12 1020 [zasłonięte] 2[zasłonięte]4010002 [zasłonięte] 027277

Po wylicytowaniu przedmiotu koniecznie wypełnij formularz dostawy, jeśli chcesz zmienić adres dostawy - zrób to właśnie tutaj.

Do zakupionych książek dostaniesz paragon (na życzenie fakturę VAT), gwarantujące Ci rozpatrzenie reklamacji.

Kontaktując się z nami, zawsze używaj swojego nicka, pozwoli to nam szybciej zająć się Twoją sprawą.

Każdą przesyłkę starannie pakujemy w tekturowe pudełko albo kopertę ochronną, tak aby w stanie nienaruszonym dotarła do odbiorcy.

Za przesyłkę płacisz raz.
Oszczędź na kosztach wysyłki,
połącz zamówienia z:

ksiazka_z_pasja
ksiazka_gliwice
MercuriusGliwice

W serii Markowe wykłady z matematyki autor ukazuje całościowy obraz matematyki wykładanej na studiach matematycznych i technicznych. Omawia w niej najważniejsze pojęcia i metody, ale szczególny nacisk kładzie na konkretne, interesujące problemy.

Matematyka dyskretna - drugi tom tej serii - została pomyślana jako podstawowy podręcznik dla studentów informatyki i matematyki. Może stanowić także interesującą lekturę dla ambitniejszych uczniów szkół średnich. Tom zawiera standardowy kurs kombinatoryki i teorii grafów, wzbogacony o elementy teorii liczb, teorii prawdopodobieństwa i złożoności obliczeniowej.

Przy okazji Czytelnik poznaje:
* matematyczne aspekty gier i łamigłówek
* otwarte problemy matematyki
* podstawy współczesnej kryptografii (RSA)
* wiele intrygujących zadań
* teoretyczne ograniczenia informatyki.

Krótko mówiąc prawdziwa matematyka dla (prawie) wszystkich.


Marek Zakrzewski jest absolwentem Wydziału Matematyki i Mechaniki Uniwersytetu Warszawskiego. Od roku 1976 pracuje w Instytucie Matematyki i Informatyki Politechniki Wrocławskiej. Zajmuje się nauczaniem i popularyzacją matematyki, a także jej historią. Poza tym słucha muzyki i pisze książki, ta jest dziewiątą.


SPIS TREŚCI:

Wstęp XIII

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 Prufera 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. Erdos 150

III. Teoria liczb 151

17. Liczby pierwsze 155
17.1. Twierdzenie Euklidesa i sito Eratostenesa 155
17.2. Algorytm Euklidesa i jego konsekwencje 159

18. Kongruencje i ich zastosowania 163
18.1. Kongruencje 163
18.2. Dwa klasyczne twierdzenia: Wilsona i Fermata 167

19. Twierdzenie Eulera i protokoły kryptograficzne 171
19.1. Funkcja Eulera i twierdzenie Eulera 171
19.2. ABC kryptografii asymetrycznej 174

20. Rozpoznawanie pierwszości i faktoryzacja 179
20.1. Rozpoznawanie pierwszości 179
20.2. Faktoryzacja 181

21. Rozmieszczenie liczb pierwszych 187
21.1. Dwa "łatwe" twierdzenia 187
21.2. Twierdzenie o Rozmieszczeniu Liczb Pierwszych 189
21.3. TRLP: idea dowodu** 192

IV. Teoria prawdopodobieństwa 195

22. Prawdopodobieństwo 199
22.1. Przestrzeń zdarzeń i rozkład prawdopodobieństwa 199
22.2. Prawdopodobieństwo warunkowe i niezależność 202

23. Trzy zadania z nieoczekiwaną odpowiedzią 205
23.1. Paradoksy nietranzytywności 205
23.2. Paradoks urodzinowy i jego zastosowania 207
23.3. Problem sekretarki* 210

24. Zmienna losowa i problem kolekcjonera 213
24.1. Zmienna losowa i jej rozkład 213
24.2. Czekanie na sukces i problem kolekcjonera 216

25. Nierówność Czebyszewa i Prawo Wielkich Liczb 219
25.1. Miary rozproszenia; wariancja i odchylenie standardowe 219
25.2. Nierówność Czebyszewa 222
25.3. Rozkład dwumianowy i Prawo Wielkich Liczb 224
25.4. Łapiące i Czebyszew 227

26. Aproksymacje rozkładu dwumianowego 229
26.1. Aproksymacja poissonowska 230
26.2. Rozkład normalny i aproksymacja gaussowska 234
26.3. Gauss 236

27. Prawdopodobieństwo i funkcje tworzące 237
27.1. Nowe spojrzenie na wartość średnia i wariancję 237
27.2. Błądzenie losowe** 240

V. Złożoność, obliczalność i twierdzenie Godła 243

28. Złożoność algorytmów i zagadnienie P-NP 247
28.1. Algorytmy sortowania i złożoność problemów 247
28.2. Hierarchia funkcji i zagadnienie P-NP 253

29. Granice obliczalności i problem stopu 255
29.1. Obliczalność i rozstrzygalność 255
29.2. Funkcja Rado i problem stopu 259
29.3. Turing 262

30. Arytmetyka Peano i twierdzenie Godla 263
30.1 Arytmetyka jako system formalny 264
30.2 Twierdzenie Godla 266
30.3 Godel 268

Odpowiedzi i wskazówki 269
Indeks 279