Od matematyki do programowania uogólnionego

Pasjonująca matematyka dla programistów!
Program to nic innego jak ciąg poleceń realizujących zadany algorytm. A gdy mówimy o algorytmach, jesteśmy tylko o krok od matematyki! To wyjątkowo interesująca dziedzina, którą w praktyce powinien znać każdy programista. Jeżeli chciałbyś zrozumieć uogólnione zasady programowania oraz podstawy matematycznych abstrakcji, na których się ono opiera, to trzymasz w rękach odpowiednią publikację.

Na kolejnych stronach znajdziesz interesujące informacje na temat pierwszych algorytmów, historii zera oraz nowoczesnych teorii liczb. Po zdobyciu podstawowych wiadomości oraz poznaniu ogólnej historii matematyki przejdziesz do zaznajamiania się z abstrakcjami, takimi jak grupy, monoidy, półgrupy. Następnie opanujesz m.in. takie zagadnienia, jak wyprowadzanie algorytmu uogólnionego, struktury algebraiczne oraz sposoby organizacji wiedzy matematycznej. Sprawdzisz też, jak wyglądają najważniejsze koncepcje programowania, co to są algorytmy permutacyjne i czym zajmuje się kryptologia. Książka ta jest doskonałą lekturą, która pochłonie Cię na wiele godzin!

Poznasz między innymi:

jak uogólnić liczący cztery tysiące lat algorytm, niezrównane ujęcie klarowności i wydajności;
starożytne paradoksy, piękne twierdzenia i produktywne napięcie występujące między tym, co ciągłe, i tym, co dyskretne;
prosty algorytm znajdowania największego wspólnego dzielnika (NWD) i nowoczesne, wywodzące się z niego abstrakcje;
solidne matematyczne podejścia do abstrakcji;
że algebra abstrakcyjna dostarcza koncepcji pozostających w samym centrum programowania uogólnionego;
aksjomaty, dowody, teorie i modele, czyli zastosowanie metod matematycznych do organizowania wiedzy o Twoich algorytmach i strukturach danych;
zaskakujące subtelności tkwiące w prostych zadaniach programistycznych i co jest w nich pouczającego;
jak wykorzystać wiedzę teoretyczną w praktycznych implementacjach,

a także poczujesz ducha i aurę, które otaczały myślicieli, matematyków i twórców algorytmów od najdawniejszych czasów po współczesność.

Przekonaj się, jakie tajemnice kryje świat matematyki!

Alexander A. Stepanov — jest autorem licznych prac o podstawach programowania. W swojej karierze programował systemy operacyjne, narzędzia, kompilatory oraz dodatkowe biblioteki. Jest laureatem nagrody Excellence in Programming, przyznawanej przez miesięcznik „Dr. Dobb’s Journal”, i autorem projektu standardowej biblioteki szablonów (STL) w języku C++.

Daniel E. Rose — zajmował kierownicze stanowiska w firmach Apple, AltaVista, Xigo, Yahoo! i A9.com. W swoich badaniach skupia się na wszystkich aspektach związanych z wyszukiwaniem danych. Na Uniwersytecie Kalifornijskim w San Diego zrobił doktorat z kognitywistyki.

Spis treści: 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 (58)
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)

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)

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 (281)