This page intentionally left blank
本页无内容

with contributions from 与贡献者合作

David T. Smith 大卫·T·史密斯

Indiana University of Pennsylvania
宾夕法尼亚印第安纳大学

Dennis Brylow 丹尼斯·布赖洛

Marquette University 马凯特大学

Editorial Director: Marcia Horton Editor-in-Chief: Michael Hirsch Editorial Assistant: Stephanie Sellinger Vice President of Marketing: Patrice Jones Marketing Manager: Yezan Alayan Marketing Coordinator: Kathryn Ferranti Vice President, Production: Vince O'Brien Managing Editor: Jeff Holcomb
主编：Marcia Horton 编辑总监：Michael Hirsch 编辑助理：Stephanie Sellinger 市场副总裁：Patrice Jones 市场经理：Yezan Alayan 市场协调员：Kathryn Ferranti 生产副总裁：Vince O'Brien 主编：Jeff Holcomb

Production Project Manager: Kayla Smith-Tarbox
生产项目经理：凯拉·史密斯-塔伯克斯

Senior Operations Supervisor: Lisa McDowell Art Directors: Jayne Conte and Kristine Carney
高级运营主管：Lisa McDowell 艺术总监：Jayne Conte 和 Kristine Carney
Cover Designer: Rachael Cronin
封面设计：Rachael Cronin

Cover Image: "Slot Canyon"
摄影作品封面："Slot Canyon"

(C) gettyimages Inc.
（C）Getty Images 公司。

RF Media Editor: Dan Sandin and Wanda Rockwell
RF 媒体编辑：丹·桑丁和旺达·洛克韦尔

Project Management: GEX Publishing Services Composition and Illustration: GEX Publishing Services
项目管理：GEX 出版服务构图和插图：GEX 出版服务

Printer/Binder: Edwards Brothers
爱德华兹兄弟打印机/装订机

Cover Printer: Lehigh-Phoenix Color/Hagerstown
封面印刷：Lehigh-Phoenix Color/Hagerstown

Figure 0.3: "An abacus ". Wayne Chandler. Figure 0.4: "The Mark I computer." Courtesy of IBM corporate archives. Unauthorized use is not permitted.
图 0.3："算盘"。韦恩·钱德勒著。图 0.4："Mark I 计算机"。IBM 公司档案馆提供。未经授权使用不被允许。
Figure 10.1: "A photograph of a viral world produced by using 3D graphics (from Toy Story by Walt Disney/Pixar Animation Studios) © Disney/Pixar. Figure 10.6: "A scene from Shrek 2 by Dreamworks SKG. ) Dreamworks/ Picture Desk Inc./Kobal collection.
图 10.1：使用 3D 图形制作的病毒世界照片（取自迪士尼/皮克斯动画工作室的《玩具总动员》）© 迪士尼/皮克斯。图 10.6：梦工厂 SKG 的《怪物史莱克 2》场景。）梦工厂/图片桌公司/Kobal 收藏。
Figure 11.19: "Results of using a neural network to classify pixels in an image." Inspired by www.actapress.com. Chapter 11, Robots Making History feature: a. "A soccer robot kicks a ball during the RoboCup German Open 2010 on April 15, 2010 in Magdeburg, eastern Germany." ) Jens Schlueter/AFP/ Getty Images/ Newscom. b.
图 11.19：“使用神经网络对图像中的像素进行分类的结果。”灵感来自 www.actapress.com。第 11 章，机器人创造历史特辑：a. “2010 年 4 月 15 日，在德国东部马格德堡举行的 RoboCup 德国公开赛上，一个足球机器人正在踢球。”）Jens Schlueter/AFP/Getty Images/Newscom。b.
"Tartan Racing's "Boss-winner of the Urban Challenge, a contest sponsored by DARPA to have vehicles drive themselves an urban environment." () DARPA. c. "One of NASA's rovers-a robot geologist exploring the surface of Mars." Courtesy of NASA/JPL-Caltech.
Tartan Racing 的“Boss-赢得了由 DARPA 赞助的城市挑战比赛，旨在让车辆在城市环境中自行驾驶。”（）DARPA。c。“NASA 的一辆探测器-一台探索火星表面的机器地质学家。”由 NASA/JPL-Caltech 提供。

Copyright © 2012, 2009, 2007, 2005, 2003 Pearson Education, Inc., publishing as AddisonWesley. All rights reserved. Manufactured in the United States of America.
版权 © 2012, 2009, 2007, 2005, 2003 Pearson Education, Inc.，以 AddisonWesley 名义出版。保留所有权利。在美国制造。
This publication is protected by Copyright, and permission should be obtained from the publisher prior to any prohibited reproduction, storage in a retrieval system, or transmission in any form or by any means, electronic, mechanical, photocopying, recording, or likewise.
本出版物受版权保护，未经出版商事先许可，不得进行任何禁止的复制、存储于检索系统中或以任何形式或方式传输，包括电子、机械、复印、录音等。
To obtain permission(s) to use material from this work, please submit a written request to Pearson Education, Inc., Permissions Department, 501 Boylston Street, Suite 900, Boston, Massachusetts 02116.
请提交书面请求至 Pearson Education, Inc. 权限部门，地址为 501 Boylston Street，Suite 900，波士顿，马萨诸塞州 02116，以获得使用此作品材料的许可。

Many of the designations by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and the publisher was aware of a trademark claim, the designations have been printed in initial caps or all caps.
许多制造商和销售商为区分其产品而指定的名称被视为商标。在本书中出现这些名称时，出版商已经意识到商标声明，因此这些名称已经以首字母大写或全部大写形式打印。

is an imprint of
是的印记公司

This book presents an introductory survey of computer science. It explores the breadth of the subject while including enough depth to convey an honest appreciation for the topics involved.
本书介绍了计算机科学的入门调查，旨在探索该学科的广度，同时又深入到足以传达对涉及主题的真诚欣赏。

I wrote this text for students of computer science as well as students from other disciplines.
我为计算机科学专业的学生以及其他学科的学生撰写了这篇文字。
As for computer science students, most begin their studies with the illusion that computer science is programming, Web browsing, and Internet file sharing since that is essentially all they have seen. Yet computer science is much more than this.
对于计算机科学学生来说，大多数人在开始学习时会怀有这样的幻想，即计算机科学就是编程、浏览网页和互联网文件共享，因为这基本上是他们所见到的全部。然而，计算机科学远不止于此。
In turn, beginning computer science students need exposure to the breadth of the subject in which they are planning to major. Providing this exposure is the theme of this book.
相反，初学计算机科学的学生需要接触他们打算主修的学科的广度。这本书的主题是提供这种接触。
It gives students an overview of computer science-a foundation from which they can appreciate the relevance and interrelationships of future courses in the field. This survey approach is, in fact, the model used for introductory courses in the natural sciences.
它为学生提供了计算机科学的概述，从中他们可以理解未来课程在该领域中的相关性和相互关系。事实上，这种调查方法是自然科学入门课程中采用的模式。

This broad background is also what students from other disciplines need if they are to relate to the technical society in which they live.
这种广泛的背景也是其他学科的学生所需要的，以便他们能够与他们所生活的技术社会建立联系。
A computer science course for this audience should provide a practical, realistic understanding of the entire field rather than merely an introduction to using the Internet or training in the use of some popular software packages.
面向这一受众的计算机科学课程应该提供对整个领域的实际、现实的理解，而不仅仅是简单介绍如何使用互联网或培训使用一些流行软件包。
There is, of course, a proper place for training, but this text is about educating.
当然，有一个适当的地方进行培训，但这篇文章讨论的是教育。

Thus, while writing this text, maintaining accessibility for nontechnical students was a major goal.
因此，在撰写本文时，主要目标是确保非技术学生能够轻松理解。
The result is that previous editions have been used successfully in courses for students over a wide range of disciplines and educational levels, ranging from high school to graduate courses. This eleventh edition is designed to continue that tradition.
结果是，以前的版本已经成功地在涵盖从高中到研究生课程的各种学科和教育水平的课程中使用。这第十一版旨在延续这一传统。

The underlying theme during the development of this eleventh edition was to update the text to include handheld mobile devices, in particular smartphones. Thus, you will find that the text has been modified, and at times expanded, to
在开发第十一版时的基本主题是更新文本，以包括手持移动设备，特别是智能手机。因此，您会发现文本已经被修改，并有时进行了扩展。
present the relationship between the subject matter being discussed and smartphone technology. Specific topics include:
展示所讨论主题与智能手机技术之间的关系。具体主题包括：

These additions are most noticeable in Chapters 3 (Operating Systems) and 4 (Networking) but is also observable in Chapters 6 (Programming Languages), and 7 (Software Engineering).
这些增加最为明显的地方在第 3 章（操作系统）和第 4 章（网络）中，但也可以在第 6 章（编程语言）和第 7 章（软件工程）中看到。

Other prominent changes to this edition include updates to the following topics:
本版本的其他重要更改还包括以下主题的更新：

Finally, you will find that the material throughout the text has been updated to reflect the state of today's technology. This is most prevalent in Chapter 0 (Introduction), Chapter 1 (Data Storage), and Chapter 2 (Data Manipulation).
最后，您会发现整个文本中的内容已经更新，以反映当今技术的现状。这在第 0 章（介绍）、第 1 章（数据存储）和第 2 章（数据操作）中最为显著。

This text follows a bottom-up arrangement of subjects that progresses from the concrete to the abstract-an order that results in a sound pedagogical presentation in which each topic leads to the next.
本文按照从具体到抽象的顺序安排主题，形成了一个合理的教学呈现，每个主题都引导到下一个主题。
It begins with the fundamentals of information encoding, data storage, and computer architecture (Chapters 1 and 2); progresses to the study of operating systems (Chapter 3) and computer networks (Chapter 4); investigates the topics of algorithms, programming languages, and software development (Chapters 5 through 7); explores techniques for enhancing the accessibility of information (Chapters 8 and 9); considers some major applications of computer technology via graphics (Chapter 10) and artificial intelligence (Chapter 11); and closes with an introduction to the abstract theory of computation (Chapter 12).
本书从信息编码、数据存储和计算机体系结构的基础开始（第 1 章和第 2 章），然后深入研究操作系统（第 3 章）和计算机网络（第 4 章），接着探讨算法、编程语言和软件开发的主题（第 5 至 7 章），探索提高信息可访问性的技术（第 8 和 9 章），考虑计算机技术在图形（第 10 章）和人工智能（第 11 章）领域的一些主要应用，最后介绍计算的抽象理论（第 12 章）。

Although the text follows this natural progression, the individual chapters and sections are surprisingly independent and can usually be read as isolated units or rearranged to form alternative sequences of study.
虽然文本按照自然的顺序进行，但各个章节和部分却出奇地独立，通常可以作为独立的单元阅读，或重新排列以形成不同的学习顺序。
Indeed, the book is often used as a text for courses that cover the material in a variety of orders. One of these alternatives begins with material from Chapters 5 and 6 (Algorithms and Programming Languages) and returns to the earlier chapters as desired.
实际上，这本书经常被用作覆盖各种顺序材料的课程的教材。其中一种选择是从第 5 章和第 6 章（算法和编程语言）的材料开始，然后根据需要返回到较早的章节。
In contrast, I know of one course that starts with the material on computability from Chapter 12. In still other cases the text has been used in "senior capstone" courses where it serves as merely a backbone from which to branch into projects in different areas.
相反，我知道有一门课程是从第 12 章的可计算性材料开始的。在其他情况下，这本书被用于“高年级顶峰”课程，仅仅作为一个支柱，用来展开不同领域项目的起点。
Courses for less technically oriented audiences may want to concentrate on Chapters 4 (Networking and the Internet), 9 (Database Systems), 10 (Computer Graphics), and 11 (Artificial Intelligence).
针对技术水平较低的受众的课程可能需要重点关注第 4 章（网络和互联网）、第 9 章（数据库系统）、第 10 章（计算机图形）和第 11 章（人工智能）。

On the opening page of each chapter, I have used asterisks to mark some sections as optional. These are sections that cover topics of more specific interest or
在每章的开头页上，我使用星号标记了一些部分作为可选内容。这些部分涵盖了更具体的兴趣话题。
perhaps explore traditional topics in more depth. My intention is merely to provide suggestions for alternative paths though the text. There are, of course, other shortcuts. In particular, if you are looking for a quick read, I suggest the following sequence:
或许可以更深入地探索传统主题。我的意图仅仅是提供对文本的替代路径的建议。当然，还有其他捷径。特别是，如果你想快速阅读，我建议以下顺序：

