正版新书]计算机科学导论(原书第3版)/计算机科学丛书(美)贝赫鲁

出版者的话

译者序

前言

第1章绪论

1.1图灵模型

1.1.1数据处理器

1.1.2可编程数据处理器

1.1.3通用图灵机

1.2冯·诺依曼模型

1.2.14个子系统

1.2.2存储程序概念

1.2.3指令的顺序执行

1.3计算机组成部分

1.3.1计算机硬件

1.3.2数据

1.3.3计算机软件

1.4历史

1.4.1机械计算机器(1930年以前)

1.4.2电子计算机的诞生(1930~1950年)

1.4.3计算机的诞生(1950年至今)

1.5社会问题和道德问题

1.5.1社会问题

1.5.2道德问题

1.6计算机科学作为一门学科

1.7课程纲要

1.7.1第一部分：数据的表示与运算

1.7.2第二部分：计算机硬件

1.7.3第三部分：计算机软件

1.7.4第四部分：数据组织与抽象

1.7.5第五部分：不错话题

1.8章末材料

1.9练习

第2章数字系统

2.1引言

2.2位置化数字系统

2.2.1十进制系统(以10为底)

2.2.2二进制系统(以2为底)

2.2.3十六进制系统(以16为底)

2.2.4八进制系统(以8为底)

2.2.54种位置化数字系统的小结

2.2.6转换

2.3非位置化数字系统

2.4章末材料

2.5练习

第3章数据存储

3.1数据类型

3.2存储数字

3.2.1存储整数

3.2.23种系统的比较

3.2.3实数

3.3存储文本

3.4存储音频

3.4.1采样

3.4.2量化

3.4.3编码

3.4.4声音编码标准

3.5存储图像

3.5.1光栅图

3.5.2矢量图

3.6存储视频

3.7章末材料

3.8练习

第4章数据运算

4.1逻辑运算

4.1.1位层次上的逻辑运算

4.1.2模式层次上的逻辑运算

4.2移位运算

4.3算术运算

4.3.1整数的算术运算

4.3.2实数的算术运算

4.4章末材料

4.5练习

第5章计算机组成

5.1引言

5.2中央处理单元

5.2.1算术逻辑单元

5.2.2寄存器

5.2.3控制单元

5.3主存储器

5.3.1地址空间

5.3.2存储器的类型

5.3.3存储器的层次结构

5.3.4高速缓冲存储器

5.4输入/输出子系统

5.4.1非存储设备

5.4.2存储设备

5.5子系统的互连

5.5.1CPU和存储器的连接

5.5.2I/O设备的连接

5.5.3输入/榆出设备的寻址

5.6程序执行

5.6.1机器周期

5.6.2输入/输出操作

5.7不同的体系结构

5.7.1CISC

5.7.2RISC

5.7.3流水线

5.7.4并行处理

5.8简单计箅机

5.8.1CPU

5.8.2主存

5.8.3榆入/揄出子系统

5.8.4指令集

5.8.5处理指令

5.8.6存储程序和数据

5.8.7指令周期

5.8.8另一个例子

5.8.9可重用寸生

5.9章末材料

5.10练习

第6章计算机网络和因特网

6.1引言

6.1.1网络

6.1.2因特网

6.1.3硬件和软件

6.1.4协议分层

6.1.5TCP/IP协议族

6.2应用层

6.2.1提供服务

6.2.2应用层模式

6.2.3标准化客户机-服务器应用

6.2.4文件传输协议

6.2.5电子邮件

6.2.6TELNET

6.2.7安全外壳

6.2.8域名系统

6.2.9端到端模式

6.3传输层

6.3.1传输层服务

6.3.2传输层协议

6.4网络层

6.4.1网络层提供的服务

6.4.2网络层协议

6.5数据链路层

6.5.1节点和链接

6.5.2局域网

6.5.3广域网

6.6物理层

6.6.1数据和信号

6.6.2数字化传输

6.6.3模拟传输

6.7传输介质

6.7.1导向介质

6.7.2非导向介质

6.8章末材料

6.9练习

第7章操作系统

7.1引言

7.1.1操作系统

7.1.2自举过程

7.2演化

7.2.1批处理系统

7.2.2分时系统

7.2.3个人系统

7.2.4并行系统

7.2.5分布式系统

7.2.6实时系统

7.3组成部分

