Грэм, Кнут, Паташник: Конкретная математика.

Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Matematyka konkretna

tytuł oryginału: Concrete Mathematics. A Foundation for Computer Science

stan dobry

Z okładki

„Jest to niezwykła książka o matematyce. Autorzy, wybitni matematycy informatyczni, dostrzegli lukę na rynku wydawniczym — brak książki, w której byłyby zebrane treści matematyczne potrzebne informatykowi. Chodziło o wyłożenie metod rozwiązywania skomplikowanych problemów, wyliczania ogromnych sum i dostrzegania subtelnych wzorców w otaczającym nas świecie. Umiejętności te potrzebne są przy konstruowaniu i analizowaniu algorytmów komputerowych.

Powstało dzieło, które nie ma odpowiednika w całej literaturze matematycznej. Autorzy starają się przedstawić nie tylko samą matematykę, ale i proces jej odkrywania. Bawią się przy tym wraz z czytelnikiem — nie wahają się zapędzić w ślepą uliczkę, czynią pasjonujące dygresje, żartują sobie wielokrotnie, a wydatnie im w tym pomagają pierwsi czytelnicy tej książki, ich studenci, którzy umieścili swoje uwagi na marginesie.

W tej książce znajdzie dla siebie rzeczy ciekawe zarówno licealista zainteresowany matematyką lub informatyką, jak i zawodowy matematyk czy programista. Polecamy ją wszystkim studentom matematyki, informatyki, wydziałów politechnicznych, jak również wszystkim tym, którzy po prostu lubią matematykę i lubią się nią cieszyć.”

Z przedmowy

„Książka ta powstała na podstawie wykładu o tej samej nazwie prowadzonego na Uniwersytecie Stanforda od 1970 r. Zazwyczaj przedmiot ten wybierało około 50 studentów, głównie magistrantów i doktorantów, choć zdarzali się również studenci starszych i młodszych lat. Ci, którzy zaliczyli ten przedmiot, zaczęli prowadzić podobne wykłady na innych uczelniach. Wygląda na to, że nadszedł czas, kiedy powinno się zaprezentować materiał wykładu szerszej publiczności (włączając w to studentów pierwszego roku).

Matematyka konkretna powstała w czasie burzliwej dekady. Zaczęto kwestionować wtedy nie podważane do tej pory wartości, przy czym kolebkę niepokojów stanowiły uniwersytety. Rewidowano programy studiów uniwersyteckich, i matematyka nie uniknęła znalezienia się pod lupą. John Hammersley napisał wtedy prowokujący artykuł »O osłabieniu umiejętności matematycznych przez ‘Matematykę Współczesną’ i przez jej podobne papki intelektualne serwowane w szkołach i na uniwersytetach«. Inni przerażeni matematycy pytali wręcz »Czy można uratować matematykę?« Jeden z autorów tej książki (DEK) wplątał się w pisanie serii książek pod tytułem »The Art of Computer Programming« (»Sztuka programowania komputerów«) i w trakcie przygotowywania pierwszego tomu zorientował się, że brakuje mu narzędzi matematycznych. Te, których potrzebował w celu gruntownego zrozumienia programów komputerowych, różniły się znacznie od tych, które poznał w czasie, kiedy odbywał klasyczne studia matematyczne. Wprowadził więc nowy przedmiot, aby uczyć tego, czego jemu samemu brakowało w czasie jego studiów.

Tytuł wykładu »Matematyka Konkretna« miał początkowo stanowić antidotum na coś, co się wtedy nazywało »Matematyka Abstrakcyjna«, jako że ta druga na fali mody nazwanej »Nową Matematyką« została wyprana nagle ze wszystkich konkretnych wyników stanowiących rdzeń matematycznej klasyki. Matematyka abstrakcyjna jest wspaniałym przedmiotem i nie ma w niej niczego złego: jest piękna, ogólna i użyteczna. Niestety, jej promotorzy doszli do wniosku, że cała reszta matematyki jest nic nie warta. Uogólnianie stało się tak modne, że całe pokolenie matematyków nie było w stanie docenić piękna przypadków szczególnych, ani podjąć wyzwania rozwiązywania konkretnych problemów ilościowych, czy nawet dostrzec wartość w tym, że ktoś posiada sprawność rachunkową. Upojona sukcesami matematyka abstrakcyjna zaczęła tracić kontakt z rzeczywistością. Potrzeba było konkretnej przeciwwagi, aby przywrócić wykształceniu matematycznemu zdrową równowagę.

