MATEMATYKA DAWNA I NOWA TOM II STRUKTURA I PRZYPADEK

Wstęp

I Kombinatoryka

1 Permutacje i kombinacje, czyli sztuka mnożenia
1.1 Permutacje i kombinacje bez powtórzeń
1.2 Ustawienia i kombinacje z powtórzeniami

2 Współczynniki dwumianowe i liczby Fibonacciego
2.1 Współczynniki dwumianowe i trójkąt Pascala
2.2 Tożsamości kombinatoryczne
2.3 Liczby Fibonacciego
2.4 Pascal

3 Wzór włączeń i wyłączeń, czyli sztuka dodawania
3.1 Wzór włączeń i wyłączeń i jego zastosowania
3.2 Liczby Stirlinga i liczby Bella
3.3 Nieporządki i punkty stałe permutacji

4 Równoważności i porządki
4.1 Relacje równoważności, typy i rozbicia na klasy
4.2 Porządki i twierdzenie Spernera

II Prawdopodobieństwo

5 Podstawowe pojęcia
5.1 Przestrzeń zdarzeń i rozkład prawdopodobieństwa
5.2 Prawdopodobieństwo warunkowe i niezależność
5.3 Prawdopodobieństwo geometryczne
5.4 De Moivre

6 Trzy zadania z nieoczekiwaną odpowiedzią
6.1 Paradoksy nietranzytywności
6.2 Paradoks urodzinowy
6.3 Problem sekretarki

7 Zmienna losowa i problem kolekcjonera
7.1 Zmienna losowa i jej rozkład
7.2 Czekanie na sukces i problem kolekcjonera

8 Nierówność Czebyszewa i prawo wielkich liczb
8.1 Miary rozproszenia: wariancja i odchylenie standardowe
8.2 Nierówność Czebyszewa
8.3 Rozkład dwumianowy i prawo wielkich liczb
8.4 Laplace i Czebyszew

9 Aproksymacje rozkładu dwumianowego
9.1 Aproksymacja poissonowska
9.2 Rozkład normalny i aproksymacja gaussowska
9.3 Gauss

10 Prawdopodobieństwo i funkcje tworzące
10.1 Inne spojrzenie na wartość średnią i wariancję
10.2 Zadanie o ruinie gracza
10.3 Błądzenie losowe*
10.4 Pólya

III Liczby zespolone i konstrukcje geometryczne

11 Liczby zespolone i zasadnicze twierdzenie algebry
11.1 Wprowadzenie
11.2 Zasadnicze twierdzenie algebry i faktoryzacja wielomianów
11.3 Dowód zasadniczego twierdzenia algebry

12 Pierwiastki z jedności, wielokąty foremne i wzory Cardana
12.1 Postać trygonometryczna i wzór de Moivre‘a
12.2 Pierwiastkowanie i postać wykładnicza
12.3 Pierwiastki z jedności a wielokąty foremne
12.4 Równania algebraiczne trzeciego stopnia

13 Pierścienie, ciała i faktoryzacja wielomianów
13.1 Pierścienie i ciała
13.2 Pierścień F[x] i faktoryzacja
13.3 Algorytm Euklidesa i lemat Bezouta

14 Pierścienie ilorazowe i ciała skończone
14.1 Pierścienie ilorazowe i ciała
14.2 Ciała skończone

15 Rozszerzenia ciał i konstrukcje geometryczne
15.1 Rozszerzenia ciała liczb wymiernych
15.2 Konstrukcje geometryczne
15.3 Euklides i jego Elementy

IV Grupy i symetrie

16 Symetrie figur i pojęcie grupy
16.1 Symetrie figur i grupy przekształceń
16.2 Ogólne pojęcie grupy
16.3 Kilka prostych, ale ważnych twierdzeń

17 Podgrupy, iloczyny i twierdzenie Lagrange‘a
17.1 Podgrupy
17.2 Grupy cykliczne i iloczyn grup
17.3 Twierdzenie Lagrange‘a i rozbicia na warstwy
17.4 Twierdzenia Cauchy‘ego i Sylova

18 Grupy permutacji
18.1 Permutacje i grupa symetryczna Sn
18.2 Parzystość permutacji i grupy alternujące An
18.3 O tasowaniu kart

19 Izomorfizm i struktura grup
19.1 Izomorfizm
19.2 Generatory i relacje
19.3 Twierdzenie Cayleya
19.4 Noether i van der Waerden

20 Symetrie wielościanów
20.1 Trzy łatwe wielościany
20.2 Dwa przypadki trudniejsze

21 Dzielniki normalne, homomorfizmy i grupy ilorazowe
21.1 Elementy sprzężone i dzielniki normalne
21.2 Grupy proste
21.3 Homomorfizmy i grupy ilorazowe*

22 Wprowadzenie do teorii Galois*
22.1 Automorfizmy ciał
22.2 Ciało rozkładu wielomianu i grupa Galois
22.3 Nierozwiązalność równań piątego stopnia
22.4 Abel i Galois

