Concrete Mathematics

From Wikipedia, the free encyclopedia

Concrete Mathematics: A Foundation for Computer Science
The cover displays the mathematical symbol for summation, ∑, inscribed in concrete.
Author	Ronald Graham, Donald Knuth, and Oren Patashnik
Country	United States
Language	English
Genre	Mathematics Computer science
Publisher	Addison–Wesley
Publication date	1994
Media type	Print (Hardcover)
Pages	657 pp (Second Edition)
ISBN	0-201-55802-5
OCLC	29357079
Dewey Decimal	510 20
LC Class	QA39.2 .G733 1994

Concrete Mathematics: A Foundation for Computer Science, by Ronald Graham, Donald Knuth, and Oren Patashnik, is a textbook that is widely used in computer-science departments.

Contents and history

The book provides mathematical knowledge and skills for computer science, especially for the analysis of algorithms. According to the preface, the topics in Concrete Mathematics are "a blend of CONtinuous and disCRETE mathematics." Calculus is frequently used in the explanations and exercises. The term "concrete mathematics" also denotes a complement to "abstract mathematics".

The book is based on a course begun in 1970 by Knuth at Stanford University. The book expands on the material in the "Mathematical Preliminaries" section of Knuth's The Art of Computer Programming. Consequently, some readers use it as an introduction to that famous series of books.

Concrete Mathematics has an informal and often humorous style. The authors reject what they see as the dry style of most mathematics textbooks. The margins contain "mathematical graffiti", comments submitted by the text's first editors: Knuth and Patashnik's students at Stanford.

As with many of Knuth's books, readers are invited to claim a reward for any error found in the book—in this case, whether an error is "technically, historically, typographically, or politically incorrect."^[1]

The book has popularized a lot of mathematical notation. This includes Iverson bracket, Floor and ceiling functions and notation for rising and falling factorials.

Typography

Donald Knuth used the first edition of Concrete Mathematics as a test case for the AMS Euler typeface and Concrete Roman font.^[2]

Chapter outline

Recurrent Problems
Summation
Integer Functions
Number Theory
Binomial Coefficients
Special Numbers
Generating Functions
Discrete Probability
Asymptotics

Editions

First Edition: September 1988 (ISBN 0-201-14236-8): Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1989). Concrete Mathematics. Advanced Book Program (First ed.). Reading, MA: Addison-Wesley Publishing Company. pp. xiv+625. ISBN 0-201-14236-8. MR 1001562.
Second Edition: February 1994 (ISBN 0-201-55802-5): Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1994). Concrete Mathematics (Second ed.). Reading, MA: Addison-Wesley Professional. pp. xiv+657. ISBN 0-201-55802-5. MR 1397498.

Notes

↑ Graham, Knuth and Patashnik: Concrete Mathematics
↑ Donald E. Knuth. Typesetting Concrete Mathematics, TUGboat 10 (1989), 31–36, 342. Reprinted as chapter 18 of the book Digital Typography.

External links

v t e Donald Knuth

Publications	The Art of Computer Programming "The Complexity of Songs" Computers and Typesetting Concrete Mathematics Surreal Numbers Things a Computer Scientist Rarely Talks About Selected papers series

Software	TeX MIXAL (MIX MMIX GNU MDK)

Fonts	AMS Euler Computer Modern Metafont

Literate programming	WEB CWEB

Algorithms	Knuth's Algorithm X Knuth–Bendix completion algorithm Knuth–Morris–Pratt algorithm Knuth shuffle Robinson–Schensted–Knuth correspondence Trabb Pardo–Knuth algorithm Generalization of Dijkstra's algorithm

Other	Dancing Links Knuth reward check Knuth Prize Man or boy test Quater-imaginary base -yllion Potrzebie system of weights and measures

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.