Od matematyki do programowania uogólnionego

Podziękowania       7
O autorach       9
Nota od autorów       11
1. O czym jest ta książka       13
1.1. Programowanie a matematyka       14
1.2. Perspektywa historyczna       15
1.3. Wymagania       15
1.4. Przewodnik       16
2. Pierwszy algorytm       19
2.1. Mnożenie po egipsku       20
2.2. Ulepszenie algorytmu       23
2.3. Przemyślenia związane z rozdziałem       26
3. Teoria liczb według starożytnych Greków       27
3.1. Geometryczne proporcje liczb całkowitych       27
3.2. Odsiewanie liczb pierwszych       30
3.3. Implementacja i optymalizacja kodu       33
3.4. Liczby doskonałe       38
3.5. Program pitagorejski       42
3.6. Fatalny błąd w tym programie       43
3.7. Przemyślenia związane z rozdziałem       47
4. Algorytm Euklidesa       49
4.1. Ateny i Aleksandria       49
4.2. Algorytm Euklidesa znajdowania największej wspólnej miary       51
4.3. Tysiąc lat bez matematyki       57
4.4. Dziwna historia zera       584 Spis treści
4.5. Algorytmy obliczania reszty i ilorazu       60
4.6. Współużytkowanie kodu       63
4.7. Uprawomocnienie tego algorytmu       65
4.8. Przemyślenia związane z rozdziałem       67
5. Pojawienie się nowoczesnej teorii liczb       69
5.1. Liczby pierwsze Mersenne’a i liczby pierwsze Fermata       69
5.2. Małe twierdzenie Fermata       74
5.3. Skracanie       78
5.4. Udowodnienie małego twierdzenia Fermata       82
5.5. Twierdzenie Eulera       84
5.6. Zastosowania arytmetyki modularnej       88
5.7. Przemyślenia związane z rozdziałem       89
6. Abstrakcja w matematyce       91
6.1. Grupy       91
6.2. Monoidy i półgrupy       95
6.3. Niektóre twierdzenia o grupach       98
6.4. Podgrupy i grupy cykliczne       101
6.5. Twierdzenie Lagrange’a       103
6.6. Teorie i modele       107
6.7. Przykłady teorii kategorycznych i niekategorycznych       110
6.8. Przemyślenia związane z rozdziałem       113
7. Wyprowadzenie algorytmu uogólnionego       115
7.1. Rozwikłanie wymagań dotyczących algorytmu       115
7.2. Wymagania dotyczące A       116
7.3. Wymagania dotyczące N       120
7.4. Nowe wymagania       122
7.5. Zamiana mnożenia na potęgowanie       123
7.6. Uogólnianie operacji       124
7.7. Obliczanie liczb Fibonacciego       127
7.8. Przemyślenia związane z rozdziałem       130
8. Więcej struktur algebraicznych       131
8.1. Wielomiany Stevina i NWD       131
8.2. Getynga i matematyka niemiecka       137
8.3. Noether i narodziny algebry abstrakcyjnej       142
8.4. Pierścienie       144
8.5. Mnożenie macierzy i półpierścienie       147
8.6. Zastosowanie: sieci społeczne i najkrótsze ścieżki       149
8.7. Dziedziny euklidesowe       151
8.8. Ciała i inne struktury algebraiczne       152
8.9. Przemyślenia związane z rozdziałem       154
 
 Spis treści 5
9. Uporządkowanie wiedzy matematycznej       157
9.1. Dowody       157
9.2. Pierwsze twierdzenie       160
9.3. Euklides i metoda aksjomatyczna       163
9.4. Geometrie alternatywne wobec euklidesowej       165
9.5. Formalistyczne podejście Hilberta       168
9.6. Peano i jego aksjomaty       171
9.7. Budowanie arytmetyki       174
9.8. Przemyślenia związane z rozdziałem       177
10. Podstawowe koncepcje programowania       179
10.1. Arystoteles i abstrakcja       179
10.2. Wartości i typy       182
10.3. Koncepty       183
10.4. Iteratory       187
10.5. Kategorie, cechy i operacje iteratorowe       188
10.6. Przedziały       191
10.7. Wyszukiwanie liniowe       193
10.8. Wyszukiwanie binarne       194
10.9. Przemyślenia związane z rozdziałem       199
11. Algorytmy permutacyjne       201
11.1. Permutacje i transpozycje       201
11.2. Zamiana przedziałów       205
11.3. Rotacja       208
11.4. Zastosowanie cykli       211
11.5. Odwracanie       215
11.6. Złożoność przestrzenna       218
11.7. Algorytmy dostosowujące się do pamięci       219
11.8. Przemyślenia związane z rozdziałem       220
12. Rozszerzenia NWD       221
12.1. Ograniczenia sprzętowe i efektywniejsze algorytmy       221
12.2. Uogólnienie algorytmu Steina       224
12.3. Tożsamość Bézouta       227
12.4. Rozszerzony NWD       231
12.5. Zastosowania NWD       235
12.6. Przemyślenia związane z rozdziałem       236
13. Zastosowanie praktyczne       237
13.1. Kryptologia       237
13.2. Sprawdzanie pierwszości       240
13.3. Test Millera-Rabina       243
13.4. Algorytm RSA — jak działa i dlaczego       245
13.5. Przemyślenia związane z rozdziałem       248
 
 6 Spis treści
14. Wnioski       249
Lektury uzupełniające       251
A Notacja       257
B Typowe techniki dowodowe       261
B.1. Dowód nie wprost       261
B.2. Dowód przez indukcję       262
B.3. Zasada klatek w gołębniku       263
C C++ dla nieprogramujących w C++       265
C.1. Funkcje szablonowe       265
C.2. Koncepty       266
C.3. Składnia deklaracji i stałe z typami       267
C.4. Obiekty funkcyjne       268
C.5. Warunki początkowe i końcowe oraz asercje       269
C.6. Algorytmy STL i struktury danych       269
C.7. Iteratory i przedziały       271
C.8. Zastosowanie synonimów i funkcji typów w C++11       272
C.9. Listy inicjatorów w C++11       272
C.10. Funkcje lambda w C++11       273
C.11. Uwaga o podprogramach otwartych       273
Literatura       275
Skorowidz       279
Źródła materiału zdjęciowego       285