7.3.1用户界面

7.3.2内存管理器

7.3.3进程管理器

7.3.4文件管理器

7.4主流操作系统

7.4.1UNIX

7.4.2Linux

7.4.3Windows

7.5章末材料

7.6练习

第8章算法

8.1概念

8.1.1非正式定义

8.1.2定义动作

8.1.3细化

8.1.4泛化

8.2三种结构

8.2.1顺序

8.2.2一判断

8.2.3循环

8.3算法的表示

8.3.1UML

8.3.2伪代码

8.4更正式的定义

8.4.1定义良好

8.4.2明确步骤

8.4.3产生结果

8.4.4在有限的时间内终止

8.5基本算法

8.5.1求和

8.5.2乘积

8.5.3优选和最小

8.5.4排序

8.5.5查找

8.6子算法

8.7递归

8.7.1迭代的定义

8.7.2递归的定义

8.8章末材料

8.9练习

第9章程序设计语言

9.1演化

9.1.1机器语言

9.1.2汇编语言

9.1.3不错语言

9.2翻译

9.2.1编译

9.2.2解释

9.2.3翻译过程

9.3编程模式

9.3.1过程式模式

9.3.2面向对象模式

9.3.3函数式模式

9.3.4说明式模式

9.4共同概念

9.4.1标识符

9.4.2数据类型

9.4.3语句

9.5章末材料

9.6练习

第10章软件工程

10.1软件生命周期

10.2分析阶段

10.2.1面向过程分析

10.2.2面向对象分析

10.3设计阶段

10.3.1面向过程设计

10.3.2面向对象设计

10.4实现阶段

10.4.1语言的选择

10.4.2软件质量

10.5测试阶段

10.5.1白盒测试

10.5.2黑盒测试

10.6文档

10.6.1用户文档

10.6.2系统文档

10.6.3技术文档

10.7章末材料

10.8练习

第11章数据结构

11.1数组

11.1.1数组名与元素名

11.1.2多维数组

11.1.3存储配置

11.1.4数组操作

11.1.5数组的应用

11.2记录

11.2.1记录名与域名

11.2.2记录与数组的比较

11.2.3记录数组

11.2.4数组与记录数组

11.3链表

11.3.1数组与链表

11.3.2链表名与节点名

11.3.3链表操作

11.3.4链表的应用

11.4章末材料

11.5练习

第12章抽象数据类型

12.1背景

12.1.1简单抽象数据类型

12.1.2复杂抽象数据类型

12.1.3定义

12.1.4抽象数据类型的模型

12.1.5实现

12.2栈

12.2.1栈的操作

12.2.2栈的抽象数据类型

12.2.3栈的应用

12.2.4栈的实现

12.3队列

12.3.1队列的操作

12.3.2队列抽象数据类型

12.3.3队列的应用

12.3.4队列的实现

12.4广义线性表

12.4.1广义线性表的操作

12.4.2广义线性表的抽象数据类型

12.4.3广义线性表的应用

12.4.4广义线性表的实现

12.5树

12.5.1二叉树

12.5.2二叉树的操作

12.5.3二叉树的应用

12.5.4二叉树的实现

12.5.5二叉搜索树

12.5.6二叉搜索树的抽象数据类型

12.5.7二叉搜索树的实现

12.6图

12.7章末材料

12.8练习

第13章文件结构

13.1引言

13.1.1顺序存取

13.1.2随机存取

13.2顺序文件

13.3索引文件

13.4散列文件

13.4.1散列方法

13.4.2冲突

13.5目录

13.6文本文件与二进制文件

13.6.1文本文件

13.6.2二进制文件

13.7章末材料

13.8练习

第14章数据库

14.1引言

14.1.1定义

14.1.2数据库的优点

14.1.3数据库管理系统

14.2数据库体系结构

14.2.1内层

14.2.2概念层

14.2.3外层

14.3数据库模型

14.3.1层次模型

14.3.2网状模型

14.3.3关系模型

14.4关系数据库模型

14.5关系的操作

14.5.1结构化查询语言

14.5.2插入

14.5.3删除

14.5.4更新

14.5.5选择

14.5.6投影

14.5.7连接

14.5.8并

14.5.9交

14.5.10差

14.6数据库设计

14.6.1实体关系模型

14.6.2从E-R图到关系

14.6.3规范化