Basics of data encoding and storage
数据编码和存储基础概述

Machine architecture and machine language
计算机结构和机器语言

Operating systems 操作系统

Networking and the Internet
网络和互联网

Algorithms and algorithm design
算法和算法设计

Programming languages 编程语言领域

Software engineering 软件工程领域

Data abstractions 数据抽象化

Database systems 数据库系统管理

Computer graphics 计算机图形学

Artificial intelligence 人工智能技术

Theory of computation 计算理论

There are several themes woven throughout the text. One is that computer science is dynamic. The text repeatedly presents topics in a historical perspective, discusses the current state of affairs, and indicates directions of research.
本文涉及多个主题。其中之一是计算机科学的动态性。文本反复以历史视角呈现主题，讨论当前事务状态，并指出研究方向。
Another theme is the role of abstraction and the way in which abstract tools are used to control complexity.
另一个主题涉及抽象的作用，以及如何运用抽象工具来控制复杂性。
This theme is introduced in Chapter 0 and then echoed in the context of operating system architecture, networking, algorithm development, programming language design, software engineering, data organization, and computer graphics.
该主题首先在第 0 章中引入，然后在操作系统架构、网络、算法开发、编程语言设计、软件工程、数据组织和计算机图形的背景中得到了呼应。

There is more material in this text than can normally be covered in a single semester so do not hesitate to skip topics that do not fit your course objectives or to rearrange the order as you see fit.
此文本内容涵盖的材料超出了一个学期的范围，因此请放心跳过与您课程目标不符的主题，或根据需要重新调整顺序。
You will find that, although the text follows a plot, the topics are covered in a largely independent manner that allows you to pick and choose as you desire. The book is designed to be used as a course resource - not as a course definition.
你会发现，尽管文本有一个情节，但主题基本上是独立处理的，这样您可以随心所欲地选择。这本书的设计初衷是作为课程资源使用，而不是课程定义。
I suggest encouraging students to read the material not explicitly included in your course. I think we underrate students if we assume that we have to explain everything in class. We should be helping them learn to learn on their own.
我建议鼓励学生阅读课程中未明确包含的材料。我认为，如果我们假设必须在课堂上解释一切，那么我们就低估了学生。我们应该帮助他们学会自主学习。

I feel obliged to say a few words about the bottom-up, concrete-to-abstract organization of the text. I think as academics we too often assume that students will appreciate our perspective of a subject-often one that we have developed over many years of working in a field.
我觉得有必要谈一下文本的自下而上、由具体到抽象的组织方式。作为学者，我们经常过于假设学生会欣赏我们对一个主题的观点，而这些观点往往是我们在该领域工作多年积累的。
As teachers I think we do better by presenting material from the student's perspective. This is why the text starts with data representation/storage, machine architecture, operating systems, and networking.
作为教师，我认为我们更好地通过从学生的角度呈现材料来教学。这就是为什么文本从数据表示/存储、机器体系结构、操作系统和网络开始。
These are topics to which students readily relate-they have most likely heard terms such as JPEG and MP3; they have probably recorded data on CDs and DVDs; they have purchased computer components; they have interacted with an operating system; and they have used the Internet.
这些是学生们很容易与之相关的话题-他们很可能听过像 JPEG 和 MP3 这样的术语；他们很可能在 CD 和 DVD 上记录过数据；他们购买过计算机组件；他们与操作系统互动过；他们使用过互联网。
By starting the course with these topics, students discover answers to many of the "why" questions they have been carrying for years and learn to view the course as practical
通过从这些主题开始课程，学生可以找到多年来一直携带的许多“为什么”问题的答案，并学会将课程视为实用的
rather than theoretical.
实际上，而非理论性。
From this beginning it is natural to move on to the more abstract issues of algorithms, algorithmic structures, programming languages, software development methodologies, computability, and complexity that those of us in the field view as the main topics in the science.
从这一起点开始，自然而然地转向更抽象的问题，如算法、算法结构、编程语言、软件开发方法论、可计算性和复杂性等，这些是我们领域中视为科学主要议题的内容。
As I've said before, the topics are presented in a manner that does not force you to follow this bottom-up sequence, but I encourage you to give it a try.
正如我之前所说，这些主题的呈现方式并不强制你按照自下而上的顺序进行，但我鼓励你尝试一下。

We are all aware that students learn a lot more than we teach them directly, and the lessons they learn implicitly are often better absorbed than those that are studied explicitly. This is significant when it comes to "teaching" problem solving.
我们都知道，学生学到的远不止我们直接教给他们的知识，他们隐性学到的教训往往比明确学习的更容易吸收。这一点在“教授”解决问题时尤为重要。
Students do not become problem solvers by studying problem-solving methodologies.
学生不是通过学习问题解决方法论来成为问题解决者的。
They become problem solvers by solving problems-and not just carefully posed "textbook problems." So this text contains numerous problems, a few of which are intentionally vague-meaning that there is not necessarily a single correct approach or a single correct answer.
通过解决问题，他们成为问题解决者，而不仅仅是解决精心设计的“教科书问题”。因此，这个文本包含许多问题，其中一些是有意模糊的，这意味着不一定有一个正确的方法或一个正确的答案。
I encourage you to use these and to expand on them.
我鼓励您使用这些内容，并进行进一步拓展。

Another topic in the "implicit learning" category is that of professionalism, ethics, and social responsibility. I do not believe that this material should be presented as an isolated subject that is merely tacked on to the course.
在“隐性学习”类别中的另一个话题是职业素养、道德和社会责任。我认为这些内容不应该被单独呈现，而是应该融入到课程中。
Instead, it should be an integral part of the coverage that surfaces when it is relevant. This is the approach followed in this text.
相反，它应该成为覆盖范围的一个重要组成部分，当相关时才显现出来。这是本文所采用的方法。
You will find that Sections 3.5, 4.5, 7.8, 9.7, and 11.7 present such topics as security, privacy, liability, and social awareness in the context of operating systems, networking, database systems, software engineering, and artificial intelligence.
在操作系统、网络、数据库系统、软件工程和人工智能的背景下，您将发现第 3.5、4.5、7.8、9.7 和 11.7 节涉及安全、隐私、责任和社会意识等主题。
Moreover, Section 0.6 introduces this theme by summarizing some of the more prominent theories that attempt to place ethical decision making on a philosophically firm foundation.
此外，第 0.6 节通过总结一些更为突出的理论，试图为道德决策奠定哲学基础。
You will also find that each chapter includes a collection of questions called Social Issues that challenge students to think about the relationship between the material in the text and the society in which they live.
您还会发现，每一章都包含一系列名为社会问题的问题，这些问题挑战学生思考文本中的内容与他们所生活的社会之间的关系。

Thank you for considering my text for your course. Whether you do or do not decide that it is right for your situation, I hope that you find it to be a contribution to the computer science education literature.
感谢您考虑将我的文本纳入您的课程。无论您是否认为它适合您的情况，我希望您认为它对计算机科学教育文献有所贡献。

This text is the product of many years of teaching. As a result, it is rich in pedagogical aids. Paramount is the abundance of problems to enhance the student's participation-over 1,000 in this eleventh edition.
这段文字是多年教学经验的结晶。因此，它富含教学辅助内容。其中最重要的是大量问题，旨在提升学生的参与度-本书第十一版中包含超过 1,000 个问题。
These are classified as Questions/Exercises, Chapter Review Problems, and Social Issues. The Questions/ Exercises appear at the end of each section (except for the introductory chapter).
这些内容被分类为问题/练习、章节复习问题和社会问题。问题/练习出现在每个部分的末尾（除了导论章节）。
They review the material just discussed, extend the previous discussion, or hint at related topics to be covered later. These questions are answered in Appendix F.
他们会复习刚讨论过的材料，延伸之前的讨论，或者暗示稍后将要涉及的相关主题。这些问题将在附录 F 中得到解答。

The Chapter Review Problems appear at the end of each chapter (except for the introductory chapter). They are designed to serve as "homework" problems in that they cover the material from the entire chapter and are not answered in the text.
章节复习问题出现在每章末尾（除了导论章节）。它们旨在作为“家庭作业”问题，因为涵盖整章的内容，并且在文本中没有答案。

Also at the end of each chapter are the questions in the Social Issues category. They are designed for thought and discussion. Many of them can be used to launch research assignments culminating in short written or oral reports.
每章末尾还有社会问题类别的问题。这些问题旨在引发思考和讨论，许多问题可用于启动研究任务，并最终完成简短的书面或口头报告。

Each chapter also ends with a list called Additional Reading that contains references to other material relating to the subject of the chapter.
每一章节最后都会附上一个名为“附加阅读”的清单，其中包含与该章节主题相关的其他资料的参考文献。
The Web sites identified in this preface, in the text, and in the sidebars of the text are also good places to look for related material.
本序言中标识的网站，文本中以及文本旁注中的网站也是寻找相关资料的好去处。

A variety of supplemental materials for this text are available at the book's Companion Website: www.pearsonhighered.com/brookshear. The following are accessible to all readers:
本文提供了丰富的补充材料，可在该书的同伴网站上获取：www.pearsonhighered.com/brookshear。以下内容对所有读者均可访问：

In addition, the following supplements are available to qualified instructors at Pearson Education's Instructor Resource Center. Please visit www.pearsonhighered.com or contact your Pearson sales representative for information on how to access them:
此外，Pearson Education 的教师资源中心提供以下补充材料给合格的教师。请访问 www.pearsonhighered.com 或联系您的 Pearson 销售代表，了解如何获取这些材料：

You may also want to check out my personal Web site at www.mscs.mu .edu/ glennb. It is not very formal (and it is subject to my whims and sense of humor), but I tend to keep some information there that you may find helpful. In particular, you will find an errata page that lists corrections to errors in the text that have been reported to me.
您可能也想查看我的个人网站 www.mscs.mu.edu/glennb。这个网站并不十分正式（受我的兴致和幽默感影响），但我通常会在那里保留一些您可能会发现有用的信息。特别是，您会找到一个勘误页面，列出了读者向我报告的文本错误的更正。

I'm a bit of a nonconformist (some of my friends would say more than a bit) so when I set out to write this text I didn't always follow the advice I received. In particular, many argued that certain material was too advanced for beginning students.
我有点不随大流（我的一些朋友会说我更甚一些），所以当我着手撰写这段文字时，并没有一直遵循我收到的建议。特别是，许多人认为某些内容对初学者来说太过高级。
But, I believe that if a topic is relevant, then it is relevant even if the academic community considers it to be an "advanced topic." You deserve a text that presents a complete picture of computer science-not a watered-down version containing artificially simplified presentations of only those topics that have been deemed appropriate for introductory students.
但是，我相信，如果一个话题是相关的，那么即使学术界认为它是一个“高级话题”，它也是相关的。您应该得到一份呈现计算机科学完整图景的文本，而不是一个含有人为简化呈现的、仅包含那些被认为适合初学者的主题的精简版本。
Thus, I have not avoided topics. Instead I've sought better explanations. I've tried to provide enough depth to give you an honest picture of what computer science is all about.
因此，我没有回避话题，而是努力寻求更好的解释。我试图提供足够的深度，让您对计算机科学有一个真实的了解。
As in the case of spices in a recipe, you may choose to skip some of the topics in the following pages, but they are there for you to taste if you wish-and I encourage you to do so.
就像食谱中的香料一样，您可以选择跳过以下页面中的一些主题，但如果您愿意，它们就在那里等着您品尝，我鼓励您这样做。

I should also point out that in any course dealing with technology, the details you learn today may not be the details you will need to know tomorrow. The field is dynamic-that's part of the excitement.
我还要指出，在任何涉及技术的课程中，你今天学到的细节可能不是明天需要了解的细节。这个领域是充满活力的，这也是其中的乐趣之一。
This book will give you a current picture of the subject as well as a historical perspective. With this background you will be prepared to grow along with technology. I encourage you to start the growing process now by exploring beyond this text. Learn to learn.
这本书将为您提供主题的当前画面以及历史视角。有了这个背景，您将准备好随着技术一起成长。我鼓励您立即开始探索超越这段文字，学会学习。

