|
《计算机科学概论》第8版
进入本专题首页:更多资源免费下载
第0章
导 引
计算机科学是一门这样的学科，它试图为计算机设计、计算机程序设计、信息处理、问题的算法解和算法过程本身等主题建立科学基础。它是当今也是明天的计算机应用基础。其广泛性意味着，我们不可能仅仅通过学习几个孤立的主题或者仅仅通过学习今天的计算工具怎样使用就能成为计算机科学的行家里手。相反，为了理解计算的科学，我们必须尽可能地领悟它所涉及的各种主题的思想及其变化发展。
本书将对那些构成典型的大学计算机科学课程总体的各类主题进行广泛的介绍。因此，本书可以作为学习计算机科学的低年级大学生的学习用书，也可以作为想探究隐藏在当今这个面向计算机的社会背后的科学原理的其他大学生的参考资料。
0.1 算法的作用
我们从计算机科学最基本的概念“算法”开始学习。通俗地说，算法（algorithm）是规定某一任务怎样完成的一组步骤。（在第5章中，我们将作比较精确的定义。）例如，有关于烹调的算法（称为食谱）、在陌生的城市找路的算法（较为通常的说法是找方向）、操作洗衣机的算法（通常写在洗衣机盖的内壁，也许贴在自助式洗衣店的墙上）、演奏音乐的算法（以乐谱形式表示）和表演魔术戏法的算法（见图0.1）。
在一台像计算机那样的机器可以完成一项任务之前，必须找到完成该任务的算法，并以与该机器兼容的方式进行表示。一个算法的表示称为一个程序（program）。为了便于人们读写，计算机程序通常打印在纸上或显示在计算机的屏幕上。为了便于机器识别，程序须以与机器的技术兼容的形式进行编码。开发一个程序，以与机器兼容的形式进行编码并把它们输入到机器中的过程称为程序设计（programming）。程序以及它们所表示的算法总称为软件（software），而机器本身称为硬件（hardware）。
效果：表演者从普通的扑克牌中选取若干张牌，经过充分的洗牌后将牌正面朝下展开在桌面上。然后，当观众要一张红牌或黑牌时，表演者能够翻出相应颜色的牌。 秘诀 步骤1：从普通的扑克牌中选择取10张红牌和10张黑牌。根据颜色把它们分为两叠，扣在桌面上。 步骤2：告诉观众你已经选取了若干张红牌和黑牌。 步骤3：拿起红牌，佯装要把它们整理好，用左手把牌正面朝下拿好，同时用右手的拇指和食指挤压这叠牌的两端，把牌面向下推，使得每张牌呈现向下的弧形。然后，继续把牌扣在桌子上，并声称：“这是其中的红牌。”
步骤4：拿起黑牌，按照第3步的方法，使这些牌呈现向上的弧形。然后，继续把牌扣在桌子上，并声称：“这是其中的黑牌。” 步骤5：当把黑牌放回桌面后，立即用左右手把红牌和黑牌掺和在一起（仍然正面朝下），展开在桌面上。说明你已经洗好了牌。 步骤6：只要桌面上还有扣着的牌，可以重复下面的把戏： （1）请观众要一张红牌或黑牌。 （2）如果所要的牌为红色，而且桌面上存在凹形的牌，就翻开其中的一张，说“这是一张红牌。” （3）如果所要的牌为黑色，而且桌面上存在凸形的牌，就翻开其中的一张，说“这是一张黑牌。” （4）否则说，桌面上没有所要求颜色的牌了，然后翻开桌面上所有的牌，以证实你的断言。 |
图0.1 一个魔术戏法的算法
算法的研究开始时是作为一门数学学科。的确，在今天的计算机研制出之前的很长一段时间里，算法的研究是数学家的重要活动。它的目的是要寻求描述如何解决某一个特定类型的所有问题的一组命令。早期研究中一个最著名的例子是求两个多位数的商的长除算法。另一个例子是求两个正整数的最大公因子的欧几里得算法，它是由古希腊的数学家欧几里得发现的（见图0.2）。
描述：本算法假定它的输入是两个正整数，目的是要计算这两个数的最大公因子。 过程 步骤1：分别给M和N赋以这两个数中较大的一个和较小的一个的值。 步骤2：用M除以N，命余数为R。 步骤3：如果R不为0，那么将N的值赋给M，并将R的值赋给N，回到步骤2；否则最大公因子就是N的当前值。 |
图0.2 求两个正整数的最大公因子的欧几里得算法
?完成一个任务的算法一旦被我们找到，那么在完成该任务时就不再需要了解该算法所依据的原理了。该任务的完成就演变为遵循算法的指示办事的过程。（我们可以依据长除算法找到商或者依据欧几里得算法找到最大公因子，而不需要了解算法为什么是这样的。）在某种程度上说，解决这个问题的智能被编码到这个算法中。
通过算法来得到和转达智能（至少是智能行为），我们能够建造起完成那些有用任务的机器。因此，机器所表现的智能级别受限于算法所转达的智能。仅当我们找到了完成某一任务的算法，我们才可能建造完成该任务的机器。反之，如果我们找不到解决一个问题的算法，那么该问题的解就超出了机器的能力范围。
鉴别算法的能力的局限性作为数学的一个课题来研究，凝聚在库尔特·哥德尔（Kurt Gödel）在20世纪30年代发表的不完备性定理的论文中。这个定理从本质上证明，在任何一个包括传统意义的算术系统的数学理论内，存在既不能证实又不能否认的命题。简言之。对于算法系统的任何彻底研究已经超出了算法活动的能力。
这一现实动摇了数学的基础，算法能力的研究导致了今天被称为计算机科学的学科的产生。的确，算法的研究是计算机科学的核心。
----------------------------------------------
现在，更多的称为计算科学（computing science）。其实，本书的作者在书中使用了计算科学、计算的科学和计算机科学等名称，赋予它们的含义没有什么区别。——译者注
上一节 本专题首页更多资源下载 下一节
