《计算机科学导论》是国外计算机等IT相关专业本科生的一本基础课教材，也是一本非常经典的计算机入门读物。作为一本百科全书式的计算机专业基础入门读物，书中涉及计算机科学的方方面面。虽然读者对象是计算机专业的学生，但这本书深入浅出，引人入胜，勾画出计算机科学体系的框架，为有志于IT行业的学生奠定计算机科学知识的基础，架设进一步深入专业理论学习的桥梁。

经典的计算机专业导论教材，展示计算机科学体系框架，奠定学科知识基础

计算机在我们的日常生活中扮演着一个重要的角色，而且在未来也将一样。计算机科学是一个充满了挑战和发展机遇的年轻学科。计算机网络将位于地球上每一个角落的我们连接在一起。虚拟现实创造了炫目的三维图像。宇宙空间探险的成功也部分归功于计算机的发展。计算机创建的特效改变了电影行业。计算机在遗传学研究中也扮演了重要的角色。
本书读者对象
这本书同时面向学术和专业读者。本书可以作为感兴趣的专业人士的自学指南。作为教材，本书包含一学期（semester）或一学季（quarter）的教学内容，是计算机科学的入门教程。本书是基于美国计算机学会（ACM）推荐的CS0课程设计的。它从广度上覆盖了计算机科学的所有领域。其他领域的学生需要对计算机科学有大致的了解时，无论是从本书中选读部分内容还是通读全书，都会有帮助。
第4版中的改动
在本版中进行了以下修改。
几乎所有的章节都做出了较小的修改。本书增添了两个新章（第19和20章）。第4章中的一些材料被移除，并扩展成两个新的附录（附录I和附录J）。
本书的组织
本书由20章和10个附录构成。
章节
章节的作用是提供基本的学习材料，但并不是书中的每一个章节都对学生有用。教这门课的教师可以自主选择教学章节。我们会在后面提供一份教学指南。
附录
附录的作用是为理解书中讨论的概念快速提供一份参照或复习材料。本书中有10个可供学生参照和学习的附录。
缩略语
本书包含的缩略语可帮助学生快速找到对应的术语。
术语表
为了使学生熟悉书中使用的术语，本书提供了一份全面的术语表。
教学法
本书中的教学特色可以帮助学生非常简便地理解书中的内容。
图文并茂
本书图文并茂，而且不使用复杂的公式来展示高深内容。本书附图超过400幅，以便读者形象而直观地了解本书内容。图片对于解释构成整体的各组件之间的关系极为重要。对于很多学生来说，通过图片比通过文字更容易掌握概念。
重点
把重要的概念放在阴影框中以便快速参考和即时注意。
范例和应用
在合适的情况下，书中引入了可以说明概念的例子。
算法
书中包含的算法有助于学生熟悉问题求解和编程。
UML
本书通篇使用UML图以使学生熟悉该工具，因为这已经成为业界的实际标准。
章末材料
每一章以一系列材料结束，包括以下部分：
推荐读物：简明地给出该章推荐书目列表。这些列表也用于快速地找到相应的文献。
小结：包括对该章中所有内容的概括，把该章最重要的内容整合在一起以便阅读。
练习
每章包括为强化重要概念同时鼓励学生进行实践而设计的练习。练习包括三部分内容：小测验、复习题、练习题。
小测验：本书网站上的小测验提供对概念掌握情况的快速测试。学生可以通过这些小测验来检测自己对所学内容的理解。
复习题：这个部分包括与书中讨论的概念有关的简单题。本书网站上为学生提供了奇数编号复习题的答案以供核对。
练习题：这一部分包括难度更大的题目，求解这些题目需要对该章讨论的内容有更深层次的理解。强烈推荐学生尝试求解这部分的全部题目。奇数编号练习题的答案也已经公布在本书网站上，以便学生进行核对。
教师资源
本书为教授该课程的教师提供了完整的教学资源，可以从本书网站下载它们。
演示文稿
本书网站为教授该课程的教师提供了一系列动画式的彩色幻灯片演示文稿。
练习答案
本书网站为教授该课程的教师提供了所有复习题和练习题的答案。
学生资源
在本书网站上包含完整的学生资源，包括：
小测验
学生可以完成章末小测验，以检查自己对相应章节材料的理解程度。
奇数编号练习题答案
为了方便学生使用，本书网站上提供了所有奇数编号复习题和练习题的答案。
如何使用本书
本书的章节组织灵活，建议按以下指南学习：
第1～8章内容对理解本书其余内容而言是必要的。
如果时间允许，可以教授第9～14章内容。在学季制中这些内容可以省去。
第15～20章内容应该基于学生的专业和教师的判断有选择地教授。
致谢
显而易见，出版这样一本教材需要很多人的支持。
感谢为本书的出版做出贡献的审稿人员，他们是：
南澳大学的Sam Ssemugabi
博茨瓦纳会计学院的Ronald Chikati
林波波大学的Alex Dandadzi
埃因霍温科技大学的Tom Verhoeff
比勒陀利亚大学的Stefan Gruner
英国白金汉大学的Harin Sellahwea
威尔士大学的John Newman
Birbeck学院的Steve Maybank
斯特灵大学的Mario Kolberg
伍斯特大学的Colin Price
伦敦城市大学的Boris Cogan
希尔德斯海姆大学的Thomas Mandl
南非大学的Daphne Becker
阿卜杜拉国王大学的Lubna Fekry Abdulhai和Osama Abulnaja
利物浦大学的Katie Atkinson
特别感谢出版社的工作人员：Andrew Ashwin、Annabel Ainscow、Jennifer Grene、Phillipa Davidson-Blake。