Thank you for the trust you have placed in me by choosing to read my book. As an author I have an obligation to produce a manuscript that is worth your time. I hope you find that I have lived up to this obligation.
感谢您选择阅读我的书，对我表示信任。作为作者，我有责任创作一部值得您花时间阅读的作品。希望您觉得我已经做到了。

I first thank those of you who have supported this book by reading and using it in previous editions. I am honored.
首先，我要感谢那些通过阅读和使用这本书支持过它的人。我深感荣幸。

David T. Smith (Indiana University of Pennsylvania) and Dennis Brylow (Marquette University) played significant roles in the production this eleventh edition. David concentrated on Chapters , and 11; and Dennis focused on Chapters 3, 4, 6, and 10 . Without their hard work this new edition would not exist today. I sincerely thank them.
大卫·T·史密斯（印第安纳大学宾夕法尼亚分校）和丹尼斯·布赖洛（马凯特大学）在制作这第十一版中发挥了重要作用。大卫负责第 章和第 11 章；丹尼斯负责第 3、4、6 和 10 章。没有他们的辛勤付出，这个新版本今天将不复存在。我由衷感谢他们。

As mentioned in the preface to the tenth edition, I am indebted to Ed Angel, John Carpinelli, Chris Fox, Jim Kurose, Gary Nutt, Greg Riccardi, and Patrick Henry Winston for their assistance in the development of that edition.
正如第十版序言中所提到的，我要感谢 Ed Angel，John Carpinelli，Chris Fox，Jim Kurose，Gary Nutt，Greg Riccardi 和 Patrick Henry Winston 在该版本的开发过程中提供的帮助。
The results of their efforts remain visible in this eleventh edition.
他们的努力成果仍然清晰可见于这第十一版。

Others who have contributed in this or previous editions include J. M. Adams, C. M. Allen, D. C. S. Allison, R. Ashmore, B. Auernheimer, P. Bankston, M. Barnard, P. Bender, K. Bowyer, P. W. Brashear, C. M. Brown, H. M Brown, B. Calloni, M. Clancy, R. T. Close, D. H. Cooley, L. D.
其他在本届或之前版本中做出贡献的人还包括 J. M. Adams，C. M. Allen，D. C. S. Allison，R. Ashmore，B. Auernheimer，P. Bankston，M. Barnard，P. Bender，K. Bowyer，P. W. Brashear，C. M. Brown，H. M Brown，B. Calloni，M. Clancy，R. T. Close，D. H. Cooley，L. D.
Cornell, M. J. Crowley, F. Deek, M. Dickerson, M. J. Duncan, S. Ezekiel, S. Fox, N. E. Gibbs, J. D. Harris, D. Hascom, L. Heath, P. B. Henderson, L. Hunt, M. Hutchenreuther, L. A. Jehn, K. K. Kolberg, K. Korb, G. Krenz, J. Liu, T. J. Long, C. May, J. J. McConnell, W. McCown, S.
康奈尔，M. J. 克劳利，F. 迪克，M. 迪克森，M. J. 邓肯，S. 以西结，S. 福克斯，N. E. 吉布斯，J. D. 哈里斯，D. 哈斯科姆，L. 希思，P. B. 亨德森，L. 亨特，M. 胡琴罗瑟，L. A. 詹，K. K. 科尔伯格，K. 科尔布，G. 克伦兹，J. 刘，T. J. 龙，C. 梅，J. J. 麦康奈尔，W. 麦考恩，S.
J. Merrill, K. Messersmith, J. C. Moyer, M. Murphy, J. P. Myers, Jr., D. S. Noonan, W. W. Oblitey, S. Olariu, G. Rice, N. Rickert, C. Riedesel, J. B. Rogers, G. Saito, W. Savitch, R. Schlafly, J. C. Schlimmer, S. Sells, G. Sheppard, Z. Shen, J. C. Simms, M. C. Slattery, J.
Slimick, J. A. Slomka, D. Smith, J. Solderitsch, R. Steigerwald, L. Steinberg, C. A. Struble, C. L. Struble, W. J. Taffe, J. Talburt, P. Tonellato, P. Tromovitch, E. D. Winter, E. Wright, M. Ziegler, and one anonymous. To these individuals I give my sincere thanks.
Slimick, J. A. Slomka, D. Smith, J. Solderitsch, R. Steigerwald, L. Steinberg, C. A. Struble, C. L. Struble, W. J. Taffe, J. Talburt, P. Tonellato, P. Tromovitch, E. D. Winter, E. Wright, M. Ziegler，以及一位匿名人士。我向这些个人致以诚挚的感谢。

As already mentioned, you will find Java and C++ manuals at the text's Companion Website that teach the basics of these languages in a format compatible with the text. These were written by Diane Christie. Thank you Diane.
正如前面提到的，您可以在文本的附属网站上找到由 Diane Christie 编写的 Java 和 C++手册，这些手册以与文本兼容的格式教授这两种语言的基础知识。感谢 Diane。
Another thank you goes to Roger Eastman who was the creative force behind the chapter-by-chapter activities that you will also find at the Companion Website.
另外，还要感谢罗杰·伊斯曼，他是章节活动的创意推动力，您也可以在伴随网站上找到这些活动。

I also thank the people at Addison-Wesley who have contributed to this project. They are a great bunch to work with-and good friends as well. If you are thinking about writing a textbook, you should consider having it published by Addison-Wesley.
我也要感谢 Addison-Wesley 的团队为这个项目所做出的贡献。他们不仅是一群很棒的合作伙伴，也是很好的朋友。如果你正在考虑写一本教科书，不妨考虑让它由 Addison-Wesley 出版。

I continue to be grateful to my wife Earlene and daughter Cheryl who have been tremendous sources of encouragement over the years. Cheryl, of course, grew up and left home several years ago. But Earlene is still here. I'm a lucky man.
我一直感激我的妻子厄琳和女儿谢丽尔，多年来她们一直是我巨大的鼓励。当然，谢丽尔几年前长大离家了，但厄琳仍在身边。我是一个幸运的人。
On the morning of December 11, 1998, I survived a heart attack because she got me to the hospital in time. (For those of you in the younger generation I should explain that surviving a heart attack is sort of like getting an extension on a homework assignment.)
1998 年 12 月 11 日早上，因为她及时送我去医院，我幸免于心脏病发作。（对于年轻一代的人来说，我应该解释一下，幸免于心脏病发作有点像是延长了一次作业的截止时间。）

Finally, I thank my parents, to whom this book is dedicated. I close with the following endorsement whose source shall remain anonymous: "Our son's book is really good. Everyone should read it."
最后，我要感谢我的父母，这本书是献给他们的。最后，我引用一段匿名背书：“我们儿子的书真的很棒，每个人都应该读一读。”

Chapter 0 Introduction ..... 1
第 0 章 简介 ..... 1
0.1 The Role of Algorithms ..... 2
0.1 算法的角色 ..... 2
0.2 The History of Computing ..... 4
0.2 计算机历史 ..... 4
0.3 The Science of Algorithms ..... 10
0.3 算法科学 ..... 10
0.4 Abstraction ..... 11
0.4 抽象 ..... 11
0.5 An Outline of Our Study ..... 12
0.5 我们研究的概述 ..... 12
0.6 Social Repercussions ..... 13
0.6 社会影响 ..... 13
Chapter 1 Data Storage ..... 19
第 1 章 数据存储 ..... 19
1.1 Bits and Their Storage ..... 20
1.1 位元及其存储方式.....20
1.2 Main Memory ..... 26
1.2 主存储器 ..... 26
1.3 Mass Storage ..... 29
1.3 存储空间 ..... 29
1.4 Representing Information as Bit Patterns ..... 35
1.4 以位模式表示信息 ..... 35
*1.5 The Binary System ..... 42
二进制系统 ..... 42
*1.6 Storing Integers ..... 47
存储整数至 47
*1.7 Storing Fractions ..... 53
*1.7 存储分数 ..... 53
*1.8 Data Compression ..... 58
*1.8 数据压缩 ..... 58
*1.9 Communication Errors ..... 63
*1.9 通信错误 ..... 63
Chapter 2 Data Manipulation ..... 73
第 2 章 数据处理 ..... 73
2.1 Computer Architecture ..... 74
2.1 计算机体系结构 ..... 74
2.2 Machine Language ..... 77
2.2 机器语言 ..... 77
2.3 Program Execution ..... 83
2.3 程序执行 ..... 83
*2.4 Arithmetic/Logic Instructions ..... 90
*2.4 算术/逻辑指令 ..... 90
*2.5 Communicating with Other Devices ..... 94
与其他设备进行通信..... 94
..... 100 Chapter 3 Operating Systems ..... 109
..... 100 第 3 章 操作系统 ..... 109
3.1 The History of Operating Systems ..... 110
3.1 操作系统的发展历程 ..... 110
3.2 Operating System Architecture ..... 114
3.2 操作系统架构 ..... 114
3.3 Coordinating the Machine's Activities ..... 122
3.3 协调机器活动的过程 ..... 122
*3.4 Handling Competition Among Processes ..... 125
处理进程间的竞争问题 ..... 125
3.5 Security ..... 130
3.5 安全 ..... 130
Chapter 4 Networking and the Internet ..... 139
第 4 章 网络和互联网 ..... 139
4.1 Network Fundamentals ..... 140
4.1 网络基础 ..... 140
4.2 The Internet ..... 149
4.2 互联网 ..... 149
4.3 The World Wide Web ..... 158
4.3 互联网的普及 ..... 158
*4.4 Internet Protocols ..... 167
*4.4 互联网协议 ..... 167
4.5 Security ..... 173
4.5 安全 ..... 173
Chapter 5 Algorithms ..... 187
第 5 章 算法 ..... 187
5.1 The Concept of an Algorithm ..... 188
5.1 算法的概念 ..... 188
5.2 Algorithm Representation ..... 191
5.2 算法表示方式 ..... 191
5.3 Algorithm Discovery ..... 198
5.3 算法探索 ..... 198
5.4 Iterative Structures ..... 204
5.4 迭代结构 ..... 204
5.5 Recursive Structures ..... 214
5.5 递归结构 ..... 214
5.6 Efficiency and Correctness ..... 222
5.6 效率和正确性 ..... 222
Chapter 6 Programming Languages ..... 239
第 6 章 编程语言 ..... 239
6.1 Historical Perspective ..... 240
6.1 历史背景 ..... 240
6.2 Traditional Programming Concepts ..... 248
6.2 传统编程概念 ..... 248
6.3 Procedural Units ..... 260
6.3 程序单元.....260
6.4 Language Implementation ..... 268
6.4 语言实现 ..... 268
6.5 Object-Oriented Programming ..... 276
6.5 面向对象编程 ..... 276
*6.6 Programming Concurrent Activities ..... 283
*6.6 编写并发程序 ..... 283
*6.7 Declarative Programming ..... 286
6.7 声明式编程 ..... 286
Chapter 7 Software Engineering ..... 299
第 7 章 软件工程 ..... 299
7.1 The Software Engineering Discipline ..... 300
7.1 软件工程学科 ..... 300
7.2 The Software Life Cycle ..... 302
7.2 软件生命周期 ..... 302
7.3 Software Engineering Methodologies ..... 306
7.3 软件工程方法论 ..... 306
7.4 Modularity ..... 308
7.4 模块化.....308
7.5 Tools of the Trade ..... 316
7.5 工具......316
7.6 Quality Assurance ..... 324
7.6 质量保证 ..... 324
7.7 Documentation ..... 328
7.7 文档.....328
7.8 The Human-Machine Interface ..... 329
7.8 人机界面 ..... 329
7.9 Software Ownership and Liability ..... 332
7.9 软件所有权和责任 ..... 332
Chapter 8 Data Abstractions ..... 341
第 8 章 数据抽象 ..... 341
8.1 Basic Data Structures ..... 342
8.1 基本数据结构 ..... 342
8.2 Related Concepts ..... 345
8.2 相关概念 ..... 345
8.3 Implementing Data Structures ..... 348
8.3 实现数据结构 ..... 348
8.4 A Short Case Study ..... 362
8.4 一个简短的案例研究 ..... 362
8.5 Customized Data Types ..... 367
8.5 自定义数据类型 ..... 367
*8.6 Classes and Objects ..... 371
第 8.6 节 类和对象 ..... 371
*8.7 Pointers in Machine Language ..... 372
*8.7 机器语言中的指针..... 372
Chapter 9 Database Systems ..... 383
第 9 章 数据库系统 ..... 383
9.1 Database Fundamentals ..... 384
9.1 数据库基础 ..... 384
9.2 The Relational Model ..... 389
9.2 关系模型 ..... 389
*9.3 Object-Oriented Databases ..... 400
9.3 面向对象数据库 ..... 400
*9.4 Maintaining Database Integrity ..... 402
9.4 维护数据库完整性 ..... 402
*9.5 Traditional File Structures ..... 406
9.5 传统文件结构 ..... 406
9.6 Data Mining ..... 414
9.6 数据挖掘 ..... 414
9.7 Social Impact of Database Technology ..... 416
9.7 数据库技术的社会影响 ..... 416
Chapter 10 Computer Graphics ..... 425
第 10 章 计算机图形 ..... 425
10.1 The Scope of Computer Graphics ..... 426
10.1 计算机图形学的范围 ..... 426
10.2 Overview of 3D Graphics ..... 428
10.2 3D 图形概览 ..... 428
10.3 Modeling ..... 430
10.3 建模.....430
10.4 Rendering ..... 439
10.4 渲染中.....439
*10.5 Dealing with Global Lighting ..... 449
处理全局照明中的问题 ..... 449
10.6 Animation ..... 452
10.6 动画.....452
Chapter 11 Artificial Intelligence ..... 461
第 11 章 人工智能 ..... 461
11.1 Intelligence and Machines ..... 462
11.1 智能与机器 ..... 462
11.2 Perception ..... 467
11.2 知觉 ..... 467
11.3 Reasoning ..... 473
11.3 推理 ..... 473
11.4 Additional Areas of Research ..... 484
11.4 其他研究领域 ..... 484
11.5 Artificial Neural Networks ..... 489
11.5 - 人工神经网络 ..... 489
11.6 Robotics ..... 497
11.6 机器人技术 ..... 497
11.7 Considering the Consequences ..... 500
11.7 考虑后果......500
Chapter 12 Theory of Computation ..... 509
第 12 章 计算理论 ..... 509
12.1 Functions and Their Computation ..... 510
12.1 函数及其计算.....510
12.2 Turing Machines ..... 512
12.2 图灵机 ..... 512
12.3 Universal Programming Languages ..... 516
12.3 通用编程语言 ..... 516
12.4 A Noncomputable Function ..... 522
12.4 一个不可计算的函数 ..... 522
12.5 Complexity of Problems ..... 527
问题复杂度为 12.5 ..... 527
*12.6 Public-Key Cryptography ..... 536
*12.6 公钥密码学 ..... 536

