计算思维 计算学科导论PDF电子书下载

第1章 计算与计算思维 2

1.1 计算需求与计算技术的演变 3

1.1.1 远古时代的原始计算方法 3

1.1.2 机械式计算技术 6

1.1.3 机电式计算技术 7

1.1.4 电子计算技术 8

1.1.5 并行与分布式计算 10

1.1.6 云计算与海计算 11

1.1.7 未来的计算 12

1.2 科学研究的三大方法——理论、实验和计算 13

1.3 计算（机）科学与计算学科 14

1.4 计算思维 16

1.4.1 什么是计算思维 16

1.4.2 狭义计算思维与广义计算思维 18

1.4.3 计算思维之应用 20

阅读材料：计算机发展史大事记 23

第2章 充满智慧与挑战的计算理论（技术）基础 31

2.1 独辟蹊径的数据表示方法 31

2.1.1 数据的表示——弃“十”选“二”的神来之笔 31

2.1.2 有限的字长与大小不一的数据 38

2.1.3 符号的表示——编码 40

2.1.4 鸿沟与代价 41

2.2 从逻辑学到逻辑电路——思维可计算吗 45

2.2.1 生活中的“逻辑问题” 45

2.2.2 逻辑与思维 46

2.2.3 数理逻辑 50

2.2.4 逻辑推理与人工智能 53

2.2.5 逻辑门电路 54

2.3 “九九归一”的加法运算 56

2.3.1 加法运算及其加法器的设计 56

2.3.2 补码运算——把减法当加法做 59

2.4 计算的本质——图灵机及其计算能力 60

2.4.1 图灵机模型 60

2.4.2 图灵机的工作原理 62

2.4.3 图灵机的计算能力 63

2.5 计算机的构造——冯·诺依曼机及其工作原理 69

2.5.1 冯·诺依曼型计算机的组成和工作原理 69

2.5.2 思想与技术的演化 72

2.5.3 冯·诺依曼型计算机的特点及其局限性 74

2.6 计算技术的开拓与发展 75

2.7 什么都能计算吗——难题及其可计算性 79

2.7.1 难题何其多 79

2.7.2 可计算性与计算复杂性 82

2.7.3 难题大挑战及其科学意义 84

阅读材料：计算机系统（PC）的硬件组成 87

第3章 计算思维之方法学 94

3.1 问题求解过程 94

3.1.1 人类解决客观世界问题的思维过程 94

3.1.2 借助于计算机的问题求解过程 96

3.1.3 两种问题求解过程的对比 99

3.2 数学模型——问题的抽象表示 99

3.3 数据存储结构 102

3.3.1 顺序存储结构 103

3.3.2 链式存储结构 104

3.3.3 索引存储结构 105

3.3.4 散列存储结构 106

3.4 客观世界到计算机世界的映射方法 107

3.4.1 面向过程的结构化设计方法学 107

3.4.2 面向对象程序设计方法学 110

3.5 时间与空间及其相互转换 116

3.6 抽象 118

3.6.1 什么是抽象 118

3.6.2 计算学科中的抽象 121

3.6.3 抽象的层次性 122

3.6.4 程序中的抽象 125

3.6.5 抽象与模型 126

3.6.6 抽象与计算机语言 127

3.7 串行与并行 130

3.8 局部化与信息隐藏 132

3.9 精确、近似与模糊 134

3.10 折中与中庸之道 135

阅读材料：计算机软件及其软件系统 137

第4章 计算思维之算法基础 143

4.1 算法 143

4.1.1 什么是算法 143

4.1.2 算法的性质 146

4.1.3 算法的种类 147

4.1.4 算法的表示（描述） 148

4.1.5 算法与程序 153

4.1.6 算法的比较与分析 154

4.2 算法设计的基本思想与方法 157

4.2.1 穷举法（也称为枚举法，Enumeration） 157

4.2.2 递推法（Recurrence） 159

4.2.3 递归法 161

4.2.4 回溯法（Backtracking）＊ 165

4.2.5 分治法（Divide and Conquer） 171

4.2.6 仿生法——蚁群算法（Ant colony optimization,ACO）＊ 174

4.2.7 并行算法＊ 177

4.2.8 算法设计与计算思维 178

4.3 常用的经典算法 179

4.3.1 累加和、连乘积与最大（小）值 179

4.3.2 查找 180

4.3.3 排序 183

4.3.4 逻辑分析与推理 193

阅读材料：Matlab问题表示与计算 197

