![]() ![]() |
Dieses Buch ist das außergewöhnlichste mathematische Juwel, das einem Mathematik- oder Informatikstudenten während seiner Ausbildung in die Hände fallen kann. Aber auch für die, die nach dem Studium die Lust am Lösen von mathematischen Problemen nicht verloren haben oder wiederentdecken wollen, vermittelt es eine solide und komfortable Basis mathematischer Fertigkeiten, wobei bewußt auf die Aneinanderreihung von Theoremen verzichtet wird. Viele Themen entspringen der klassischen Literatur zur Diskreten Mathematik und der erfrischenden und humorvollen Stil der drei Autoren macht die sonst so abstrakte Welt der Mathematik sehr lebendig. ![]() |
Allgemeines zum Buch
Basierend auf einer Vorlesung, die seit 1970 an der Standford University gehalten wird, fesselt dieses Werk auf 657 Seiten den Leser mit seinem unkonventionellen lockeren Stil. Neben vielen berühmten Zitaten von Mathematikern vergangener Generationen hält der Seitenrand witzige Sprüche und Hinweise der Studenten bereit. Diesbezüglich bemerken die Autoren: “Some of these marginal markings are merely cory, some are profound; […] others are typical comments made by ‘wise’ guys in the back row.”
Auch wenn das Buch in englischer Sprache verfasst ist, so macht das Lesen auch ohne besondere Sprachkenntnisse Spaß, da immer wieder der Humor der Autoren durchdringt: “So we think the book has turned out to be a tale of mathematical beauty and surprise, and we hope that our reader will share at least of the pleasure we had while writing it.”
Am Ende jedes Kapitels findet man insgesamt 587 Übungen, die in verschiedene Kategorien (Aufwärm-Übungen, Grundaufgaben, Hausaufgaben, Prüfungsaufgaben, Bonus-Aufgaben, Forschungsprobleme) unterteilt sind. Da zu jeder Übung dessen Lösung oder zumindest Hinweise und Denkanstöße gegeben werden, ist dieses Buch ein Unicum und absolut empfehlenswert.
Wie bei allen Projekten, die Knuth angeht, scheint auch hier sein Perfektionismus durch. Verspricht er doch jedem Leser, der als Erster einen beliebigen Fehler findet – sei er logischer, historischer oder auch orthografischer Natur – $ 2.56.
Zum Inhalt des Buches
Recurrent Problems. Als einführendes Beispiel für das Lösen von Problemen mit rekursiven Methoden dienen den drei Autoren die schon oft zitierten “Türme von Hanoi”. Sehr anschaulich und strukturiert wird dieses Problem studiert. Dabei geht es den Autoren vielmehr darum, dem Leser zu zeigen, wie ein Vielzahl von Problemen geknackt werden können. In späteren Übungen wird das “Türme von Hanoi”-Problem immer wieder leicht modifiziert, wobei die erlernten Techniken direkt angewendet werden können.
Bei einem weiteren Problem geht es um die Bestimmung der minimale Anzahl von Gebieten, die mit einer festen Anzahl Geraden in der Ebene erzeugt werden können. Auch werden später Varianten dieses Problems in den Übungen vorgestellt.
Höhepunkt dieses Kapitels bildet das so genannte “Josephus Problem”. Dabei stehen n Männer (nummeriert von 1 bis n) im Kreis. Fortlaufend wird – beginnend beim ersten Mann – jeder Zweite exekutiert, bis es nur noch einen Überlebenden gibt. Die Nummer des Überlebenden ist die n-te Josephus Zahl. Die anfangs sehr chaotisch wirkende Josephus-Folge stellt sich doch als relativ harmlos heraus. Das sich aus dem Problem ergebene rekursive Gleichungssystem wird schließlich verallgemeinert und mit der Repertoire-Methode gelöst.
Sums. Überall in der Mathematik tauchen Summen auf. Ob sie nun endlich oder unendlich sind, Summen lassen oft Mathematiker gegen Stonewalls laufen. Dieses Kapitel vermittelt neben der Notation und den grundlegenden Techniken zur Manipulation dieser einen sehr interessante Ansatz mit dem Namen “Finite Calculus”. Dieser Kalkül stellt das endliche Pedant zur Ableitung bereit, wobei Summen den Integralen in der Infinitesimalrechnung entsprechen.
Integer Functions. Ganze Zahlen stellen das Rückgrat der Diskreten Mathematik dar, und oft werden reellen Zahlen oder Brüche in ganze Zahlen konvertiert. Ziel dieses Kapitels ist es, dem Leser die bemerkenswerten Eigenschaften solcher Umwandlungen besonders in Kombination mit Summen näher zu bringen. Sind erst einmal die Basics zum Ab- und Aufrunden vermittelt, zeigen die Autoren die Anwendung bei rekursionen Problemen. Man muss zugeben, dass diese Kapitel ein wenig trocken geraten ist, aber die darauf folgenden Kapitel entschädigen.
Number Theory. Das vorangegangene Kapitel hat den Einstieg in die Zahlentheorie gemeistert. Doch erst mit der Definition der Teilbarkeit und der Untersuchung der Primzahlen treten wir in die Spuren von Gauss, Euler und anderen Mathematikern, die sich unter anderem der reinen Mathematik verschrieben haben.
Binomial Coefficients. Nicht selten tauchen bei kombinatorischen Abzählproblemen die praktischen Binomialkoeffizienten auf. Diese sind hier Gegenstand der Untersuchung, wobei eine Vielzahl von verblüffenden Identitäten enthalten sind. Das in diesem Buch wichtigste Konzept die erzeugenden Funktionen (generating functions) werden hier erstmals motiviert und später im siebten Kapitel ausführlich eingeführt, untersucht und angewendet.
Special Numbers. Einige Zahlenfolgen tauchen in der Mathematik in so vielfältigen Zusammenhängen auf, dass Mathematiker ihnen speziellen Namen geben. In den vorangegangenen Kapiteln blitzen solche fundamentalen Zahlenfolgen hier und da auf. Dieses Kapitel enthält weitere Folgen, wie zum Beispiel die Stirling-Zahlen und die Eulerschen Zahlen, die jeweils wie die Binomialkoeffizienten durch eine dreieckige Zahlenformation veranschaulicht werden können. Darüber hinaus werden die Fibonacci-Zahlen, die Bernoulli-Zahlen und die harmonischen Zahlen unter die Lupe genommen.
Generating Functions. Erzeugende Funnktion liefern ein wichtiges Hilfsmittel zum Lösen von Rekursionen und Differenzengleichungen. Dabei wird versucht, zu einer Zahlenfolge eine analytische Funktion, die als erzeugende Funktion bezeichnet wird, zu finden, die mit den Koeffizienten ihrer Potenzreihe übereinstimmt. Diese Verbindung von Diskreter Mathematik und Funktionentheorie erlaubt es, die Manipulationen von Zahlenfolge als Operationen von ihren entsprechenden erzeugenden Funktionen auszudrücken.
Discrete Probability. Viele Vorgänge im wahren Leben sind nicht vorhersagbar: Münzen werfen, Zerfallsprozesse oder Risikomanagment. Es wird in diesem Kapitel eine solide aber knappe Einführung in die Wahrscheinlichkeitsrechnung gegeben. Dabei verstehen die Autoren wiederum, den formalen Kalkül durch intuitive Notation dem Leser näher zu bringen. Die Übungen zu diesem Kapitel zeichnet sich durch viele witzig gestellte Probleme aus.
Asymptotics. Eine exakte Antwort auf ein Problem ist großartig, wenn wir sie finden können. Doch viele Probleme, speziell das Finden einer geschlossenen Form für gewissen Summen, lassen uns auch mit sehr mächtigen Methoden gegen Wände laufen. Dann ist es Zeit für Approximationen. Aber selbst, wenn wir eine geschlossene Form gefunden haben, kann unser Wissen nicht vollständig sein. Mit der O-Notation konzentriert man sich auf die wesentlichen Terme einer Funktion und betrachtet ihr Wachstum im Unendlichen.
Inhaltsverzeichnis