Behrouz A. Forouzan
加利福尼亚州洛杉矶
2018年1月

计算机科学及应用

本书是国际知名的高等学校计算机科学及相关专业基础课教材，也是非常受欢迎的计算机入门读物。该教材是一本百科全书式的计算机专业入门指南，涉及计算机科学的方方面面。虽然读者对象是计算机专业的学生，但这本书深入浅出、引人入胜，勾画出了计算机科学体系的框架，可以为有志于IT行业的学生奠定计算机科学知识的基础，架设进一步深入专业理论学习的桥梁。
作为一本条理清晰并且深入浅出的教材，本书强调的是概念而不是数学模型和技术细节，并通过加入大量图、表来增强读者对知识的理解和掌握，提供相关范例来讲解概念和相关的数学模型，精心设计章末的关键术语、小结和练习来帮助读者复习巩固学习效果。
本书是基于美国计算机学会（ACM）推荐的CS0课程设计的，从广度上覆盖了计算机科学所有的领域，既适合国内高等学校用作计算机基础课教材，也可以供有意在计算机方面发展的非计算机专业读者作为入门参考。
本书第4版与时俱进，根据课程要求进行了修改，新增了两章（分别是第19章社交媒体导论与第20章社会和道德问题），并基于计算机技术的发展和变化更新了相关章节内容。

作者简介：
贝赫鲁兹·佛罗赞（Behrouz Forouzan） 毕业于加州大学欧文分校，在工业界和教育领域具有30多年的研发和教学经验。在离开工业界后，他在德安扎学院（De Anza College）担任计算机科学教授，现已退休。除了这本教材之外，他还编写了该学科的多部畅销教材。

[美] 贝赫鲁兹·佛罗赞（Behrouz Forouzan） 著：Behrouz Forouzan，毕业于加州大学欧文分校，在工业界和教育领域具有30多年的研发和教学经验。在离开工业界后，他在德安扎学院（De Anza College）担任计算机科学教授，现已退休。除了这本教材之外，他还编写了该学科的多部畅销教材