第5章 面向计算之问题求解思想与方法 203

5.1 大海捞针的搜索引擎 203

5.1.1 网页的自动下载与存储 204

5.1.2 网页索引与匹配 205

5.1.3 网页排序方法 208

5.2 瞒天过海的密码技术 214

5.2.1 有趣的对称加密技术 215

5.2.2 难解的非对称加密技术 218

5.2.3 数字签名及其应用 222

5.3 令人期待的人工智能 224

5.3.1 人工智能时代正在快步走来 224

5.3.2 人工智能方法论 226

5.3.3 人工智能应用 230

5.3.4 展望未来，人工智能会颠覆一切 231

5.4 不可思议的自纠错技术 231

5.4.1 面临的问题与挑战 232

5.4.2 重复传输 233

5.4.3 冗余编码 234

5.4.4 校验 236

5.4.5 错误定位 238

5.4.6 推广应用 240

5.5 柳暗花明的自然语言处理 242

5.5.1 美好愿景 242

5.5.2 原始的“逐词替换” 242

5.5.3 基于“规则”的方法 244

5.5.4 从“规则”到“统计” 247

5.5.5 基于统计的机器翻译 248

5.6 削尖脑袋的数据压缩技术 250

5.6.1 无损压缩及其方法 250

5.6.2 有损压缩之“thinking” 263

5.6.3 展望未来 264

阅读材料：计算机网络 264

第6章 计算思维之程序基础 268

6.1 数据的类型与本质 268

6.1.1 我们熟悉的数与数据 268

6.1.2 计算机世界中的数据 270

6.1.3 数据的类型与本质 271

6.2 变量的特定含义 273

6.2.1 “先定义，后使用” 274

6.2.2 变量得有自己“好听”的名字 274

6.2.3 变量是有类型的 275

6.2.4 变量的作用域 275

6.2.5 变量的生命周期 276

6.3 有穷与无穷 277

6.3.1 数据的有穷性 278

6.3.2 程序的有穷性 279

6.4 程序的基本控制结构 279

6.4.1 顺序结构 279

6.4.2 条件选择结构 280

6.4.3 循环结构 281

6.5 问题求解的本质过程 281

6.6 效率与可读性 282

6.7 程序的构造特性 284

6.8 上下文无关文法 285

6.9 二义性 286

6.10 严谨性 286

阅读材料：计算机语言概述 287

第7章 基于计算之问题求解思想和方法 292

7.1 重复迭代，寻根问底——方程求根 292

7.1.1 二分法（Bisection Method） 292

7.1.2 简单迭代法 294

7.1.3 牛顿法 296

7.1.4 其他求根方法 298

7.2 有限划分，无限逼近——定积分的计算 299

7.2.1 问题求解的基本思路与方法 300

7.2.2 求解算法 303

7.3 千年求精，万年求真——求解圆周率π 304

7.3.1 关于圆周率的计算 304

7.3.2 圆周率的计算史 304

7.3.3 圆周率的计算方法 307

7.3.4 圆周率的计算永无止境 309

7.3.5 研究圆周率的意义 310

7.4 大事化小，小事化了——有限元计算 311

7.4.1 有限元方法的诞生 312

7.4.2 什么是有限元方法 312

7.4.3 有限元方法的基本思想 313

7.4.4 有限元法求解问题的步骤 313

7.4.5 有限元方法的应用 314

7.4.6 有限元方法中的计算思维 314

7.5 万事俱备，不欠东风——数值天气预报 317

7.5.1 天气预报的发展 318

7.5.2 现代数值天气预报原理 320

7.5.3 天气预报对计算技术永无止境的需求 323

7.6 赌城之名，绝妙之法——蒙特·卡罗法 324

7.6.1 蒙特·卡罗方法导引 325

7.6.2 蒙特·卡罗方法的基本思想与过程 326

7.6.3 蒙特·卡罗方法的应用与分析 326

7.7 精确制导，百步穿杨——巡航导弹制导系统 328

7.7.1 制导方法分类 329

7.7.2 “战斧”式巡航导弹 331

7.8 红楼遗梦，作者存疑——《红楼梦》作者是谁 333

阅读材料：Python语言 333

第8章 从“计算”到“文化” 341

8.1 文化与计算文化 341

8.2 计算文化的本质特征 342

8.3 计算文化与传统文化 344

阅读材料：一路走来的“云计算” 346

附录A ASCII码字符集 350

附录B 几种常用进位制数值对照表 351

参考文献 352