计算机科学导论（原书第4版）

计算机在我们的日常生活中扮演着一个重要的角色，而且在未来也将一样。计算机科学是一个充满了挑战和发展机遇的年轻学科。计算机网络将位于地球上每一个角落的我们连接在一起。虚拟现实创造了炫目的三维图像。宇宙空间探险的成功也部分归功于计算机的发展。计算机创建的特效改变了电影行业。计算机在遗传学研究中也扮演了重要的角色。
本书读者对象
这本书同时面向学术和专业读者。本书可以作为感兴趣的专业人士的自学指南。作为教材，本书包含一学期（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相关专业本科生的一本基础课教材，也是一本非常经典的计算机入门读物。作为一本百科全书式的计算机专业基础入门读物，书中涉及计算机科学的方方面面。虽然读者对象是计算机专业的学生，但这本书深入浅出，引人入胜，勾画出计算机科学体系的框架，为有志于IT行业的学生奠定计算机科学知识的基础，架设进一步深入专业理论学习的桥梁。

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

出版者的话
译者序
前言
第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

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

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