本书是国外著名大学采用的计算机基础课教材，供大学低年级学生使用。本书涉及了计算机科学的诸多方面，就像一部百科全书一样便于读者学习，增强读者对计算机科学的兴趣，为今后的课程学习打下坚实的基础。
本书是基于美国计算机学会（ACM）推荐的CS0课程设计的，涵盖了计算机科学的所有领域。本书在内容安排上既体现了计算机科学的广度，又兼顾了相关主题的深度，同时紧跟当前的技术发展趋势（如社交网络等），除此之外还增添了社会道德问题等方面的内容。在这本书中，作者通过大量的图片、图表和演示来增强读者对内容的理解和知识的掌握，并通过关键术语、小结和练习帮助读者复习知识要点。为了让读者更好地理解书中所讨论的概念，书末还配有10个可供读者参考的附录。这是一本不可多得的教学用书。
本书既适合作为高等院校计算机相关专业的计算机基础课教材，也适合作为非计算机专业学生深化计算机知识和技能的学习教材，同时还可以供广大计算机爱好者参考。
本书的主要译者为吕云翔、杨洪洋、曾洪立，胡健宁、高峻逸、索宇澄、陈妙然和唐思渊也参与了部分内容的翻译。本书涉及的知识面广，技术内容又很新，这给我们的翻译带来了一定的挑战性。由于译者水平有限，书中难免有疏漏之处，恳请各位同仁和广大读者予以批评指正（E-mail：yunxianglu@hotmail.com）。

译　者
2020年1月

