算法与数据结构：计算的科学

摘自：《Algorithms and Data Structures: The Science of Computing 》by Douglas Baldwin and Greg W. Scragg
刘建文略译（http://blog.csdn.net/keminlau ）

Charles River Media © 2004 (640 pages)

ISBN:1584502509

Back Cover

While many computer science textbooks are confined to teaching programming code and languages, Algorithms and Data Structures: The Science of Computing takes a step back to introduce and explore algorithms -- the content of the code. Focusing on three core topics: design (the architecture of algorithms), theory (mathematical modeling and analysis), and the scientific method (experimental confirmation of theoretical results), the book helps students see that computer science is about problem solving, not simply the memorization and recitation of languages. Unlike many other texts, the methods of inquiry are explained in an integrated manner so students can see explicitly how they interact. Recursion and object oriented programming are emphasized as the main control structure and abstraction mechanism, respectively, in algorithm design.

很多计算机科学教科书都一开始就讲授（并且只局限于讲授）如何用编程语言编写代码，这是不够的。本书的作为知识的补充，退一步，讲讲代码的实质——算法。 本书集中论述三个主题：设计（算法的架构）、理论（数学模型和分析）和科学方法（理论成果的实证）。本书提醒同学们计算机科学是关于问题解决的科学，而不 是简单的对某种编程语言的死记硬背。
另外，本书还特意对质询方法（methods of inquiry）进行系统全面的解释，让同学们注意质询方法的区别与工作原理。递归和面向对象编程分别是讨论算法设计时重点的[控制结构 ]和[抽象机制 ]。

Preface

Algorithms and Data Structures: The Science of Computing (which we usually refer to simply as The Science of Computing) is about understanding computation. We see it as a distinct departure from previous second-course computer science texts, which emphasize building computations. The Science of Computing develops understanding by coupling algorithm design to mathematical and experimental techniques for modeling and observing algorithms' behavior. Its attention to rigorous scientific experimentation particularly distinguishes it from other computing texts. The Science of Computing introduces students to computer science's three core methods of inquiry: design, mathematical theory, and the scientific method. It introduces these methods early in the curriculum, so that students can use them throughout their studies. The book uses a strongly hands-on approach to demonstrate the importance of, and interactions between, all three methods.

本书的主要目标是理解什么是计算，而不像其它图书集中关注如何构建计算。为了达到理解计算的本质，本书耦合（coupling）算法设计与数学方法和实验 技术，对算法行为进行捕捉和建模。与一般的教材不一样，本书特别注重学术的严谨性。本书给同学们介绍计算机科学中三个核心研究方法：设计、数学理论和科学 方法。这三个研究方法将用于同学的整个学业，所以越早熟悉越有裨益。

ORGANIZATION OF THIS BOOK

The Science of Computing has four Parts. The titles of those parts, while descriptive, can be misleading if considered out of context. All three methods of inquiry are addressed in every part, but the emphasis shifts as students mature.

本书分为四部分，如果不考虑上下文，光看每部分的标题会有被误导的可能。那三大研究方法会出现在每一部分，只不过会越来越深入。

For example, Part I: The Science of Computing's Three Methods of Inquiry has four chapters, the first of which is an introduction to the text in the usual form. It is in that chapter that we introduce the first surprise of the course: that the obvious algorithm may not be the best. The other three chapters serve to highlight the three methods of inquiry used throughout this text. These chapters are the only place where the topics are segregated-all subsequent chapters integrate topics from each of the methods of inquiry.

比如，第一个部分--计算机科学的三种研究方法--有四章，第一章是一般的简介，而在这一章我们引入第一个让人震惊的事实，就是备受推崇的算法常常都不是最佳的。余下的三章分别讲述那三种研究方法。这三章也本书中唯一独立地分别讲述三种研究方法，接下来的章节都结合这三种研究方法进行讲述。

The central theme of Part II: Program Design is indeed the design of programs. It reviews standard control structures, but treats each as a design tool for solving certain kinds of problems, with mathematical techniques for reasoning about its correctness and performance, and experimental techniques for confirming the mathematical results. Recursion and related mathematics (induction and recurrence relations) are the heart of this part of the book.

第二部分的主轴程序的设计。本部分复述了一些常用的控制结构，不过我们把这些控制结构看成处理一种特定类型问题的工具对待，并用数学知识推理它的正确性与效率，用实践技术验证这些数学结论。递归和相关数学知识（归纳和递推关系）是这部分的核心内容。

Armed with these tools, students are ready for Part III: Data Structures (the central topic of many CS 2 texts). The tools related to algorithm analysis and to recursion, specifically, can be applied directly to the development of recursively defined data structures, including trees, lists, stacks, queues, hash tables, and priority queues. We present these structures in a manner that continues the themes of Parts I and II: lists as an example of how ideas of repetition and recursion (and related analytic techniques) can be applied to structuring data just as they structured control; stacks and queues as adaptations of the list structure to special applications; trees as structures that improve theoretical and empirical performance; and hash tables and priority queues as case studies in generalizing the previous ideas and applying them to new problems.

