计算思维的结构

第1章 绪论 1
1.1 计算思维概述 2
1.2 计算思维的结构 5
1.3 计算机方法论概述 8
习题1 10
第2章 计算学科的基本问题 12
2.1 汉诺塔问题 12
2.2 算法复杂性中的难解性问题 14
2.3 证比求易算法 14
2.4 P=NP？ 15
2.5 RSA公开密钥密码系统 16
2.6 停机问题 19
2.7 旅行商问题与组合爆炸问题 21
2.8 找零问题、背包问题与贪婪算法 23
2.9 GOTO语句与程序的结构 24
2.10 哲学家共餐问题与计算机的
资源管理 26
2.11 两军问题与计算机网络 27
2.11.1 两军问题 27
2.11.2 互联网软件的分层结构 28
2.12 人工智能中的若干哲学问题 29
2.12.1 图灵测试 29
2.12.2 西尔勒的“中文屋子” 31
2.12.3 计算机中的博弈问题 31
习题2 33
第3章 计算学科的3个学科形态 34
3.1 一个关于“学生选课”的例子 34
3.1.1 对“学生选课”例子的
感性认识 34
3.1.2 对“学生选课”例子的
理性认识 36
3.1.3 “学生选课”系统的工程设计 37
3.2 抽象形态 38
3.3 理论形态 38
3.4 设计形态 39
3.5 3个学科形态的内在联系 40
3.6 计算机语言的发展及其3个学科
形态的内在联系 42
3.6.1 自然语言与形式语言 42
3.6.2 图灵机与冯 诺依曼计算机 44
3.6.3 机器指令与汇编语言 50
3.6.4 虚拟机 52
3.6.5 高级语言 54
3.6.6 应用语言 55
3.6.7 自然语言 56
习题3 58
第4章 计算学科的核心概念 61
4.1 算法 61
4.1.1 算法的历史简介 61
4.1.2 算法的定义和特征 62
4.1.3 算法实例 63
4.1.4 算法分析 66
4.1.5 常用的两类算法：搜索与排序 71
4.2 数据结构 77
4.2.1 数据结构的基本概念 77
4.2.2 基于Vcomputer机器的
数据结构概述 78
4.2.3 基于Vcomputer机器的
数据的逻辑结构 79
4.2.4 基于Vcomputer机器的
数据的存储结构 83
4.3 数据的存储和表示 86
4.3.1 补码在计算机中的表示 87
4.3.2 图像 89
4.4 数据的编码、校验 90
4.4.1 字符、字符串和汉字 91
4.4.2 奇偶校验算法 92
4.5 CC1991报告提取的核心概念 93
习题4 95
第5章 计算学科中的数学方法 99
5.1 数学的基本特征 99
5.2 数学方法的作用 100
5.3 计算学科中常用的数学
概念和术语 100
5.3.1 集合 100
5.3.2 函数和关系 102
5.3.3 代数系统 103
5.3.4 构造计算学科的逻辑电路的
基础——布尔代数 104
5.3.5 一位加法器的设计 105
5.3.6 定义、定理和证明 108
5.3.7 必要条件和充分条件 109
5.4 证明方法 109
5.4.1 直接证明法和间接证明法 109
5.4.2 反证法 110
5.4.3 归纳法 111
5.4.4 构造性证明 112
5.5 计算学科构造性的基础
——递归和迭代 112
5.5.1 递归 113
5.5.2 迭代 115
5.6 随机数和蒙特卡洛方法 116
5.6.1 随机数 116
5.6.2 蒙特卡洛方法 118
5.7 公理化方法 119
5.7.1 理论体系 119
5.7.2 公理化方法的基本概念 120
5.7.3 实例 121
5.8 计算学科的形式化方法 122
5.8.1 形式系统的组成、基本
特点和局限性 122
5.8.2 形式化方法概述 123
5.8.3 形式规格 124
5.8.4 形式验证 125
习题5 126
第6章 计算学科中的系统
科学方法 128
6.1 系统科学与系统科学方法 128
6.1.1 系统科学的基本概念 128
6.1.2 系统科学遵循的一般原则 130
6.1.3 常用的几种系统科学方法 131
6.1.4 实例 131
6.2 软件开发中使用系统科学方法的原因 132
6.2.1 人固有能力的局限性以及
使用工具后产生的力量 132
6.2.2 复杂性 133
6.2.3 软件系统的复杂性 134
6.2.4 软件开发的系统化方法
需要遵循的基本原则 135
6.3 使用系统方法的思考 137
习题6 138
第7章 跨学科的计算问题案例 139
7.1 社会与职业中3个典型的计算问题 139
7.1.1 职业化 139
7.1.2 道德的选择 140
7.1.3 检举 140
7.2 割圆术的计算问题 141
7.2.1 割圆术的形式化描述 142
7.2.2 割圆术的步骤 142
7.2.3 实例 143
7.2.4 使用Raptor模拟割圆术 144
7.3 森林火灾的计算问题 145
7.3.1 森林火灾的形式化描述 146
7.3.2 模拟森林火灾的步骤 146
7.3.3 实例 147
7.4 多普勒效应的计算问题 149
7.4.1 多普勒效应的形式化描述 149
7.4.2 模拟多普勒效应的步骤 150
7.4.3 实例 150
7.5 小世界网络模型的计算问题 151
7.5.1 小世界网络重连的形式化描述 151
7.5.2 模拟小世界网络重连的步骤 152
7.5.3 实例 152

7.6 科赫曲线 154
7.6.1 科赫曲线的形式化描述 154
7.6.2 模拟生成科赫曲线的步骤 155
7.6.3 实例 155
7.6.4 使用Raptor模拟科赫曲线 155
7.7 向日葵种子生长模拟 157
7.7.1 预备知识 158
7.7.2 向日葵种子生长模拟的
形式化描述 158
7.7.3 模拟向日葵种子生长的步骤 159
7.7.4 实例 159
7.7.5 使用Raptor模拟向日葵
种子生长 159
7.8 烟花模拟 161


7.8.1 烟花模拟的形式化描述 162
7.8.2 烟花模拟问题的粒子系统模型
中粒子运动的相关方程 163
7.8.3 烟花模拟的步骤 164
7.8.4 使用Raptor对烟花模型
进行仿真 164
7.9 俄罗斯方块游戏 167
7.9.1 俄罗斯方块游戏的形式化描述 167
7.9.2 构建一个俄罗斯方块模型
的算法步骤 168
7.9.3 使用Raptor模拟俄罗斯
方块游戏 168
习题7 171
参考文献 173