Matematyka dawna i nowa Tom II Struktura i przypadek

Opis

Matematyka dawna i nowa Tom II Struktura i przypadek

Wydawnictwo: GIS

Autorzy: Marek Zakrzewski

 

Dwutomowa ,,Matematyka dawna i nowa” jest panoramicznym spojrzeniem na matematykę. Książka powstała na bazie siedmiu tomów autorskiej serii ,,Markowe wykłady z matematyki” i pozornie wygląda na ich skróconą wersję. Jednak jest to zasadniczo nowa książka. Ma inny cel oraz konstrukcję, a ponadto adresowana jest do nieco innego czytelnika. Publikacja przedstawia matematykę, jako pewną całość. Autor kładzie akcent na powiązania między jej różnymi działami, a przede wszystkim pokazuje naturalne motywacje dla zainteresowania się daną problematyką. Prosty język oraz troska o elementarność wykładu sprawiają, że książka jest dostępna dla studenta pierwszego roku matematyki, fizyki lub informatyki, a także dla ambitnych miłośników matematyki. Z drugiej strony rozległość tematyki i oryginalność ujęcia zainteresuje też starszych studentów oraz doktorantów. Każdy z tomów zawiera ponad 600 zadań. Do większości z nich dołączone są odpowiedzi lub wskazówki.

 

Spis treści

Wstęp xv

I Kombinatoryka 1

1 Permutacje i kombinacje, czyli sztuka mnożenia 3

1.1 Permutacje i kombinacje bez powtórzeń . . . . . . . . . . . . . 3

1.2 Ustawienia i kombinacje z powtórzeniami . . . . . . . . . . . . 9

2 Współczynniki dwumianowe i liczby Fibonacciego 13

2.1 Współczynniki dwumianowe i trójkąt Pascala . . . . . . . . . . 13

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

2.3 Liczby Fibonacciego . . . . . . . . . . . . . . . . . . . . . . . . 19

2.4 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 Liczby Stirlinga i liczby Bella . . . . . . . . . . . . . . . . . . . 28

3.3 Nieporządki i punkty stałe permutacji . . . . . . . . . . . . . . 30

4 Równoważności i porządki 33

4.1 Relacje równoważności, typy i rozbicia na klasy . . . . . . . . . 33

4.2 Porządki i twierdzenie Spernera . . . . . . . . . . . . . . . . . . 36

II Prawdopodobieństwo 39

5 Podstawowe pojęcia 42

5.1 Przestrzeń zdarzeń i rozkład prawdopodobieństwa . . . . . . . 42

5.2 Prawdopodobieństwo warunkowe i niezależność . . . . . . . . . 45

5.3 Prawdopodobieństwo geometryczne . . . . . . . . . . . . . . . . 48

5.4 De Moivre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

6 Trzy zadania z nieoczekiwaną odpowiedzią 51

6.1 Paradoksy nietranzytywności . . . . . . . . . . . . . . . . . . . 51

6.2 Paradoks urodzinowy . . . . . . . . . . . . . . . . . . . . . . . . 53

6.3 Problem sekretarki . . . . . . . . . . . . . . . . . . . . . . . . . 55

7 Zmienna losowa i problem kolekcjonera 59

7.1 Zmienna losowa i jej rozkład . . . . . . . . . . . . . . . . . . . 59

7.2 Czekanie na sukces i problem kolekcjonera . . . . . . . . . . . . 62

8 Nierówność Czebyszewa i prawo wielkich liczb 65

8.1 Miary rozproszenia: wariancja i odchylenie standardowe . . . . 65

8.2 Nierówność Czebyszewa . . . . . . . . . . . . . . . . . . . . . . 68

8.3 Rozkład dwumianowy i prawo wielkich liczb . . . . . . . . . . . 70

8.4 Laplace i Czebyszew . . . . . . . . . . . . . . . . . . . . . . . . 73

9 Aproksymacje rozkładu dwumianowego 75

9.1 Aproksymacja poissonowska . . . . . . . . . . . . . . . . . . . . 76

9.2 Rozkład normalny i aproksymacja gaussowska . . . . . . . . . . 80

9.3 Gauss . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82

10 Prawdopodobieństwo i funkcje tworzące 83

