《算机科学的基本概念.ppt》由会员分享，可在线阅读，更多相关《算机科学的基本概念.ppt（51页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第二章第二章 计算机科学的基本概念和基本知识计算机科学的基本概念和基本知识2.1 2.1 计算模型与二进制计算模型与二进制 数学不等于计算，但数学确实起源于对计算的研究。数学不等于计算，但数学确实起源于对计算的研究。数学、计算模型（计算方法、数学机器）、形式化与形数学、计算模型（计算方法、数学机器）、形式化与形式化方法式化方法 我们说，形式是事物的内容存在的外在方式、形状和结我们说，形式是事物的内容存在的外在方式、形状和结构的总和。所谓形式化是将事物的内容与形式相分离，用事构的总和。所谓形式化是将事物的内容与形式相分离，用事物的某种形式来表示事物。形式化方法是在对事物描述形式物的某种形式来表示
2、事物。形式化方法是在对事物描述形式化的基础上，通过研究事物的形式变化规律来研究事物变化化的基础上，通过研究事物的形式变化规律来研究事物变化规律的全体方法的总称。规律的全体方法的总称。1.1.1 1.1.1 计算模型与图灵机计算模型与图灵机 所谓计算模型是刻划计算这一概念的一种抽象的形式系所谓计算模型是刻划计算这一概念的一种抽象的形式系统或数学系统，而算法是对计算过程步骤（或状态的一种刻统或数学系统，而算法是对计算过程步骤（或状态的一种刻划，是计算方法的一种能行实现方式。在计算机科学中，我划，是计算方法的一种能行实现方式。在计算机科学中，我们通常所说的计算模型，并不是指在其静态或动态数学描述们通
3、常所说的计算模型，并不是指在其静态或动态数学描述基础上建立求解某一基础上建立求解某一(类类)问题计算方法的数学模型，而是指问题计算方法的数学模型，而是指具有状态转换特征，能够对所处理的对象的数据或信息进行具有状态转换特征，能够对所处理的对象的数据或信息进行表示、加工、变换、输出的数学机器。由于观察计算的角度表示、加工、变换、输出的数学机器。由于观察计算的角度不同，产生了各种不同的计算模型。不同，产生了各种不同的计算模型。递归函数、递归函数、TuringTuring机等机等 (1)s(x)(1)s(x)x x1 1 （后继函数）后继函数）(2)o(x)(2)o(x)0 0 （零函数）零函数）(3
4、)U(3)Uj j(n)(n)(x(x1 1，x x2 2，x xn n)x xj j （射影函数）射影函数）由由初初始始函函数数和和有有限限次次使使用用算算子子可可以以构构造造各各种种复复杂杂的的递递归归函数，或者可计算函数。函数，或者可计算函数。图灵机的示意图图灵机的示意图控制器的命令可表示为：控制器的命令可表示为：（状态，符号）（状态，符号）（写符号，移动，状态）；（写符号，移动，状态）；控制器控制器 一旦图灵机在运行中进入了一个状态，而且这个状态一旦图灵机在运行中进入了一个状态，而且这个状态是一个结束状态，那么，图灵机就停机，计算任务宣告完是一个结束状态，那么，图灵机就停机，计算任务宣
5、告完成，此时带上的内容就是计算的输出结果。成，此时带上的内容就是计算的输出结果。例例1 1 M M的的字字母母表表A A00，1 1，bb，b b表表示示空空格格。状状态态集集Q Qqq1 1，q q2 2，q q3 3，其中，指定其中，指定q q1 1是开始状态，是开始状态，q q3 3是终止状态。是终止状态。M M的程序（控制器的命令）如下：的程序（控制器的命令）如下：q q1 1 0 1 R q 0 1 R q1 1；q q1 1 1 0 R q 1 0 R q1 1；q q1 1 b b R q b b R q2 2；q q2 2 b b L q b b L q3 3；q q2 2 0
6、 0 H q 0 0 H q1 1；q q2 2 1 1 H q 1 1 H q1 1；对图灵机的工作过程从不同的角度考察，可以给予不对图灵机的工作过程从不同的角度考察，可以给予不同的解释。同的解释。第一第一，把图灵机看作识别器，即判断带子上最初的内，把图灵机看作识别器，即判断带子上最初的内容能否被图灵机所接受。假定图灵机从左向右扫描完带子上容能否被图灵机所接受。假定图灵机从左向右扫描完带子上的内容后停机则为接受，否则为不接受。的内容后停机则为接受，否则为不接受。例例2 2 一台图灵机可以设计成识别下面的序列：一台图灵机可以设计成识别下面的序列：1000110,10011101,0101010
7、111000110,10011101,010101011。第第二二，把把图图灵灵机机看看作作生生成成器器，对对给给定定的的输输入入集集合合，考考察察输输出出集集合合，并并研研究究输输入入输输出出集集合合性性质质之之间间的的关关系系，这这就就研研究究了图灵机的生成能力。了图灵机的生成能力。例例3 3 设设一一台台图图灵灵机机的的输输入入集集合合为为InIn11n n0 0n nnNnN，可可设设计计一一台台图图灵灵机机，对对给给定定的的输输入入集集合合InIn，得得到到输输出出集集合合OutOut00n n1 1n nnNnN。其中，其中，N N是全体自然数的集合。是全体自然数的集合。第第三三，
8、把把图图灵灵机机看看作作计计算算器器，相相当当于于一一个个函函数数。图图灵灵机机的输入是函数的自变量的值，图灵机的输出是函数的值。的输入是函数的自变量的值，图灵机的输出是函数的值。例例4 4 图灵机可以计算下列函数：图灵机可以计算下列函数：(1)s(x)(1)s(x)x x1 1；(2)o(x)(2)o(x)0 0；(3)A(0(3)A(0，y)y)y y1 1，A(xA(x1 1，0)0)A(xA(x，1)1)，A(xA(x1 1，y y1)1)A(xA(x，A(xA(x1 1，y)y)。第一和第二个函数读者不难从图灵机的定义出发感悟第一和第二个函数读者不难从图灵机的定义出发感悟到它们是图灵
9、机可以计算的函数，而第三个函数就比较复到它们是图灵机可以计算的函数，而第三个函数就比较复杂，一时难于判断。顺便提一下，第三个函数叫做阿克曼杂，一时难于判断。顺便提一下，第三个函数叫做阿克曼函数，它是阿克曼（函数，它是阿克曼（W.AckermannW.Ackermann）在研究原始递归函数和在研究原始递归函数和递归函数的关系时给出的。这个函数在计算理论中具有重递归函数的关系时给出的。这个函数在计算理论中具有重要价值。事实上，图灵机还可以计算形式上比第三个函数要价值。事实上，图灵机还可以计算形式上比第三个函数更复杂的函数。更复杂的函数。沿着这样一种思路，图灵机被证明具有很强的计算能沿着这样一种思路
10、，图灵机被证明具有很强的计算能力，它与力，它与3030年代发展的递归函数论（一种能行可计算性理年代发展的递归函数论（一种能行可计算性理论）中一类最一般的可计算函数（部分递归函数或部分可论）中一类最一般的可计算函数（部分递归函数或部分可计算函数）在计算表达能力上是等价的。然而，图灵机简计算函数）在计算表达能力上是等价的。然而，图灵机简洁的构造和运行原理隐含了存储程序的原始思想，深刻地洁的构造和运行原理隐含了存储程序的原始思想，深刻地揭示了现代通用电子数字计算机最核心的内容。揭示了现代通用电子数字计算机最核心的内容。图灵奖图灵奖 2.1.2 2.1.2 二进制二进制 也许是图灵机读写带上只出现两个
11、符号启发了研究者，也许是图灵机读写带上只出现两个符号启发了研究者，在当时的技术条件下，从便于元器件的设计和制造考虑，在当时的技术条件下，从便于元器件的设计和制造考虑，计算机的研制很自然地选择了二进制。后来的实践也证明计算机的研制很自然地选择了二进制。后来的实践也证明了这种选择具有极大的优点。了这种选择具有极大的优点。十进制数的表示十进制数的表示 例如，例如，1997.6301997.630这个数可以写成：这个数可以写成：1997.6301997.6301 110103 39 910102 29 910101 17 710100 0 6 61010-1-13 31010-2-20 01010-3
12、-3 一般地，任何一个十进制数一般地，任何一个十进制数S S都可以表示为：都可以表示为：S Sk kn nk kn-1n-1 k k0 0.k k-m-m k kn n1010n nk kn-1n-11010n-1n-1k k0 010100 0k k-m-m1010-m-m -m -m k ki i1010i i i in n其中，其中，1010称为十进制的基数称为十进制的基数,k,ki i0,1,2,3,4,5,6,7,8,90,1,2,3,4,5,6,7,8,9，m m，n n为正整数。小数点的位置不言自明。为正整数。小数点的位置不言自明。二进制和十进制一样，是一种数制，它用于表示数的符
13、二进制和十进制一样，是一种数制，它用于表示数的符号（数字）由于在书写中的位置不同而具有不同的值。二进号（数字）由于在书写中的位置不同而具有不同的值。二进制表示数的符号只有两个，即制表示数的符号只有两个，即0 0和和1 1，其数值与十进制中的，其数值与十进制中的0 0和和1 1相同。此外，与十进制不同之处在于二进制数是逢二进一。相同。此外，与十进制不同之处在于二进制数是逢二进一。例如，十进制数与二进制数中的一些可作如下对应：例如，十进制数与二进制数中的一些可作如下对应：十进制十进制 二进制二进制 (0)(0)(0)(0)(1)(1)(1)(1)(2)(10)(2)(10)(3)(11)(3)(1
14、1)(4)(100)(4)(100)(5)(101)(5)(101)(9)(1001)(9)(1001)(10)(1010)(10)(1010)一般地，任何一个二进制数一般地，任何一个二进制数S S都可以表示为：都可以表示为：S Sk kn nk kn-1n-1 k k0 0.k k-m-m k kn n2 2n nk kn-1n-12 2n-1n-1k k0 02 20 0k k-m-m2 2-m-m -m -m k ki i2 2i i i in n 其中，其中，2 2称为二进制的基数，称为二进制的基数，k ki i0,1,m,n0,1,m,n为正整数。为正整数。进一步，读者可从十进制数和
15、二进制数的一般表示公进一步，读者可从十进制数和二进制数的一般表示公式得到启发，将这种表示推广到更一般的任意进制，不同式得到启发，将这种表示推广到更一般的任意进制，不同之处只是基数不一样。之处只是基数不一样。二进制的运算规则比十进制的运算规则简单得多。二进制的运算规则比十进制的运算规则简单得多。只只要建立两种进制的数据之间的转换方法，那么，二进制将要建立两种进制的数据之间的转换方法，那么，二进制将具有更多的优势。具有更多的优势。计算机的理论基础是逻辑和代数。当二计算机的理论基础是逻辑和代数。当二进制与同样只使用进制与同样只使用“真真”和和“假假”两个值的逻辑代数建立两个值的逻辑代数建立了联系后，
16、这就为计算机的逻辑设计提供了便利的工具。了联系后，这就为计算机的逻辑设计提供了便利的工具。2.2 2.2 存储程序式计算机的基本结构与工作原理存储程序式计算机的基本结构与工作原理 图灵机的出现为现代计算机的发明提供了重要的思想。图灵机的出现为现代计算机的发明提供了重要的思想。图灵机的带子可以看成是计算机的存储设备，数据可以存图灵机的带子可以看成是计算机的存储设备，数据可以存储在上面，也可以根据需要擦去。图灵机的命令相当于一组储在上面，也可以根据需要擦去。图灵机的命令相当于一组事先设计、存储好了的程序，它们在控制器安排下，决定读事先设计、存储好了的程序，它们在控制器安排下，决定读写头的每一步操作
17、。这样一种数学机器，如果不考虑它的实写头的每一步操作。这样一种数学机器，如果不考虑它的实用性，就思想和原理而言，确实包含了存储程序的重要思想。用性，就思想和原理而言，确实包含了存储程序的重要思想。程序与存储程序式计算机程序与存储程序式计算机 图灵机诞生后不到十年，在以冯图灵机诞生后不到十年，在以冯诺依曼为代表的一批诺依曼为代表的一批科学家的努力下，现代存储程序式电子数字计算机的基本结科学家的努力下，现代存储程序式电子数字计算机的基本结构与工作原理被确定下来。它主要由如下的五部分组成（见构与工作原理被确定下来。它主要由如下的五部分组成（见P8P8图）：图）：存储器，运算器，控制器，输入设备，输出
18、设备存储器，运算器，控制器，输入设备，输出设备 在学科的发展历程中，习惯上，人们将不带有软件系在学科的发展历程中，习惯上，人们将不带有软件系统的存储程序式电子数字计算机系统称为硬件裸机，将硬统的存储程序式电子数字计算机系统称为硬件裸机，将硬件裸机，参与构成硬件裸机的各类部件及其研究范畴统称件裸机，参与构成硬件裸机的各类部件及其研究范畴统称为硬件（方向）。为硬件（方向）。2.3 2.3 数字逻辑与集成电路数字逻辑与集成电路 数数字字逻逻辑辑是是数数字字电电路路逻逻辑辑设设计计的的简简称称，其其内内容容是是应应用用数数字字电电路路进进行行数数字字系系统统逻逻辑辑设设计计。电电子子数数字字计计算算机
19、机是是由由具具有有各各种种逻逻辑辑功功能能的的逻逻辑辑部部件件组组成成的的，这这些些逻逻辑辑部部件件按按其其结结构构可可分分为为组组合合逻逻辑辑电电路路和和时时序序逻逻辑辑电电路路。组组合合逻逻辑辑电电路路是是由由与与门门、或或门门和和非非门门等等门门电电路路组组合合形形成成的的逻逻辑辑电电路路；时时序序逻逻辑辑电电路路是是由由触触发发器器和和门门电电路路组组成成的的具具有有记记忆忆能能力力的的逻逻辑辑电电路路。有有了了组组合合逻逻辑辑电电路路和和时时序序逻逻辑辑电电路路，再再进进行行合合理理的的设设计计和和安安排排，就就可可以以表表示示和和实实现现布布尔尔代代数数的的基基本本运运算算。而而布
20、尔代数只使用布尔代数只使用1 1（真）和（真）和0 0（假）两个数，这样，当二进（假）两个数，这样，当二进制的加法、乘法等运算与布尔代数的运算建立了对应关系制的加法、乘法等运算与布尔代数的运算建立了对应关系后，就可以用逻辑部件来实现二进制数据的加法、乘法等后，就可以用逻辑部件来实现二进制数据的加法、乘法等各种运算。各种运算。例例5 5 基本的基本的“与与”、“或或”、“非非”门电路。门电路。“与与”门电路一般有两个以上的输入和一个输出。图门电路一般有两个以上的输入和一个输出。图(a)(a)表示了一个表示了一个“与与”门电路，其输出门电路，其输出P P和输入和输入A A、B B、C C之间之间的
21、逻辑关系可用下面的式子表示：的逻辑关系可用下面的式子表示：P PABCABC 电路设计中，用高电平信号表示电路设计中，用高电平信号表示1 1，低电平信号表示，低电平信号表示0 0，那么，那么，“与与”门电路只有当输入门电路只有当输入A A、B B、C C同时为同时为1 1时，输时，输出出P P才为才为1 1，否则，否则，P P为为0 0。“或或”门电路可以用图门电路可以用图(b)(b)表示。一般地说，表示。一般地说，“或或”门门电路是一种具有逻辑加法功能的电路，它有两个以上的输电路是一种具有逻辑加法功能的电路，它有两个以上的输入和入和一个输出，其输出一个输出，其输出P P和输入和输入A A、B
22、 B、C C之间的逻辑关系可用下之间的逻辑关系可用下面的式子表示：面的式子表示：P PA AB BC C 在具体的电路设计中，如果我们用高电平信号表示在具体的电路设计中，如果我们用高电平信号表示1 1，低电平信号表示低电平信号表示0 0，那么，那么，“或或”门电路仅当输入门电路仅当输入A A、B B、C C中有一个为中有一个为1 1时，输出时，输出P P就为就为1 1，否则，否则，P P为为0 0。“非非”门电路可以用图门电路可以用图(c)(c)表示。一般地说，表示。一般地说，“非非”门门电路是一种具有逻辑取反功能的电路，它只有一个输入和电路是一种具有逻辑取反功能的电路，它只有一个输入和一个输
23、出，其输出一个输出，其输出P P和输入和输入A A之间的逻辑关系可用下面的式之间的逻辑关系可用下面的式子表示：子表示：P PA A 在具体的电路设计中，如果我们用高电平信号表示在具体的电路设计中，如果我们用高电平信号表示1 1，低电平信号表示低电平信号表示0 0，那么，那么，“非非”门电路当输入门电路当输入A A为为0 0时，输时，输出出P P就为就为1 1，否则，当输入，否则，当输入A A为为1 1时，输出时，输出P P为为0 0。“与与”、“或或”、“非非”三种门电路示意图三种门电路示意图PPPABCABCA （a）（b）（c）将布尔代数和前面谈到的二进制联系起来，我们可以将布尔代数和前面
24、谈到的二进制联系起来，我们可以看出，看出，“与与”、“或或”、“非非”门电路的作用与集合运算门电路的作用与集合运算“交交”、“并并”、“补补”是一致的。一旦门电路中仅使用是一致的。一旦门电路中仅使用两个电平信号两个电平信号0 0和和1 1，引入二进制及其运算规则，那么，用，引入二进制及其运算规则，那么，用门电路及其组门电路及其组合就可以实现二进制的各种运算，而对复杂电路的计算，合就可以实现二进制的各种运算，而对复杂电路的计算，如电路的化简就有可能通过布尔代数的方法进行。事实上如电路的化简就有可能通过布尔代数的方法进行。事实上也正是如此。也正是如此。由此可见，真正构成计算机科学基本的、核心的内容
25、由此可见，真正构成计算机科学基本的、核心的内容是围绕计算而展开的大量带有规律性的知识，而不是具体是围绕计算而展开的大量带有规律性的知识，而不是具体的实现技术。因为，在将来，我们完全可能发展一种能表的实现技术。因为，在将来，我们完全可能发展一种能表示二进制数及其运算的新技术，它比今天的微电子技术精示二进制数及其运算的新技术，它比今天的微电子技术精度更高、生产价格更便宜。如果真是那样，这种技术就可度更高、生产价格更便宜。如果真是那样，这种技术就可能取代微电子技术在计算科学中的地位。近年来科学研究能取代微电子技术在计算科学中的地位。近年来科学研究的发展已显现出一些很有希望但尚不成熟的技术，如光电的发
26、展已显现出一些很有希望但尚不成熟的技术，如光电子技术，金属表面处理技术等。当然，程序技术在可预见子技术，金属表面处理技术等。当然，程序技术在可预见的将来尚不太可能被别的技术所代替，原因是它与各种应的将来尚不太可能被别的技术所代替，原因是它与各种应用相联系，而且在形式上易于反映能行性这一本质的计算用相联系，而且在形式上易于反映能行性这一本质的计算特征，在表达形式上与通常算法的描述较为接近特征，在表达形式上与通常算法的描述较为接近,设计和设计和生产的成本也比较低，又不存在工业污染的问题，所以不生产的成本也比较低，又不存在工业污染的问题，所以不易被取代。因此，我们常说，从这个意义上讲，软件技术易被取
27、代。因此，我们常说，从这个意义上讲，软件技术比微电子技术对计算科学更重要一些。比微电子技术对计算科学更重要一些。2.4 2.4 机器指令与汇编语言机器指令与汇编语言 用用计计算算机机求求解解一一个个问问题题，必必须须事事先先编编制制好好程程序序。程程序序是是由由指指令令组组成成的的。每每一一台台计计算算机机都都设设计计规规定定了了一一组组指指令令集集合，称为机器指令系统。合，称为机器指令系统。机器指令的格式一般分为两部分，如下所示：机器指令的格式一般分为两部分，如下所示：指令格式：指令格式：操作码操作码 地址部分地址部分 其中，操作码指出运算的种类，如，其中，操作码指出运算的种类，如，跳转，跳
28、转等，地址部分用来指示参与运算的数据保存在什么地方，等，地址部分用来指示参与运算的数据保存在什么地方，如存储器的某个地址或某个寄存器等。操作码和地址部分如存储器的某个地址或某个寄存器等。操作码和地址部分都用二进制代码表示。都用二进制代码表示。机器指令一般可根据其功能划分为以下几类：机器指令一般可根据其功能划分为以下几类：(1)(1)控制指令；控制指令；(2)(2)算术运算指令；算术运算指令；(3)(3)逻辑运算指令；逻辑运算指令；(4)(4)移位操作指令；移位操作指令；(5)(5)传送操作指令；传送操作指令；(6)(6)输入输入/输出指令。输出指令。应当注意的是，不同的机器，其指令系统是不同的
29、。应当注意的是，不同的机器，其指令系统是不同的。指令系统的日渐增大虽然给用户的程序设计带来了方便，指令系统的日渐增大虽然给用户的程序设计带来了方便，但也带来了硬件设计复杂性的增加和因译码、存储、寻址等但也带来了硬件设计复杂性的增加和因译码、存储、寻址等开销的增大而使运算速度下降。研究发现，开销的增大而使运算速度下降。研究发现，指令系统存在着指令系统存在着改进的必要和可能。改进的必要和可能。真正使研究人员对指令系统进行较大改进的原因是超大真正使研究人员对指令系统进行较大改进的原因是超大规模集成电路（规模集成电路（VLSIVLSI）技术的发展和采用微程序技术实现体技术的发展和采用微程序技术实现体系
30、结构设计思想的过程中硬件复杂性的不断增长带来的技术系结构设计思想的过程中硬件复杂性的不断增长带来的技术上的困难，使人们开始认识到在进行计算机系统设计时，应上的困难，使人们开始认识到在进行计算机系统设计时，应公平对待硬件与软件的地位，使两者平衡负担整个系统的复公平对待硬件与软件的地位，使两者平衡负担整个系统的复杂性。这一认识的转变直接导致了精简指令系统计算机杂性。这一认识的转变直接导致了精简指令系统计算机（RISCRISC）的诞生。所谓的诞生。所谓RISCRISC是根据指令系统中各种指令应用是根据指令系统中各种指令应用的规律，将最常用的指令，以及一些控制较为简单的寄存器的规律，将最常用的指令，以
31、及一些控制较为简单的寄存器寄存器的操作与寄存器等一起直接做在寄存器的操作与寄存器等一起直接做在VLSIVLSI芯片上，靠减芯片上，靠减少译码、存储、寻址方式和次数等开销而大大增加运算速度。少译码、存储、寻址方式和次数等开销而大大增加运算速度。实际上，实际上，RISCRISC主要是一种体系结构设计的思想，而不只是一主要是一种体系结构设计的思想，而不只是一种计算机产品种计算机产品。RISCRISC技术由于极大地提高了计算机的运算速技术由于极大地提高了计算机的运算速度，因而它的问世被认为是计算机体系结构发展史上的一个度，因而它的问世被认为是计算机体系结构发展史上的一个里程碑。里程碑。汇编语言汇编语言
32、 汇编语言实际上是由一组汇编指令构成的语言。每一条汇编语言实际上是由一组汇编指令构成的语言。每一条汇编指令用某个西文字符串的缩写来表示其所代表的操作，汇编指令用某个西文字符串的缩写来表示其所代表的操作，用符号来代表数据的二进制、八进制和十进制数字序列。大用符号来代表数据的二进制、八进制和十进制数字序列。大多数情况下，一条汇编指令对应一条机器指令，少数对应几多数情况下，一条汇编指令对应一条机器指令，少数对应几条机器指令。例如，下面是几条汇编指令的操作符，右边中条机器指令。例如，下面是几条汇编指令的操作符，右边中文是名称。文是名称。addadd 加法加法 idividiv 有符号除法有符号除法 m
33、ulmul 无符号乘法无符号乘法negneg 求补求补 xchgxchg 交换交换 testtest 逻辑比较逻辑比较 jmpjmp 无条件转移无条件转移 有了汇编语言，就得编写和设计汇编语言翻译程序（简有了汇编语言，就得编写和设计汇编语言翻译程序（简称汇编程序），专门负责把使用汇编语言书写的程序翻译成称汇编程序），专门负责把使用汇编语言书写的程序翻译成可直接执行的机器指令程序。一般说来，汇编程序被看成是可直接执行的机器指令程序。一般说来，汇编程序被看成是系统软件的一部分。系统软件的一部分。当然，汇编语言在可读性和编写程序时仍然是不能令人当然，汇编语言在可读性和编写程序时仍然是不能令人满意的，
34、这导致进一步发展了高级程序设计语言。不过，由满意的，这导致进一步发展了高级程序设计语言。不过，由于高级语言在使用时通常还是要通过编译程序逐步将高级语于高级语言在使用时通常还是要通过编译程序逐步将高级语言写的程序翻译成机器指令的程序，而这种翻译的结果往往言写的程序翻译成机器指令的程序，而这种翻译的结果往往不如机器指令或汇编语言写的程序效率高，所以，直到今天，不如机器指令或汇编语言写的程序效率高，所以，直到今天，不少工程师在系统软件的开发中还在使用机器指令和汇编语不少工程师在系统软件的开发中还在使用机器指令和汇编语言。言。2.5 2.5 算法、过程与程序算法、过程与程序 求解一个给定的问题，不同的
35、人常编写出不同的然而都求解一个给定的问题，不同的人常编写出不同的然而都是正确的程序，这是为什么呢？是正确的程序，这是为什么呢？这里存在两个层面的问题，一个是与计算方法密切相关这里存在两个层面的问题，一个是与计算方法密切相关的算法问题，另一个是程序设计的技术问题。的算法问题，另一个是程序设计的技术问题。例例6 6 给定两个整数，求它们的最大公因数。给定两个整数，求它们的最大公因数。不失一般性，设有不全为不失一般性，设有不全为0 0的整数的整数x x、y y，记，记gcd(xgcd(x，y)y)为为它们的最大公因数，即同时能整除它们的最大公因数，即同时能整除x x、y y的公因数中的最大者。的公因
36、数中的最大者。显然显然，gcd(xgcd(x，y)y)可表示为可表示为 gcd(xgcd(x，y)y)maxz z|xmaxz z|x，z|yz|y 这个问题许多中学生都会解，最常见的有著名的欧几里这个问题许多中学生都会解，最常见的有著名的欧几里德辗转相除计算方法。当然，还有许多种解法。我们首先从德辗转相除计算方法。当然，还有许多种解法。我们首先从函数函数gcd(xgcd(x，y)y)的性质出发来求解。函数的性质出发来求解。函数gcd(xgcd(x，y)y)具有如下具有如下性质：性质：(1)(1)gcd(agcd(a，b)b)gcd(bgcd(b，a)a)(2)(2)gcd(agcd(a，b)
37、b)gcd(agcd(a，b)b)(3)(3)gcd(agcd(a，0)0)|a|a|(4)(4)gcd(agcd(a，b)b)gcd(bgcd(b，a mod b)a mod b)，0a mod b0a mod bb b（欧几里德辗转相除计算方法）欧几里德辗转相除计算方法）根据以上性质，我们可以设计如下算法：根据以上性质，我们可以设计如下算法：算法算法A A（计算函数计算函数gcd(xgcd(x，y)y)）A A1 1.输入输入x x，y y；z z是辅助变量；是辅助变量；A A2 2.重复执行如下操作步骤：重复执行如下操作步骤：(1)(1)若若y y0 0，则输出则输出|x|x|，算法停止
38、算法停止 (2)(2)若若y0y0，则，则zx mod yzx mod y，xyxy，yzyz；有了计算函数有了计算函数gcd(xgcd(x，y)y)的算法，用程序设计语言很容的算法，用程序设计语言很容易写出可在计算机上执行的程序。算法易写出可在计算机上执行的程序。算法A A的核心是利用了函的核心是利用了函数数gcd(xgcd(x，y)y)的上述第四条性质。倘若我们使用的不是第四的上述第四条性质。倘若我们使用的不是第四条性质，那么，算法就会发生改变。条性质，那么，算法就会发生改变。不难想象，不同的求解方法将产生出不同的算法，不不难想象，不同的求解方法将产生出不同的算法，不同的算法将使我们设计出
39、不同的程序，而决定这个程序功同的算法将使我们设计出不同的程序，而决定这个程序功能能的的本本质质是是计计算算方方法法及及其其算算法法。一一般般地地说说，对对不不同同计计算算方方法法过过程程的的抽抽象象描描述述就就产产生生了了相相应应的的不不同同算算法法，但但同同一一算算法法由不同的人来写程序则完全可能设计出差别很大的程序。由不同的人来写程序则完全可能设计出差别很大的程序。凭直觉想象给出的算法往往不是最好的算法。凭直觉想象给出的算法往往不是最好的算法。例例7 7 用程序变换技术设计的计算函数用程序变换技术设计的计算函数gcd(x,ygcd(x,y)的程序的程序 利利用用一一种种叫叫做做程程序序变变
40、换换技技术术的的程程序序设设计计方方法法，可可以以产产生计算函数生计算函数gcd(x,ygcd(x,y)的如下递归过程性程序：的如下递归过程性程序：Procedure Procedure gcd(xgcd(x，y:inty:int，varvar z:intz:int)；begin if xbegin if x0 then z:0 then z:y y；xy&x0 then xy&x0 then gcd(xgcd(x，y yx x，z)z)；x xy&x0 then y&x0 then gcd(ygcd(y，x x，z)z)endifendif end end；显然，这个程序要一眼看出其功能是困
41、难的。实际上，显然，这个程序要一眼看出其功能是困难的。实际上，这个反映辗转相除计算方法程序经过程序变换，形式上已这个反映辗转相除计算方法程序经过程序变换，形式上已发生了很大变化。发生了很大变化。这两个例子进一步引发我们的一些思考：如何确保算这两个例子进一步引发我们的一些思考：如何确保算法和程序的正确性？既然求解同一个问题可以有不同的方法和程序的正确性？既然求解同一个问题可以有不同的方法，不同的算法，不同的程序，那么，怎么来判断算法和法，不同的算法，不同的程序，那么，怎么来判断算法和程序的好坏呢？程序变换是否改变算法呢？程序的好坏呢？程序变换是否改变算法呢？上面两个例子初步表明算法、程序与数学之
42、间存在着上面两个例子初步表明算法、程序与数学之间存在着密切的联系。要解决上面的问题，没有数学和计算科学理密切的联系。要解决上面的问题，没有数学和计算科学理论的支持恐怕不行。多年来大学计算机科学本科教学的实论的支持恐怕不行。多年来大学计算机科学本科教学的实践已反复证明，实际情况正是如此。践已反复证明，实际情况正是如此。在计算机科学研究中，事实上存在在计算机科学研究中，事实上存在一条规律：一条规律：一个问一个问题，当它的描述及其求解方法或求解过程可以用构造性数学题，当它的描述及其求解方法或求解过程可以用构造性数学描述，而且该问题所涉及的论域为有穷，或虽为无穷但存在描述，而且该问题所涉及的论域为有穷
43、，或虽为无穷但存在有穷表示时，那么，这个问题一定能用计算机来求解；有穷表示时，那么，这个问题一定能用计算机来求解；反过来，凡是能用计算机求解的问题，也一定能对该问题的反过来，凡是能用计算机求解的问题，也一定能对该问题的求解过程数学化，而且这种数学化是构造性的。求解过程数学化，而且这种数学化是构造性的。当当一一个个问问题题的的求求解解获获得得了了计计算算方方法法和和算算法法时时，并并不不等等于于万万事事大大吉吉了了。在在许许多多情情况况下下，找找到到求求解解一一个个问问题题的的算算法法只只是是走走完完了了第第一一步步。至至于于现现实实是是否否可可以以计计算算，则则取取决决于于算算法法的的存存在在
44、性性和和计计算算的的复复杂杂性性，即即取取决决于于该该问问题题是是否否存存在在求求解解算算法法，算算法法所所需需要要的的时时间间和和空空间间在在数数量量级级上上能能否否被被接接受受。要要注注意意的的是是，有有的的问问题题虽虽然然存存在在求求解解问问题题的的计计算算方方法法，但但是是，不不存存在在算算法法。原原因因有有两两种种可可能能：一一是是计计算算方方法法可可能能不不是是构构造造性性的的；二二是是虽虽为为构构造造性性的的，但但计计算算方方法法不不能能保保证证计计算算过过程程在在任任何何初初值的情况下都能结束。值的情况下都能结束。算法复杂性算法复杂性 什么是算法的复杂性呢？什么是算法的复杂性呢
45、？使用计算机计算各种问题，需要存储空间、计算时间。使用计算机计算各种问题，需要存储空间、计算时间。不同的算法计算所需要的时间和空间是不同的。所谓算法不同的算法计算所需要的时间和空间是不同的。所谓算法的复杂性就是对算法计算所需要的时间和空间的一种度量。的复杂性就是对算法计算所需要的时间和空间的一种度量。由于不同的计算机千差万别，运算速度和字长可以相差很大，由于不同的计算机千差万别，运算速度和字长可以相差很大，因此，不可能用算法在某一台计算机上计算所需要的实际的因此，不可能用算法在某一台计算机上计算所需要的实际的时间和存储单元（空间）去衡量这个算法的复杂性。那么，时间和存储单元（空间）去衡量这个算
46、法的复杂性。那么，怎样才能准确刻划算法的计算复杂性呢？怎样才能准确刻划算法的计算复杂性呢？引入引入渐近增长率渐近增长率的概念来刻划算法的计算复杂性。渐进的概念来刻划算法的计算复杂性。渐进增长率用复杂性度量函数表示，该函数表示了算法随问题规增长率用复杂性度量函数表示，该函数表示了算法随问题规模大小变化引起的算法中抽象的基本运算执行的次数或存储模大小变化引起的算法中抽象的基本运算执行的次数或存储空间量的变化规律。如某个计算问题当输入规模分别为空间量的变化规律。如某个计算问题当输入规模分别为1 1，2 2，3 3，n n时，经分析算法中抽象的基本运算次数分别为时，经分析算法中抽象的基本运算次数分别为
47、1 1，4 4，9 9，n n2 2，那么，就可以用函数那么，就可以用函数n n2 2来刻划这个算法的来刻划这个算法的时间复杂性，并称这个算法的时间复杂性度量为时间复杂性，并称这个算法的时间复杂性度量为(n(n2 2)级。级。有了复杂性度量函数，一旦选定具体计算机，可以根据这台有了复杂性度量函数，一旦选定具体计算机，可以根据这台计算机对某个计算机对某个n n值的实际运算速度比较准确地估算出对其他值的实际运算速度比较准确地估算出对其他的的n n值完成计算所需要的时间。于是，对各种算法的复杂值完成计算所需要的时间。于是，对各种算法的复杂性进行分析的关键是要设法去找出这样的函数，它涉及到与性进行分析
48、的关键是要设法去找出这样的函数，它涉及到与数学密切相关的算法的设计原理、思想和方法，算法分析是数学密切相关的算法的设计原理、思想和方法，算法分析是具有智力挑战性的研究课题。具有智力挑战性的研究课题。证比求易算法证比求易算法（本书上的三个中国人算法）（本书上的三个中国人算法）在算法计算复杂性的研究中，一个算法如果存在图灵机在算法计算复杂性的研究中，一个算法如果存在图灵机可计算的多项式时间计算复杂性算法，就将这个算法归入可计算的多项式时间计算复杂性算法，就将这个算法归入P P类，如果存在非确定性图灵机可计算的多项式时间计算复杂类，如果存在非确定性图灵机可计算的多项式时间计算复杂性算法，就将其归入性
49、算法，就将其归入NPNP类。对大多数实际问题来说，找到一类。对大多数实际问题来说，找到一个解可能很难，检验一个解常常比较容易，所以都属于个解可能很难，检验一个解常常比较容易，所以都属于NPNP类。类。现在，计算科学研究中一个悬而未决的重要问题是：现在，计算科学研究中一个悬而未决的重要问题是：P PNPNP？。？。P PNPNP？这个问题不仅具有理论上的价值，而且具有重大实这个问题不仅具有理论上的价值，而且具有重大实用价值。因为到目前为止，已经发现了一批可计算但有相当用价值。因为到目前为止，已经发现了一批可计算但有相当难度的问题是属于难度的问题是属于NPNP类的，并且常通过证明一个问题与已知类的
50、，并且常通过证明一个问题与已知属于属于NPNP类中的某个问题（如可满足性问题，简称类中的某个问题（如可满足性问题，简称SATSAT问题）问题）等价将其归入等价将其归入NPNP类。不过，该问题是否属于类。不过，该问题是否属于 P P类，即是否能类，即是否能找到多项式时间计算复杂性算法求解该问题，或证明该问题找到多项式时间计算复杂性算法求解该问题，或证明该问题不存在多项式时间计算复杂性算法求解，至今尚未解决。现不存在多项式时间计算复杂性算法求解，至今尚未解决。现在，很多人都猜测秋碧贞楠的看法是对的：求解一个问题总在，很多人都猜测秋碧贞楠的看法是对的：求解一个问题总是比验证一个问题的解要难，用公式表