出版者的话
译者序
前言
第1章　绪论1
1.1　图灵模型1
1.1.1　数据处理器1
1.1.2　可编程数据处理器2
1.1.3　通用图灵机3
1.2　冯·诺依曼模型3
1.2.1　4个子系统3
1.2.2　存储程序概念4
1.2.3　指令的顺序执行4
1.3　计算机组成部分4
1.3.1　计算机硬件4
1.3.2　数据4
1.3.3　计算机软件5
1.4　历史6
1.4.1　机械计算机器（1930年以前）6
1.4.2　电子计算机的诞生（1930～1950年）7
1.4.3　计算机的诞生（1950年至今）7
1.5　计算机科学作为一门学科8
1.6　课程纲要8
1.6.1　第一部分：数据的表示与运算8
1.6.2　第二部分：计算机硬件8
1.6.3　第三部分：计算机软件8
1.6.4　第四部分：数据组织与抽象9
1.6.5　第五部分：高级话题9
1.6.6　第六部分：社交媒体和社会话题9
1.7　章末材料9
1.8　练习10
第2章　数字系统11
2.1　引言11
2.2　位置化数字系统11
2.2.1　十进制系统12
2.2.2　二进制系统13
2.2.3　十六进制系统14
2.2.4　八进制系统15
2.2.5　4种位置化数字系统小结16
2.2.6　转换16
2.3　非位置化数字系统21
2.4　章末材料22
2.5　练习23
第3章　数据存储27
3.1　数据类型27
3.1.1　计算机内部的数据28
3.1.2　数据压缩28
3.1.3　错误检测和纠正29
3.2　存储数字29
3.2.1　存储整数29
3.2.2　3种系统的比较34
3.2.3　实数35
3.3　存储文本41
3.3.1　代码41
3.4　存储音频42
3.4.1　采样42
3.4.2　量化42
3.4.3　编码43
3.4.4　声音编码标准43
3.5　存储图像43
3.5.1　光栅图43
3.5.2　矢量图44
3.6　存储视频45
3.7　章末材料45
3.8　练习47
第4章　数据运算50
4.1　逻辑运算50
4.1.1　位层次上的逻辑运算 50
4.1.2　模式层次上的逻辑运算52
4.2　移位运算54
4.2.1　逻辑移位运算54
4.3　算术运算56
4.3.1　整数的算术运算56
4.3.2　实数的算术运算58
4.4　章末材料58
4.5　练习59
第5章　计算机组成61
5.1　引言61
5.2　中央处理单元61
5.2.1　算术逻辑单元62
5.2.2　寄存器62
5.2.3　控制单元63
5.3　主存储器63
5.3.1　地址空间63
5.3.2　存储器的类型64
5.3.3　存储器的层次结构65
5.3.4　高速缓冲存储器65
5.4　输入/输出子系统66
5.4.1　非存储设备66
5.4.2　存储设备66
5.5　子系统的互连70
5.5.1　CPU和存储器的连接70
5.5.2　I/O设备的连接71
5.5.3　输入／输出设备的寻址73
5.6　程序执行74
5.6.1　机器周期74
5.6.2　输入／输出操作75
5.7　不同的体系结构77
5.7.1　CISC77
5.7.2　RISC77
5.7.3　流水线77
5.7.4　并行处理78
5.8　简单计算机79
5.8.1　CPU80
5.8.2　主存80
5.8.3　输入/输出子系统80
5.8.4　指令集81
5.8.5　处理指令82
5.8.6　存储程序和数据83
5.8.7　指令周期83
5.8.8　另一个例子85
5.8.9　可重用性87
5.9　章末材料87
5.10　练习89
第6章　计算机网络和因特网92
6.1　引言92
6.1.1　网络92
6.1.2　因特网93
6.1.3　硬件和软件95
6.1.4　协议分层95
6.1.5　TCP/IP协议族97
6.2　应用层99
6.2.1　提供服务100
6.2.2　应用层模式100
6.2.3　标准客户机-服务器应用101
6.2.4　文件传输协议103
6.2.5　电子邮件104
6.2.6　TELNET105
6.2.7　安全外壳106
6.2.8　域名系统106
6.2.9　端到端模式108
6.3　传输层109
6.3.1　传输层服务110
6.3.2　传输层协议111
6.4　网络层111
6.4.1　网络层提供的服务112
6.4.2　网络层协议114
6.5　数据链路层116
6.5.1　节点和链接117
6.5.2　局域网118
6.5.3　广域网120
6.6　物理层122
6.6.1　数据和信号122
6.6.2　数字化传输124
6.6.3　模拟传输124
6.7　传输介质125
6.7.1　导向介质125
6.7.2　非导向介质：无线126
6.8　章末材料127
6.9　练习129
第7章　操作系统132
7.1　引言132
7.1.1　操作系统132
7.1.2　自举过程133
7.2　演化133
7.2.1　批处理系统133
7.2.2　分时系统133
7.2.3　个人系统134
7.2.4　并行系统134
7.2.5　分布式系统134
7.2.6　实时系统134
7.3　组成部分134
7.3.1　用户界面135
7.3.2　内存管理器135
7.3.3　进程管理器138
7.3.4　文件管理器142
7.4　主流操作系统142
7.4.1　UNIX143
7.4.2　Linux144
7.4.3　Windows144
7.5　章末材料145
7.6　练习147
第8章　算法149
8.1　概念149
8.1.1　非正式定义149
8.1.2　示例149
8.1.3　定义动作151
8.1.4　细化151
8.1.5　泛化152
8.2　三种结构152
8.2.1　顺序152
8.2.2　判断152
8.2.3　循环152
8.3　算法的表示153
8.3.1　UML153
8.3.2　伪代码153
8.4　更正式的定义155
8.4.1　定义良好156
8.4.2　明确步骤156
8.4.3　产生结果156
8.4.4　在有限的时间内终止156
8.5　基本算法156
8.5.1　求和156
8.5.2　乘积157
8.5.3　最大和最小157
8.5.4　排序157
8.5.5　查找161
8.6　子算法163
8.6.1　结构图163
8.7　递归164
8.7.1　迭代的定义164
8.7.2　递归的定义164
8.8　章末材料166
8.9　练习167
第9章　程序设计语言170
9.1　演化170
9.1.1　机器语言170
9.1.2　汇编语言171
9.1.3　高级语言171
9.2　翻译172
9.2.1　编译172
9.2.2　解释172
9.2.3　翻译过程173
9.3　编程模式173
9.3.1　过程式模式174
9.3.2　面向对象模式176
9.3.3　函数式模式177
9.3.4　声明式模式179
9.4　共同概念179
9.4.1　标识符179
9.4.2　数据类型179
9.4.3　变量180
9.4.4　字面值180
9.4.5　常量181
9.4.6　输入和输出181
9.4.7　表达式181
9.4.8　语句182
9.4.9　子程序184
9.5　章末材料187
9.6　练习188
第10章　软件工程191
10.1　软件生命周期191
10.1.1　开发过程模型191
10.2　分析阶段192
10.2.1　面向过程分析192
10.2.2　面向对象分析193
10.3　设计阶段194
10.3.1　面向过程设计194
10.3.2　面向对象设计195
10.4　实现阶段195
10.4.1　语言的选择196
10.4.2　软件质量196
10.5　测试阶段197
10.5.1　白盒测试197
10.5.2　黑盒测试199
10.6　文档199
10.6.1　用户文档199
10.6.2　系统文档199
10.6.3　技术文档200
10.7　章末材料200
10.8　练习201
第11章　数据结构203
11.1　数组203
11.1.1　数组名与元素名205
11.1.2　多维数组205
11.1.3　存储配置205
11.1.4　数组操作206
11.1.5　字符串207
11.1.6　数组的应用207
11.2　记录208
11.2.1　记录名与域名208
11.2.2　记录与数组的比较208
11.2.3　记录数组209
11.2.4　数组与记录数组209
11.3　链表209
11.3.1　数组与链表210
11.3.2　链表名与节点名211
11.3.3　链表操作211
11.3.4　链表的应用218
11.4　章末材料218
11.5　练习219
第12章　抽象数据类型221
12.1　背景221
12.1.1　简单抽象数据类型221
12.1.2　复杂抽象数据类型222
12.1.3　定义222
12.1.4　抽象数据类型的模型222
12.1.5　实现223
12.2　栈223
12.2.1　栈的操作223
12.2.2　栈的抽象数据类型224
12.2.3　栈的应用224
12.2.4　栈的实现226
12.3　队列227
12.3.1　队列的操作227
12.3.2　队列的抽象数据类型228
12.3.3　队列的应用229
12.3.4　队列的实现230
12.4　广义线性表230
12.4.1　广义线性表的操作231
12.4.2　广义线性表的抽象数据类型232
12.4.3　广义线性表的应用233
12.4.4　广义线性表的实现234
12.5　树234
12.5.1　二叉树235
12.5.2　二叉树的操作236
12.5.3　二叉树的应用237
12.5.4　二叉树的实现238
12.5.5　二叉搜索树238
12.6　图240
12.7　章末材料240
12.8　练习242
第13章　文件结构244
13.1　引言244
13.1.1　顺序存取244
13.1.2　随机存取244
13.2　顺序文件245
13.2.1　更新顺序文件245
13.3　索引文件246
13.3.1　倒排文件247
13.4　散列文件247
13.4.1　散列方法248
13.4.2　冲突249
13.5　目录251
13.5.1　UNIX操作系统中的目录251
13.6　文本文件与二进制文件252
13.6.1　文本文件253
13.6.2　二进制文件253
13.7　章末材料253
13.8　练习255
第14章　数据库257
14.1　引言257
14.1.1　定义257
14.1.2　数据库的优点257
14.1.3　数据库管理系统258
14.2　数据库体系结构259
14.2.1　内层259
14.2.2　概念层259
14.2.3　外层259
14.3　数据库模型259
14.3.1　层次模型259
14.3.2　网状模型260
14.3.3　关系模型260
14.4　关系数据库模型260
14.4.1　关系260
14.4.2　关系的操作261
14.5　数据库设计265
14.5.1　实体关系模型266
14.5.2　从E-R图到关系266
14.5.3　规范化267
14.6　其他数据库模型268
14.6.1　分布式数据库268
14.6.2　面向对象数据库269
14.7　章末材料269
14.8　练习271
第15章　数据压缩273
15.1　引言273
15.2　无损压缩方法273
15.2.1　游程长度编码274
15.2.2　赫夫曼编码275
15.2.3　Lempel Ziv编码276
15.3　有损压缩方法279
15.3.1　图像压缩：JPEG280
15.3.2　视频压缩：MPEG282
15.3.3　音频压缩283
15.4　章末材料283
15.5　练习285
第16章　安全287
16.1　引言287
16.1.1　安全目标287
16.1.2　攻击288
16.1.3　服务和技术289
16.2　机密性289
16.2.1　对称密钥密码术290
16.2.2　非对称密钥密码术295
16.3　其他安全服务299
16.3.1　消息完整性299
16.3.2　消息验证300
16.3.3　数字签名301
16.3.4　实体验证304
16.3.5　密钥管理306
16.4　防火墙309
16.4.1　包过滤防火墙310
16.4.2　代理防火墙311
16.5　章末材料311
16.6　练习313
第17章　计算理论316
17.1　简单语言316
17.1.1　递增语句316
17.1.2　递减语句316
17.1.3　循环语句317
17.1.4　简单语言的威力317
17.2　图灵机319
17.2.1　图灵机组成部件319
17.2.2　对简单语言的模拟321
17.2.3　邱奇-图灵论题323
17.3　歌德尔数324
17.3.1　表示一个程序324
17.3.2　翻译一个数字324
17.4　停机问题325
17.4.1　停机问题是不可解的325
17.5　问题的复杂度326
17.5.1　不可解问题327
17.5.2　可解问题327
17.6　章末材料328
17.7　练习329
第18章　人工智能331
18.1　引言331
18.1.1　什么是人工智能331
18.1.2　人工智能简史331
18.1.3　图灵测试332
18.1.4　智能体332
18.1.5　编程语言332
18.2　知识表示332
18.2.1　语义网333
18.2.2　框架333
18.2.3　谓词逻辑334
18.2.4　基于规则的系统338
18.3　专家系统339
18.3.1　抽取知识339
18.3.2　抽取事实340
18.3.3　体系结构340
18.4　感知341
18.4.1　图像处理341
18.4.2　语言理解343
18.5　搜索345
18.5.1　搜索方法345
18.6　神经网络348
18.6.1　生物神经元348
18.6.2　感知器349
18.6.3　多层网络350
18.6.4　应用350
18.7　章末材料350
18.8　练习351
第19章　社交媒体导论354
19.1　引言354
19.2　Facebook355
19.2.1　梗概355
19.2.2　网页356
19.2.3　成员357
19.2.4　获取Facebook的服务358
19.2.5　朋友358
19.2.6　交换信息359
19.3　Twitter360
19.3.1　梗概360
19.3.2　页面361
19.3.3　成员361
19.3.4　获取Twitter的服务362
19.3.5　跟随以及被跟随362
19.3.6　发送推文363
19.3.7　接收推文364
19.4　章末材料364
19.5　练习365
第20章　社会和道德问题366
20.1　道德原则366
20.1.1　道德规则366
20.1.2　使用366
20.1.3　社会契约366
20.2　知识产权367
20.2.1　知识产权的类型367
20.3　隐私368
20.4　计算机犯罪368
20.4.1　攻击的类型368
20.4.2　动机369
20.4.3　攻击保护369
20.4.4　花费369
20.5　黑客369
20.6　章末材料369
20.7　练习370
附录A　Unicode372
附录B　UML376
附录C　伪代码384
附录D　结构图387
附录E　布尔代数和逻辑电路390
附录F　C、C++和Java程序示例403
附录G　数学知识410
附录H　错误检测和纠正417
附录I　符号加绝对值整数的加减法428
附录J　实数的加减法431
缩略语434
术语表436