有了以上的工具的武装，同学们可以开始下一部分--第三部分：数据结构。与算法分析相关，特别地与递归相关的工具（知识）可直接用来创建递归定义的数据结构，包括树、列表、栈、队列、散列表和优先队列。我们以承接第一二部分的主题的方式继续讲述这些数据结构：就像流程控制可被结构化一样，数据也可以被结构化；列表就是一种如何利用重复和循环递归的思想（和相关的分析技术）结构化数据的例子；栈和队列是为特殊应用而调整的列表结构；（有层次的结构）树在理论上和实践上可提高（算法的）性能；而散列表和优先队列则是一般化前面的思想（KEMIN:就是数据可结构化并根具体问题作相应的调整）并应用到新问题的一个很好的案例。

Finally, Part IV: The Limits of Computer Science takes students through material that might normally be reserved for later theory courses, using the insights that students have developed for both algorithms and data structures to understand just how big some problems are and the recognition that faster computers will not solve all problems.

最后，第四部分--计算机科学的极限--将带给同学们一些一般保留给后续理论课的材料，目的为了掌握数据结构和算法的同学们能够理解有一些问题的难度到底有多大，并且意识到即便是高性能计算机也不能解决所有问题。

Part I: The Science of Computing's Three Methods of Inquiry

CHAPTER LIST
Chapter 1: What is the Science of Computing? 什么是计算科学？
Chapter 2: Abstraction: An Introduction to Design
Chapter 3: Proof: An Introduction to Theory
Chapter 4: Experimentation: An Introduction to the Scientific Method
Does it strike you that there's a certain self-contradiction in the term "computer science"? "Computer" refers to a kind of man-made machine; "science" suggests discovering rules that describe how some part of the universe works. "Computer science" should therefore be the discovery of rules that describe how computers work. But if computers are machines, surely the rules that determine how they work are already understood by the people who make them. What's left for computer science to discover?

你有否觉得“计算机科学”这个词有点自相矛盾的呢？“计算机”指一种人造机器；而“科学”是指发掘宇宙间事物的运动规律。从而“计算机科学”则是发掘计算 机的运动规律了。但是如果计算机是一台可运行的机器，那么人们在制造它的时候不是已经掌握了它的运动规律了吗，还有什么东西留给计算机科学发掘？

The problem with the phrase "computer science" is its use of the word "computer." "Computer" science isn't the study of computers; it's the study of computing, in other words, the study of processes for mechanically solving problems. The phrase "science of computing" emphasizes this concern with general computing processes instead of with machines.[1] [1]In fact, many parts of the world outside the United States call the field "informatics," because it is more concerned with information and information processing than with machines.

“计算机科学”的问题出在“计算机”上。“计算机”科学不是研究计算机，而是研究计算（computing），换句话说，是研究机械地（自动地）解决问题的过程。因此，“计算的科学”比机器的科学更中肯。很多国家干脆叫这一领域为信息科学，用信息科学或信息处理也比机器来得中肯。

The first four chapters of this book explain the idea of "processes" that solve problems and introduce the methods of inquiry with which computer scientists study those processes. These methods of inquiry include designing the processes, mathematically modeling how the processes should behave, and experimentally verifying that the processes behave in practice as they should in theory.

Part III: Introduction to Data Structures

CHAPTER LIST
Chapter 11: Lists
Chapter 12: Queues and Stacks
Chapter 13: Binary Trees
Chapter 14: Case Studies in Design: Abstracting Indirection
The emphasis of the first half of this text has been on actions (methods or algorithms): types of actions, defining new actions, predicting results, and evaluating actions. But the objects manipulated by algorithms can be quite interesting in their own right. In fact some algorithms all but require new perspectives on the nature of objects. This section expands the concept of object and investigates the implications of that expansion on the algorithms that manipulate them.

本书的前半部分集中关注“动作”（actions 方法或算法）：动作的类型、定义新动作、对结果预测和对动作进行评估。但是算法所操作的数据对象本身也有着很有趣的性质或规则…………本部分将展开（算法所操作的）数据对象的概念（KEMIN：一个概念的定义常常使用间接概念来定义，而当读者对间接概念仍不了解的时候必须进一步对间接概念进行释义。释义就是这里的展开吧），并研究这些被展开的概念在算法中的含意。

Thus far, objects have been viewed as fixed entities, fully specified by their class. The internal structure of an object does not change over time. A robot can't grow a new wheel, develop a new color palette, or rearrange its internal components. But some problems do require such references to or manipulation of the relationship of an object's subparts to each other or to the object as a whole. Part III describes techniques that enable an object to change in important ways. The resulting object classes with internally addressable structures are called data structures: subparts can be added, removed, reordered, or queried. The three methods of inquiry developed in Parts I and II continue to provide the cornerstone of the investigation, but the four chapters of Part III also add to that collection of tools to describe four classes of data structures and conclude by using those tools in new situations, developing new problem solutions.

到目前为止，数据对象被看成一个固定的整体，全由其类型指定。数据对象的内部结构不会改变。不过有一些问题确实需要访问和操控数据对象内部各子对象…………本部分就是讲述操控数据对象内部各子对象技术。这种内部分可访问的新数据对象被叫作数据结构：内部对象可添加、删除、重组和查询。