计算与算法导论

第一部分
计算视角
第1章
技术、科学与文化的发展史 2
1.1
技术创新与人类进化 2
1.1.1
历史发展的模式 3
1.1.2
科学领域的范式变迁 3
1.1.3
范式变迁的特点 3
1.2
范式发展历史的概述 4
1.2.1
原始部族意识时代 4
1.2.2
字母表和抽象思维的萌芽 4
1.2.3
绝对抽象思维的时代 5
1.2.4
机械的媒体技术 6
1.2.5
“机械”思维的时代 7
1.2.6
电子媒体技术 7
1.3
最近几十年来技术发展回顾 8
1.3.1
社会形态变迁过程描述 8
1.3.2
正在形成中的社会形态的特征 9
1.3.3
新的社会形态的中心主题 10
1.4
正在形成中的社会形态 11
1.4.1
现象的算法概念 12
1.4.2
模拟和实验的方法 12
1.4.3
得到的启发 14
习题 16
第2章
算法模型 18
2.1
什么是算法 18
2.2
好算法的要素 21
2.2.1
精度 21
2.2.2
简单 21
2.2.3
抽象分级 22
2.3
算法与计算机 24
2.3.1
计算机做什么 24
2.3.2
计算机与二进制数据 24
2.3.3
计算机中的抽象分级 25
2.3.4
比较算法与计算机程序 27
2.3.5
比较数据与信息 27
2.4
算法组件 28
2.4.1
数据结构 28
2.4.2
数据操作指令 28
2.4.3
条件表达式 29
2.4.4
控制结构 29
2.4.5
模块 29
2.5
从计算视角看问题 30
2.5.1
用算法表达式构思行为 30
2.5.2
用过程构思展示行为的东西 30
2.5.3
用不同抽象等级构思算法 30
2.5.4
理解复杂度如何限制算法的有用性 31
2.5.5
撇开其他视角 32
小结 33
习题 34
第二部分
算法工具
第3章
基本数据与操作 38
3.1
算法语言 38
3.2
创建简单变量 39
3.2.1
变量标识符 40
3.3
运算符 40
3.3.1
赋值运算符 40
3.3.2
基本操作 41
3.3.3
输入/输出运算符 42
3.4
原子数据类型 44
3.4.1
数字型 44
3.4.2
字符 44
3.4.3
布尔型 45
3.4.4
指针型 45
3.5
复杂数据类型 45
3.5.1
字符串 45
3.5.2
其他复杂数据类型 46
3.6
变量声明和初始化 46
3.6.1
数据声明的位置 46
3.6.2
选择标识符名字 46
3.6.3
初始化变量 46
3.7
固定的数据 47
3.7.1
常量 47
3.7.2
文字值 47
3.8
一般规则 48
3.8.1
算法的一般结构 48
3.8.2
标识符格式 49
3.8.3
类型匹配 49
3.9
算法判定 50
3.9.1
基本判定 50
3.9.2
判定与数据类型 51
3.9.3
判定活动 51
3.9.4
复杂判定与布尔操作比较 54
3.9.5
嵌套的判定 56
小结 59
习题 59
第4章
过程抽象的方法 62
4.1
基本思想 62
4.2
根据什么模块化 63
4.3
对模块接口的需要 63
4.3.1
参数 64
4.3.2
参数的三种基本类型 64
4.4
模块的创建和使用 64
4.4.1
创建过程和函数 65
4.4.2
调用过程和函数 67
4.4.3
使用多个参数 68
4.5
参数表 71
4.6
数据作用域 71
4.6.1
作用域的三种有效范围 72
4.6.2
变量的作用域 72
4.6.3
常量作用域 72
4.7
参数的类型 73
4.7.1
输入参数 74
4.7.2
输出参数 75
4.7.3
输入/输出参数 78
4.8
较大的范例 80
4.9
过程抽象的重要性 83
4.9.1
编写算法 83
4.9.2
测试代码 84
4.9.3
维护代码 85
4.9.4
重用逻辑 85
4.9.5
在不同算法中重用编码 87
4.10 递归控制 87
4.10.1 递归的两种形式 88
4.10.2 跟踪递归模块的执行 89
4.10.3 用递归解决问题 90
4.10.4 使用堆栈来跟踪代码 91
4.10.5 递归的作用 94
小结 96
习题 97
第5章
数据抽象的方法 102
5.1
数据的意义 102
5.2
组织多个数据块 103
5.3
记录 103
5.3.1
创建新的记录数据类型 104
5.3.2
访问记录的数据域 105
5.4
类型与变量的区别 105
5.4.1
数据类型扩展了语言 105
5.4.2
数据类型的作用域 106
5.4.3
用户自定义数据类型的抽象能力 106
5.4.4
匿名数据类型 107
5.5
指针 107
5.6
动态数据结构 109
5.7
链表 110
5.7.1
链表的结构 110
5.7.2
使用指针来访问节点 111
5.7.3
使用指针来添加节点 115
5.7.4
使用指针来删除节点 115
5.7.5
导航链表 117
5.7.6
遍历链表 117
5.7.7
递归链表遍历 117
5.7.8
递归链表的查找 120
5.7.9
简化表达式的计算 120
5.7.10 建立链表 121
5.7.11 从链表中删除值 124
5.7.12 链表特性小结 125
5.8
链接数据的作用域 125
5.8.1
静态与动态变量 125
5.8.2
在链接数据的参数保护中的漏洞 128
5.9
二叉树 129
5.9.1
遍历二叉树 130
5.9.2
二叉查找树 132
5.9.3
中序遍历BST 132
5.9.4
前序和后序遍历 135
5.9.5
查找二叉查找树 136
5.9.6
添加节点到BST中 138
5.9.7
从BST中删除节点 138
5.10 图 139
5.11 迭代控制 140
5.12 迭代与递归 143
5.13 数组 144
5.13.1
数组与链表 146
5.13.2
遍历数组 146
5.13.3
查找数组 147
5.13.4
更有效的数组查找 147
5.14 常量的强大抽象能力 149
5.14.1
易修改性 149
5.14.2
可读性 150
5.15 创建新数据类型的强大抽象能力 150
5.15.1
混合使用原子类型和复杂类型 151
5.15.2
记录数组 151
5.15.3
记录的记录 154
5.15.4
数组的数组 155
小结 157
习题 158
第6章
构造算法的方法 162
6.1
遍历 162
6.1.1
遍历线性结构 162
6.1.2
遍历非线性结构 163
6.1.3
堆栈和队列 164
6.1.4
广度优先遍历 167
6.1.5
广度优先遍历的实现 169
6.2
查找 170
6.2.1
用遍历实现简单查找 170
6.2.2
关键字域 170
6.2.3
更有效的查找 171
6.3
排序 172
6.4
划分与求解 173
6.5
优化 176
6.5.1
贪心算法 176
6.5.2
动态编程 179
小结 181
习题 182
第7章
现实世界对象的建模方法 185
7.1
面向对象的范式 185
7.1.1
面向对象方法的优势 186
7.1.2
面向对象方法应具有的特征 186
7.2
实现良好的封装性 186
7.2.1
过程抽象和数据抽象的局限性 187
7.2.2
抽象数据类型的概念 187
7.2.3
使用类定义抽象数据类型 188
7.2.4
使用对象来创建抽象数据类型的实例 190
7.3
类的剖析 190
7.3.1
public部分 192
7.3.2
protected部分 192
7.3.3
类中数据的作用域 193
7.3.4
说明 194
7.3.5
声明和使用对象 194
7.4
类属参数和可重用性 195
7.5
跟踪对象行为的执行 197
7.6
复制和克隆操作 198
7.7
实现良好的可适应性 201
7.7.1
继承和扩展行为 201
7.7.2
重新定义继承的标识 202
7.7.3
修改public/protected状态 204
7.7.4
继承类型小结 204
7.7.5
解决二义性 205
7.8
实现多态性 205
7.9
任何事物都是对象 208
小结 213
习题 214
第8章
验证正确性的方法 218
8.1
Bug和调试 218
8.1.1
二义性 219
8.1.2
语法错误 219
8.1.3
语义错误 219
8.1.4
逻辑错误 221
8.2
证明算法的正确性 223
8.3
验证法 225
8.4
能做的最重要的事情 225
小结 228
习题 228
第9章
估算成本和复杂度的方法 232
9.1
性能度量 232
9.2
工作度量 234
9.3
所做工作的分析 235
9.4
实际输入与随机输入 236
9.5
增加复杂度 236
9.6
性能和数据结构 240
9.7
进一步增加复杂度 241
9.8
估算冒泡排序法的复杂度 243
9.9
合理算法和不合理算法 247
9.10 不合理算法的种类 250
小结 252
习题 252
第三部分
计算的局限性
第10章
并发与并行 256
10.1
概述：并发与并行 256
10.1.1
什么是并发 256
10.1.2
什么是并行 257
10.1.3
两者之间的混淆 257
10.2
并发 258
10.2.1
多道程序设计 258
10.2.2
多重处理 258
10.2.3
多任务 258
10.2.4
分布式系统 259
10.3
并发中的问题 259
10.3.1
保护 259
10.3.2
公平性 259
10.3.3
死锁 260
10.3.4
并发问题的总结 261
10.4
并行 261
10.5
并行的局限 263
10.5.1
处理器的固定数量 263
10.5.2
额外开销 264
10.5.3
依赖 264
10.5.4
优先顺序 268
小结 271
习题 271
第11章
问题复杂度的层次 274
11.1
问题复杂度 274
11.2
开放式问题和闭合式问题 275
11.3
简单问题和复杂问题 275
11.4
跨越界限的问题 276
11.5
NP完全问题 276
11.6
证明、预言和确定性 277
11.6.1
证明 278
11.6.2
预言 278
11.6.3
确定性与非确定性 279
11.7
NP完全问题和复杂问题 279
11.8
不可判定问题 279
11.8.1
不可判定问题的证明 281
小结 282
习题 283
第12章
计算与算法的历史 285
12.1
原始范式 285
12.2
抽象的出现 285
12.3
完全抽象的范式 286
12.4
机械装置的出现 286
12.5
机械论思想的范式 286
12.6
实时连接的出现 287
12.7
互联过程范式 287
12.8
未来趋势 288