Concrete Mathematics

Last updated
Concrete Mathematics: A Foundation for Computer Science
Concrete Mathematics - Cover.png
The cover displays the mathematical symbol for  summation,  Σ, inscribed in  concrete.
Author Ronald Graham, Donald Knuth, and Oren Patashnik
LanguageEnglish
Subject Mathematics
Computer science
Publisher Addison–Wesley
Publication date
1994
Publication placeUnited States
Media typePrint (Hardcover)
Pages657 pp (Second Edition)
ISBN 0-201-55802-5
OCLC 29357079
510 20
LC Class QA39.2 .G733 1994

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.

Contents

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 (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

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

Chapter outline

  1. Recurrent Problems
  2. Summation
  3. Integer Functions
  4. Number Theory
  5. Binomial Coefficients
  6. Special Numbers
  7. Generating Functions
  8. Discrete Probability
  9. Asymptotics

Editions

Related Research Articles

<span class="mw-page-title-main">Algorithm</span> Sequence of operations for a task

In mathematics and computer science, an algorithm is a finite sequence of mathematically rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing calculations and data processing. More advanced algorithms can use conditionals to divert the code execution through various routes and deduce valid inferences.

In number theory, two integers a and b are coprime, relatively prime or mutually prime if the only positive integer that is a divisor of both of them is 1. Consequently, any prime number that divides a does not divide b, and vice versa. This is equivalent to their greatest common divisor (GCD) being 1. One says also ais prime tob or ais coprime withb.

<span class="mw-page-title-main">Donald Knuth</span> American computer scientist and mathematician (born 1938)

Donald Ervin Knuth is an American computer scientist and mathematician. He is a professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer science. Knuth has been called the "father of the analysis of algorithms".

<span class="mw-page-title-main">Discrete mathematics</span> Study of discrete mathematical structures

Discrete mathematics is the study of mathematical structures that can be considered "discrete" rather than "continuous". Objects studied in discrete mathematics include integers, graphs, and statements in logic. By contrast, discrete mathematics excludes topics in "continuous mathematics" such as real numbers, calculus or Euclidean geometry. Discrete objects can often be enumerated by integers; more formally, discrete mathematics has been characterized as the branch of mathematics dealing with countable sets. However, there is no exact definition of the term "discrete mathematics".

In mathematics, the factorial of a non-negative integer , denoted by , is the product of all positive integers less than or equal to . The factorial of also equals the product of with the next smaller factorial: For example, The value of 0! is 1, according to the convention for an empty product.

TeX, stylized within the system as TeX, is a typesetting program which was designed and written by computer scientist and Stanford University professor Donald Knuth and first released in 1978. The term now refers to the system of extensions – which includes software programs called TeX engines, sets of TeX macros, and packages which provide extra typesetting functionality – built around the original TeX language. TeX is a popular means of typesetting complex mathematical formulae; it has been noted as one of the most sophisticated digital typographical systems.

In theoretical computer science and mathematics, the theory of computation is the branch that deals with what problems can be solved on a model of computation, using an algorithm, how efficiently they can be solved or to what degree. The field is divided into three major branches: automata theory and formal languages, computability theory, and computational complexity theory, which are linked by the question: "What are the fundamental capabilities and limitations of computers?".

<i>The Art of Computer Programming</i> Books about algorithms by Donald Knuth

The Art of Computer Programming (TAOCP) is a comprehensive monograph written by the computer scientist Donald Knuth presenting programming algorithms and their analysis. Volumes 1–5 are intended to represent the central core of computer programming for sequential machines.

Big <i>O</i> notation Describes limiting behavior of a function

Big O notation is a mathematical notation that describes the limiting behavior of a function when the argument tends towards a particular value or infinity. Big O is a member of a family of notations invented by German mathematicians Paul Bachmann, Edmund Landau, and others, collectively called Bachmann–Landau notation or asymptotic notation. The letter O was chosen by Bachmann to stand for Ordnung, meaning the order of approximation.

<span class="mw-page-title-main">Robert Sedgewick (computer scientist)</span> American computer scientist

Robert Sedgewick is an American computer scientist. He is the founding chair and the William O. Baker Professor in Computer Science at Princeton University and was a member of the board of directors of Adobe Systems (1990–2016). He previously served on the faculty at Brown University and has held visiting research positions at Xerox PARC, Institute for Defense Analyses, and INRIA. His research expertise is in algorithm science, data structures, and analytic combinatorics. He is also active in developing college curriculums in computer science.

<span class="mw-page-title-main">Ronald Graham</span> American mathematician (1935–2020)

Ronald Lewis Graham was an American mathematician credited by the American Mathematical Society as "one of the principal architects of the rapid development worldwide of discrete mathematics in recent years". He was president of both the American Mathematical Society and the Mathematical Association of America, and his honors included the Leroy P. Steele Prize for lifetime achievement and election to the National Academy of Sciences.

<span class="mw-page-title-main">Fractional part</span> Excess of a non-negative real number beyond its integer part

The fractional part or decimal part of a non‐negative real number is the excess beyond that number's integer part. The latter is defined as the largest integer not greater than x, called floor of x or . Then, the fractional part can be formulated as a difference:

Addison–Wesley is an American publisher of textbooks and computer literature. It is an imprint of Pearson plc, a global publishing and education company. In addition to publishing books, Addison–Wesley also distributes its technical titles through the O'Reilly Online Learning e-reference service. Addison–Wesley's majority of sales derive from the United States (55%) and Europe (22%).

<span class="mw-page-title-main">Knuth reward check</span> Awards issued by computer scientist Donald Knuth

Knuth reward checks are checks or check-like certificates awarded by computer scientist Donald Knuth for finding technical, typographical, or historical errors, or making substantial suggestions for his publications. The MIT Technology Review describes the checks as "among computerdom's most prized trophies".

Jeffrey David Ullman is an American computer scientist and the Stanford W. Ascherman Professor of Engineering, Emeritus, at Stanford University. His textbooks on compilers, theory of computation, data structures, and databases are regarded as standards in their fields. He and his long-time collaborator Alfred Aho are the recipients of the 2020 Turing Award, generally recognized as the highest distinction in computer science.

In mathematics, the Iverson bracket, named after Kenneth E. Iverson, is a notation that generalises the Kronecker delta, which is the Iverson bracket of the statement x = y. It maps any statement to a function of the free variables in that statement. This function is defined to take the value 1 for the values of the variables for which the statement is true, and takes the value 0 otherwise. It is generally denoted by putting the statement inside square brackets: In other words, the Iverson bracket of a statement is the indicator function of the set of values for which the statement is true.

Oren Patashnik is an American computer scientist. He co-created BibTeX and co-authored Concrete Mathematics: A Foundation for Computer Science.

<span class="mw-page-title-main">Sylvester's sequence</span> Doubly exponential integer sequence

In number theory, Sylvester's sequence is an integer sequence in which each term is the product of the previous terms, plus one. Its first few terms are

<span class="mw-page-title-main">Computational complexity of mathematical operations</span> Algorithmic runtime requirements for common math procedures

The following tables list the computational complexity of various algorithms for common mathematical operations.

<span class="mw-page-title-main">Svante Janson</span> Swedish mathematician

Carl Svante Janson is a Swedish mathematician. A member of the Royal Swedish Academy of Sciences since 1994, Janson has been the chaired professor of mathematics at Uppsala University since 1987.

References

  1. 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.
  2. Knuth, Donald E. (1997). "Mathematical Preliminaries". The Art of Computer Programming, Volume 1. Fundamental Algorithms (3rd ed.). ISBN   9780321635747.
  3. Graham, Knuth and Patashnik: Concrete Mathematics
  4. Donald E. Knuth. Typesetting Concrete Mathematics , TUGboat 10 (1989), 3136, 342. Reprinted as chapter 18 of the book Digital Typography.