A ASCII 547

B Circuits to Manipulate Two's Complement Representations 548
操纵二进制补码表示的电路 548

C A Simple Machine Language 551
C 一种简单的机器语言 551

D High-Level Programming Languages 553
高级编程语言 553

E The Equivalence of Iterative and Recursive Structures 555
迭代和递归结构的等效性

F Answers to Questions & Exercises 557
F 问题和练习的答案 557

In this preliminary chapter we consider the scope of computer science, develop a historical perspective, and establish a foundation from which to launch our study.
在这个初步章节中，我们将探讨计算机科学的范围，发展历史视角，并奠定一个基础，为我们的学习铺平道路。
0.1 The Role of Algorithms
0.1 算法的作用
0.3 The Science 0.3 科学
0.2 The History 0.2 历史
of Algorithms 算法的原理
of Computing 计算机的起源
0.5 An Outline of
大纲概述
0.4 Abstraction 0.4 抽象化
Our Study 我们的研究
0.6 Social Repercussions
0.6 社会影响的影响

Computer science is the discipline that seeks to build a scientific foundation for such topics as computer design, computer programming, information processing, algorithmic solutions of problems, and the algorithmic process itself.
计算机科学是一门学科，旨在为诸如计算机设计、计算机编程、信息处理、问题的算法解决方案以及算法过程本身等主题建立科学基础。
It provides the underpinnings for today's computer applications as well as the foundations for tomorrow's computing infrastructure.
它为当今的计算机应用程序提供了基础，也为未来的计算基础设施打下了基础。

This book provides a comprehensive introduction to this science. We will investigate a wide range of topics including most of those that constitute a typical university computer science curriculum. We want to appreciate the full scope and dynamics of the field.
这本书全面介绍了这门科学。我们将探讨广泛的主题，包括典型大学计算机科学课程中的大部分内容。我们希望能够深入了解这个领域的全部范围和动态。
Thus, in addition to the topics themselves, we will be interested in their historical development, the current state of research, and prospects for the future.
因此，除了关注主题本身，我们还将关注它们的历史发展、当前研究现状以及未来的发展前景。
Our goal is to establish a functional understanding of computer science-one that will support those who wish to pursue more specialized studies in the science as well as one that will enable those in other fields to flourish in an increasingly technical society.
我们的目标是建立对计算机科学的功能性理解，这将支持那些希望在科学领域进行更专业研究的人，也将使其他领域的人在一个日益技术化的社会中蓬勃发展。

We begin with the most fundamental concept of computer science-that of an algorithm. Informally, an algorithm is a set of steps that defines how a task is performed.
我们从计算机科学中最基本的概念开始，即算法。非正式地说，算法是一组定义了如何执行任务的步骤。
(We will be more precise later in Chapter 5.) For example, there are algorithms for cooking (called recipes), for finding your way through a strange city (more commonly called directions), for operating washing machines (usually displayed on the inside of the washer's lid or perhaps on the wall of a laundromat), for playing music (expressed in the form of sheet music), and for performing magic tricks (Figure 0.1).
（我们稍后在第 5 章会更加详细地讨论。）例如，有用于烹饪的算法（称为食谱），用于在陌生城市中找路的算法（通常称为方向），用于操作洗衣机的算法（通常显示在洗衣机盖内侧或洗衣店墙壁上），用于演奏音乐的算法（以乐谱形式表达），以及用于表演魔术的算法（图 0.1）。

Before a machine such as a computer can perform a task, an algorithm for performing that task must be discovered and represented in a form that is compatible with the machine. A representation of an algorithm is called a program.
在计算机等机器执行任务之前，必须先找到并以一种适合机器的形式表示执行该任务的算法。算法的表现被称为程序。
For the convenience of humans, computer programs are usually printed on paper or displayed on computer screens. For the convenience of machines, programs are encoded in a manner compatible with the technology of the machine.
为了方便人类使用，计算机程序通常会被打印在纸张上或显示在计算机屏幕上。为了方便机器操作，程序会以与机器技术兼容的方式进行编码。
The process of developing a program, encoding it in machine-compatible form, and inserting it into a machine is called programming.
编程是指开发程序、将其编码为机器兼容形式，并插入机器的过程。
Programs, and the algorithms they represent, are collectively referred to as software, in contrast to the machinery itself, which is known as hardware.
程序和它们所代表的算法被统称为软件，与硬件相对应，后者指的是机械本身。

The study of algorithms began as a subject in mathematics. Indeed, the search for algorithms was a significant activity of mathematicians long before the development of today's computers.
算法的研究始于数学学科。事实上，在今天的计算机发展之前，数学家们长期以来一直在寻找算法。
The goal was to find a single set of directions that described how all problems of a particular type could be solved. One of the best known examples of this early research is the long division algorithm for finding the quotient of two multiple-digit numbers.
目标是找到一套单一的指导方针，描述如何解决特定类型的所有问题。这项早期研究中最著名的例子之一是长除法算法，用于找到两个多位数的商。
Another example is the Euclidean algorithm, discovered by the ancient Greek mathematician Euclid, for finding the greatest common divisor of two positive integers (Figure 0.2).
另一个例子是欧几里得算法，由古希腊数学家欧几里得发现，用于找到两个正整数的最大公约数（见图 0.2）。

Once an algorithm for performing a task has been found, the performance of that task no longer requires an understanding of the principles on which the algorithm is based. Instead, the performance of the task is reduced to the process of merely following directions.
一旦找到执行任务的算法，执行该任务的性能就不再需要理解算法的基本原理。相反，任务的执行被简化为仅仅遵循指示的过程。
(We can follow the long division algorithm to find a quotient or the Euclidean algorithm to find a greatest common divisor without understanding why the algorithm works.) In a sense, the intelligence required to solve the problem at hand is encoded in the algorithm.
从某种意义上说，解决手头问题所需的智慧被编码在算法中，我们可以按照长除法算法找到商，或者按照欧几里得算法找到最大公约数，而无需理解算法为何有效。

Effect: The performer places some cards from a normal deck of playing cards face down on a table and mixes them thoroughly while spreading them out on the table. Then, as the audience requests either red or black cards, the performer turns over cards of the requested color.
表演者将一些普通扑克牌背面朝下放在桌子上，并彻底混合。然后，根据观众要求的红色或黑色牌，翻开相应颜色的牌。

Step 1. From a normal deck of cards, select ten red cards and ten black cards. Deal these cards face up in two piles on the table according to color.
从一副普通的扑克牌中，选择十张红牌和十张黑牌。根据颜色在桌子上分成两堆，将这些牌面朝上展示。

Step 2. Announce that you have selected some red cards and some black cards.
宣布您已选择了一些红牌和一些黑牌。

Step 3. Pick up the red cards. Under the pretense of aligning them into a small deck, hold them face down in your left hand and, with the thumb and first finger of your right hand, pull back on each end of the deck so that each card is given a slightly backward curve.
第三步。拿起红牌。假装将它们整齐地叠放成一小叠，用左手握住它们朝下，用右手的拇指和食指拉回每张牌的两端，使每张牌都略微向后弯曲。
Then place the deck of red cards face down on the table as you say, "Here are the red cards in this stack."
然后将红牌堆放在桌子上，同时说：“这是红牌堆中的红牌。”

Step 4. Pick up the black cards. In a manner similar to that in step 3, give these cards a slight forward curve. Then return these cards to the table in a face-down deck as you say, "And here are the black cards in this stack."
第四步。拿起黑色的卡片。像第三步那样，给这些卡片稍微向前弯曲。然后将这些卡片以面朝下的方式放回桌子上，同时说：“这叠牌里有黑色的卡片。”

Step 5. Immediately after returning the black cards to the table, use both hands to mix the red and black cards (still face down) as you spread them out on the tabletop. Explain that you are thoroughy mixing the cards.
在将黑牌放回桌子后，立即用双手在桌面上展开红牌和黑牌（仍然面朝下）进行混合。解释正在彻底搅拌牌。

Step 6. As long as there are face-down cards on the table, repeatedly execute the following steps:
当桌子上还有背面朝上的卡牌时，重复执行以下步骤：

6.1. Ask the audience to request either a red or a black card.
6.1. 请观众选择红牌或黑牌。

6.2. If the color requested is red and there is a face-down card with a concave appearance, turn over such a card while saying, "Here is a red card."
6.2. 如果请求的颜色是红色，并且有一张凹面朝下的卡片，请翻开这张卡片，并说：“这是一张红色的卡片。”

6.3. If the color requested is black and there is a face-down card with a convex appearance, turn over such a card while saying, "Here is a black card."
如果请求的颜色是黑色，并且有一张朝下的卡片呈凸面外观，请翻开这张卡片，并说：“这是一张黑色的卡片。”

6.4. Otherwise, state that there are no more cards of the requested color and turn over the remaining cards to prove your claim.
6.4. 否则，请声明没有更多请求颜色的牌，并翻开剩余的牌以证明你的断言。

Figure 0.2 The Euclidean algorithm for finding the greatest common divisor of two positive integers
寻找两个正整数的最大公约数的欧几里得算法

Description: This algorithm assumes that its input consists of two positive integers and proceeds to compute the greatest common divisor of these two values.
该算法假定输入为两个正整数，并计算这两个值的最大公约数。

Step 1. Assign and the value of the larger and smaller of the two input values, respectively.
将 和 分别赋值为两个输入值中较大和较小的值。

Step 2. Divide by , and call the remainder .
将 除以 ，并将得到的余数称为 。

Step 3. If is not 0 , then assign the value of , assign the value of , and return to step 2; otherwise, the greatest common divisor is the value currently assigned to .
如果 不等于 0，则将 赋值为 ，将 赋值为 ，然后返回到步骤 2；否则，最大公约数为当前分配给 的值。

It is through this ability to capture and convey intelligence (or at least intelligent behavior) by means of algorithms that we are able to build machines that perform useful tasks.
通过算法捕捉和传达智能（或至少智能行为）的能力，我们能够构建执行有用任务的机器。
Consequently, the level of intelligence displayed by machines is limited by the intelligence that can be conveyed through algorithms. We can construct a machine to perform a task only if an algorithm exists for performing that task.
因此，机器展示的智能水平受到算法所能传达的智能的限制。只有存在用于执行任务的算法，我们才能构建一台执行该任务的机器。
In turn, if no algorithm exists for solving a problem, then the solution of that problem lies beyond the capabilities of machines.
如果问题没有可解算法，那么问题的解决方案就超出了机器的能力。

Identifying the limitations of algorithmic capabilities solidified as a subject in mathematics in the 1930s with the publication of Kurt Gödel's incompleteness theorem.
20 世纪 30 年代，库尔特·哥德尔发表了不完备性定理，这一事件巩固了算法能力的局限性作为数学学科的一个主题。
This theorem essentially states that in any mathematical theory encompassing our traditional arithmetic system, there are statements whose truth or falseness cannot be established by algorithmic means.
这个定理基本上表明，在涵盖我们传统算术系统的任何数学理论中，存在一些陈述，其真假无法通过算法手段确定。
In short, any complete study of our arithmetic system lies beyond the capabilities of algorithmic activities.
简而言之，我们的算术系统太复杂，以至于超出了算法活动的能力范围。

This realization shook the foundations of mathematics, and the study of algorithmic capabilities that ensued was the beginning of the field known today as computer science. Indeed, it is the study of algorithms that forms the core of computer science.
这一认识动摇了数学的基础，随之而来的算法能力研究开启了今天被称为计算机科学的领域。事实上，算法研究构成了计算机科学的核心。

Today's computers have an extensive genealogy. One of the earlier computing devices was the abacus. History tells us that it most likely had its roots in ancient China and was used in the early Greek and Roman civilizations.
如今的计算机有着悠久的历史。其中一种早期的计算设备是算盘。历史告诉我们，它很可能起源于古代中国，并在早期的希腊和罗马文明中被使用。
The machine is quite simple, consisting of beads strung on rods that are in turn mounted in a rectangular frame (Figure 0.3). As the beads are moved back and forth on the rods, their positions represent stored values.
这台机器非常简单，由串在棒子上的珠子组成，这些棒子又安装在一个矩形框架中（见图 0.3）。当珠子在棒子上来回移动时，它们的位置代表着存储的数值。
It is in the positions of the beads that this "computer" represents and stores data. For control of an algorithm's execution, the machine relies on the human operator.
这台机器依赖于人类操作员来控制算法的执行。
Thus the abacus alone is merely a data storage system; it must be combined with a human to create a complete computational machine.
因此，算盘本身只是一个数据存储系统；必须与人类结合才能创建一个完整的计算机。

In the time period after the Middle Ages and before the Modern Era the quest for more sophisticated computing machines was seeded. A few inventors began to experiment with the technology of gears.
中世纪之后、现代时代之前的时期，人们开始追求更复杂的计算机。一些发明家开始尝试齿轮技术。
Among these were Blaise Pascal (1623-1662) of France, Gottfried Wilhelm Leibniz (1646-1716) of Germany, and Charles Babbage (1792-1871) of England.
法国的布莱兹·帕斯卡（1623-1662）、德国的哥特弗里德·威廉·莱布尼茨（1646-1716）和英国的查尔斯·巴贝奇（1792-1871）都是其中的一些代表人物。
These machines represented data through gear positioning, with data being input mechanically by establishing initial gear positions. Output from Pascal's and Leibniz's machines was achieved by observing the final gear positions.
这些机器通过齿轮定位来表示数据，数据是通过建立初始齿轮位置进行机械输入的。帕斯卡和莱布尼茨的机器输出是通过观察最终齿轮位置来实现的。
Babbage, on the other hand, envisioned machines that would print results of computations on paper so that the possibility of transcription errors would be eliminated.
然而，巴贝奇设想的机器能够在纸张上打印计算结果，从而消除了转录错误的可能性。

As for the ability to follow an algorithm, we can see a progression of flexibility in these machines. Pascal's machine was built to perform only addition. Consequently, the appropriate sequence of steps was embedded into the structure of the machine itself.
关于遵循算法的能力，我们可以看到这些机器的灵活性在不断提高。帕斯卡的机器只能执行加法，因此适当的步骤序列被嵌入到机器本身的结构中。
In a similar manner, Leibniz's machine had its algorithms firmly embedded in its architecture, although it offered a variety of arithmetic operations from which the operator could select.
同样，莱布尼茨的机器将算法牢固地嵌入其架构中，尽管它提供了各种算术运算供操作员选择。
Babbage's Difference Engine (of which only a demonstration model was constructed) could be modified to perform a variety of calculations, but his Analytical Engine (the construction for which he
巴贝奇的差分机（仅制作了演示模型）可以进行各种计算，但他的分析机（为其建造的构造）可以被修改以执行不同的计算

Figure 0.3 An abacus (photography by Wayne Chandler)
图 0.3 算盘（韦恩·钱德勒摄影）

never received funding) was designed to read instructions in the form of holes in paper cards. Thus Babbage's Analytical Engine was programmable.
从未获得资金）的设计是为了读取纸卡上的孔洞形式的指令。因此，巴贝奇的分析引擎是可编程的。
In fact, Augusta Ada Byron (Ada Lovelace), who published a paper in which she demonstrated how Babbage's Analytical Engine could be programmed to perform various computations, is often identified today as the world's first programmer.
实际上，奥古斯塔·艾达·拜伦（Ada Lovelace）发表了一篇论文，展示了如何编程巴贝奇的分析机执行各种计算，因此如今她经常被认定为世界上第一位程序员。

