Impressum

Autoren

Ronald Lewis Graham
Ronald Lewis Graham
wurde am 31. Oktober 1936 in Taft (Kalifornien) geboren. Er leistete bahnbrechende Arbeiten auf dem Gebiet der diskreten Mathematik, insbesondere der Ramsey-Theorie. Graham ist auch bekannt für seine Unterstützung des Konzepts der Erdös-Zahl, die den Ko-Autorenabstand jedes Mathematikers bezogen auf Paul Erdös angibt. 1962 erlangte Graham seinen Doctor of Philosophy in Mathematik an der University of California, Berkeley. Verheiratet ist er mit der Professorin Fan Chung. 1979 wettete er mit Erdös, dass Erdös es nicht schaffen würde, einen Monat lang keine Amphetamine zu nehmen. Erdös gewann zwar die Wette, begann aber nach dem besagten Monat sofort wieder mit seinem üblichen Konsum und warf Graham vor, den mathematischen Fortschritt um einen Monat aufgehalten zu haben.
Donald Ervin Knuth
Donald Ervin Knuth
erblickt am 10. Januar 1938 in Milwaukee (Bundesstaat Wisconsin) das Licht der Welt. Er begann 1956 zunächst Physik zu studieren, wandte sich dann aber entschlossen der Mathematik zu. 1960 zog es ihn an das California Institute of Technology, wo er 1963 in Mathematik promovierte. Danach wurde er an diesem Institut Assistenzprofessor und später ordentlicher Professor. 1961 heiratete Knuth und bekam mit seiner Frau zwei Kinder. In den sechziger Jahren beschäftigte sich Knuth mit Algorithmen für das Lösen von algebraischen, kombinatorischen und analytischen Problemen. Zu dieser Zeit begann er auch mit den Arbeiten an der Bibel für Informatiker "The Art of Computer Programming". Sein Werk umfasst derzeit drei Bände, wobei der vierte bald erscheinen wird. Insgesamt sollen es sieben Bände werden, die er bis 2015 abschliessen möchte. Legendär ist auch sein Textsetzungssystem TeX, dass er eigens für dieses mehrbändige Komposium entwickelte. Heute ist Donald Knuth emeritierter Professor für Informatik an der Stanford University, was bedeutet, dass er weiterhin noch Doktoranten betreut.
Oren Patashnik
Oren Patashnik
wurde 1954 geboren. Es ist relativ wenig bekannt über ihn. Er studierte an der Yale University und arbeitete später unter Donald Knuth an der Stanford University. Aktuell forscht er am Center for Communications Research in La Jolla, einem Stadtteil San Diegos.

Concrete Mathematics

A Foundation for Computer Science

 
Concrete Mathematics Vergrößern 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 epsilon 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

  1. Recurrent Problems
    • The Tower of Hanoi
    • Lines in the Plane
    • The Josephus Problem
    • Exercises
  2. Sums
    • Notation
    • Sums and Recurrences
    • Manipulation of Sums
    • Multiple Sums
    • General Methods
    • Finit and Infinite Calculus
    • Infinite Sums
    • Exercises
  3. Integer Functions
    • Floors and Ceilings
    • Floor/Ceiling Applications
    • FloorCeiling Recurrences
    • ‘mod’: The Binary Operation
    • Floor/Ceiling Sums
    • Exercises
  4. Number Theory
    • Divisibility
    • Primes
    • Prime Examples
    • Factorial Factors
    • Relative Primality
    • ‘mod’: The Congruence Relation
    • Independent Residues
    • Additional Applications
    • Phi and Mu
    • Exercises
  5. Binomial Coefficients
    • Basic Identities
    • Basic Practice
    • Tricks of the Trade
    • Generating Functions
    • Hypergeometric Functions
    • Hypergeometric Transformations
    • Partial Hypergeometric Sums
    • Mechanical Summation
    • Exercises
  6. Special Numbers
    • Stirling Numbers
    • Eulerian Numbers
    • Harmonic Numbers
    • Harmonic Summations
    • Bernoulii Numbers
    • Fibonacci Numbers
    • Continuants
    • Exercises
  7. Generating Functions
    • Domino Theory and Change
    • Basic Maneuvers
    • Solving Recurrences
    • Special Generating Functions
    • Convolutions
    • Exponential Generating Functions
    • Dirichlet Generating Functions
    • Exercises
  8. Discrete Probability
    • Definitions
    • Mean and Variance
    • Probability Generating Functions
    • Flipping Coins
    • Hashing
    • Exercises
  9. Asymptotics
    • A Hierachy
    • O Notation
    • O Manipulation
    • Two Asymptotic Tricks
    • Euler’s Summation Formula
    • Final Summations
    • Exercises
  10. Answers to Exercises
  11. Bibliography
 
Lesen Sie Rezensionen von anderen Lesern bei Amazon.