计算机科学概论（第8版）（英文影印版）

.social issues 70
additional reading 71
chapter 2 data manipulation 73
2.1 computer architecture 74
2.2 machine language 77
2.3 program execution 83
2.4 arithmetic/logic instructions 90
2.5 communicating with other devices 94
2.6 other architectures 99
chapter review problems 102
social issues 107
additional reading 108
chapter 3 operating systems 109
3.1 the evolution of operating systems 110
3.2 operating system architecture 113
3.3 coordinating the machine's activities 120
3.4 handling competition among processes 123
3.5 security 127
chapter review problems 129
social issues 132
additional reading 133
chapter 4 networking and the internet 135
4.1 network fundamentals 136
4.2 the internet 141
4.3 the world wide web 147
4.4 network protocols 156
4.5 security 164
chapter review problems 167
social issues 169
additional reading 170
chapter 5 algorithms 171
5.1 the concept of an algorithm 172
5.2 algorithm representation 175
5.3 algorithm discovery 182
5.4 iterative structures 188
5.5 recursive structures 199
5.6 efficiency and correctness 207
chapter review problems 216
social issues 222
additional reading 223
chapter 6 programming languages 225
6.1 historical perspective 226
6.2 traditional programming concepts 235
6.3 procedural units 246
6.4 language implementation 254
6.5 object-oriented programming 263
6.6 programming concurrent activities 269
6.7 declarative programming 272
chapter review problems .. 278
social issues 282
additional reading 283
chapter 7 software engineering 285
7.1 the software engineering discipline 286
7.2 the software life cycle 288
7.3 modularity 293
7.4 design methodologies 299
7.5 tools of the trade 303
7.6 testing 308
7.7 documentation 309
7.8 software ownership and liability 311
chapter review problems 313
social issues 316
additional reading 317
chapter 8 data abstractions 319
8.1 data structure fundamentals 320
8.2 implementing data structures 324
8.3 a short case study 337
8.4 customized data types 342
8.5 classes and objects 346
8.6 pointers in machine language 348
chapter review problems 350
social issues 355
additional reading 357
chapter 9 database systems 359
9.1 database fundamentals 360
9.2 the relational model 364
9.3 object-oriented databases 376
9.4 maintaining database integrity 379
9.5 traditional file structures 382
9.6 data mining 391
9.7 social impact of database technology 393
chapter review problems 395
social issues 400
additional reading 401
chapter 10 artificial intelligence 403
10.1 intelligence and machines 404
10.2 understanding images 408
10.3 reasoning 411
10.4 artificial neural networks 423
10.5 genetic algorithms 434
10.6 other areas of research 438
10.7 considering the consequences 446
chapter review problems 448
social issues 453
additional reading 455
chapter 11 theory of computation 457
11.1 functions and their computation 458
11.2 turing machines 460
11.3 universal programming languages 464
11.4 a noncomputable function 470
11.5 complexity of problems 476
11.6 public key cryptography 485
chapter review problems 489
social issues 493
additional reading 494
appendixes 495
a ascii 495
b circuits to manipulate two's complement
representations 497
c a simple machine language 501
d high-level language program examples 503
e the equivalence of iterative and recursive structures 511
f answers to questions/exercises 513
index ... 550