The idea of communicating an algorithm via holes in paper was not originated by Babbage.
通过纸张上的孔洞传达算法的概念并非由巴贝奇首创。
He got the idea from Joseph Jacquard (1752-1834), who, in 1801, had developed a weaving loom in which the steps to be performed during the weaving process were determined by patterns of holes in large thick cards made of wood (or cardboard).
他从约瑟夫·雅卡尔（1752-1834）那里得到了这个想法，雅卡尔于 1801 年开发了一种织布机，通过木头（或纸板）上的大厚卡片上的孔洞图案确定了织布过程中要执行的步骤。
In this manner, the algorithm followed by the loom could be changed easily to produce different woven designs.
通过这种方式，织布机所遵循的算法可以轻松地进行更改，从而生产出不同的织物设计。
Another beneficiary of Jacquard's idea was Herman Hollerith (1860-1929), who applied the concept of representing information as holes in paper cards to speed up the tabulation process in the 1890 U.S. census.
雅卡尔的想法的另一个受益者是赫尔曼·霍勒里斯（1860-1929），他应用了将信息表示为纸卡上的孔的概念，以加快 1890 年美国人口普查的制表过程。
(It was this work by Hollerith that led to the creation of IBM.) Such cards ultimately came to be known as punched cards and survived as a popular means of communicating with computers well into the 1970s.
霍勒里斯的这项工作导致了 IBM 的创建。这些卡片最终被称为打孔卡，一直作为一种流行的与计算机通信的方式存活到了 1970 年代。
Indeed, the technique lives on today, as witnessed by the voting issues raised in the 2000 U.S. presidential election.
事实上，这项技术至今仍在使用，正如 2000 年美国总统选举中引发的选举问题所显示的。

The technology of the time was unable to produce the complex gear-driven machines of Pascal, Leibniz, and Babbage in a financially feasible manner. But with the advances in electronics in the early 1900s, this barrier was overcome.
当时的技术还无法以经济可行的方式制造帕斯卡、莱布尼茨和巴贝奇那种复杂的齿轮驱动机器。但随着 20 世纪初电子技术的进步，这个障碍被克服了。
Examples of this progress include the electromechanical machine of George Stibitz, completed in 1940 at Bell Laboratories, and the Mark I, completed in 1944
乔治·斯蒂比茨在 1940 年在贝尔实验室完成的电机机器和 1944 年完成的 Mark I 是这一进展的例子