14.7其他数据库模型

14.8章末材料

14.9练习

第15章数据压缩

15.1引言

15.2无损压缩

15.2.1游程长度编码

15.2.2赫夫曼编码

15.2.3Lempel Ziv编码

15.3有损压缩方法

15.3.1图像压缩：JPEG

15.3.2视频压缩：MPEG

15.3.3音频压缩

15.4章末材料

15.5练习

第16章安全

16.1引言

16.1.1安全目标

16.1.2攻击

16.1.3服务和技术

16.2机密性

16.2.1对称密钥密码术

16.2.2非对称密钥密码术

16.3其他安全服务

16.3.1消息完整性

16.3.2消息验证

16.3.3数字签名

16.3.4实体验证

16.3.5密钥管理

16.4防火墙

16.4.1包过滤防火墙

16.4.2代理防火墙

16.5章末材料

16.6练习

第17章计算理论

17.1引言

17.2简单语言

17.2.1递增语句

17.2.2递减语句

17.2.3循环语句

17.2.4简单语言的威力

17.3图灵机

17.3.1图灵机组成部件

17.3.2对简单语言的模拟

17.3.3邱奇-图灵论题

17.4歌德尔数

17.4.1表示一个程序

17.4.2翻译一个数字

17.5停机问题

17.6问题的复杂度

17.6.1不可解问题

17.6.2可解问题

17.7章末材料

17.8练习

第18章人工智能

18.1引言

18.1.1什么是人工智能

18.1.2人工智能简史

18.1.3图灵测试

18.1.4智能体

18.1.5编程语言

18.2知识表示

18.2.1语义网

18.2.2框架

18.2.3谓词逻辑

18.2.4基于规则的系统

18.3专家系统

18.3.1抽取知识

18.3.2抽取事实

18.3.3体系结构

18.4感知

18.4.1图像处理

18.4.2语言理解

18.5搜索

18.6神经网络

18.6.1生物神经元

18.6.2感知器

18.6.3多层网络

18.6.4应用

18.7章末材料

18.8练习

附录AUnicode

附录BUML

附录C伪代码

附录D结构图

附录E布尔代数和逻辑电路

附录FC、C++和Java程序示例

附录G数学知识

附录H误差检测和校正

缩略语

术语表