.　　11．1～11．2计算理论
　　除了整体情节外，还有几个贯穿全书的论题。论题之一是计算机科学是不断发展变化的。本教程以历史的观点来陈述各个专题，讨论这些专题的技术状况，并指出当今研究的一些方向。另一个论题是关于抽象的作用以及抽象工具用于控制复杂性的方法。该论题在第10章中引入，然后在操作系统体系结构、算法开发、编程语言设计、软件工程、数据表示和数据库系统等部分反复进行讨论。
　　给学生
　　在美国海军服役期间，我开始进入计算领域，那是在20世纪60年代末70年代初。(的确，服役使我的年龄变大了，但是年长使人变得明智，从而有可能写出一本好的教材)。我服役的大部分时间是维护位于英国伦敦的海军计算机设备的系统软件。服役期满后，我回到了学校，1975年获得了数学博士学位。从那时候开始，我一直从事计算机科学和数学的教学工作。
　　在这期间，计算机科学里许多东西已经改变了，但也有许多东西依然没有变。特别是，计算机依然是那么迷人，它衍生了许多令人敬畏的东西。因特网的发展、人工智能的进步以及信息获取和传播的能力以前所未有的速度提高，这些将影响人们生活的方式。生活在这令人振奋、富于变化的世界里，你们将大有作为，行动吧!
　　我有一点儿不听规劝(我的一些朋友会说远不只是“一点儿”)。在编写这本教程的过程中，我并不总是听从所收到的各种规劝。特别是，好多人认为，本教程的某些内容对于初学的大学生来说过于高深。但是，我相信，如果一个论题对于本教程是切题的，那么它就是合适的，即使这个论题被学院派认为是“高级论题”。人们应该得到一本全面而生动地介绍计算机科学的教科书，而不应该是个缩了水的版本——只包括那些被认为初学的大学生可以接受的主题，而且只做简化的介绍。因此，我不回避任何论题，而且尝试做出更好的讲解。我试图给出一幅具有足够深度的关于计算机科学的全面真实写照。如同给食谱加入调料，你们可以有选择地跳过某些专题，但是，将它们放在那儿是供你需要时品味的——我也鼓励你们这样做。..
　　最后，我应当指出，在任何一门关于技术的课程中，你们今天学习的细节可能并不是你们明天想要知道的细节。这个领域是不断发展变化的，这也是它充满激情的地方。本教程将给你们一幅本学科当前情况的写照以及它的历史背景。具有这些基础性知识，你们就能够伴随技术的进步而成长。我鼓励大家通过探索超越本教程所谈到的知识，开始成长的过程。学习，再学习。
　　感谢你们对我的信任，选择了这本教材，作为一个作者，我有责任写出一本值得你们花费时间去阅读的作品。我希望你们会发现，我尽到了这个责任。
　　给教师
　　本教程所包含的内容比一个学期能够讲授的要多，所以当你们想略掉那些不符合你的课程的那些主题时，或者当你们想选择合适的主题重新编排顺序讲授时，请不要犹豫。我写这本书是把它作为一种课程资源，而不是作为课程的定义。你们会发现，尽管本教程是遵循一条线索撰写的，但是有关的主题是以独立的方式讲述的，所以你们可以按照你们所希望的那样选择其中的内容。
　　在每章开始的目录中，我使用星号(*)来标识那些我建议的作为可选的章节。按我的看法，这些章节所探究的内容程度比较深，或者转到了你们不想涉及的方向。但这仅仅是建议，你们可以有许多选择。如果我把你们所喜欢的部分标为可选，那么你们也不必因此而烦恼。你们可以认为这是我的错误，你们尽可选择所需要的内容。
　　我还建议你们把某些题目的内容作为阅读材料，鼓励学生自己学习课堂上没有讲过的内容。我想，如果认为需要在课堂上讲清楚每一个问题，那么这就低估学生了。我们应该帮助他们学会如何自主地学习。
　　我前面已经说过，本教程遵循一种自底向上、从具体到抽象的结构，对此我还想做进一步的说明。作为学者，我们往往认为学生们会欣赏我们对某一学科的观点，这是我们多年来在特定领域里工作所积累的。作为老师，我认为最好从学生的观点来捉供教材。这就是本教程为什么从数据的表示和存储、计算机体系结构和机器语言开始的道理，因为这些正是学生们极其关心的问题——他们能够看到计算机部件，并且能够拿一拿它们，而且大多数学生将会购买并使用计算机。从这些主题开始这门课程的讲授，我发现学生们自己找到了那些已经困惑他们多年的“为什么”问题的答案，并且学会将本课程看成是一门实践课程而不是理论课程。从这出发，就会很自然转到诸如算法的开发、设计、表示和复杂性等比较抽象的主题(那些被该领域的人认为是这一课程主要论题)上来。
　　我认为，学生们潜移默化学到的东西要比教师课堂上教给他们的多得多，而且他们对于潜移默化学到的知识更容易吸收。在“讲授”问题求解时，这一点尤为重要。我认为，学生们要在通过解决问题的活动中学会解决问题，而不是依靠学习问题求解来获得这种本领。所以，我在本教程中提供了大量的问题。我鼓励你们使用这些问题，并拓展它们。
　　我在这里要指出的另一个问题是职业道德、伦理和社会责任感。我不认为这些问题可以作为孤立的主题来讲解。相反，当涉及到这些问题时就应该面对，这是我在本教程中的处理方法。你们会发现，0．6、3．5、4．5、7．1、7．8、9．7和10．7节提到了在操作系统、组网、数据库系统、软件工程和人工智能等领域里的安全、隐私、责任和社会意识问题。你们还将发现每一章都包含了一个称为“社会议题”的问题集合，这些问题向学生提出了一种挑战，让他们去思考本教程中的教材与他们生活的社会之间的关系。
　　感谢你们把本教程作为教科书。不管你们怎样判断本教程是否适合你们的情况，我还是希望你们会发现，本书是对计算机科学教学文献的一个贡献。
　　教学特点
　　本教程是多年教学的结晶。因此，它提供了丰富的教学辅助手段。最主要的是提供了许许多多的问题以加强学生们的参与——在第8版里包括了1000多个问题(确切地说是1007个)。它们分为“问题与练习(Questions／Exercises)”、“本章复习题(Chapter Review Problems)”和“社会议题(Social Issues)”三类。“问题与练习”在每节末尾，用于回顾刚刚讨论过的内容，扩展前面的讨论，或者暗示以后将会涉及的有关主题。这些问题的答案在附录F中。
　　“本章复习题”在每章的末尾(除第0章外)，它们被设计成“课外作业”形式，因为它们涉及整章的内容。这些问题本教程没有给出答案。
　　在每章的末尾还设有“社会议题”类问题，它们是供思考和讨论用的。许多问题可以用来开展课外研究，可采用简短的书面报告或口头报告的形式来描述研究的结果。
　　在每章的末尾还附有一个“课外阅读(Additional Reading)”，它列出了与本章内容有关的其他参考资料。
　　关于第8版
　　第8版相对以前各版本而言有几个重大的修改。以前版本有关操作系统和组网的那一章现在分为两章——第3章与第4章。在第4章中，扩充了组网的内容以正确反映网络发展的状况。“文件结构”那一章被取消了，有关的内容被分散到其他有关的各章中。(如果寻找有关顺序文件、索引文件和散列文件基本知识的资料，那么它们已经精简了，作为第9章中的可选节。)
　　第8版中其他的改变有：第0章的许多地方重写了。第1章有些内容作了重新安排，以加强二进制系统的分量。“程序设计语言”那一章(现在第6章)已经精简了。第7章关于设计模式的小节重写了，以包括组件系结构。关于“数据结构”一章的重点(和标题)已变成“数据抽象”(第8章)。第9章“数据库系统”中加了“数据挖掘”一节。第10章开始部分按照代理的观点重新写了，而“机器人”小节更新了。第11章讨论公开密钥加密方法时，现在是用RSA算法，而不再是背包问题。当然，整本教程处处都有许多细小的修改，以提供清晰的、更新的主题及其内容。
　　我很高兴编写第8版，希望大家也能够喜欢它。...