计算机科学导论

第1章 计算机科学概貌 1

1.1 什么是计算机科学 2

1.1.1 计算思维 4

1.1.2 步骤、符号、操作与计算过程 8

1.1.3 能够自动执行的抽象 16

1.2 计算机科学的发展实例 18

1.2.1 巴贝奇问题——计算机系统实例 19

1.2.2 布什问题——计算机使用模式实例 21

1.2.3 图灵问题——智能应用实例 24

1.2.4 计算机科学的三个奇妙之处 29

1.3 计算机科学的创新故事 36

1.3.1 文王演周易 36

1.3.2 自由软件的故事 41

1.3.3 为什么未来不需要我们 46

1.4 编程练习 49

1.5 习题 53

第2章 计算模型与逻辑思维 54

2.1 从一个实例看逻辑思维 54

2.2 逻辑思维要点 55

2.2.1 布尔逻辑 55

2.2.2 图灵机模型 62

2.2.3 悖论与不完备定理 66

2.2.4 能够自动执行的精准逻辑 67

2.3 计算逻辑的创新故事 69

2.3.1 布尔的故事 69

2.3.2 图灵的故事 72

2.3.3 臭虫与病毒 73

2.4 习题 79

第3章 算法思维 81

3.1 从一个实例看算法 81

3.2 算法思维的要点与实例 83

3.2.1 分治算法 83

3.2.2 其他算法实例 90

3.2.3 算法复杂度浅介 96

3.3 算法的创新故事 98

3.3.1 平稳复杂度 98

3.3.2 红帽的故事 101

3.3.3 创业公司五步曲 103

3.4 编程练习 111

3.5 习题 113

第4章 网络思维 116

4.1 从一个实例看网络与协议 117

4.2 网络思维的要点 119

4.2.1 名字空间 119

4.2.2 网络拓扑 122

4.2.3 互联网协议栈 124

4.2.4 服务质量与用户体验 126

4.2.5 网络的规律举例 127

4.3 网络的创新故事 130

4.3.1 ARPANET 131

4.3.2 以太网、路由器和TCP/IP协议 134

4.3.3 万维网 139

4.3.4 社交网络 143

4.4 编程练习 145

4.5 习题 147

第5章 系统思维 150

5.1 从一个实例看计算系统 151

5.2 计算系统思维要点 153

5.2.1 抽象化 154

5.2.2 模块化 159

5.2.3 无缝衔接 172

5.2.4 抽象是应对系统复杂度的利器 179

5.3 计算系统创新故事 180

5.3.1 半导体集成电路 180

5.3.2 计算机硬件 188

5.3.3 计算机软件 213

5.4 编程练习 227

5.5 习题 232

第6章 课程实践 234

6.1 构造图灵机实验 234

6.1.1 实验目的和原理 234

6.1.2 实验内容、方法和步骤 235

6.1.3 实验注意事项 236

6.1.4 成绩评定方法 236

6.1.5 思考题 236

6.2 算法游戏实验 236

6.2.1 实验目的和原理 236

6.2.2 实验内容、方法和步骤 237

6.2.3 实验注意事项 238

6.2.4 成绩评定方法 238

6.2.5 思考题 238

6.3 网络路由实验 238

6.3.1 实验目的和原理 238

6.3.2 实验内容、方法和步骤 239

6.3.3 实验注意事项 240

6.3.4 成绩评定方法 241

6.3.5 思考题 241

6.4 淝水之战系统实验 241

6.4.1 实验目的和原理 241

6.4.2 实验内容、方法和步骤 242

6.4.3 实验注意事项 244

6.4.4 成绩评定方法 245

6.4.5 思考题 245

6.5 班级快速排序实验 245

6.5.1 实验目的和原理 245

6.5.2 实验内容、方法和步骤 246

6.5.3 实验注意事项 246

6.5.4 成绩评定方法 247

6.5.5 思考题 247

6.6 莱布尼茨问题实验 247

6.6.1 实验目的和原理 247

6.6.2 实验内容、方法和步骤 247

6.6.3 实验注意事项 248

6.6.4 成绩评定方法 248

6.7 信息隐藏编程实验 248

6.7.1 实验目的和原理 248

6.7.2 实验准备 249

6.7.3 实验内容、方法和步骤 258

6.7.4 实验注意事项 273

6.7.5 成绩评定方法 274

附录A 计算机科学技术中常用的倍数和分数 275

附录B 原文阅读列表 277

参考文献 279