Wykładając po raz pierwszy Matematykę Konkretną na Uniwersytecie Stanforda, DEK wyjaśniał ten cokolwiek dziwny tytuł wykładu mówiąc, że jest to próba przedstawienia matematycznego wykładu kursowego w sposób twardy, a nie miękki. […]

Choć Matematyka Konkretna powstała w reakcji na inne trendy, rzeczywiste przyczyny jej powstania były pozytywne, a nie negatywne. W miarę, jak wykład ten stawał się w trakcie studiów popularnym przedmiotem, jego treść »utwardzając się« okazywała się użyteczna w wielu nowych zastosowaniach. Tymczasem nadeszło nowe potwierdzenie trafności nazwy tej dziedziny, gdy Z. A. Melzak opublikował dwuczęściową książkę pod tytułem »Companion to Concrete Mathematics«.

Materiał matematyki konkretnej zdaje się na pierwszy rzut oka być workiem przypadkowych chwytów, jednak praktykowanie ich przetwarza go w zorganizowany warsztat z gotowymi narzędziami. W rzeczywistości przedstawione w tej książce techniki charakteryzują się pewną jednorodnością i na wielu wywierają duże wrażenie. Kiedy inny z autorów (RLG) po raz pierwszy prowadził ten przedmiot w 1979 r., studentom tak się wykład spodobał, że wielu z nich zobaczył jeszcze raz rok później.

Czym dokładnie jest Matematyka Konkretna? Jest to mieszanina matematyki ciągłej i dyskretnej. Konkretniej, w jej zakres wchodzi usystematyzowane przetwarzanie wzorów matematycznych oparte na zestawie odpowiednich technik rozwiązywania problemów. Gdy opanujesz, Czytelniku, materiał zawarty w tej książce, wówczas wszystko, czego będziesz potrzebował, to niezmącony umysł, trochę papieru i całkiem niemało pisania, aby wyliczać wartości jakichś horrendalnie wyglądających sum, rozwiązywać złożone relacje rekurencyjne i odkrywać subtelne wzorce w danych. Będziesz na tyle biegły w stosowaniu technik algebraicznych, że często będziesz wolał znajdywać wartości dokładne, niż ich oszacowania.

Podstawowe zagadnienia ujęte w tej książce zawierają sumy, rekurencje, elementarną teorię liczb, współczynniki dwumianowe, funkcje tworzące, prawdopodobieństwo dyskretne i metody asymptotyczne. Główny nacisk jest położony nawet nie na twierdzenia egzystencjalne, czy myślenie kombinatoryczne, a na techniki rachunkowe. Celem książki jest bowiem zaznajomienie czytelnika z działaniami dyskretnymi (takimi jak część całkowita, czy sumowanie skończone) w podobnym stopniu, w jakim studiujący analizę matematyczną zapoznają się z działaniami ciągłymi (takimi jak wartość bezwzględna czy całkowanie).

Warto zauważyć, że przedstawiona lista zagadnień różni się zasadniczo od tego, co zwyczajowo jest wykładane pod nazwą »Matematyki Dyskretnej«. Potrzebujemy więc odrębnej nazwy, a »Matematyka Konkretna« okazała się nazwą równie wygodną, jak pozostałe powszechnie używane dla określenia innych dziedzin.

Początkowo podręcznikiem do stanfordzkiego wykładu był rozdział »Mathematical Preliminaries« z książki »The Art of Computer Programming«. Materiał zawarty na 110 stronach tego rozdziału był jednak zbyt zwięzły, więc trzeci z autorów (OP) wpadł na pomysł opracowania notatek uzupełniających, które przyjęły całkiem spore rozmiary. Książka ta stanowi rozwinięcie tych notatek. Jest to więc uzupełnienie wspomnianego rozdziału i bardziej przystępne wprowadzenie do materiału w nim zawartego. Niektóre znajdujące się tam zbyt zaawansowane części pominięto w tej książce, inne z kolei zagadnienia dodano dla pełności wywodu.

Autorzy mieli dużo satysfakcji przy tworzeniu tej książki, gdyż jej temat krzepł przed ich oczyma i zaczynał żyć swoim własnym życiem; w czasie pracy nad nią książka ta zdawała pisać się sama. Co więcej, przyjęte przez nas dość niekonwencjonalne metody przedstawienia materiału tak dobrze zaczęły do siebie pasować, ze — po latach doświadczeń — nie możemy oprzeć się wrażeniu, że książka ta jest rodzajem manifestu na temat tego, w jaki sposób powinno się uprawiać matematykę. Z naszego punktu widzenia książka ta jest bajką o matematycznym pięknie i przypadku. Mamy nadzieję, że czytelnicy podzielą z nami choć ε tej przyjemności, którą mieliśmy w trakcie tworzenia tej książki.