10.1 Inne spojrzenie na wartość średnią i wariancję . . . . . . . . . . 83

10.2 Zadanie o ruinie gracza . . . . . . . . . . . . . . . . . . . . . . 86

10.3 Błądzenie losowe* . . . . . . . . . . . . . . . . . . . . . . . . . 87

10.4 Pólya . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

III Liczby zespolone i konstrukcje geometryczne 91

11 Liczby zespolone i zasadnicze twierdzenie algebry 93

11.1 Wprowadzenie . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

11.2 Zasadnicze twierdzenie algebry i faktoryzacja wielomianów . . . 98

11.3 Dowód zasadniczego twierdzenia algebry . . . . . . . . . . . . . 101

12 Pierwiastki z jedności, wielokąty foremne i wzory Cardana 103

12.1 Postać trygonometryczna i wzór de Moivre’a . . . . . . . . . . 103

12.2 Pierwiastkowanie i postać wykładnicza . . . . . . . . . . . . . . 106

12.3 Pierwiastki z jedności a wielokąty foremne . . . . . . . . . . . . 108

12.4 Równania algebraiczne trzeciego stopnia . . . . . . . . . . . . . 110

13 Pierścienie, ciała i faktoryzacja wielomianów 114

13.1 Pierścienie i ciała . . . . . . . . . . . . . . . . . . . . . . . . . . 114

13.2 Pierścień F[x] i faktoryzacja . . . . . . . . . . . . . . . . . . . . 118

13.3 Algorytm Euklidesa i lemat Bezouta . . . . . . . . . . . . . . . 121

14 Pierścienie ilorazowe i ciała skończone 124

14.1 Pierścienie ilorazowe i ciała . . . . . . . . . . . . . . . . . . . . 124

14.2 Ciała skończone . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

15 Rozszerzenia ciał i konstrukcje geometryczne 132

15.1 Rozszerzenia ciała liczb wymiernych . . . . . . . . . . . . . . . 132

15.2 Konstrukcje geometryczne . . . . . . . . . . . . . . . . . . . . . 135

15.3 Euklides i jego Elementy . . . . . . . . . . . . . . . . . . . . . . 138

IV Grupy i symetrie 139

16 Symetrie figur i pojęcie grupy 141

16.1 Symetrie figur i grupy przekształceń . . . . . . . . . . . . . . . 141

16.2 Ogólne pojęcie grupy . . . . . . . . . . . . . . . . . . . . . . . . 144

16.3 Kilka prostych, ale ważnych twierdzeń . . . . . . . . . . . . . . 147

17 Podgrupy, iloczyny i twierdzenie Lagrange’a 151

17.1 Podgrupy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151

17.2 Grupy cykliczne i iloczyn grup . . . . . . . . . . . . . . . . . . 154

17.3 Twierdzenie Lagrange’a i rozbicia na warstwy . . . . . . . . . . 156

17.4 Twierdzenia Cauchy’ego i Sylova . . . . . . . . . . . . . . . . . 159

18 Grupy permutacji 161

18.1 Permutacje i grupa symetryczna Sn . . . . . . . . . . . . . . . . 161

18.2 Parzystość permutacji i grupy alternujące An . . . . . . . . . . 164

18.3 O tasowaniu kart . . . . . . . . . . . . . . . . . . . . . . . . . . 167

19 Izomorfizm i struktura grup 170

19.1 Izomorfizm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 170

19.2 Generatory i relacje . . . . . . . . . . . . . . . . . . . . . . . . 173

19.3 Twierdzenie Cayleya . . . . . . . . . . . . . . . . . . . . . . . . 176

19.4 Noether i van der Waerden . . . . . . . . . . . . . . . . . . . . 178

20 Symetrie wielościanów 179

20.1 Trzy łatwe wielościany . . . . . . . . . . . . . . . . . . . . . . . 179

20.2 Dwa przypadki trudniejsze . . . . . . . . . . . . . . . . . . . . . 183

21 Dzielniki normalne, homomorfizmy i grupy ilorazowe 185

21.1 Elementy sprzężone i dzielniki normalne . . . . . . . . . . . . . 185

21.2 Grupy proste . . . . . . . . . . . . . . . . . . . . . . . . . . . . 188

