Concrete Mathematics: A Foundation for Computer Science, by Ronald Graham, Donald Knuth, and Oren Patashnik, first published in 1989, is a textbook that is widely used in computer-science departments as a substantive but light-hearted treatment of the analysis of algorithms.
 | |
| Author | Ronald Graham, Donald Knuth, and Oren Patashnik |
|---|---|
| Language | English |
| Genre | Mathematics Computer science |
| Publisher | Addison–Wesley |
Publication date | 1994 |
| Publication place | United States |
| Media type | Print (Hardcover) |
| Pages | 657 pp (Second Edition) |
| ISBN | 0-201-55802-5 |
| OCLC | 29357079 |
| 510 20 | |
| LC Class | QA39.2 .G733 1994 |
Contents and history
editThe 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 (approximately 100 pages)[1] in the "Mathematical Preliminaries"[2] section of Knuth's The Art of Computer Programming. Consequently, some readers use it as an introduction to that 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".[3]
The book popularized some mathematical notation: the Iverson bracket, floor and ceiling functions, and notation for rising and falling factorials.
Typography
editDonald Knuth used the first edition of Concrete Mathematics as a test case for the AMS Euler typeface and Concrete Roman font.[4]
Chapter outline
editEditions
edit- Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (1989). Concrete Mathematics - A foundation for computer science. Advanced Book Program (1st ed.). Reading, MA, USA: Addison-Wesley Publishing Company. pp. xiv+625. ISBN 0-201-14236-8. MR 1001562.
- Graham, Ronald L.; Knuth, Donald E.; Patashnik, Oren (February 1994). Concrete Mathematics - A foundation for computer science (2nd ed.). Reading, MA, USA: Addison-Wesley Professional. pp. xiv+657. ISBN 0-201-55802-5. MR 1397498. Errata: [1] (1994), [2] (January 1998), [3] Archived 2020-11-06 at the Wayback Machine (27th printing, May 2013)
References
edit- ^ Stenger, Allen (18 November 2010). "Review of Concrete Mathematics: A Foundation for Computer Science, 2nd edition by Ronald L. Graham, Donald E. Knuth, and Oren Patashnik". MAA Reviews, Mathematical Association of America.
- ^ Knuth, Donald E. (1997). "Mathematical Preliminaries". The Art of Computer Programming, Volume 1. Fundamental Algorithms (3rd ed.). ISBN 9780321635747.
- ^ 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.