Książka ta powstała w środowisku uniwersyteckim, staraliśmy się więc oddać ducha współcześnie prowadzonych zajęć za pomocą nieformalnego stylu prezentacji materiału. Niektórzy uważają, że matematyka to przedsięwzięcie poważne i że musi w związku z tym być zimna i sucha. My jednak sądzimy, że matematyka jest zabawą i nie wstydzimy się tego ujawnić. W imię czego mielibyśmy oddzielać grubą kreską pracę od zabawy? Matematyka konkretna jest pełna pociągających wzorców; przekształcenia nie zawsze są łatwe, ale uzyskiwane odpowiedzi bywają zaskakująco atrakcyjne. Radości i smutki naszej matematycznej pracy są oddane tu wprost, gdyż są częścią naszego życia.

[…]

Obecne, drugie wydanie tej książki, zawiera nowy rozdział 5.8, który przedstawia pewne ważne pomysły odkryte przez Dorona Zeilbergera krótko po tym, jak pierwsze wydanie poszło do druku. Prawie na każdej stronie tego wydania można znaleźć poprawki w stosunku do wydania pierwszego.”

Spis treści

Przedmowa

Notacja

1. Problemy rekurencyjne

  1.1. Wieże z Hanoi

  1.2. Proste na płaszczyźnie

  1.3. Problem Józefa Flawiusza

  Ćwiczenia

2. Sumy

  2.1. Notacja

  2.2. Sumy i rekurencje

  2.3. Przekształcenia sum

  2.4. Sumy wielokrotne

  2.5. Metody ogólne

  2.6. Rachunek różnicowy i różniczkowy

  2.7. Sumy nieskończone

  Ćwiczenia

3. Funkcje całkowitoliczbowe

  3.1. Funkcje podłoga i sufit

  3.2. Użycie funkcji podłoga i sufit

  3.3. Rekurencje z podłogą i sufitem

  3.4. Działanie dwuargumentowe ‘mod’

  3.5. Sumy podłogi i sufitu

  Ćwiczenia

4. Teoria liczb

  4.1. Podzielność

  4.2. Liczby pierwsze

  4.3. Pierwsze przykłady

  4.4. Współczynniki rozkładu silni

  4.5. Liczby względnie pierwsze

  4.6. Relacja kongruencji ‘mod’

  4.7. Niezależne reszty

  4.8. Dalsze zastosowania

  4.9. Fi oraz mi

  Ćwiczenia

5. Współczynniki dwumianowe

  5.1. Podstawowe tożsamości

  5.2. Podstawowe ćwiczenia

  5.3. Podstawowe techniki

  5.4. Funkcje tworzące

  5.5. Funkcje hipergeometryczne

  5.6. Przekształcenia hipergeometryczne

  5.7. Częściowe sumy hipergeometryczne

  5.8. Sumowanie mechaniczne

  Ćwiczenia

6. Liczby szczególne

  6.1. Liczby Stirlinga

  6.2. Liczby Eulera

  6.3. Liczby harmoniczne

  6.4. Sumowanie harmoniczne

  6.5. Liczby Bernoulliego

  6.6. Liczby Fibonacciego

  6.7. Kontynuanty

  Ćwiczenia

7. Funkcje tworzące

  7.1. Teoria domina i rozmieniania

  7.2. Podstawowe techniki

  7.3. Rozwiązywanie rekurencji

  7.4. Szczególne funkcje tworzące

  7.5. Sploty

  7.6. Wykładnicze funkcje tworzące

  7.7. Funkcje tworzące Dirichleta

  Ćwiczenia

8. Prawdopodobieństwo dyskretne

  8.1. Definicje

  8.2. Wartość oczekiwana i wariancja

  8.3. Funkcje tworzące prawdopodobieństwa

  8.4. Rzucanie monetą

  8.5. Haszowanie

  Ćwiczenia

9. Asymptotyka

  9.1. Hierarchia

  9.2. Notacja O

  9.3. Przekształcenia typu O

  9.4. Dwie sztuczki asymptotyczne

  9.5. Wzór sumacyjny Eulera

  9.6. Końcowe sumowania

  Ćwiczenia

A. Odpowiedzi do ćwiczeń

B. Bibliografia

C. Źródła ćwiczeń

Skorowidz

Wykaz tabel