21.3 Homomorfizmy i grupy ilorazowe* . . . . . . . . . . . . . . . . 190

22 Wprowadzenie do teorii Galois* 193

22.1 Automorfizmy ciał . . . . . . . . . . . . . . . . . . . . . . . . . 194

22.2 Ciało rozkładu wielomianu i grupa Galois . . . . . . . . . . . . 196

22.3 Nierozwiązalność równań piątego stopnia . . . . . . . . . . . . . 199

22.4 Abel i Galois . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201

V Teoria liczb 203

23 Liczby pierwsze: od Euklidesa do Eulera 205

23.1 Twierdzenie Euklidesa i sito Eratostenesa . . . . . . . . . . . . 205

23.2 Zeta Riemanna i twierdzenie Eulera . . . . . . . . . . . . . . . 209

23.3 Cztery problemy Landaua . . . . . . . . . . . . . . . . . . . . . 211

24 Kongruencje i ich zastosowania 214

24.1 Kongruencje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214

24.2 Dwa klasyczne twierdzenia: Wilsona i Fermata . . . . . . . . . 217

24.3 Twierdzenia Lagrange’a i jego zastosowania . . . . . . . . . . . 220

25 Funkcja Eulera i pierwiastki pierwotne 222

25.1 Funkcja Eulera i twierdzenie Eulera . . . . . . . . . . . . . . . 222

25.2 Pierwiastki pierwotne . . . . . . . . . . . . . . . . . . . . . . . 225

25.3 Twierdzenie Dirichleta . . . . . . . . . . . . . . . . . . . . . . . 227

25.4 Dirichlet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 229

26 Protokoły kryptograficzne i rozpoznawanie pierwszości 230

26.1 Szyfry symetryczne i uzgadnianie klucza . . . . . . . . . . . . . 231

26.2 RSA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234

26.3 Rozpoznawanie pierwszości . . . . . . . . . . . . . . . . . . . . 237

26.4 Faktoryzacja* . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240

27 Rozmieszczenie liczb pierwszych 244

27.1 Twierdzenie o rozmieszczeniu Liczb pierwszych . . . . . . . . . 244

27.2 Twierdzenie Czebyszewa i hipoteza Sierpińskiego . . . . . . . . 249

27.3 Elementarne oszacowania funkcji π(x)* . . . . . . . . . . . . . . 250

28 Sumy potęg i liczby wielokątne 254

28.1 Lemat Minkowskiego i twierdzenie Fermata-Eulera . . . . . . . 255

28.2 Twierdzenia Lagrange’a . . . . . . . . . . . . . . . . . . . . . . 259

28.3 Sumy potęg i twierdzenie Hilberta-Waringa . . . . . . . . . . . 261

28.4 Liczby wielokątne i twierdzenie Cauchy’ego . . . . . . . . . . . 264

28.5 Sierpiński . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265

29 Równania diofantyczne 266

29.1 Równanie Pitagorasa . . . . . . . . . . . . . . . . . . . . . . . . 267

29.2 Równanie Pella . . . . . . . . . . . . . . . . . . . . . . . . . . . 271

29.3 Ułamki łańcuchowe i równanie Pella . . . . . . . . . . . . . . . 274

VI Grafy, geometria i gra 277

30 Grafy, drogi i cykle 279

30.1 Język teorii grafów . . . . . . . . . . . . . . . . . . . . . . . . . 279

30.2 Mosty królewieckie i grafy eulerowskie . . . . . . . . . . . . . . 281

30.3 Grafy hamiltonowskie i dwudzielność . . . . . . . . . . . . . . . 283

30.4 Izomorfizm i zliczanie grafów . . . . . . . . . . . . . . . . . . . 286

31 Drzewa i twierdzenie Cayleya 289

31.1 Drzewa i związki acykliczne . . . . . . . . . . . . . . . . . . . . 289

31.2 Kody Pr¨ufera i twierdzenie Cayleya . . . . . . . . . . . . . . . . 291

31.3 Macierz grafu i twierdzenie Kirchoffa . . . . . . . . . . . . . . . 294

31.4 Cayley . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 296

32 Grafy planarne i wzór Eulera 297

