算法之道(让你学不会算法都难)(china-pub首发)(版权输出至台湾)
基本信息
- 作者: 邹恒明
- 出版社:机械工业出版社
- ISBN:9787111294948
- 上架时间:2010-1-29
- 出版日期:2010 年2月
- 开本:16开
- 页码:292
- 版次:1-1
- 所属分类:
计算机 > 计算机科学理论与基础知识 > 计算理论 > 算法
编辑推荐
揭橥算法之道,求开智慧之门
逻辑演绎、生活归纳、趣味交织、入木三分地揭示算法的奥妙。
新的角度、新的分析、新的境界、耳目一新地阐述算法的精华。
推荐阅读
内容简介回到顶部↑
作译者回到顶部↑
目录回到顶部↑
前言
第一篇 算法基础篇
第1章 从无有到无穷 2
1.1 意念与现实 3
1.2 什么是算法 4
1.3 算法的表示 6
1.4 算法之魂 7
1.5 如何比较速度 8
1.6 算法与计算机的关系 9
1.7 算法的范畴 10
1.8 为什么学习算法 10
思考题 11
第2章 计数与渐近 12
2.1 算法的分析 12
2.1.1 正确性分析 13
2.1.2 时空效率分析 14
2.1.3 时空特性分析 14
2.2 计数:算法分析的核心 14
2.3 算法设计 15
2.4 算法效率表示 16
第一篇 算法基础篇
第1章 从无有到无穷 2
1.1 意念与现实 3
1.2 什么是算法 4
1.3 算法的表示 6
1.4 算法之魂 7
1.5 如何比较速度 8
1.6 算法与计算机的关系 9
1.7 算法的范畴 10
1.8 为什么学习算法 10
思考题 11
第2章 计数与渐近 12
2.1 算法的分析 12
2.1.1 正确性分析 13
2.1.2 时空效率分析 14
2.1.3 时空特性分析 14
2.2 计数:算法分析的核心 14
2.3 算法设计 15
2.4 算法效率表示 16
前言回到顶部↑
起初神创造天地。地是空虚混沌,渊面黑暗;神的灵运行在水面上。神说:“要有光”。就有了光。神看光是好的,就把光与暗分开了。神称光为昼,暗为夜。有晚上,有早晨,这是头一日。
......
神就照着自己的形象造人,
......
神说:“看哪!我将遍地上一切结种子的菜蔬,和一切树上所结有核的果子,全赐给你们作食物。至于地上的走兽和空中的飞鸟,以及各样爬在地上有生命的物,我将青草赐给它们作食物”。事就这样成了。
神看着一切所造的都甚好。有晚上,有早晨,是第6日。天地万物都造齐了。
图1 米开朗基罗创作的西斯廷教堂穹顶画《创世纪》。这幅画里隐含着算法
6天
圣经上写着:神6天创造天地万有,第7日安歇。
对于神创论者来说,这是不可怀疑的事实。但对于进化论者来说,6天创造一切根本就不可能。
作为一本算法书,我们当然不打算加入到神创论者和进化论者的永无休止的争论当中去。我们关心的是这么一个问题:圣经上为什么给出的是6天,而不是其他的时间长度。不管是神创论者还是进化论者,弄清楚6这个数字的来历很可能会对己方的观点有所帮助。在这6天里,神将他的创作方程式重复了6次,每天1次。对于全能的神来说,他完全可以在1天、1秒或者任何他所愿意的时间长度里创造天地万物,但却为什么是不多不少的6天呢?而不管圣经上的 “1天”是多长,这个问题都是值得讨论的。
我们知道,任何一个自然数的约数中都有1和它本身,而所有小于它本身的因数叫做这个自然数的真约数。例如,6的所有真约数是1、2、3;8的真约数是1、2、4。如果一个数的真约数之和等于这个自然数本身,则这个自然数就称为完全数,或者完美数。例如,6 = 1+2+3,因此6是完美数;而8 ( 1+2+4,因此8不是完美数。因此,神6天创造世界,暗示着该创造是完美的!
以完美数来昭示创造的完美,似乎合情合理。但问题是,完美数只有6这一个数吗?如果不是,为什么不使用其他的完美数呢?答案是,完美数虽然不止有6这一个,但确实数量稀少。一直到现在(2009年6月),数学家们探索了2600年,并且现代数学家们还借助了超级计算机,但也仅仅找到了47个完美数。其中第1个完美数是6,接下来的4个完美数分别是: 28、496、8128、33 550 336。而第47个完美数有25 956 377个数位,(注意,是数位,不是数值!)它的数值为:243 112 608 × (243 112 609 ? 1)。
完美数的稀少昭示着达到完美的难度,而神选择6天来创造天地万有也许是因为6是最小的完美数,即创造天地万有对于神来说是轻而易举的一件事情……
完美与算法
完美数由于其各种神秘属性(真约数之和等于自身只是其中的一个性质)而受到了特殊的关注。但到底哪些数是完美数则不是一件容易判断的事情。显然,按照完美数的定义,判断一个数是否是完美数的不二法则是找出它的所有真约数,然后求和看看其是否等于自身。然而这种方法效率太过低下,因为这意味着因式分解,而这是十分困难的(本书后面将会讨论到这个问题)。
如果判断一个数是否是完美数就已经非常困难,那么要找出所有的完美数则更是一个难上加难的任务。因为这就意味着将所有的数进行上面描述的判断验证:因式分解。这似乎是人类不可能完成的任务。即使用世界上超大的计算机来进行计算,情况也不会有任何数量级的改善。
显然,我们需要新的解决方案,而不是发明或使用新的计算工具!研究这样的问题就可以归结到算法的范畴里,因为如何高效地解决问题正是算法要研究的核心课题。
有意思的是,判断和搜索完美数是算法的研究范畴,而算法本身的追求却也是“完美”(见图2)。
图2 算法所追求的理想就是完美
......
神就照着自己的形象造人,
......
神说:“看哪!我将遍地上一切结种子的菜蔬,和一切树上所结有核的果子,全赐给你们作食物。至于地上的走兽和空中的飞鸟,以及各样爬在地上有生命的物,我将青草赐给它们作食物”。事就这样成了。
神看着一切所造的都甚好。有晚上,有早晨,是第6日。天地万物都造齐了。
图1 米开朗基罗创作的西斯廷教堂穹顶画《创世纪》。这幅画里隐含着算法
6天
圣经上写着:神6天创造天地万有,第7日安歇。
对于神创论者来说,这是不可怀疑的事实。但对于进化论者来说,6天创造一切根本就不可能。
作为一本算法书,我们当然不打算加入到神创论者和进化论者的永无休止的争论当中去。我们关心的是这么一个问题:圣经上为什么给出的是6天,而不是其他的时间长度。不管是神创论者还是进化论者,弄清楚6这个数字的来历很可能会对己方的观点有所帮助。在这6天里,神将他的创作方程式重复了6次,每天1次。对于全能的神来说,他完全可以在1天、1秒或者任何他所愿意的时间长度里创造天地万物,但却为什么是不多不少的6天呢?而不管圣经上的 “1天”是多长,这个问题都是值得讨论的。
我们知道,任何一个自然数的约数中都有1和它本身,而所有小于它本身的因数叫做这个自然数的真约数。例如,6的所有真约数是1、2、3;8的真约数是1、2、4。如果一个数的真约数之和等于这个自然数本身,则这个自然数就称为完全数,或者完美数。例如,6 = 1+2+3,因此6是完美数;而8 ( 1+2+4,因此8不是完美数。因此,神6天创造世界,暗示着该创造是完美的!
以完美数来昭示创造的完美,似乎合情合理。但问题是,完美数只有6这一个数吗?如果不是,为什么不使用其他的完美数呢?答案是,完美数虽然不止有6这一个,但确实数量稀少。一直到现在(2009年6月),数学家们探索了2600年,并且现代数学家们还借助了超级计算机,但也仅仅找到了47个完美数。其中第1个完美数是6,接下来的4个完美数分别是: 28、496、8128、33 550 336。而第47个完美数有25 956 377个数位,(注意,是数位,不是数值!)它的数值为:243 112 608 × (243 112 609 ? 1)。
完美数的稀少昭示着达到完美的难度,而神选择6天来创造天地万有也许是因为6是最小的完美数,即创造天地万有对于神来说是轻而易举的一件事情……
完美与算法
完美数由于其各种神秘属性(真约数之和等于自身只是其中的一个性质)而受到了特殊的关注。但到底哪些数是完美数则不是一件容易判断的事情。显然,按照完美数的定义,判断一个数是否是完美数的不二法则是找出它的所有真约数,然后求和看看其是否等于自身。然而这种方法效率太过低下,因为这意味着因式分解,而这是十分困难的(本书后面将会讨论到这个问题)。
如果判断一个数是否是完美数就已经非常困难,那么要找出所有的完美数则更是一个难上加难的任务。因为这就意味着将所有的数进行上面描述的判断验证:因式分解。这似乎是人类不可能完成的任务。即使用世界上超大的计算机来进行计算,情况也不会有任何数量级的改善。
显然,我们需要新的解决方案,而不是发明或使用新的计算工具!研究这样的问题就可以归结到算法的范畴里,因为如何高效地解决问题正是算法要研究的核心课题。
有意思的是,判断和搜索完美数是算法的研究范畴,而算法本身的追求却也是“完美”(见图2)。
图2 算法所追求的理想就是完美
评论交流
共有61人开贴评论 71人参与评论 29人参与打分 查看
评价等级:





发表于:2010-4-1 13:26:00
这本书是帮朋友买的,在把书给朋友之前我自己草草的通读了一遍。
书中所写的也算新颖,但是就所讲内容而言,绝对与china-pub给出的副标题严重不符!什么“让你学不会算法都难”……
书中对一些算法的本质描述倒是很有意思,就像读故事一样。噼里啪啦举例子摆论证,说了一大堆,让你兴致盎然。可是一涉及到算法的描述上依然和那些算法教科书没有任何区别——劈头就是令人无可奈何的数学公式。就这一点上说来,与其说这本书虎头蛇尾。倒不如说这本书也有着一副无可奈何的表情。数学……你要学算法,不可能不学数学。
如果你被副标题所吸引,“让不学不会算法都难”,那就听我的。掂量掂量自己数学水平……如果连离散数学都没搞明白,放下这本书,先买本《离散数学及其应用》吧。
如果数学水平还算过得去,去买《算法导论》吧。
如果数学水平也不错,基础算法也了熟于胸,并且想在算法的讨论上找点乐子,我才推荐你买这本书……
书本的质量非常不错,纸张也很有质感,这是值得表扬的。
书中所写的也算新颖,但是就所讲内容而言,绝对与china-pub给出的副标题严重不符!什么“让你学不会算法都难”……
书中对一些算法的本质描述倒是很有意思,就像读故事一样。噼里啪啦举例子摆论证,说了一大堆,让你兴致盎然。可是一涉及到算法的描述上依然和那些算法教科书没有任何区别——劈头就是令人无可奈何的数学公式。就这一点上说来,与其说这本书虎头蛇尾。倒不如说这本书也有着一副无可奈何的表情。数学……你要学算法,不可能不学数学。
如果你被副标题所吸引,“让不学不会算法都难”,那就听我的。掂量掂量自己数学水平……如果连离散数学都没搞明白,放下这本书,先买本《离散数学及其应用》吧。
如果数学水平还算过得去,去买《算法导论》吧。
如果数学水平也不错,基础算法也了熟于胸,并且想在算法的讨论上找点乐子,我才推荐你买这本书……
书本的质量非常不错,纸张也很有质感,这是值得表扬的。
| 我要写评论 |
| 查看所有评论交流(共61条) |








点击看大图






加载中...
