计算机科学概论

本书由两位知名的计算机科学教育家编写，全面而细致地介绍了计算机科学的各个方面。书中从信息层开始，历经硬件层、程序设计层、操作系统层、应用程序层和通信层，深入剖析了计算系统的每个分层，很后讨论了计算的限制。此外，正文中穿插了大量的人物传记、历史点评、道德问题和近期新的技术发展信息，有助于你进一步了解计算机科学。每章后面都附带有大量的练习，可以帮助你即时重温并掌握这一章所述的内容。

内尔·黛尔(Nell Dale)，计算机科学领域广受推崇的教育家。在得克萨斯大学奥斯汀分校执教的二十多年中。她编写了四十多本计算机科学方面的本科生教材。她于得克萨斯大学奥斯汀分校获得了硕士学位和计算机科学博士学位。由于在计算机科学领域做出了很好贡献，她于1996年获得了ACM SIGCSE计算机科学教育杰出贡献奖。于2001年获得了ACM Karl Karlston杰出教师奖。她于2010年被选为ACM会士。

出版者的话
译者序
前言
第一部分基础篇
第1章全景图 2
1.1计算系统 2
1.1.1计算系统的分层 3
1.1.2抽象 4
1.2计算的历史 5
1.2.1计算硬件简史 5
1.2.2计算软件简史 12
1.2.3预言 16
1.3计算工具与计算学科 16
小结 18
道德问题：the Tenth Strand 18
练习 19
思考题 20
第二部分信息层
第2章二进制数值与记数系统 22
2.1数字与计算 22
2.2位置记数法 23
2.2.1二进制、八进制和十六进制 26
2.2.2其他记数系统中的运算 27
2.2.3以2的幂为基数的记数系统 27
2.2.4把十进制数转换成其他数制的数 29
2.2.5二进制数值与计算机 29
小结 31
道德问题：the Tenth Strand的知识单元 31
练习 33
思考题 34
第3章数据表示法 35
3.1数据与计算机 35
3.1.1模拟数据与数字数据 36
3.1.2二进制表示法 38
3.2数字数据表示法 39
3.2.1负数表示法 39
3.2.2实数表示法 42
3.3文本表示法 44
3.3.1ASCII字符集 45
3.3.2Unicode字符集 45
3.3.3文本压缩 46
3.4音频数据表示法 49
3.4.1音频格式 50
3.4.2MP3音频格式 50
3.5图像与图形表示法 51
3.5.1颜色表示法 51
3.5.2数字化图像与图形 52
3.5.3图形的矢量表示法 53
3.6视频表示法 53
小结 55
道德问题：道德准则 55
练习 56
思考题 58
第三部分硬件层
第4章门和电路 60
4.1计算机和电学 60
4.2门 62
4.2.1非门 62
4.2.2与门 63
4.2.3或门 63
4.2.4异或门 64
4.2.5与非门和或非门 64
4.2.6门处理回顾 65
4.2.7具有更多输入的门 65
4.3门的构造 66
4.4电路 67
4.4.1组合电路 68
4.4.2加法器 70
4.4.3多路复用器 71
4.5存储器电路 72
4.6集成电路 73
4.7CPU芯片 73
小结 74
道德问题：这些违反道德规范吗？ 74
练习 75
思考题 77
第5章计算部件 78
5.1独立的计算机部件 78
5.2存储程序的概念 82
5.2.1冯·诺伊曼体系结构 82
5.2.2读取-执行周期 87
5.2.3RAM和ROM 88
5.2.4二级存储设备 89
5.2.5触摸屏 92
5.3嵌入式系统 93
5.4并行体系结构 94
5.4.1并行计算 94
5.4.2并行硬件分类 95
小结 96
道德问题：数字鸿沟 96
练习 97
思考题 98
第四部分程序设计层
第6章低级程序设计语言与伪代码 102
6.1计算机操作 102
6.2机器语言 103
6.3一个程序实例 108
6.3.1手工模拟 109
6.3.2Pep/8模拟程序 109
6.4汇编语言 111
6.4.1Pep/8汇编语言 112
6.4.2汇编器指令 112
6.4.3Hello程序的汇编语言版本 113
6.4.4一个新程序 113
6.4.5具有分支的程序 115
6.4.6具有循环的程序 116
6.5表达算法 118
6.5.1伪代码的功能 118
6.5.2执行伪代码算法 121
6.5.3写伪代码算法 123
6.5.4翻译伪代码算法 124
6.6测试 125
小结 126
道德问题：版权与软件盗版 127
练习 127
思考题 129
第7章问题求解与算法设计 130
7.1如何解决问题 130
7.1.1提出问题 130
7.1.2寻找熟悉的情况 132
7.1.3分治法 132
7.1.4算法 133
7.1.5计算机问题求解过程 133
7.1.6方法总结 134
7.1.7测试算法 135
7.2有简单参数的算法 135
7.2.1带有选择的算法 135
7.2.2带有循环的算法 136
7.3复杂变量 139
7.3.1数组 139
7.3.2记录 140
7.4搜索算法 141
7.4.1顺序搜索 141
7.4.2有序数组中的顺序搜索 141
7.4.3二分检索 142
7.5排序 144
7.5.1选择排序 144
7.5.2冒泡排序 145
7.5.3插入排序 147
7.6递归算法 147
7.6.1子程序语句 148
7.6.2递归阶乘 149
7.6.3递归二分检索 149
7.6.4快速排序 150
7.7几个重要思想 153
7.7.1信息隐蔽 153
7.7.2抽象 154
7.7.3事物命名 155
7.7.4测试 155
小结 155
道德问题：开源软件 156
练习 157
思考题 159
第8章抽象数据类型与子程序 160
8.1抽象数据类型 160
8.2栈 161
8.3队列 161
8.4列表 162
8.5树 164
8.5.1二叉树 164
8.5.2二叉检索树 165
8.5.3其他操作 169
8.6图 169
8.6.1创建图 171
8.6.2图算法 171
8.7子程序 176
8.7.1参数传递 177
8.7.2值参与引用参数 178
小结 180
道德问题：工作场所监视 180
练习 181
思考题 183
第9章面向对象设计与高级程序设计语言 184
9.1面向对象方法 184
9.1.1面向对象 185
9.1.2设计方法 185
9.1.3一个计算机示例 187
9.2翻译过程 189
9.2.1编译器 190
9.2.2解释器 190
9.3程序设计语言的范型 192
9.3.1命令式范型 192
9.3.2声明式范型 193
9.4高级程序设计语言的功能性 194
9.4.1布尔表达式 194
9.4.2数据归类 196
9.4.3输入/输出结构 199
9.4.4控制结构 200
9.5面向对象语言的功能性 204
9.5.1封装 204
9.5.2类 205
9.5.3继承 206
9.5.4多态 207
9.6过程设计与面向对象设计的区别 207
小结 208
道德问题：恶作剧与诈骗 209
练习 210
思考题 212
第五部分操作系统层
第10章操作系统 214
10.1操作系统的角色 214
10.1.1内存、进程与CPU管理 216
10.1.2批处理 216
10.1.3分时 217
10.1.4其他OS要素 218
10.2内存管理 218
10.2.1单块内存管理 219
10.2.2分区内存管理 220
10.2.3页式内存管理 221
10.3进程管理 223
10.3.1进程状态 223
10.3.2进程控制块 224
10.4CPU调度 224
10.4.1先到先服务 225
10.4.2最短作业优先 226
10.4.3轮询法 226
小结 227
道德问题：医疗隐私——健康保险携带与责任法案 228
练习 229
思考题 231
第11章文件系统和目录 232
11.1文件系统 232
11.1.1文本文件和二进制文件 233
11.1.2文件类型 233
11.1.3文件操作 234
11.1.4文件访问 235
11.1.5文件保护 236
11.2目录 237
11.2.1目录树 237
11.2.2路径名 239
11.3磁盘调度 241
11.3.1先到先服务磁盘调度法 242
11.3.2最短寻道时间优先磁盘调度法 242
11.3.3SCAN磁盘调度法 242
小结 243
道德问题：选择加入和选择退出 243
练习 244
思考题 246
第六部分应用程序层
第12章信息系统 248
12.1信息管理 248
12.2电子制表软件 249
12.2.1电子数据表公式 250
12.2.2循环引用 254
12.2.3电子数据表分析 254
12.3数据库管理系统 255
12.3.1关系模型 256
12.3.2关系 257
12.3.3结构化查询语言 258
12.3.4数据库设计 260
12.4电子商务 261
小结 262
道德问题：从竞选来看政治与网络 262
练习 263
思考题 265
第13章人工智能 266
13.1思维机 266
13.1.1图灵测试 267
13.1.2AI问题的各个方面 268
13.2知识表示 268
13.2.1语义网 268
13.2.2检索树 271
13.3专家系统 273
13.4神经网络 275
13.4.1生物神经网络 275
13.4.2人工神经网络 276
13.5自然语言处理 277
13.5.1语音合成 277
13.5.2语音识别 278
13.5.3自然语言理解 279
13.6机器人学 280
13.6.1感知-规划-执行范型 280
13.6.2包孕体系结构 282
13.6.3物理部件 283
小结 283
道德问题：从民众来看政治与网络 284
练习 284
思考题 286
第14章模拟、图形学、游戏和其他应用 287
14.1什么是模拟 287
14.1.1复杂系统 287
14.1.2模型 288
14.1.3构造模型 288
14.2特殊模型 289
14.2.1排队系统 289
14.2.2气象模型 292
14.2.3计算生物学 295
14.2.4其他模型 295
14.2.5必要的计算能力 296
14.3计算机图形学 296
14.3.1光的工作原理 297
14.3.2物体形状 298
14.3.3光模拟 298
14.3.4复杂对象的建模 299
14.3.5让物体动起来 303
14.4游戏 304
14.4.1游戏的历史 304
14.4.2创建虚拟世界 305
14.4.3游戏设计与开发 305
14.4.4游戏编程 306
小结 307
道德问题：游戏成瘾 307
练习 308
思考题 309
第七部分通信层
第15章网络 312
15.1连网 312
15.1.1网络的类型 313
15.1.2Internet连接 315
15.1.3包交换 317
15.2开放式系统与协议 318
15.2.1开放式系统 318
15.2.2网络协议 319
15.2.3TCP/IP 319
15.2.4高层协议 320
15.2.5MIME类型 321
15.2.6防火墙 321
15.3网络地址 322
15.4云计算 324
小结 325
道德问题：社交网络的影响 326
练习 327
思考题 328
第16章万维网 329
16.1Web简介 329
16.1.1搜索引擎 331
16.1.2即时消息 331
16.1.3博客 331
16.1.4cookie 332
16.2HTML 333
16.2.1基本的HTML格式 335
16.2.2图像与链接 335
16.2.3HTML5 337
16.3交互式网页 337
16.3.1Java小程序 337
16.3.2Java服务器页 338
16.4XML 339
16.5社交网络 341
小结 342
道德问题：赌博与互联网 344
练习 344
思考题 346
第17章计算机安全 347
17.1各级安全 347
17.2阻止未授权访问 349
17.2.1密码 349
17.2.2验证码 351
17.2.3指纹分析 352
17.3恶意代码 352
17.3.1杀毒软件 353
17.3.2安全攻击 353
17.4密码学 355
17.5保护你的在线信息 357
17.5.1安全与可移动设备 359
17.5.2维基解密 359
小结 360
道德问题：博客 361
练习 362
思考题 363
第八部分总结
第18章计算的限制 366
18.1硬件 366
18.1.1算术运算的限制 366
18.1.2部件的限制 370
18.1.3通信的限制 371
18.2软件 372
18.2.1软件的复杂度 372
18.2.2当前提高软件质量的方法 373
18.2.3臭名昭著的软件错误 376
18.3问题 377
18.3.1算法比较 377
18.3.2图灵机382
18.3.3停机问题 384
18.3.4算法分类 386
小结 387
道德问题：Therac-25灾难剖析 387
练习 388
思考题 389
参考文献 390
索引 396