32.1 Planarność i wzór Eulera . . . . . . . . . . . . . . . . . . . . . 297

32.2 Twierdzenie o czterech barwach i kolorowanie grafów . . . . . . 301

32.3 Kombinatoryka, geometria i gra . . . . . . . . . . . . . . . . . . 304

32.4 Conway . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307

33 Parkietaże, wielościany i czwarty wymiar 308

33.1 Parkietaże . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 308

33.2 Wielościany platońskie i archimedesowe . . . . . . . . . . . . . 310

33.3 Czwarty wymiar i jeszcze dalej . . . . . . . . . . . . . . . . . . 313

34 Być albo nie być, czyli kwestie istnienia 317

34.1 Zasada szufladkowa . . . . . . . . . . . . . . . . . . . . . . . . . 318

34.2 Kolorowanie i parzystość . . . . . . . . . . . . . . . . . . . . . . 321

34.3 Proste twierdzenie o prostych . . . . . . . . . . . . . . . . . . . 323

34.4 Żołnierze Conwaya . . . . . . . . . . . . . . . . . . . . . . . . . 324

34.5 Gardner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327

35 Twierdzenia ramseyowskie 328

35.1 Gra w trójkąty i liczby Ramseya . . . . . . . . . . . . . . . . . 328

35.2 Twierdzenie van der Waerdena . . . . . . . . . . . . . . . . . . 332

35.3 Dwa oszacowania* . . . . . . . . . . . . . . . . . . . . . . . . . 335

35.4 Erd˝os . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338

VII Geometria nieeuklidesowa 339

36 Geometria sfery 342

36.1 Proste i okręgi na sferze . . . . . . . . . . . . . . . . . . . . . . 343

36.2 Kąty, trójkąty i twierdzenie Pitagorasa . . . . . . . . . . . . . . 346

36.3 Twierdzenie Girarda-Harriota i pola wielokątów . . . . . . . . . 348

36.4 Harriot i Girard . . . . . . . . . . . . . . . . . . . . . . . . . . . 350

37 Przekształcenia M¨obiusa i inwersje 351

37.1 Przekształcenia M¨obiusa . . . . . . . . . . . . . . . . . . . . . . 351

37.2 Własności inwersji . . . . . . . . . . . . . . . . . . . . . . . . . 358

38 Płaszczyzna hiperboliczna 362

38.1 Punkty, proste i piąty postulat . . . . . . . . . . . . . . . . . . 362

38.2 Homografie rzeczywiste i przystawanie . . . . . . . . . . . . . . 366

38.3 Długość krzywej i odległość . . . . . . . . . . . . . . . . . . . . 369

38.4 Łobaczewski i Bolyai . . . . . . . . . . . . . . . . . . . . . . . . 372

39 Twierdzenie Gaussa-Bonneta i jego konsekwencje 373

39.1 Pole trójkąta i twierdzenie Gaussa-Bonneta . . . . . . . . . . . 373

39.2 Wielokąty i parkietaże . . . . . . . . . . . . . . . . . . . . . . . 377

39.3 Kąt równoległości i absolutna miara długości . . . . . . . . . . 380

39.4 Poincar´e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 382

VIII Złożoność, obliczalność i twierdzenie G¨odla 383

40 Złożoność algorytmów i zagadnienie P-NP 386

40.1 Algorytmy sortowania i złożoność problemów . . . . . . . . . . 386

40.2 Hierarchia funkcji i zagadnienie P-NP . . . . . . . . . . . . . . 392

41 Granice obliczalności i problem stopu 394

41.1 Obliczalność i rozstrzygalność . . . . . . . . . . . . . . . . . . . 394

41.2 Funkcja Rado i problem stopu . . . . . . . . . . . . . . . . . . . 398

41.3 Turing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401

42 Twierdzenie G¨odla i równania diofantyczne 402

42.1 Formalizacja arytmetyki i twierdzenie G¨odla . . . . . . . . . . . 403

42.2 Rekurencyjna przeliczalność i zbiory diofantyczne . . . . . . . . 408

42.3 Peano i G¨odel . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411

Epilog 413

Uwagi o literaturze 419

Odpowiedzi i wskazówki 421

Indeks 450