本书采用大量最新素材，全面介绍计算机科学领域的基础知识。本书由当今该领域备受赞誉且经验丰富的教育家Nell Dale和John Lewis共同编写。就整体而言，全书内容翔实、覆盖面广，旨在向读者展示计算机科学的全貌；从细节上看，本书层次清晰、描述生动；从信息讲起，分别介绍了关于硬件、编程、操作系统、应用以及通信方面的内容，涉及计算机科学的各个层面。
本书内容严谨、深入浅出，是计算机科学专业学生理想的入门教材。
本书特点：
●采用一般语言对编程概念进行了描述，关于Java、C++语言对该问题的描述在本书的配套网站 (http://csilluminated.jbpub.com) 中提供。
●增加了名人传记、历史事件以及技术发展的前沿知识；并在每章中就科技发展对人类社会伦理道德的影响进行了探讨。
●包含大量练习和思考题，方便教学。
●本书的配套网站集学术性及趣味性于一体，提供了大量教学资源：Flash幻灯片、在线术语表、互动学习、填字游戏、HTML帮助信息等，以更灵活的方式多方位地加深读者对本书知识的理解。
无
论题选择
为了制定这本CS0教材的论题大纲，我们利用了许多资源，包括课程目录、教材大纲以及一个email调查问卷。设计这个调查问卷的目的在于了解我们的同事对这门课应该包括哪些内容的想法。我要求他们和自己列出下列三种清单。
* 如果CS0这门课是学生在大学阶段学习的唯一一门计算机科学的课程，请列出四种你认为他们应该掌握的论题。
* 请列出四种你想要学生在进入CS1这门课之前掌握的论题。
* 请补充四种你想要学习CS1的学生熟悉的论题。
这些资源的交集反应出的大多数人的意见构成了本书的大纲。在学习CS1之前掌握了本书内容的学生将为继续学习计算机科学打下坚实的基础。尽管我们的意图是编写一本CS0教材，但是许多评论家都认为本书的覆盖面非常广泛，可以作为一种程序设计语言的计算机科学导论的参考书。
结构说明
在第1章中，我们介绍了硬件和软件的历史，并且用洋葱的结构来类比计算机系统的结构。计算机和它的机器语言构成了洋葱的芯，软件层和更复杂的硬件一层层地裹住了这个芯。首先介绍的是机器语言，然后是高级语言，包括FORTRAN、Lisp、Pascal、C、C++和Java。在介绍这些语言的同时，还介绍了利用它们进行程序设计的过程，包括自顶向下的设计和面向对象的设计。我们对抽象数据类型及其实现所扮演的角色的理解已经成熟了。操作系统和它的资源管理技术（包括更大、更快的二级存储介质上的文件）包围着这些程序，并对它们进行管理。
接下来的一层由更复杂的通用或专用软件系统构成，它们覆盖了操作系统。这些功能强大的程序由计算机科学中的并行理论支持。最后一层由网络和网络软件构成，网络软件包括计算机之间通信必需的所有工具。Internet和万维网给这一层画上了最后一笔。
当这些层随着时间的流逝逐渐增长时，用户对计算机系统的硬件接触得越来越少。每个层都是它下面的计算机系统的抽象。随着每个层的发展，新层的用户和内部层的用户联合起来，在经济领域的高科技部门创造了大量的生产力。本书的目的是提供各个层的概述，介绍基础的硬件和软件技术，使学生了解和欣赏计算系统的方方面面。
在介绍这种洋葱式结构时，我们有两种选择，一种是从内向外逐层介绍，另一种是从外向内进行介绍。从外向内的方法看来非常吸引人。我们可以从最抽象的层开始介绍，一次剥掉一个层，直到具体的机器层为止。但是，研究表明，比起抽象的例子，学生们更容易理解具体的例子，即使他们本身是抽象思想家。因此，我们选择从具体的机器层开始，按照层的创建顺序进行分析，当学生完全理解了一个层之后，再转移到下一个层就比较容易。
第2版中的变化
一本全新的书的第1版就像一艘新船的试航。如果设计足够好，那么就只有一些小问题需要调整。当这本书成了旧的，它未来的版本可能会要求全面修订。幸运的是，我们的读者认为这本书的设计是稳定的，在这一版中，只需要进行一些改动。
我们更新了一些传记，把旧的轶闻趣事换成了新的，而且还使“道德问题”部分反映的是当前的问题。我们将在下面的摘要中指出内容的变化。
除了内容的变化，我们还修改了练习。练习中的问题被分为两类，即主观题和客观题。许多教育者认为客观练习（包括多项选择、对错判断和填空）是无用的。但是，根据伊利诺伊大学的测试和评估部的研究，主观测试和客观测试可以衡量相似的内容和学习目标。根据两项相隔42年的研究，学生对短文和涵盖相同内容的客观测试题的反应几乎完全一样。
因此，我们决定同时采用客观题和主观题。每一章都有多项选择题和判断题，还有简答题和需要解决方案的问题。对于大班来说，讲师可以利用这些问题快速地设计出小测验。
摘要
如前面的小节中所述，第1章是基础篇。第2章和第3章则分析了包含在物理硬件中的层。我们称这个层为信息层，它反映了如何在计算机上表示信息。第2章介绍了二进制数制以及它与其他数制（如人们日常用的十进制系统）的关系。第3章研究了如何获取多种类型（如数字、文本、图像、音频和视频）的信息以及如何用二进制格式表示它们。此外，本章还介绍了如何把数字的小数部分转换成二进制的。这一版中还加入了关于MP3音频格式的讨论。
第4章和第5章说明了硬件层。计算机硬件包括的设备有晶体管、门和电路，它们都按照基本原理控制电流。正是这些核心电路，使专用的元件（如计算机的中央处理器CPU）得以运转。第4章介绍了门和电路。第5章介绍了计算机的元件，以及在von Neumann体系结构中这些元件是如何交互的。我们对第5章进行了下列修改：使用的广告变了；表示速度时，采用以10为底的幂，表示内存大小时，采用以2为底的幂；最后添加了一个关于触摸屏的小节。
第6～9章介绍了程序设计层。第6章分析了问题求解过程，同时涉及人类和计算机的问题求解方法。引导这个论题的是George Polya的人类问题求解策略。两种问题求解方法—自顶向下的设计和面向对象的设计都有相关的示例。第7章使用模拟计算机Pep/7介绍了机器语言和汇编语言的概念。简单的问题被转化成了机器代码和汇编语言。这一章的改变相当大。读者建议简化它的体系结构，介绍一些分支，所以，这里只利用了一个寄存器，介绍了两个分支语句。第8章介绍了高级程序设计语言的概念。我们用四种程序设计语言设计了一些小例子来说明这些概念，它们是Ada、VB.NET（Visual Basic 7）、C++和Java。第9章强调了抽象数据类型和数据结构在程序设计过程中的角色。
第10章和第11章介绍了操作系统层。第10章讨论了操作系统的资源管理任务，介绍了一些用于实现这些任务的基础算法。第11章介绍了文件系统，包括什么是文件系统，以及操作系统如何管理它们。第10章增加了关于设备驱动程序的讨论。
第12～14章介绍了应用层。这一层由人们用来解决问题的通用应用程序和专用应用程序构成。我们根据这些程序的基础，把这一层分到了计算机科学的几个子学科中。第12章分析了信息系统，第13章分析了人工智能，第14章分析了模拟、计算机辅助设计法和嵌入式系统。
第15章和第16章介绍了通信层。第15章说明了计算机之间通信的理论和应用。第16章介绍了万维网和它对当今生活的影响。第16章增加了搜索引擎和即时消息传送两个小节，并且详细讨论了cookie。
从第2～16章都是说明计算机可以做什么以及它是如何做的。第17章进行了总结，讨论了计算机硬件和软件的固有局限性，以及计算机能够解决和不能解决的问题。在讨论算法的有效性时，采用了大O符号，以便讨论算法的分类。此外还介绍了停机问题，以说明某些不能解决的问题。
本书的第1章和最后一章就像一对书挡，第1章说明了计算系统是什么，第17章告诫我们计算系统不能做什么。它们之间的章节则深入探讨了构成计算系统的各个层。
为什么不介绍一种语言？
本书原来的大纲中包括Java入门一章。有些评论家对本书是否应该包括对一种语言的介绍感到很矛盾，而另一些评论家则质疑，为什么包括Java语言，而不是C++。我们决定让用户自己选择，在本书的网站上有Java语言入门、C++语言入门和Pascal语言入门的章节，它们的格式与本书的设计一致。
如果除了本书中的背景资料，学生还有能力掌握一种语言的基本语法和语义，那么让他们下载相应的文章即可。另外，还可以将这些文章作为具有较强背景的学生的补充资料。
特性
本书具有三种特性，用于强调计算的历史、广度以及新技术带来的道德义务。每一章都有一个简短的人物传记，介绍对计算做出了杰出贡献的人。这些人包括对信息层做出贡献的George Boole和Ada Lovelace，以及对通信层做出贡献的Doug Engelbart和Tim Berners-Lee。这些传记的目的是让学生们了解计算世界的历史以及那些对计算世界做过贡献和正在做贡献的人们。
我们称第二个特性为“标注”，因为没有更好的词可以表达它。标注显示在文本框中，是过去、现在和未来的一些轶闻趣事，它们来自历史记录、当今的报纸和作者的见闻。这些小插曲的目的是为了使学生开心、鼓舞他们、激发他们的兴趣，当然还为了教育他们。
第三个特性是每章中的“道德问题”小节。这些小节的目的是为了说明在利用计算的好处时要承担的义务。隐私权、黑客、病毒和言论自由都属于我们的论题。在每章练习的结尾处有一个思考题部分，涉及这些道德问题和这一章的内容。
本书的网站
本书的网站（http://csilluminated.jbpub.com）包括大量的补充信息。在这个网站上可以访问更多的人物传记、更多的标注以及关于道德问题的更新。
此外，还可以下载Java语言、C++语言和Pascal语言的入门文章以及Pep/7虚拟机。
本书中给出了部分练习的答案，剩下的答案都在这个网站上。此外，网站上还有其他的练习，它们使用了新的格式。
致谢
除了出版社的审校者，还有一些人也审读了我们的部分手稿：Mary Dee Harris，Chris Edmondson-Yurkanan，UT大学计算机科学系的Ben Kuipers，宾夕法尼亚州的Dave Stauffer，北爱荷华大学的John McCormick以及Pulaski技术学院的Mike Mc Millan。感谢这些朋友和同仁，你们的评论和建议十分宝贵。
我们还要感谢采用本书第1版作为教材的三位用户所提供的很好的建议，他们是：芝加哥Loyola大学的Michael Goldwasse和Andrew Harrington，马萨诸塞州Wellesley的MassBay Community大学的Daniel R. Collins。
我还必须感谢我的网球朋友使我有一个健康的体魄，感谢我的桥牌朋友使我的头脑十分机敏，感谢我的家人做我的坚强后盾。
Nell Dale, John Lewis：Nell Dale: 计算机科学领域广受推崇的教育家。在得克萨斯大学执教的25年中，由她编写的计算机科学方面的大学本科教材就超过了20种。她从得克萨斯大学取得了数学硕士学位以及计算机科学博士学位。由于她对计算机科学教学领域的突出贡献，1996年她被授予了ACM SIGCSE 计算机科学教育最杰出贡献奖。
John Lewis: 计算机科学领域著名的教育家和作家。由他编写的Java软件及程序设计教材在该类书籍的畅销榜上赫赫有名。他于弗吉尼亚理工大学获得硕士及博士学位，并任教于维拉诺瓦大学计算机科学系。执教期间他获奖无数，研究方向包括面向对象技术、多媒体以及软件工程。
张欣 等：暂无简介
《计算机科学概论》是每一个学习计算机科学的人应该读的第一本书。当我翻译完整本书后，一直在想，为什么在我的大学课程中，没有这样一门课，能够系统连贯地讲述一遍计算机科学发展的历史，以至于学完了所有的大学课程，对于计算机科学还没有一个整体的认识。这本书除了系统地介绍整个计算机系统，同时还讲述了计算机系统的发展史。在阅读每个章节时，你都会明白这个章节要介绍的硬件、软件、语言等的来龙去脉，这样就能为以后的深入研究打下坚实的基础。
本书的主旨就是为了给初学者提供一本全面了解计算机科学的教材。本书的作者具有丰富的实际教学经验，真正了解初学者需要什么，而且他们还集思广益，使得这本书的内容更加完善。在这本书中，作者用了一个形象的比喻，把计算机系统比作洋葱，它们的相似之处就在于内部结构都是一层层的。
第1章是基础篇，介绍了硬件和软件的历史，以及计算机系统的洋葱式结构。以后的各章就根据这种结构，分别介绍了计算机系统的信息层、硬件层、程序设计层、操作系统层、应用程序层和通信层，最后则总结性地讨论了计算机硬件和软件固有的局限性，以及计算机能够解决和不能解决的问题。
除了详细地介绍计算机系统的方方面面，这本书还有三个亮点。第一，在每一章中都有一篇人物传记，记述了对计算机科学的发展做出过杰出贡献的人的生平。你可以想到的计算机界的传奇人物，几乎都可以在本书中找到他或她的踪影。第二，在每一章的结尾，还有一篇涉及法律和道德的短文，探讨了计算机科学发展史上出现过的一些有争议的问题。读过这些短文，你一定会对计算机科学有更深一步的了解。第三，每章后面都附带有大量的练习，可以帮助你即时重温这一章所讲述的内容，有助于你更好地掌握这些内容。
本书很适合作为计算机科学专业学生的入门教材。不过，即使是非计算机专业的学生和非专业人员，想要了解计算机科学的概况，本书也不失为一个很好的选择。
本书由张欣组织翻译和审校，参与本书翻译的还有何健辉、黄璜、白佳、卞雨桂、陈洁、成洁、杜鲲、李才应、刘天成、刘吟、明卫军、潘秀燕、钱金蕾、王华红、魏胜、阎哲、王林、陈思锦、金川。
在翻译过程中，我们力求忠实、准确地把握原著的内容，但由于译者水平有限，书中难免有错误和不准确之处，敬请广大读者批评指正。
张 欣
于北京
2005年6月
第一部分 基 础 篇
第1章 全景图 1
1.1 计算系统 1
1.1.1 计算系统的分层 2
1.1.2 抽象 3
1.2 计算的历史 5
1.2.1 计算硬件的简史 5
1.2.2 计算软件的简史 11
1.2.3 预言 14
1.3 计算工具和计算学科 15
小结 16
练习 17
思考题 19
第二部分 信 息 层
第2章 二进制数值和记数系统 21
2.1 数字分类 21
2.2 自然数 22
2.2.1 位置记数法 22
2.2.2 二进制、八进制和十六进制 25
2.2.3 其他记数系统中的运算 26
2.2.4 以2的幂为基数的记数系统 26
2.2.5 把十进制数转换成其他数制的数 28
2.2.6 二进制数值和计算机 29
小结 30
练习 31
思考题 33
第3章 数据表示法 34
3.1 数据和计算机 34
3.1.1 模拟信息和数字信息 35
3.1.2 二进制表示法 36
3.2 数字数据的表示法 38
3.2.1 负数表示法 38
3.2.2 实数表示法 40
3.3 文本表示法 42
3.3.1 ASCII字符集 43
3.3.2 Unicode字符集 43
3.3.3 文本压缩 44
3.4 音频信息表示法 47
3.4.1 音频格式 48
3.4.2 MP3音频格式 48
3.5 图像和图形的表示法 49
3.5.1 颜色表示法 49
3.5.2 数字化图像和图形 50
3.5.3 图形的矢量表示法 51
3.6 视频表示法 52
小结 53
练习 54
思考题 57
第三部分 硬 件 层
第4章 门和电路 59
4.1 计算机和电学 59
4.2 门 61
4.2.1 非门 61
4.2.2 与门 62
4.2.3 或门 62
4.2.4 异或门 63
4.2.5 与非门和或非门 63
4.2.6 门处理回顾 64
4.2.7 具有更多输入的门 64
4.3 门的构造 65
4.4 电路 66
4.4.1 组合电路 67
4.4.2 加法器 69
4.4.3 多路复用器 71
4.5 存储器电路 71
4.6 集成电路 72
4.7 CPU芯片 73
小结 73
练习 74
思考题 77
第5章 计算部件 78
5.1 独立的计算机部件 78
5.2 存储程序的概念 80
5.2.1 von Neumann体系结构 81
5.2.2 读取-执行周期 85
5.2.3 RAM和ROM 86
5.2.4 二级存储设备 87
5.2.5 触摸屏 90
5.3 非von Neumann体系结构 91
5.4 广告解析 92
小结 92
练习 94
思考题 96
第四部分 程序设计层
第6章 问题求解和算法设计 97
6.1 问题求解 97
6.1.1 如何解决问题 98
6.1.2 计算机问题求解 101
6.1.3 执行算法 103
6.1.4 开发算法 104
6.2 自顶向下设计 104
6.2.1 一个通用的实例 105
6.2.2 一个计算机实例 106
6.2.3 方法总结 110
6.2.4 测试算法 110
6.3 面向对象设计 112
6.3.1 面向对象 112
6.3.2 类之间的关系 113
6.3.3 面向对象设计方法 114
6.3.4 一个通用的实例 117
6.3.5 一个计算机实例 118
6.4 几个重要思想 121
6.4.1 信息隐蔽 121
6.4.2 抽象 122
6.4.3 事物命名 123
6.4.4 程序设计语言 123
6.4.5 测试 124
小结 124
练习 125
思考题 128
第7章 低级程序设计语言 129
7.1 计算机操作 129
7.2 抽象的分层 130
7.3 机器语言 130
7.4 一个程序实例 135
7.4.1 问题和算法 135
7.4.2 程序 136
7.5 汇编语言 139
7.5.1 Pep/7汇编语言 140
7.5.2 具有分支的程序 144
7.6 其他的重要思想 145
小结 148
练习 149
思考题 151
第8章 高级程序设计语言 152
8.1 翻译过程 152
8.1.1 编译器 152
8.1.2 解释器 153
8.2 程序设计语言的范型 155
8.3 命令式语言的功能性 156
8.3.1 Boolean表达式 156
8.3.2 强类型化 158
8.3.3 输入/输出结构 161
8.3.4 控制结构 163
8.3.5 复合数据类型 174
8.4 面向对象语言的功能性 177
8.4.1 封装 177
8.4.2 继承 178
8.4.3 多态性 178
小结 178
练习 180
思考题 184
第9章 抽象数据类型和算法 185
9.1 抽象数据类型 185
9.2 实现 186
9.2.1 基于数组的实现 186
9.2.2 链式实现 187
9.3 列表 189
9.3.1 列表的基础操作 189
9.3.2 其他列表操作 192
9.4 排序 192
9.4.1 选择排序 193
9.4.2 冒泡排序法 194
9.4.3 快速排序 195
9.5 二分检索法 199
9.6 栈和队列 200
9.6.1 栈 201
9.6.2 队列 202
9.6.3 实现 202
9.7 树 202
9.7.1 二叉树 203
9.7.2 二叉检索树 204
9.7.3 其他操作 207
9.7.4 图 208
9.8 程序设计库 209
小结 209
练习 210
思考题 213
第五部分 操作系统层
第10章 操作系统 215
10.1 操作系统的角色 215
10.1.1 内存、进程和CPU管理 216
10.1.2 批处理 217
10.1.3 分时操作 218
10.1.4 其他OS要素 219
10.2 内存管理 219
10.2.1 单块内存管理 220
10.2.2 分区内存管理 221
10.2.3 页式内存管理 222
10.3 进程管理 224
10.3.1 进程状态 224
10.3.2 进程控制块 225
10.4 CPU调度 225
10.4.1 先到先服务 226
10.4.2 最短作业优先 227
10.4.3 循环调度法 227
小结 228
练习 230
思考题 234
第11章 文件系统和目录 235
11.1 文件系统 235
11.1.1 文本文件和二进制文件 236
11.1.2 文件类型 236
11.1.3 文件操作 237
11.1.4 文件访问 238
11.1.5 文件保护 239
11.2 目录 240
11.2.1 目录树 240
11.2.2 路径名 241
11.3 磁盘调度 244
11.3.1 先到先服务磁盘调度法 245
11.3.2 最短寻道时间优先磁盘调度法 245
11.3.3 SCAN磁盘调度法 246
小结 246
练习 247
思考题 250
第六部分 应用程序层
第12章 信息系统 251
12.1 信息管理 251
12.2 电子制表软件 252
12.2.1 电子数据表公式 253
12.2.2 循环引用 257
12.2.3 电子数据表分析 257
12.3 数据库管理系统 258
12.3.1 关系模型 259
12.3.2 关系 260
12.3.3 结构化查询语言 262
12.3.4 数据库设计 263
小结 264
练习 265
思考题 268
第13章 人工智能 269
13.1 思维机 269
13.1.1 图灵测试 270
13.1.2 AI问题的各个方面 271
13.2 知识表达 271
13.2.1 语义网络 272
13.2.2 检索树 274
13.3 专家系统 276
13.4 神经网络 278
13.4.1 生物神经网络 278
13.4.2 人工神经网络 279
13.5 自然语言处理 280
13.5.1 语音合成 281
13.5.2 语音识别 282
13.5.3 自然语言理解 283
13.6 机器人学 283
13.6.1 感知-规划-执行范型 285
13.6.2 包孕体系结构 285
13.6.3 物理部件 286
小结 288
练习 289
思考题 291
第14章 模拟和其他应用程序 292
14.1 什么是模拟 292
14.1.1 复杂系统 292
14.1.2 模型 293
14.1.3 构造模型 293
14.1.4 排队系统 294
14.1.5 气象模型 297
14.1.6 其他模型 300
14.1.7 必要的计算能力 300
14.2 图形和计算机辅助设计 301
14.3 嵌入式系统 302
小结 303
练习 304
思考题 306
第七部分 通 信 层
第15章 网络 307
15.1 连网 307
15.1.1 网络的类型 308
15.1.2 Internet连接 310
15.1.3 包交换 312
15.1.4 GPS寻宝 313
15.2 开放式系统和协议 313
15.2.1 开放式系统 313
15.2.2 网络协议 314
15.2.3 TCP/IP 314
15.2.4 高层协议 315
15.2.5 MIME类型 316
15.2.6 防火墙 316
15.3 网络地址 317
小结 319
练习 321
思考题 323
第16章 万维网 324
16.1 Web简介 324
16.1.1 搜索引擎 325
16.1.2 即时消息 326
16.1.3 cookie 326
16.2 HTML 327
16.2.1 基本的HTML格式 329
16.2.2 图像和链接 330
16.3 交互式Web页 331
16.3.1 Java小程序 332
16.3.2 Java服务器页 332
16.4 XML 333
小结 336
练习 337
思考题 340
第八部分 总 结
第17章 计算的限制 341
17.1 硬件 341
17.1.1 算术运算的限制 341
17.1.2 通信的限制 346
17.2 软件 347
17.2.1 软件的复杂度 347
17.2.2 当前提高软件质量的方法 348
17.2.3 臭名昭著的软件错误 351
17.3 问题 352
17.3.1 算法比较 353
17.3.2 图灵机 357
17.3.3 停机问题 360
17.3.4 算法分类 361
小结 363
练习 364
思考题 366
部分练习答案 368
术语表 410
参考文献 428