前  言Computer Science Illuminated, Fifth Edition论题选择为了制定这本CS0教材的论题大纲，我们利用了许多资源，包括课程目录、教材大纲以及一个电子邮件调查问卷。设计这个调查问卷的目的在于了解我们的同事对这门课应该包括哪些内容的想法。我要求大家（包括自己）列出下列三种清单：
    如果CS0这门课是学生在大学阶段学习的唯一一门计算机科学的课程，请列出四种你认为他们应该掌握的论题。
    请列出四种你想要学生在进入CS1这门课之前掌握的论题。
    请补充四种你想要学习CS1的学生熟悉的论题。
    这些资源的交集反映出的大多数人的意见，也就构成了本书的大纲。在学习CS1之前掌握了本书内容的学生将为继续学习计算机科学打下坚实的基础。尽管我们的意图是编写一本CS0教材，但是许多评论家都认为本书的覆盖面非常广泛，可以作为一种程序设计语言的计算机科学导论的参考书。
    结构说明在第1章中，我们介绍了硬件和软件的历史，并且用洋葱的结构来类比计算机系统的结构。计算机和它的机器语言构成了洋葱的芯，软件层和更复杂的硬件一层层地裹住了这个芯。首先介绍的是机器语言，然后是高级语言，包括FORTRAN、Lisp、Pascal、C、C++和Java。在介绍这些语言的同时，还介绍了利用它们进行程序设计的过程，包括自顶向下的设计和面向对象的设计。我们对抽象数据类型所扮演的角色及其实现的理解已经成熟了。操作系统及其资源管理技术（包括更大、更快的二级存储介质上的文件）包围着这些程序，并对它们进行管理。
    接下来的一层由更复杂的通用或专用软件系统构成，它们覆盖了操作系统。这些功能强大的程序由计算机科学中的并行理论支持。最后一层由网络和网络软件构成，网络软件包括计算机之间通信必需的所有工具。Internet和万维网给这一层画上了最后一笔。
    当这些层随着时间的推移逐渐出现时，用户对计算机系统的硬件接触得越来越少。每个层都是它下面的计算机系统的抽象。随着每个层的发展，新层的用户和内部层的用户联合起来，在经济领域的高科技部门创造了大量的生产力。本书的目的是提供各个层的概述，介绍基本的硬件和软件技术，使学生了解和欣赏计算系统的方方面面。
    在介绍这种洋葱式结构时，我们有两种选择，一种是从内向外逐层介绍，另一种是从外向内进行介绍。从外向内的方法看起来非常吸引人。我们可以从最抽象的层开始介绍，一次剥掉一个层，直到具体的机器层为止。但是，研究表明，比起抽象的例子，学生们更容易理解具体的例子，即使他们本身是抽象思想家。因此，我们选择从具体的机器层开始，按照层的创建顺序进行分析，当学生完全理解了一个层之后，再转移到下一个层就比较容易。
    第5版中的变化在计划这次改版时，我们咨询了CS教育学院的同事，要求他们给予一些反馈。37人回复了我们，非常感谢这些有思考、有见解的回应。
    第15章中添加了“云计算”一节，并更新了域名部分。第16章中加入了HTML5。此外，专门用一章（第17章）讨论计算机安全。老版的第17章是现在的第18章。目前，大多数的安全问题集中在网络时代信息的安全使用上，因此把第17章放在通信层的最后一章。
    除了新的章节，现在每章结尾部分的道德问题有了更为一致的主题，从道德责任的定义和一个专业计算机人士的道德责任开始，展示了两个主要的计算协会ACM和IEEE的道德准则，也给出了选择计算机专业可能面临的案例研究。这些材料在计算机课程中称为the Tenth Strand，其中对涉及计算的主要社会问题进行了讨论，包括政治、版权、工作场所监视和游戏成瘾方面。
    当然，我们对整书进行了全面调整，对“你知道吗”板块和传记部分也进行了更新。
    摘要第1章是我们探索计算机科学（计算机系统“洋葱”）的基础，描述了本书的组织结构。第2章和第3章则分析了包含在物理硬件中的层。这个层称为信息层，它反映了如何在计算机上表示信息。第2章介绍了二进制数制以及它与其他数制（如人们日常用的十进制系统）的关系。第3章研究了如何获取多种类型（如数字、文本、图像、音频和视频）的信息以及如何用二进制格式表示它们。
    第4章和第5章介绍了硬件层。计算机硬件包括的设备有晶体管、门和电路，它们都按照基本原理控制电流。正是这些核心电路使专用的元件（如计算机的中央处理器——CPU）得以运转。第4章介绍了门和电路。第5章介绍了计算机的元件，以及在冯·诺伊曼体系结构中这些元件是如何交互的。当然，第5章开头的广告已经更新了，在你阅读本书时，它可能又过时了。
    第6～9章介绍了程序设计层。第6章使用模拟计算机Pep/8介绍了机器语言和汇编语言的概念。该章引入了用伪代码编写算法的功能，介绍了循环与选择的概念，并在Pep/8中以伪代码的方式实现。
    第7章分析了问题求解过程，同时涉及人类和计算机的问题求解方法。引导这个论题的是George Polya的人类问题求解策略。该章介绍了自顶向下的方法来设计简单算法，并在讨论算法时选择经典的搜索和排序算法。因为算法是对数据进行操作，所以在此研究数据的结构，以便更有效地处理数据。该章也介绍了子算法（子程序）语句。
    第8章介绍了抽象数据类型或容器，容器是只知道其属性或行为的复合结构。该章介绍了列表、有序列表、栈、队列、二叉检索树和图，扩展讨论了子算法，包括引用参数与值参、参数传递。
    第9章介绍了高级程序设计语言的概念。许多杰出的高级语言包含与面向对象编程相关的功能，我们先绕过这个设计过程，讨论语言范型以及编译过程。我们用四种编程语言设计了一些小例子来说明伪代码的概念，即Python、VB.NET、Java和C++。
    第10章和第11章介绍了操作系统层。第10章讨论了操作系统的资源管理任务，介绍了一些用于实现这些任务的基本算法。第11章介绍了文件系统，包括什么是文件系统，以及操作系统如何管理它们。
    第12～14章介绍了应用程序层。这一层由人们用来解决问题的通用应用程序和专用应用程序构成。我们根据这些程序的基础，把这一层分到了计算机科学的几个子学科中。第12章分析了信息系统，第13章分析了人工智能，第14章分析了模拟、图形学、游戏和其他应用。
    第15～17章介绍了通信层。第15章说明了计算机之间通信的理论和应用。第16章介绍了万维网和它对当今生活的影响，包括修订的社交媒体部分。全新的第17章讨论计算机安全，涵盖了当今信息时代与保护信息安全相关的各个方面。
    第2～17章都是说明计算机可以做什么以及它是如何做的。第18章进行了总结，讨论了计算机硬件和软件的固有局限性，以及计算机能够解决和不能解决的问题。在讨论算法的有效性时，采用了大O符号，以便讨论算法的分类。此外还介绍了停机问题，以说明某些不能解决的问题。
    本书的第1章和最后一章就像一对书档，第1章说明了计算系统是什么，第18章告诫我们计算系统不能做什么。它们之间的章节则深入探讨了构成计算系统的各个层。
    特性本书具有三种特性，用于强调计算的历史、广度以及新技术带来的道德义务。首先，每一章都有一个简短的名人传记，介绍对计算做出杰出贡献的人。这些人包括对数据层做出贡献的George Boole和Ada Lovelace，以及对通信层做出贡献的Doug Engelbart和Tim Berners-Lee。这些传记的目的是让学生了解计算界的历史以及那些对计算界做过贡献和正在做贡献的人。
    我们称第二个特性为“你知道吗”，因为没有更好的词可以表达它。这部分显示在方框中，是过去、现在和未来的一些轶闻趣事，它们来自历史记录、当今的报纸和作者的见闻。这些小插曲的目的是使学生开心、鼓舞他们、激发他们的兴趣，当然也为了教育他们。
    第三个特性是每章中的“道德问题”小节。这些小节的目的是说明在利用计算的好处时要承担的义务。隐私权、黑客、病毒和言论自由都属于我们的论题。在每章练习的结尾处有一个思考题部分，涉及这些道德问题和这一章的内容。
    致谢对于这一版来说，读者是最有用的信息和建议来源。衷心感谢受调查者花时间填写了我们的网络调查问卷。还要感谢前几版的审校者，以及这一版的审校者，他们是：
    Tim Bower，堪萨斯州立大学；Mikhail Brikman，塞勒姆州立学院；Jacques Carette，麦克马斯特大学；Howard Francis，派克维尔学院；Jim Jones，格雷斯兰大学；Murray Levy，西洛杉矶学院；Lew Lowther，约克大学；Jeffrey McConnell，凯尼休斯学院；Richard Schlesinger，肯尼索州立大学；Richard Spinello，波士顿学院；Herman Tavani，里韦学院；Amy Woszczynski，肯尼索州立大学；C. Michael Allen，北卡罗来纳大学夏洛特分校；Lofton Bullard，佛罗里达亚特兰大大学；Cerian Jones，阿尔伯塔大学；Calvin Ribbens，弗吉尼亚理工大学； Susan Sells，威奇托州立大学；R. Mark Meyer，凯尼休斯学院；Tom Wiggen，北达科他大学； Mary Dee Harris，Chris Edmonson-Yurkanan，Ben Kuipers， Glenn Downin，得克萨斯大学奥斯汀分校；Dave Stauffer，宾夕法尼亚大学; John McCormick，北艾奥瓦大学；Dan Joyce，维拉诺瓦大学；Mike Goldwasser，圣路易斯大学；Andrew Harrington，洛约拉大学芝加哥分校；Daniel R. Collins，马萨诸塞州湾社区学院；J. Stanley Warford，佩珀代因大学；Richard C. Detmer，中田纳西州立大学；Chip Weems，马萨诸塞大学阿默斯特分校；Heather Chandler，西木学院；Mark Holthouse, 西木高等学校；Robert Vermilyer，国托马斯阿奎那斯学院。
    特别感谢凯尼休斯学院的Jeffrey McConnell，他编写了第14章中的图形学部分；感谢里韦学院的Herman Tavani，他参与了修改“道德问题”的工作；感谢波士顿学院的Richard Spinello，他撰写了博客的道德问题一文。
    感谢审稿人与同事对第5版的内容给出了意见与建议，他们是：
    Bob Blucher，雷恩社区学院；Dale Fletter，福尔瑟姆湖学院；Jerry Westfall博士，利伯蒂大学；Dwayne Towell，艾伯林基督大学；Kara Nance，阿拉斯加大学；Lisa Michaud，梅里马克学院；Jeffery Bergamini，门多西诺学院；Johanna Horowitz，西耶那学院；Lonnie R. Nelson，汉尼拔拉格朗日学院；Marie Hartlein，蒙哥马利县社区学院；Mark Holthouse，西木高等学校；Mikhail S. Brikman博士，塞勒姆州立大学；Patricia Roth Pierce，南理工州立大学；Quentin J. White，SR，帕洛马学院；Rakesh Arya，马里兰大学东海岸分校；Tim Bower，堪萨斯州立大学；William Honig，洛约拉大学芝加哥分校；Barbara Zimmerman，维拉诺瓦大学；Maria Jump博士，国王学院；Joe Pistone，巴洛玛社区学院；Derek Merck，佐治亚佩雷米特学院。
    还要感谢Jones&Bartlett Learning的许多人，尤其是Tim Anderson（资深编辑）、Amy Bloom（主编）、Amy Rose（出版总监）。
    我还必须感谢我的网球朋友使我有一个健康的体魄，感谢我的桥牌朋友使我的头脑十分机敏，感谢我的家人做我的坚强后盾。