V Teoria liczb

23 Liczby pierwsze: od Euklidesa do Eulera
23.1 Twierdzenie Euklidesa i sito Eratostenesa
23.2 Zeta Riemanna i twierdzenie Eulera
23.3 Cztery problemy Landaua

24 Kongruencje i ich zastosowania
24.1 Kongruencje
24.2 Dwa klasyczne twierdzenia: Wilsona i Fermata
24.3 Twierdzenia Lagrange‘a i jego zastosowania

25 Funkcja Eulera i pierwiastki pierwotne
25.1 Funkcja Eulera i twierdzenie Eulera
25.2 Pierwiastki pierwotne
25.3 Twierdzenie Dirichleta
25.4 Dirichlet

26 Protokoły kryptograficzne i rozpoznawanie pierwszości
26.1 Szyfry symetryczne i uzgadnianie klucza
26.2 RSA
26.3 Rozpoznawanie pierwszości
26.4 Faktoryzacja*

27 Rozmieszczenie liczb pierwszych
27.1 Twierdzenie o rozmieszczeniu Liczb pierwszych
27.2 Twierdzenie Czebyszewa i hipoteza Sierpińskiego
27.3 Elementarne oszacowania funkcji ?(x)*

28 Sumy potęg i liczby wielokątne
28.1 Lemat Minkowskiego i twierdzenie Fermata-Eulera
28.2 Twierdzenia Lagrange‘a
28.3 Sumy potęg i twierdzenie Hilberta-Waringa
28.4 Liczby wielokątne i twierdzenie Cauchy‘ego
28.5 Sierpiński

29 Równania diofantyczne
29.1 Równanie Pitagorasa
29.2 Równanie Pella
29.3 Ułamki łańcuchowe i równanie Pella

VI Grafy, geometria i gra

30 Grafy, drogi i cykle
30.1 Język teorii grafów
30.2 Mosty królewieckie i grafy eulerowskie
30.3 Grafy hamiltonowskie i dwudzielność
30.4 Izomorfizm i zliczanie grafów

31 Drzewa i twierdzenie Cayleya
31.1 Drzewa i związki acykliczne
31.2 Kody Prufera i twierdzenie Cayleya
31.3 Macierz grafu i twierdzenie Kirchoffa
31.4 Cayley

32 Grafy planarne i wzór Eulera
32.1 Planarność i wzór Eulera
32.2 Twierdzenie o czterech barwach i kolorowanie grafów
32.3 Kombinatoryka, geometria i gra
32.4 Conway

33 Parkietaże, wielościany i czwarty wymiar
33.1 Parkietaże
33.2 Wielościany platońskie i archimedesowe
33.3 Czwarty wymiar i jeszcze dalej

34 Być albo nie być, czyli kwestie istnienia
34.1 Zasada szufladkowa
34.2 Kolorowanie i parzystość
34.3 Proste twierdzenie o prostych
34.4 Żołnierze Conwaya
34.5 Gardner

35 Twierdzenia ramseyowskie
35.1 Gra w trójkąty i liczby Ramseya
35.2 Twierdzenie van der Waerdena
35.3 Dwa oszacowania*
35.4 Erdos

VII Geometria nieeuklidesowa

36 Geometria sfery
36.1 Proste i okręgi na sferze
36.2 Kąty, trójkąty i twierdzenie Pitagorasa
36.3 Twierdzenie Girarda-Harriota i pola wielokątów
36.4 Harriot i Girard

37 Przekształcenia Mobiusa i inwersje
37.1 Przekształcenia Mobiusa
37.2 Własności inwersji

38 Płaszczyzna hiperboliczna
38.1 Punkty, proste i piąty postulat
38.2 Homografie rzeczywiste i przystawanie
38.3 Długość krzywej i odległość
38.4 Łobaczewski i Bolyai

39 Twierdzenie Gaussa-Bonneta i jego konsekwencje
39.1 Pole trójkąta i twierdzenie Gaussa-Bonneta
39.2 Wielokąty i parkietaże
39.3 Kąt równoległości i absolutna miara długości
39.4 Poincare

VIII Złożoność, obliczalność i twierdzenie Godla

40 Złożoność algorytmów i zagadnienie P-NP
40.1 Algorytmy sortowania i złożoność problemów
40.2 Hierarchia funkcji i zagadnienie P-NP

41 Granice obliczalności i problem stopu
41.1 Obliczalność i rozstrzygalność
41.2 Funkcja Rado i problem stopu
41.3 Turing

42 Twierdzenie Godla i równania diofantyczne
42.1 Formalizacja arytmetyki i twierdzenie Godla
42.2 Rekurencyjna przeliczalność i zbiory diofantyczne
42.3 Peano i Godel

Epilog

Uwagi o literaturze

Odpowiedzi i wskazówki

Indeks