Concrete Mathematics

A Foundation for Computer Science

Concrete Mathematics - A Foundation for Computer Science

Ronald L. Graham, Donald E. Knuth, Oren Patashnik

This book introduces the mathematics that supports advanced computer programming and the analysis of algorithms. The primary aim of its well-known authors is to provide a solid and relevant base of mathematical skills - the skills needed to solve complex problems, to evaluate horrendous sums, and to discover subtle patterns in data. It is an indispensable text and reference not only for computer scientists - the authors themselves rely heavily on it! - but for serious users of mathematics in virtually every discipline.

Concrete Mathematics is a blending of CONtinuous and disCRETE mathematics. "More concretely," the authors explain, "it is the controlled manipulation of mathematical formulas, using a collection of techniques for solving problems." The subject matter is primarily an expansion of the Mathematical Preliminaries section in Knuth's classic Art of Computer Programming, but the style of presentation is more leisurely, and individual topics are covered more deeply. Several new topics have been added, and the most significant ideas have been traced to their historical roots. The book includes more than 500 exercises, divided into six categories. Complete answers are provided for all exercises, except research problems, making the book particularly valuable for self-study.

Major topics include:

  • Sums
  • Recurrences
  • Integer functions
  • Elementary number theory
  • Binomial coefficients
  • Generating functions
  • Discrete probability
  • Asymptotic methods

This second edition includes important new material about mechanical summation. In response to the widespread use of the first edition as a reference book, the bibliography and index have also been expanded, and additional nontrivial improvements can be found on almost every page. Readers will appreciate the informal style of Concrete Mathematics. Particularly enjoyable are the marginal graffiti contributed by students who have taken courses based on this material. The authors want to convey not only the importance of the techniques presented, but some of the fun in learning and using them.

Repertoire Method for Solving Recurrences

《具体数学:计算机科学基础(第二版)》第一章的“约瑟夫问题”中,介绍了一种求解递归式的奇妙技巧 —— Repertoire Method。这种技巧帮助我们将特殊解推向一般解:通过一些已知其解的参数函数,从特殊的情形推向一般的情形。


A Variation of Hanoi Problem

这道题目来自《具体数学:计算机科学基础(第二版)》第一章习题中“热身题”部分的第二题:把有 N 个圆盘的塔从左边的桩柱 A 移动到右边的桩柱 B,不允许在 A 和 B 之间直接移动,求最短的移动序列(每一次移动都必须是移动到中间的桩柱或者从中间的桩柱移出。较大的圆盘永远不能放在较小的圆盘的上面)。