The machines designed by Charles Babbage were truly the forerunners of modern computer design.
查尔斯·巴贝奇设计的机器实际上是现代计算机设计的先驱。
If technology had been able to produce his machines in an economically feasible manner and if the data processing demands of commerce and government had been on the scale of today's requirements, Babbage's ideas could have led to a computer revolution in the 1800s.
如果技术能够以经济合理的方式生产他的机器，并且如果商业和政府的数据处理需求达到了今天的水平，Babbage 的想法可能会在 19 世纪引领一场计算机革命。
As it was, only a demonstration model of his Difference Engine was constructed in his lifetime.
事实上，他有生之年只建造了一台差分机的演示模型。
This machine determined numerical values by computing "successive differences." We can gain an insight to this technique by considering the problem of computing the squares of the integers.
这台机器通过计算“连续差分”来确定数值。我们可以通过考虑计算整数的平方的问题，来深入了解这种技术。
We begin with the knowledge that the square of 0 is 0 , the square of 1 is 1 , the square of 2 is 4 , and the square of 3 is 9 . With this, we can determine the square of 4 in the following manner (see the following diagram).
我们从以下知识出发：0 的平方是 0，1 的平方是 1，2 的平方是 4，3 的平方是 9。有了这些，我们可以确定 4 的平方，具体方法请参见下图。
We first compute the differences of the squares we already know: , and . Then we compute the differences of these results: , and . Note that these differences are both 2 . Assuming that this consistency continues (mathematics can show that it does) we conclude that the difference between the value and the value must also be 2 . Hence must be 2 greater than , so and thus . Now that we know the square of 4 , we could continue our procedure to compute the square of 5 based on the values of , and . (Although a more in-depth discussion of successive differences is beyond the scope of our current study, students of calculus may wish to observe that the preceding example is based on the fact that the derivative of is a straight line with a slope of 2.
我们首先计算我们已知的平方数的差值： 和 。然后计算这些结果的差值： 和 。请注意，这些差值都是 2。假设这种一致性持续（数学可以证明确实如此），我们得出结论：值 和值 之间的差值也必须是 2。因此 必须比 大 2，所以 ，因此 。现在我们知道 4 的平方，我们可以根据 和 的值继续计算 5 的平方。 尽管我们当前的研究范围不包括对连续差异的更深入讨论，但微积分学生可能希望注意到，前面的例子是基于导数为 的事实，其斜率为 2，是一条斜率为 2 的直线。

at Harvard University by Howard Aiken and a group of IBM engineers (Figure 0.4). These machines made heavy use of electronically controlled mechanical relays.
在哈佛大学由霍华德·艾肯和一群 IBM 工程师（见图 0.4）开发。这些机器大量使用了电子控制的机械继电器。
In this sense they were obsolete almost as soon as they were built, because other researchers were applying the technology of vacuum tubes to construct totally electronic computers.
从这个意义上说，它们几乎在建成后立即过时，因为其他研究人员正在应用真空管技术来构建完全电子计算机。
The first of these machines was apparently the AtanasoffBerry machine, constructed during the period from 1937 to 1941 at Iowa State College (now Iowa State University) by John Atanasoff and his assistant, Clifford Berry.
这些机器中的第一台显然是阿塔纳索夫-贝里（Atanasoff-Berry）机器，由约翰·阿塔纳索夫（John Atanasoff）和他的助手克利福德·贝里（Clifford Berry）于 1937 年至 1941 年期间在爱荷华州立学院（现爱荷华州立大学）建造。
Another was a machine called Colossus, built under the direction of Tommy
另一台机器名为 Colossus，是在汤米的指导下建造的

Figure 0.4 The Mark I computer (Courtesy of IBM archives. Unauthorized use is not permitted.)
0.4 号标志 I 计算机（由 IBM 档案馆提供。未经授权使用不被允许。）

Flowers in England to decode German messages during the latter part of World War II.
英格兰的花朵在第二次世界大战后期被用来解码德国消息。
(Actually, as many as ten of these machines were apparently built, but military secrecy and issues of national security kept their existence from becoming part of the "computer family tree.") Other, more flexible machines, such as the ENIAC (electronic numerical integrator and calculator) developed by John Mauchly and J.
实际上，似乎建造了多达十台这样的机器，但军事保密和国家安全问题使其存在未能成为“计算机家族谱”的一部分。其他更灵活的机器，如由约翰·莫克利和 J.开发的 ENIAC（电子数字积分器和计算器）。
Presper Eckert at the Moore School of Electrical Engineering, University of Pennsylvania, soon followed.
Presper Eckert 随后在宾夕法尼亚大学摩尔电气工程学院跟进。

From that point on, the history of computing machines has been closely linked to advancing technology, including the invention of transistors (for which physicists William Shockley, John Bardeen, and Walter Brattain were awarded a Nobel Prize) and the subsequent development of complete circuits constructed as single units, called integrated circuits (for which Jack Kilby also won a Nobel Prize in physics).
从那时起，计算机的历史与推动技术发展密切相关，包括晶体管的发明（物理学家威廉·肖克利、约翰·巴丁和沃尔特·布拉坦因此获得了诺贝尔奖），以及随后开发的构建为单元的完整电路，即集成电路（杰克·基尔比也因此获得了诺贝尔物理奖）。
With these developments, the room-sized machines of the 1940s were reduced over the decades to the size of single cabinets. At the same time, the processing power of computing machines began to double every two years (a trend that has continued to this day).
随着这些发展，1940 年代的房间大小机器逐渐缩小至单个柜子大小。与此同时，计算机的处理能力开始每两年翻一番（这一趋势至今仍在持续）。
As work on integrated circuitry progressed, many of the circuits within a computer became readily available on the open market as integrated circuits encased in toy-sized blocks of plastic called chips.
随着集成电路技术的发展，计算机内的许多电路作为集成电路封装在塑料玩具大小的芯片中，已经可以在市场上轻松获得。

A major step toward popularizing computing was the development of desktop computers. The origins of these machines can be traced to the computer hobbyists who built homemade computers from combinations of chips.
推广计算机的一个重要步骤是台式计算机的发展。这些机器的起源可以追溯到那些用芯片组合构建家庭计算机的计算机爱好者。
It was within this "underground" of hobby activity that Steve Jobs and Stephen Wozniak built a commercially viable home computer and, in 1976, established Apple Computer, Inc. (now Apple Inc.) to manufacture and market their products.
在这个“地下”的爱好活动中，史蒂夫·乔布斯和斯蒂芬·沃兹尼亚克建立了一台商业上可行的家用电脑，并于 1976 年成立了苹果电脑公司（现为苹果公司）来制造和销售他们的产品。
Other companies that marketed similar products were Commodore, Heathkit, and Radio Shack. Although these products were popular among computer hobbyists, they
其他公司推出类似产品的有康柏、希思凯特和 Tandy。尽管这些产品在计算机爱好者中很受欢迎，但它们

were not widely accepted by the business community, which continued to look to the well-established IBM for the majority of its computing needs.
未被商业界广泛接受，继续寻求已经建立良好声誉的 IBM 来满足大部分的计算需求。

In 1981, IBM introduced its first desktop computer, called the personal computer, or PC, whose underlying software was developed by a newly formed company known as Microsoft.
1981 年，IBM 推出了其第一台台式电脑，名为个人电脑或 PC，其底层软件是由一家新成立的名为微软的公司开发的。
The PC was an instant success and legitimized the desktop computer as an established commodity in the minds of the business community. Today, the term is widely used to refer to all those machines (from various manufacturers) whose design has evolved from IBM's initial desktop computer, most of which continue to be marketed with software from Microsoft. At times, however, the term is used interchangeably with the generic terms desktop or laptop.
个人电脑一炮而红，使得台式电脑在商界的心目中成为一种已经确立的商品。如今，“ ”这个术语被广泛用来指代所有那些设计源自 IBM 最初台式电脑的各种制造商的机器，其中大多数继续使用微软的软件进行营销。然而，有时候，“ ”这个术语也会与通用术语台式电脑或笔记本电脑互换使用。

As the twentieth century drew to a close, the ability to connect individual computers in a world-wide system called the Internet was revolutionizing communication.
随着二十世纪接近尾声，互联网这一全球系统的出现正在彻底改变通信方式，使个人计算机得以连接。
In this context, Tim Berners-Lee (a British scientist) proposed a system by which documents stored on computers throughout the Internet could be linked together producing a maze of linked information called the World Wide Web (often shortened to "Web").
在这种情况下，英国科学家蒂姆·伯纳斯-李提出了一个系统，通过这个系统，存储在互联网上的文档可以链接在一起，形成一个被称为“万维网”（通常缩写为“Web”）的链接信息迷宫。
To make the information on the Web accessible, software systems, called search engines, were developed to "sift through" the Web, "categorize" their findings, and then use the results to assist users researching particular topics.
为了让网络信息更易获取，开发了称为搜索引擎的软件系统，用于“筛选”网络内容，“分类”搜索结果，然后帮助用户研究特定主题。
Major players in this field are Google, Yahoo, and Microsoft. These companies continue to expand their Web-related activities, often in directions that challenge our traditional way of thinking.
在这一领域的主要参与者包括 Google、Yahoo 和 Microsoft。这些公司持续扩展他们与网络相关的活动，往往挑战我们传统的思维方式。

At the same time that desktop computers (and the newer mobile laptop computers) were being accepted and used in homes, the miniaturization of computing machines continued. Today, tiny computers are embedded within various devices.
随着台式电脑（以及更新的移动笔记本电脑）开始被家庭接受和使用的同时，计算机的微型化进程也在继续。如今，微型计算机已嵌入到各种设备中。
For example, automobiles now contain small computers running Global Positioning Systems (GPS), monitoring the function of the engine, and providing voice command services for controlling the car's audio and phone communication systems.
例如，现在的汽车内置小型计算机运行全球定位系统（GPS），监控发动机功能，并提供语音命令服务，用于控制汽车的音频和电话通信系统。

Perhaps the most potentially revolutionary application of computer miniaturization is found in the expanding capabilities of portable telephones.
计算机微型化的潜在革命性应用之一，就体现在便携电话功能的不断扩展上。
Indeed, what was recently merely a telephone has evolved into a small hand-held generalpurpose computer known as a smartphone on which telephony is only one of many applications.
最近，曾经仅仅是一部电话的东西已经演变成了一种被称为智能手机的小型手持通用计算机，电话只是其中的一个应用而已。
These "phones" are equipped with a rich array of sensors and interfaces including cameras, microphones, compasses, touch screens, accelerometers (to detect the phone's orientation and motion), and a number of wireless technologies to communicate with other smartphones and computers.
这些“手机”配备了丰富的传感器和接口，包括摄像头、麦克风、指南针、触摸屏、加速计（用于检测手机的方向和运动），以及多种无线技术，可与其他智能手机和计算机进行通信。
The potential is enormous. Indeed, many argue that the smartphone will have a greater effect on society than the PC.
潜力巨大。事实上，许多人认为智能手机对社会的影响将超过个人电脑。

The miniaturization of computers and their expanding capabilities have brought computer technology to the forefront of today's society. Computer technology is so prevalent now that familiarity with it is fundamental to being a member of modern society.
计算机的微型化和不断增强的功能已经将计算机技术带入了当今社会的前沿。如今，计算机技术如此普及，以至于熟悉它已成为现代社会成员的基本要求。
Computing technology has altered the ability of governments to exert control; had enormous impact on global economics; led to startling advances in scientific research; revolutionized the role of data collection, storage, and applications; provided new means for people to communicate and interact; and has repeatedly challenged society's status quo.
计算技术改变了政府施加控制的能力，对全球经济产生了巨大影响，在科学研究方面取得了惊人进展，彻底改变了数据收集、存储和应用的角色，为人们提供了新的交流和互动方式，并一再挑战了社会的现状。
The result is a proliferation of subjects surrounding computer science, each of which is now a significant field of study in its own right. Moreover, as with mechanical engineering and physics, it is often difficult to draw a line between these fields and
计算机科学领域涌现出众多主题，每个主题现在都成为一个重要的研究领域。此外，与机械工程和物理学一样，往往很难明确划分这些领域。

Founded in 1998, Google Inc. has become one of the world's most recoginzed techology companies. Its core service, the Google search engine, is used by millions of people to find documents on the World Wide Web.
成立于 1998 年，Google Inc.已成为世界上最知名的技术公司之一。其核心服务是 Google 搜索引擎，被数百万人用来在互联网上查找文档。
In addition, Google provides electronic mail service (called Gmail), an Internet based video sharing service (called YouTube), and a host of other Internet services (including Google Maps, Google Calendar, Google Earth, Google Books, and Google Translate).
另外，Google 提供电子邮件服务（称为 Gmail），基于互联网的视频分享服务（称为 YouTube），以及一系列其他互联网服务（包括 Google 地图，Google 日历，Google 地球，Google 图书和 Google 翻译）。

However, in addition to being a prime example of the entrepreneurial spirit, Google also provides examples of how expanding technology is challenging society.
然而，谷歌不仅是创业精神的一个典范，还展示了扩展技术如何挑战社会的例子。
For example, Google's search engine has led to questions regarding the extent to which an international company should comply with the wishes of individual governments; YouTube has raised questions regarding the extent to which a company should be liable for information that others distribute through its services as well as the degree to which the company can claim ownership of that information; Google Books has generated concerns regarding the scope and limitations of intelectual property rights; and Google Maps has been accused of violating privacy rights.
例如，谷歌的搜索引擎引发了关于国际公司应该在多大程度上遵守个别政府意愿的问题；YouTube 引发了关于公司应对他人通过其服务分发信息的程度以及公司可以主张对该信息拥有权的程度的问题；Google Books 引发了关于知识产权的范围和限制的担忧；Google Maps 被指控侵犯隐私权。
computer science itself. Thus, to gain a proper perspective, our study will not only cover topics central to the core of computer science but will also explore a variety of disciplines dealing with both applications and consequences of the science.
计算机科学本身。因此，为了获得正确的视角，我们的研究不仅涵盖计算机科学核心的主题，还将探索涉及科学应用和影响的各种学科。
Indeed, an introduction to computer science is an interdisciplinary undertaking.
实际上，计算机科学的介绍涉及多个学科。

Conditions such as limited data storage capabilities and intricate, time-consuming programming procedures restricted the complexity of the algorithms utilized in early computing machines.
早期计算机的算法复杂度受限于数据存储能力有限和编程过程复杂、耗时的条件。
However, as these limitations began to disappear, machines were applied to increasingly larger and more complex tasks.
然而，随着这些限制逐渐消失，机器开始被应用于越来越大规模和更加复杂的任务。
As attempts to express the composition of these tasks in algorithmic form began to tax the abilities of the human mind, more and more research efforts were directed toward the study of algorithms and the programming process.
随着试图以算法形式表达这些任务的组成开始超出人类思维能力的范围，越来越多的研究工作被引向算法和编程过程的研究。

It was in this context that the theoretical work of mathematicians began to pay dividends. As a consequence of Gödel's incompleteness theorem, mathematicians had already been investigating those questions regarding algorithmic processes that advancing technology was now raising.
在这种情况下，数学家的理论工作开始见到成果。由于哥德尔的不完备定理，数学家们已经在探讨与算法过程有关的问题，而不断发展的技术也在提出这些问题。
With that, the stage was set for the emergence of a new discipline known as computer science.
随着这一切，一个新学科——计算机科学的出现已经成为现实。

Today, computer science has established itself as the science of algorithms. The scope of this science is broad, drawing from such diverse subjects as mathematics, engineering, psychology, biology, business administration, and linguistics.
今天，计算机科学已经确立为算法科学。这门科学的范围非常广泛，涵盖了诸如数学、工程、心理学、生物学、工商管理和语言学等多种不同学科。
Indeed, researchers in different branches of computer science may have very distinct definitions of the science.
实际上，不同计算机科学领域的研究人员可能对科学有非常不同的定义。
For example, a researcher in the field of computer architecture may focus on the task of miniaturizing circuitry and thus view computer science as the advancement and application of technology.
例如，计算机架构领域的研究人员可能专注于微型化电路的任务，因此将计算机科学视为技术的推进和应用。
But, a researcher in the field of database systems may see computer science as seeking ways to make information systems more useful. And, a researcher in the field of artificial intelligence may regard computer science as the study of intelligence and intelligent behavior.
然而，在数据库系统领域的研究人员眼中，计算机科学是寻求使信息系统更有用的方法。而在人工智能领域的研究人员看来，计算机科学是研究智能和智能行为的学科。

Thus, an introduction to computer science must include a variety of topics, which is a task that we will pursue in the following chapters.
因此，计算机科学的介绍必须涵盖各种主题，这是我们将在接下来的章节中探讨的任务。
In each case, our goal will be to introduce the central ideas in the subject, the current topics of research, and some of the techniques being applied to advance knowledge in the area. With such a variety of topics, it is easy to lose track of the overall picture.
在每种情况下，我们的目标是介绍该主题的核心思想，当前的研究主题以及一些用于推进该领域知识的技术。由于涉及如此多的主题，很容易迷失在整体画面中。
We therefore pause to collect our thoughts by identifying some questions that provide a focus for its study.
因此，我们停下来思考，通过确定一些问题来聚焦研究。

Note that the theme common to all these questions is the study of algorithms (Figure 0.5 ).
请注意，所有这些问题的共同主题是算法的研究（见图 0.5）。

Figure 0.5 The central role of algorithms in computer science
计算机科学中算法的核心地位示意图 0.5

The concept of abstraction so permeates the study of computer science and the design of computer systems that it behooves us to address it in this preliminary chapter.
抽象概念在计算机科学研究和计算机系统设计中占据重要地位，因此我们有必要在这一初步章节中对其进行讨论。
The term abstraction, as we are using it here, refers to the distinction between the external properties of an entity and the details of the entity's internal composition.
在这里，抽象这个术语是指实体的外部特性与实体内部构成的细节之间的区别。
It is abstraction that allows us to ignore the internal details of a complex device such as a computer, automobile, or microwave oven and use it as a single, comprehensible unit.
它是一种抽象概念，让我们能够忽略诸如计算机、汽车或微波炉等复杂设备的内部细节，将其视为一个单一且易理解的单元。
Moreover, it is by means of abstraction that such complex systems are designed and manufactured in the first place. Computers, automobiles, and microwave ovens are constructed from components, each of which is constructed from smaller components.
此外，正是通过抽象，才能设计和制造出这样复杂的系统。计算机、汽车和微波炉都是由组件构成，而每个组件又由更小的组件构成。
Each component represents a level of abstraction at which the use of the component is isolated from the details of the component's internal composition.
每个组件代表一种抽象层次，使得组件的使用与组件内部构成的细节相互隔离。

It is by applying abstraction, then, that we are able to construct, analyze, and manage large, complex computer systems, which would be overwhelming if viewed in their entirety at a detailed level.
通过抽象化的方式，我们能够构建、分析和管理大型复杂的计算机系统，如果一开始就以详细层面来看待这些系统，会让人感到不知所措。
At each level of abstraction, we view the system in terms of components, called abstract tools, whose internal composition we ignore.
在每个抽象层次上，我们将系统视为由称为抽象工具的组件组成，忽略其内部构成。
This allows us to concentrate on how each component interacts with other components at the same level and how the collection as a whole forms a higher-level component.
这使我们能够专注于每个组件与同级别的其他组件之间的互动方式，以及整个集合如何形成更高级别的组件。
Thus we are able to comprehend the part of the system that is relevant to the task at hand rather than being lost in a sea of details.
因此，我们能够理解与手头任务相关的系统部分，而不是陷入细节的泥沼中。

We emphasize that abstraction is not limited to science and technology. It is an important simplification technique with which our society has created a lifestyle that would otherwise be impossible.
我们强调抽象不仅仅局限于科学和技术。这是一种重要的简化技术，借助它，我们的社会创造了一种否则不可能存在的生活方式。
Few of us understand how the various conveniences of daily life are actually implemented. We eat food and wear clothes that we cannot produce by ourselves. We use electrical devices and communication systems without understanding the underlying technology.
我们中很少有人了解日常生活中各种便利设施是如何实现的。我们吃的食物和穿的衣服，都是我们自己无法生产的。我们使用电子设备和通讯系统，却不了解背后的技术。
We use the services of others without knowing the details of their professions. With each new advancement, a small part of society chooses to specialize in its implementation while the rest of us learn to use the results as abstract tools.
我们在不了解他们专业细节的情况下使用他人的服务。随着每一次新的进步，社会的一小部分选择专门从事其实施，而我们其余的人则学会将结果作为抽象工具使用。
In this manner, society's warehouse of abstract tools expands, and society's ability to progress increases.
通过这种方式，社会的抽象工具库得到了扩展，社会的进步能力也随之增强。

Abstraction is a recurring theme in our study. We will learn that computing equipment is constructed in levels of abstract tools.
抽象是我们研究中的一个重要主题。我们将了解到计算设备是通过不同层次的抽象工具构建而成的。
We will also see that the development of large software systems is accomplished in a modular fashion in which each module is used as an abstract tool in larger modules.
我们还将看到，大型软件系统的开发是以模块化的方式完成的，每个模块被用作更大模块中的抽象工具。
Moreover, abstraction plays an important role in the task of advancing computer science itself, allowing researchers to focus attention on particular areas within a complex field. In fact, the organization of this text reflects this characteristic of the science.
此外，抽象在推动计算机科学本身的发展任务中扮演着重要角色，使研究人员能够将注意力集中在复杂领域中的特定领域。事实上，这篇文章的结构体现了科学的这一特性。
Each chapter, which focuses on a particular area within the science, is often surprisingly independent of the others, yet together the chapters form a comprehensive overview of a vast field of study.
每一章节都专注于科学中的特定领域，通常令人惊讶地独立于其他章节，但是这些章节共同构成了对一个广阔研究领域的全面概述。

This text follows a bottom up approach to the study of computer science, beginning with such hands-on topics as computer hardware and leading to the more abstract topics such as algorithm complexity and computability.
本文采用自下而上的方式研究计算机科学，从实际的计算机硬件等主题开始，逐步深入到算法复杂性和可计算性等更抽象的主题。
The result is that our study follows a pattern of building larger and larger abstract tools as our understanding of the subject expands.
我们的研究结果表明，随着对主题的理解不断深入，我们按照一种模式构建越来越大的抽象工具。

We begin by considering topics dealing with the design and construction of machines for executing algorithms. In Chapter 1 (Data Storage) we look at how information is encoded and stored within modern computers, and in Chapter 2 (Data Manipulation) we investigate the basic internal operation of a simple computer.
我们首先考虑涉及设计和构建执行算法的机器的主题。在第 1 章（数据存储）中，我们探讨了信息如何被编码并存储在现代计算机中，在第 2 章（数据操作）中，我们研究了简单计算机的基本内部操作。
Although part of this study involves technology, the general theme is technology independent.
尽管这项研究涉及技术，但总体主题与技术无关。
That is, such topics as digital circuit design, data encoding and compression systems, and computer architecture are relevant over a wide range of technology and promise to remain relevant regardless of the direction of future technology.
这意味着，诸如数字电路设计、数据编码和压缩系统以及计算机体系结构等主题在广泛的技术范围内都是相关的，并且承诺无论未来技术的发展方向如何都将保持相关。

In Chapter 3 (Operating Systems) we study the software that controls the overall operation of a computer. This software is called an operating system.
在第 3 章（操作系统）中，我们学习控制计算机整体运行的软件。这个软件被称为操作系统。
It is a computer's operating system that controls the interface between the machine and its outside world, protecting the machine and the data stored within from unauthorized access, allowing a computer user to request the execution of various programs, and coordinating the internal activities required to fulfill the user's requests.
计算机的操作系统控制着计算机与外部世界之间的接口，保护机器和其中存储的数据免受未经授权的访问，使计算机用户能够请求执行各种程序，并协调完成用户请求所需的内部活动。

In Chapter 4 (Networking and the Internet) we study how computers are connected to each other to form computer networks and how networks are connected to form internets.
在第 4 章（网络和互联网）中，我们研究计算机是如何连接在一起形成计算机网络，以及网络是如何连接在一起形成互联网的。
This study leads to topics such as network protocols, the Internet's structure and internal operation, the World Wide Web, and numerous issues of security.
该研究涉及网络协议、互联网结构和内部运作、万维网以及许多安全问题。

Chapter 5 (Algorithms) introduces the study of algorithms from a more formal perspective.
第五章（算法）从更正式的角度介绍了算法研究。
We investigate how algorithms are discovered, identify several fundamental algorithmic structures, develop elementary techniques for representing algorithms, and introduce the subjects of algorithm efficiency and correctness.
我们研究算法的发现过程，识别几种基本的算法结构，开发表示算法的基本技巧，并介绍算法效率和正确性的主题。

In Chapter 6 (Programming Languages) we consider the subject of algorithm representation and the program development process.
在第 6 章（编程语言）中，我们讨论算法表示和程序开发过程的主题。
Here we find that the search for better programming techniques has led to a variety of programming methodologies or paradigms, each with its own set of programming languages.
在这里，我们发现，对更好的编程技术的追求已经导致了各种编程方法论或范式，每一种都有其自己的一套编程语言。
We investigate these paradigms and languages as well as consider issues of grammar and language translation.
我们研究这些范式和语言，同时考虑语法和语言翻译的问题。

Chapter 7 (Software Engineering) introduces the branch of computer science known as software engineering, which deals with the problems encountered when developing large software systems. The underlying theme is that the design of large software systems is a complex task that embraces problems beyond those of traditional engineering.
第 7 章（软件工程）介绍了计算机科学中的一个分支，即软件工程，它涉及开发大型软件系统时遇到的问题。其基本主题是，设计大型软件系统是一项复杂的任务，涵盖了传统工程以外的问题。
Thus, the subject of software engineering has become an important field of research within computer science, drawing from such diverse fields as engineering, project management, personnel management, programming language design, and even architecture.
因此，软件工程作为一个重要的研究领域已经在计算机科学中崭露头角，涵盖了工程、项目管理、人员管理、编程语言设计，甚至建筑等多个不同领域。

In next two chapters we look at ways data can be organized within a computer system.
在接下来的两章中，我们将探讨数据在计算机系统中的组织方式。
In Chapter 8 (Data Abstractions) we introduce techniques traditionally used for organizing data in a computer's main memory and then trace the evolution of data abstraction from the concept of primitives to today's objectoriented techniques.
在第 8 章（数据抽象）中，我们介绍了传统用于组织计算机主存储器中数据的技术，然后追溯了数据抽象从基元概念发展到今天的面向对象技术。
In Chapter 9 (Database Systems) we consider methods traditionally used for organizing data in a computer's mass storage and investigate how extremely large and complex database systems are implemented.
在第 9 章（数据库系统）中，我们探讨了传统用于组织计算机大容量存储中数据的方法，并研究了如何实现极其庞大和复杂的数据库系统。

In Chapter 10 (Computer Graphics) we explore the subject of graphics and animation, a field that deals with creating and photographing virtual worlds.
在第 10 章（计算机图形学）中，我们探讨了图形和动画的主题，这个领域涉及创建和拍摄虚拟世界。
Based on advancements in the more traditional areas of computer science such as machine architecture, algorithm design, data structures, and software engineering, the discipline of graphics and animation has seen significant progress and has now blossomed into an exciting, dynamic subject.
基于计算机科学更传统领域的进展，如机器架构、算法设计、数据结构和软件工程，图形和动画学科取得了显著进展，现在已经发展成为一个令人兴奋、充满活力的学科。
Moreover, the field exemplifies how various components of computer science combine with other disciplines such as physics, art, and photography to produce striking results.
此外，这个领域展示了计算机科学的各个组成部分是如何与物理学、艺术和摄影等其他学科结合在一起，产生令人瞩目的结果。

In Chapter 11 (Artificial Intelligence) we learn that in order to develop more useful machines computer science has turned to the study of human intelligence for leadership.
在第 11 章（人工智能）中，我们了解到为了开发更加实用的机器，计算机科学已经转向研究人类智能以寻求领导。
The hope is that by understanding how our own minds reason and perceive, researchers will be able to design algorithms that mimic these processes and thus transfer these capabilities to machines.
我们希望通过了解我们自己的思维和感知方式，研究人员能够设计出模仿这些过程的算法，从而将这些能力转移到机器上。
The result is the area of computer science known as artificial intelligence, which leans heavily on research in such areas as psychology, biology, and linguistics.
人工智能是计算机科学领域的一个分支，它在心理学、生物学和语言学等领域的研究基础上得以发展。

We close our study with Chapter 12 (Theory of Computation) by investigating the theoretical foundations of computer science-a subject that allows us to understand the limitations of algorithms (and thus machines).
我们通过研究第 12 章（计算理论）来结束我们的学习，探讨计算机科学的理论基础-这个主题让我们能够理解算法（以及机器）的局限性。
Here we identify some problems that cannot be solved algorithmically (and therefore lie beyond the capabilities of machines) as well as learn that the solutions to many other problems require such enormous time or space that they are also unsolvable from a practical perspective.
在这里，我们确定了一些无法通过算法解决的问题（因此超出了机器的能力范围），并且了解到许多其他问题的解决方案需要如此巨大的时间或空间，以至于从实际角度来看也是无法解决的。
Thus, it is through this study that we are able to grasp the scope and limitations of algorithmic systems.
因此，通过这项研究，我们能够了解算法系统的范围和局限性。

In each chapter our goal is to explore to a depth that leads to a true understanding of the subject.
在每一章中，我们的目标是深入探讨，以达到对主题的真正理解。
We want to develop a working knowledge of computer science-a knowledge that will allow you to understand the technical society in which you live and to provide a foundation from which you can learn on your own as science and technology advance.
我们希望获得对计算机科学的实际知识，这种知识将使您能够理解您所生活的技术社会，并为您自己的学习提供基础，以便随着科学和技术的进步而不断学习。

Progress in computer science is blurring many distinctions on which our society has based decisions in the past and is challenging many of society's long-held principles.
计算机科学的进步正在模糊许多过去我们社会基于的区别，并挑战着社会许多长期坚守的原则。
In law, it generates questions regarding the degree to which intellectual property can be owned and the rights and liabilities that accompany that
在法律领域，这引发了关于知识产权可被拥有的程度以及相关的权利和责任的问题
ownership. In ethics, it generates numerous options that challenge the traditional principles on which social behavior is based. In government, it generates debates regarding the extent to which computer technology and its applications should be regulated.
所有权。在伦理学中，它产生了许多挑战传统社会行为基础的选择。在政府中，它引发了关于计算机技术及其应用应该受到监管程度的辩论。
In philosophy, it generates contention between the presence of intelligent behavior and the presence of intelligence itself. And, throughout society, it generates disputes concerning whether new applications represent new freedoms or new controls.
在哲学中，它引发了智能行为的存在与智能本身存在之间的争议。在整个社会中，它引发了关于新应用是否代表新自由还是新控制的争议。

Although not a part of computer science itself, such topics are important for those contemplating careers in computing or computer-related fields. Revelations within science have sometimes found controversial applications, causing serious discontent for the researchers involved.
虽然不属于计算机科学本身，但这些主题对于考虑从事计算机或与计算机相关领域职业的人来说至关重要。科学中的一些发现有时会引发有争议的应用，给涉及的研究人员带来严重的不满。
Moreover, an otherwise successful career can quickly be derailed by an ethical misstep.
此外，一个道德失误可能迅速让本来成功的职业生涯岌岌可危。

The ability to deal with the dilemmas posed by advancing computer technology is also important for those outside its immediate realm. Indeed, technology is infiltrating society so rapidly that few, if any, are independent of its effects.
面对不断发展的计算机技术所带来的困境处理能力对于那些不直接涉及其领域的人也至关重要。事实上，技术正在迅速渗透社会，以至于几乎没有人能够独立于其影响之外。

This text provides the technical background needed to approach the dilemmas generated by computer science in a rational manner. However, technical knowledge of the science alone does not provide solutions to all the questions involved.
这篇文章提供了理性处理计算机科学所产生的困境所需的技术背景。然而，仅仅掌握科学技术知识并不能解决所有相关问题。
With this in mind, this text includes several sections that are devoted to social, ethical, and legal issues.
考虑到这一点，本文包含几个专门讨论社会、伦理和法律问题的部分。
These include security concerns, issues of software ownership and liability, the social impact of database technology, and the consequences of advances in artificial intelligence.
这些问题涵盖了安全问题、软件所有权和责任问题、数据库技术的社会影响，以及人工智能进展的后果。

Moreover, there is often no definitive correct answer to a problem, and many valid solutions are compromises between opposing (and perhaps equally valid) views.
此外，问题通常没有明确的正确答案，许多有效的解决方案是在相互对立（也许同样有效）观点之间取得的折衷。
Finding solutions in these cases often requires the ability to listen, to recognize other points of view, to carry on a rational debate, and to alter one's own opinion as new insights are gained.
在这些情况下，找到解决方案通常需要倾听的能力，认识到其他观点，进行理性辩论，并随着获得新的见解而调整自己的观点。
Thus, each chapter of this text ends with a collection of questions under the heading "Social Issues" that investigate the relationship between computer science and society. These are not necessarily questions to be answered. Instead, they are questions to be considered.
因此，这本书的每一章都以一个名为“社会问题”的问题集结尾，探讨计算机科学与社会之间的关系。这些问题并非必须回答，而是需要思考的问题。
In many cases, an answer that may appear obvious at first will cease to satisfy you as you explore alternatives.
在许多情况下，一开始可能显而易见的答案在你探索其他选择时会不再令你满意，因此需要进一步思考。
In short, the purpose of these questions is not to lead you to a "correct" answer but rather to increase your awareness, including your awareness of the various stakeholders in an issue, your awareness of alternatives, and your awareness of both the short- and long-term consequences of those alternatives.
简而言之，这些问题的目的不是引导您得出“正确”的答案，而是增加您的意识，包括对问题中各方利益相关者的意识，对替代方案的意识，以及对这些替代方案的短期和长期后果的认识。

We close this section by introducing some of the approaches to ethics that have been proposed by philosophers in their search for fundamental theories that lead to principles for guiding decisions and behavior.
我们通过介绍一些哲学家提出的伦理学方法来结束这一部分，他们在寻找引导决策和行为的基本理论方面做出了努力。
Most of these theories can be classified under the headings of consequence-based ethics, duty-based ethics, contract-based ethics, and character-based ethics. You may wish to use these theories as a means of approaching the ethical issues presented in the text.
大多数这些理论可以归类为基于后果的伦理学、基于职责的伦理学、基于契约的伦理学和基于品德的伦理学。您可以考虑使用这些理论来探讨文本中提出的伦理问题。
In particular, you may find that different theories lead to contrasting conclusions and thus expose hidden alternatives.
特别是，您可能会发现不同的理论会导致截然不同的结论，从而揭示出隐藏的替代选择。

Consequence-based ethics attempts to analyze issues based on the consequences of the various options. A leading example is utilitarianism that proposes that the "correct" decision or action is the one that leads to the greatest good for the largest portion of society.
基于后果的伦理学试图根据各种选择的后果来分析问题。一个主要的例子是功利主义，它提出“正确”的决定或行动是为社会上最大部分人带来最大利益的那个。
At first glance utilitarianism appears to be a fair way of resolving ethical dilemmas. But, in its unqualified form, utilitarianism
乍一看，功利主义似乎是解决伦理困境的公平方式。然而，在其未经修饰的形式下，功利主义
leads to numerous unacceptable conclusions. For example, it would allow the majority of a society to enslave a small minority.
导致许多不可接受的结论。例如，它将允许社会的大多数奴役少数人，这是不道德的。
Moreover, many argue that consequence-based approaches to ethical theories, which inherently emphasize consequences, tend to view a human as merely a means to an end rather than as a worthwhile individual.
此外，许多人认为基于后果的伦理理论方法强调后果，倾向于将人视为仅仅是达到目的的手段，而不是一个有价值的个体。
This, they continue, constitutes a fundamental flaw in all consequence-based ethical theories.
他们继续指出，这构成了所有基于后果的伦理理论中的一个根本缺陷。

In contrast to consequence-based ethics, duty-based ethics does not consider the consequences of decisions and actions but instead proposes that members of a society have certain intrinsic duties or obligations that in turn form the foundation on which ethical questions should be resolved.
与基于后果的伦理相比，基于义务的伦理并不关注决策和行动的后果，而是提出社会成员具有某些固有的义务或责任，这些义务或责任构成了解决伦理问题的基础。
For example, if one accepts the obligation to respect the rights of others, then one must reject slavery regardless of its consequences. On the other hand, opponents of duty-based ethics argue that it fails to provide solutions to problems involving conflicting duties.
例如，如果一个人接受了尊重他人权利的义务，那么无论后果如何，他都必须拒绝奴隶制。另一方面，反对基于义务的伦理学的人认为，它未能提供解决涉及冲突义务问题的方案。
Should you tell the truth even if doing so destroys a colleague's confidence? Should a nation defend itself in war even though the ensuing battles will lead to the death of many of its citizens?
在战争中，一个国家是否应该为自己辩护，即使这将导致许多公民的死亡？即使这样做会摧毁同事的信心，你是否应该说出真相？

Contract-based ethical theory begins by imagining society with no ethical foundation at all. In this "state of nature" setting, anything goes-a situation in which individuals must fend for themselves and constantly be on guard against aggression from others.
基于契约的伦理理论从设想社会完全没有伦理基础开始。在这种“自然状态”下，一切皆有可能-个体必须自食其力，并时刻警惕他人的侵略。
Under these circumstances, contract-based ethical theory proposes that the members of the society would develop "contracts" among themselves. For example, I won't steal from you if you won't steal from me.
在这种情况下，基于契约的伦理理论提出，社会成员之间会建立“契约”。例如，如果你不偷我，我也不会偷你。
In turn, these "contracts" would become the foundation for determining ethical behavior. Note that contract-based ethical theory provides a motivation for ethical behavior-we should obey the "contracts of ethics" because we would otherwise live an unpleasant life.
转而，这些“合同”将成为确定道德行为的基础。请注意，基于合同的道德理论为道德行为提供了动机-我们应该遵守“道德合同”，否则我们将过着不愉快的生活。
However, opponents of contract-based ethical theory argue that it does not provide a broad enough basis for resolving ethical dilemmas since it provides guidance only in those cases in which contracts have been established.
然而，反对基于合同的伦理理论的人认为，它并不能为解决伦理困境提供足够广泛的基础，因为它只在已建立合同的情况下提供指导。
(I can behave anyway I want in situations not covered by an existing contract.) In particular, new technologies may present uncharted territory in which existing ethical contracts may not apply.
我可以在现有合同未覆盖的情况下自行其是。特别是，新技术可能带来未知领域，现有的道德合同可能不适用。

Character-based ethics (sometimes called virtue ethics), which was promoted by Plato and Aristotle, argues that "good behavior" is not the result of applying identifiable rules but instead is a natural consequence of "good character." Whereas consequence-based ethics, duty-based ethics, and contractbased ethics propose that a person resolve an ethical dilemma by asking, "What are the consequences?"; "What are my duties?"; or "What contracts do I have?" character-based ethics proposes that dilemmas be resolved by asking, "Who do I want to be?" Thus, good behavior is obtained by building good character, which is typically the result of sound upbringing and the development of virtuous habits.
基于品德的伦理学（有时称为德性伦理学），由柏拉图和亚里士多德推崇，认为“良好行为”不是应用可识别规则的结果，而是“良好品格”的自然结果。相比之下，基于后果的伦理学、基于职责的伦理学和基于契约的伦理学提出，一个人应该通过问自己“后果是什么？”、“我的职责是什么？”或“我有哪些契约？”来解决伦理困境，而基于品德的伦理学则提出，困境应该通过问自己“我想成为谁？”来解决。因此，良好行为是通过培养良好品格获得的，这通常是良好教养和培养美德习惯的结果。

It is character-based ethics that underlies the approach normally taken when "teaching" ethics to professionals in various fields.
通常在向各个领域的专业人士“教授”伦理时，基于角色的伦理观是其所依据的方法的基础。
Rather than presenting specific ethical theories, the approach is to introduce case studies that expose a variety of ethical questions in the professionals' area of expertise.
与其提出具体的伦理理论，不如通过介绍案例研究来展示专业领域中的各种伦理问题。
Then, by discussing the pros and cons in these cases, the professionals become more aware, insightful, and sensitive to the perils lurking in their professional lives and thus grow in character.
随后，通过讨论这些案例中的利弊，专业人士变得更加意识到、洞察力更强，并对潜伏在他们职业生活中的危险变得更加敏感，从而在性格上得到成长。
This is the spirit in which the questions regarding social issues at the end of each chapter are presented.
这是每章末尾关于社会问题提出的方式。