具体数学 计算机科学基础（第2版）

本书是一本在大学中广泛使用的经典数学教科书．书中讲解了许多计算机科学中用到的数学知识及技巧，教你如何把一个实际问题一步步演化为数学模型，然后通过计算机解决它，特别着墨于算法分析方面．其主要内容涉及和式、整值函数、数论、二项式系数、特殊的数、生成函数、离散概率、渐近式等，都是编程所必备的知识．另外，本书包括了六大类500  多道习题，并给出了所有习题的解答，有助读者加深书中内容的理解．

本书面向从事计算机科学、计算数学、计算技术诸方面工作的人员，以及高等院校相关专业的师生。

中文版致辞

图灵社区读者评论

前言

记号注释

1  递归问题  RECURRENT  PROBLEMS

1.1  河内塔

1.2  平面上的直线

1.3  约瑟夫问题

习题

作业题

考试题

2  和式  SUMS

2.1  记号  NOTATION

2.2  和式和递归式  SUMS  AND  RECURRENCES

2.3  和式的处理  MANIPULATION  OF  SUMS

2.4  多重和式  MULTIPLE  SUMS

2.5  一般性的方法  GENERAL  METHODS

2.6  有限微积分和无限微积分  FINITE  AND  INFINITE  CALCULUS

2.7  无限和式  INFINITE  SUMS

习题

3  整值函数  INTEGER  FUNCTIONS

3.1  底和顶  FLOORS  AND  CEILINGS

3.2  底和顶的应用  FLOOR/CEILING  APPLICATIONS

3.3  底和顶的递归式  FLOOR/CEILING  RECURRENCES

3.4  mod：二元运算  ‘MOD’：THE  BINARY  OPERATION

3.5  底和顶的和式  FLOOR/CEILING  SUMS

习题

4  数论  NUMBER  THEORY

4.1  整除性  DIVISIBILITY

4.2  素数  PRIMES

4.3  素数的例子  PRIME  EXAMPLES

4.4  阶乘的因子  FACTORIAL  FACTORS

4.5  互素  RELATIVE  PRIMALITY

4.6  mod：同余关系  ‘MOD’：THE  CONGRUENCE  RELATION

4.7  独立剩余  INDEPENDENT  RESIDUES

4.8  进一步的应用  ADDITIONAL  APPLICATIONS

4.9  函数和函数  PHI  AND  MU

习题

5  二项式系数  BINOMIAL  COEFFICIENTS

5.1  基本恒等式  BASIC  IDENTITIES

5.2  基本练习  BASIC  PRACTICE

5.3  处理的技巧  TRICKS  OF  THE  TRADE

5.4  生成函数  GENERATING  FUNCTIONS

5.5  超几何函数  HYPERGEOMETRIC  FUNCTIONS

5.6  超几何变换  HYPERGEOMETRIC  TRANSFORMATIONS

5.7  部分超几何和式  PARTIAL  HYPERGEOMETRIC  SUMS

5.8  机械求和法  MECHANICAL  SUMMATION

习题

6  特殊的数  SPECIAL  NUMBERS

6.1  斯特林数  STIRLING  NUMBERS

6.2  欧拉数  EULERIAN  NUMBERS

6.3  调和数  HARMONIC  NUMBERS

6.4  调和求和法  HARMONIC  SUMMATION

6.5  伯努利数  BERNOULLI  NUMBERS

6.6  斐波那契数  FIBONACCI  NUMBERS

6.7  连项式  CONTINUANTS

习题

7  生成函数  GENERATING  FUNCTIONS

7.1  多米诺理论与换零钱  DOMINO  THEORY  AND  CHANGE

7.2  基本策略  BASIC  MANEUVERS

7.3  解递归式  SOLVING  RECURRENCES

7.4  特殊的生成函数  SPECIAL  GENERATING  FUNCTIONS

7.5  卷积  CONVOLUTIONS

7.6  指数生成函数  EXPONENTIAL  GENERATING  FUNCTIONS

7.7  狄利克雷生成函数  DIRICHLET  GENERATING  FUNCTIONS

习题

8  离散概率  DISCRETE  PROBABILITY

8.1  定义  DEFINITIONS

8.2  均值和方差  MEAN  AND  VARIANCE

8.3  概率生成函数  PROBABILITY  GENERATING  FUNCTIONS

8.4  抛掷硬币  FLIPPING  COINS

8.5  散列法  HASHING

习题

9  渐近式  ASYMPTOTICS

9.1  量的等级  A  HIERARCHY

9.2  大O记号  O  NOTATION

9.3  O运算规则  O  MANIPULATION

9.4  两个渐近技巧  TWO  ASYMPTOTIC  TRICKS

9.5  欧拉求和公式  EULER\'S  SUMMATION  FORMULA

9.6  最后的求和法  FINAL  SUMMATIONS

习题

附录  A  习题答案  ANSWERS  TO  EXERCISES

附录  B  参考文献  BIBLIOGRAPHY

附录  C  习题贡献者  CREDITS  FOR  EXERCISES

译后记