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

具体数学 计算机科学基础（第2版） 内容简介

“《具体数学》是一份‘纲领’，它的内容是我对于数学诸多方面应该如何教与学的思考。熟练掌握代数公式的基础技能，对我来说始终都是关键所在。这些内容在TAOCP里都有讨论，但只能是蜻蜓点水；在斯坦福大学的课程中，我得以深入更多的细节，而那些课程都被囊括在这本书中了。”

书中不仅讲述了数学问题和技巧，而且教导解决问题的方法，解说深入浅出，妙趣横生。大师们诙谐、细腻的笔触，描绘着数学工作中的欢乐和忧伤，那些或平淡、或深刻、或严肃、或幽默的涂鸦，更让我们在轻松愉悦的心境下体会数学的美妙。

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

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

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

第1章 递归问题

1.1 河内塔

1.2 平面上的直线

1.3 约瑟夫问题

习题

第2章 和式

2.1 记号

2.2 和式和递归式

2.3 和式的处理

2.4 多重和式

2.5 一般性的方法

2.6 有限微积分和无限微积分

2.7 无限和式

习题

第3章 整值函数

3.1 底和顶

3.2 底和顶的应用

3.3 底和顶的递归式

3.4 mod：二元运算

3.5 底和顶的和式

习题

第4章 数论

4.1 整除性

4.2 素数

4.3 素数的例子

4.4 阶乘的因子

4.5 互素

4.6 mod：同余关系

4.7 独立剩余

4.8 进一步的应用

4.9 函数和函数

习题

第5章 二项式系数

5.1 基本恒等式

5.2 基本练习

5.3 处理的技巧

5.4 生成函数

5.5 超几何函数

5.6 超几何变换

5.7 部分超几何和式

5.8 机械求和法

习题

第6章 特殊的数

6.1 斯特林数

6.2 欧拉数

6.3 调和数

6.4 调和求和法

6.5 伯努利数

6.6 斐波那契数

6.7 连项式

习题

第7章 生成函数

7.1 多米诺理论与换零钱

7.2 基本策略

7.3 解递归式

7.4 特殊的生成函数

7.5 卷积

7.6 指数生成函数

7.7 狄利克雷生成函数

习题

第8章 离散概率

8.1 定义

8.2 均值和方差

8.3 概率生成函数

8.4 抛掷硬币

8.5 散列法

习题

第9章 渐近式

9.1 量的等级

9.2 大O记号

9.3 O运算规则

9.4 两个渐近技巧

9.5 欧拉求和公式

9.6 最后的求和法

习题

附录A 习题答案

附录B 参考文献

附录C 习题贡献者

译后记

索引

表索引

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

我们首先探讨一个称为河内塔的精巧智力题，它是由法国数学家爱德华?卢卡斯于1883年发明的．给定一个由8个圆盘组成的塔，这些圆盘按照大小递减的方式套在三根桩柱中的一根上．

如果你从没有见过这个，请举手． 好的，其他人可以迅速转到式（1.1）.

我们的目的是要将整个塔移动到另一根桩柱上，每次只能移动一个圆盘，且较大的圆盘在移动过程中不能放置在较小的圆盘上面．

卢卡斯 给这个玩具赋予了一个罗曼蒂克的传说，说的是一个大得多的婆罗贺摩塔（Tower of Brahma），它由64个纯金的圆盘堆放在三座钻石做成的方尖塔上．他说，上帝一开始把这些金圆盘放到了第一座方尖塔上，并命令一组牧师按照上面的规则把它们移动到第三座方尖塔上．据说牧师们夜以继日地工作，当他们完成任务时，那座塔就将坍塌，世界也将毁灭．

金子——哇． 我们的圆盘是用混凝土（concrete）做成的吗？

这个智力题有解，只是并非显而易见，不过只要稍加思考（或者此前看见过这个问题）就能使我们确信的确如此．现在问题来了：我们能做到的最好的解法是什么？也就是说，要完成这项任务移动多少次才是必须且足够的？

解决这样问题的最好方法是对它稍加推广．婆罗贺摩塔有64个圆盘，河内塔有8个圆盘，让我们来考虑一下，如果有个圆盘将会怎样？

这样推广的一个好处是，我们可以大大简化问题．事实上，在本书中我们将反复看到，先研究小的情形是大有裨益的．移动只有一两个圆盘的塔十分容易．再通过少量的尝试就能看出如何移动有3个圆盘的塔．

求解问题的下一步是引入适当的记号：命名并求解．我们称是根据卢卡斯的规则将个圆盘从一根桩柱移动到另一根桩柱所需要的最少移动次数．那么，显然是1，而．考虑所有情形中最小的情形还可以轻松得到另一条信息，即显然有，因为一个有个圆盘的塔根本无需做任何挪动！聪明的数学家们不会羞于考虑小问题，因为当极端情形（即便它们是平凡的情形）弄得明明白白时，一般的形式就容易理解了．

现在让我们改变一下视角，来考虑大的情形：怎样才能移动一个大的塔呢？移动3个圆盘的试验表明，获胜的思路是将上面两个圆盘移动到中间的桩柱上，然后移动第三个圆盘，接着再把其余两个放到它上面．这就为移动个圆盘提供了一条线索：首先把个小的圆盘移动到一个不同的桩柱上（需要次移动），然后移动最大的圆盘（需要一次移动），最后再把那个小的圆盘移回到最大圆盘的上面（这需要另外的次移动）．这样，至多需要次移动就能移动（）个圆盘了：

这个公式用的是符号“”，而不是“ = ”，因为我们的构造仅仅证明了次移动就足够了，而没有证明次移动是必需的．智者或许能想到一条捷径．

还有更好的方法吗？实际上没有．我们迟早必须移动最大的那个圆盘．当我们这样做的时候，那个小的圆盘必须已经在某根桩柱上，而这至少需要次移动才能把它们放置到那儿．如果我们不太精明，则移动最大的圆盘可能会多于一次．但是在最后一次移动最大的那个圆盘之后，我们必须把那个小的圆盘（它们必须仍然在同一根桩柱上）移回到最大圆盘的上面，这也需要次移动．