计算机在我们的日常生活中扮演了一个重要的角色，而且在未来也将一样。计算机科学是一个充满了挑战和发展机遇的年轻学科。计算机网络将处在地球上每一个角落的我们连接在一起。虚拟现实创造了炫目的三维图像。宇宙空间探险的成功也部分归功于计算机的发展。计算机创建的特技效果改变了电影行业。计算机在遗传学研究中也扮演了一个重要的角色。
本书读者对象这本书同时面向学术的和专业的读者。本书可以作为感兴趣的专业人士的自学指南。作为教材，本书包含一学期(semester)或一学季(quarter)的教学内容，是计算机科学的入门教程。
本书是基于美国计算机学会( ACM)推荐的CSO课程设计的。它从广度上覆盖了计算机科学所有的领域。其他领域的学生需要对计算机科学有大致的了解时，无论是从本书中选读部分内容还是通读全书，都有帮助。
第3版中的改动在本版中我进行了以下几类修改。
1．修订的章节和附录针对教学目的，对本书中的两章和附录进行了全面的修订。
(1)第6章为了更便于初次接触计算机网络的学生进行理解，第6章的内容采用自顶向下的教学方法进行修订。
(2)第16章1．章节章节的作用是提供基本的学习材料，但并不是书中的每一个章节都对学生有利用价值。教这门课的老师可以自主选择教学用的章节。我们会在后面提供一份教学指南。
2．附录附录的作用是为理解书中讨论的概念所需的材料提供一个快速的参照或复习。本书中有8个可供学生参照和学习的附录。
3．缩略语本书包含一份缩略语表来帮助快速寻找到对应的术语。
4．术语表为了使学生熟悉书中使用的术语，本书提供一份广泛的术语表。
教学法本书中的部分教学法是为使学生可以很好简便地理解书中内容而设计的。
1．图文并茂本书图文并茂，而且不使用复杂的公式来展示高深内容。本书附图超过400幅，以便读者形象而直观地了解本书内容。图片对于解释构成整体的各组件之间的关系极为重要。对于很多学生来说，这些概念通过图片相比文字更容易掌握。
2．重点把重要的概念放在阴影框中以便快速参考和即时注意。
3．范例和应用在合适的情况下，在书中引入了可以说明概念的例子。
4．算法第3版增加了几十个算法，有助于学生熟悉问题求解和编程。
5．UML本书通篇使用UML图以使学生熟悉该工具，因为这已经成为业界的实际标准。
6．章末材料每一章以一系列材料结尾，包括以下部分：
(1)推荐读物这部分给出该章推荐书目列表。这些列表也用于参考引用。
(2)小结每章结尾的小结都包括了对该章中所有内容的概括。小结把该章最重要的内容都整合在一起以便阅读。
7．练习每章包括为强化重要概念同时鼓励学生进行实践而设计的练习。练习包括四部分内容：小测验、复习题、练习题和小程序。
(1)小测验本书网站上的小测验提供对概念掌握情况的快速测试。学生可以通过这些小测验来检测对所学内容的理解。
(2)复习题这个部分包括与书中讨论到的概念有关的简单题。本书网站上为学生提供了奇数编号复习?题的答案以供核对。
(3)练习题这一部分包括难度更大的题目，这些题目的求解需要对该章讨论的内容有更深层次的理解。我强烈推荐学生去尝试求解这部分的全部题目。奇数编号练习题的答案也已经公布在了本书网站以便学生进行核对。
(4)小程序Java小程序是作者编写并发布在网站上的交互式试验。这里的小程序有些用于更好地理解部分练习题的解答，而有些则用于更好地通过实践理解网络的概念。小程序是为了简化对部分范例的理解而专门设计的。
教VVif资源e本书为教该课程的老师提供完整的以下教学资源。他们可以从本书网站下载。
1．演示文稿本书网站为教授该课程的老师提供了一系列彩色的、动画式的幻灯片演示文稿。
2．练习的答案本书网站为教授该课程的老师提供了所有复习题和练习题的答案。
如何使用本书本书的章节提供了较大的灵活性组织。我建议以下几点：
·第l～8章内容对理解本书剩下内容而言是必要的。
·如果时间允许，可以教授第9～14章内容。在学季制(quarter)中这些内．容可以省去。
·第15～18章内容的教授应该基于学生的专业和老师的辨别力进行选择。
致谢显而易见，一本这样的教材得以出版需要很多人的支持。
1．书评人我要感谢为本书的发展做出贡献的书评人，他们是：
南非大学的Sam Ssemugabi博茨瓦纳会计学院的Ronald Chikati林波波大学的Alex Dandadzi埃因霍温科技大学的Tom Verhoeff比勒陀利亚大学的Stefan Gruner英国白金汉大学的Harmn Sellahwea威尔士大学的John NewmanBirbeck学院的Steve Maybank斯特灵大学的Mario Kolberge关于本书教辅资源，用书老师可向圣智学习出版公司北京代表处申请，电话：010-82862096/95/97，电子邮件：kai.yao@cengage.com或asia.infochina@cengage.com。——编辑注伍斯特大学的Colin Price伦敦城市大学的Boris Cogan希尔德斯海姆大学的Thomas Mandl南非大学的Daphne Becker阿卜杜拉国王大学的Osama Abulnaja和Lubna Fekry Abdulhai利物浦大学的Katie Atkinson2．出版社的人特另0感谢出版社的工作人员：Andrew Ashwin、Annabel Ainscow、Jennifer Grene、AlisonBurt。
Behrouz A. Forouzan加利福尼亚州，洛杉矶写于2014年1月对于第一次接触计算机科学的学生而言，安全的概念普遍较难接受。该章修订后的内容更通俗易懂。
(3)附录F该附录修订后的内容增加了三种计算机语言(C、C++和Java)的一些简易程序例子。
2．部分章节中的细微变化基于书评者的建议，部分章节的格式和内容进行了细微的修改，并且部分章节中增加了一些新的技术。
3．章末材料的变化章末材料主要经历了以下两个主要的变化：
·每章最后的多选题被删去了，增加了在线小测验，这样无论对老师检查教学成果，还是学生进行检验都方便许多。
·每章结尾增加了在线小程序来帮助学生发现一些问题的可视化解决方法。
组织这本书由18章和8个附录构成。
1．章节章节的作用是提供基本的学习材料，但并不是书中的每一个章节都对学生有利用价值。教这门课的老师可以自主选择教学用的章节。我们会在后面提供一份教学指南。
2．附录附录的作用是为理解书中讨论的概念所需的材料提供一个快速的参照或复习。本书中有8个可供学生参照和学习的附录。
3．缩略语本书包含一份缩略语表来帮助快速寻找到对应的术语。
4．术语表为了使学生熟悉书中使用的术语，本书提供一份广泛的术语表。
教学法本书中的部分教学法是为使学生可以很好简便地理解书中内容而设计的。
1．图文并茂本书图文并茂，而且不使用复杂的公式来展示高深内容。本书附图超过400幅，以便读者形象而直观地了解本书内容。图片对于解释构成整体的各组件之间的关系极为重要。对于很多学生来说，这些概念通过图片相比文字更容易掌握。
2．重点把重要的概念放在阴影框中以便快速参考和即时注意。
3．范例和应用在合适的情况下，在书中引入了可以说明概念的例子。
4．算法第3版增加了几十个算法，有助于学生熟悉问题求解和编程。
5．UML本书通篇使用UML图以使学生熟悉该工具，因为这已经成为业界的实际标准。
6．章末材料每一章以一系列材料结尾，包括以下部分：
(1)推荐读物这部分给出该章推荐书目列表。这些列表也用于参考引用。
(2)小结每章结尾的小结都包括了对该章中所有内容的概括。小结把该章最重要的内容都整合在一起以便阅读。
7．练习每章包括为强化重要概念同时鼓励学生进行实践而设计的练习。练习包括四部分内容：小测验、复习题、练习题和小程序。
(1)小测验本书网站上的小测验提供对概念掌握情况的快速测试。学生可以通过这些小测验来检测对所学内容的理解。
(2)复习题这个部分包括与书中讨论到的概念有关的简单题。本书网站上为学生提供了奇数编号复习?题的答案以供核对。
(3)练习题这一部分包括难度更大的题目，这些题目的求解需要对该章讨论的内容有更深层次的理解。我强烈推荐学生去尝试求解这部分的全部题目。奇数编号练习题的答案也已经公布在了本书网站以便学生进行核对。
(4)小程序Java小程序是作者编写并发布在网站上的交互式试验。这里的小程序有些用于更好地理解部分练习题的解答，而有些则用于更好地通过实践理解网络的概念。小程序是为了简化对部分范例的理解而专门设计的。
教VVif资源e本书为教该课程的老师提供完整的以下教学资源。他们可以从本书网站下载。
1．演示文稿本书网站为教授该课程的老师提供了一系列彩色的、动画式的幻灯片演示文稿。
2．练习的答案本书网站为教授该课程的老师提供了所有复习题和练习题的答案。
如何使用本书本书的章节提供了较大的灵活性组织。我建议以下几点：
·第l～8章内容对理解本书剩下内容而言是必要的。
·如果时间允许，可以教授第9～14章内容。在学季制(quarter)中这些内．容可以省去。
·第15～18章内容的教授应该基于学生的专业和老师的辨别力进行选择。
致谢显而易见，一本这样的教材得以出版需要很多人的支持。
1．书评人我要感谢为本书的发展做出贡献的书评人，他们是：
南非大学的Sam Ssemugabi博茨瓦纳会计学院的Ronald Chikati林波波大学的Alex Dandadzi埃因霍温科技大学的Tom Verhoeff比勒陀利亚大学的Stefan Gruner英国白金汉大学的Harmn Sellahwea威尔士大学的John NewmanBirbeck学院的Steve Maybank斯特灵大学的Mario Kolberge关于本书教辅资源，用书老师可向圣智学习出版公司北京代表处申请，电话：010-82862096/95/97，电子邮件：kai.yao@cengage.com或asia.infochina@cengage.com。——编辑注伍斯特大学的Colin Price伦敦城市大学的Boris Cogan希尔德斯海姆大学的Thomas Mandl南非大学的Daphne Becker阿卜杜拉国王大学的Osama Abulnaja和Lubna Fekry Abdulhai利物浦大学的Katie Atkinson2．出版社的人特另0感谢出版社的工作人员：Andrew Ashwin、Annabel Ainscow、Jennifer Grene、AlisonBurt。
Behrouz A. Forouzan加利福尼亚州，洛杉矶写于2014年1月