第4部分计算学科中的基概念

1、李陶深李陶深4.1 计算模型与二进制计算模型与二进制4.1.1 计算模型与图灵机计算模型与图灵机计算模型与图灵机计算模型与图灵机o 计算模型：计算模型：n 刻画计算这一概念的一种抽象的形式系统或数学刻画计算这一概念的一种抽象的形式系统或数学系统。系统。计算模型与图灵机计算模型与图灵机o 图灵的观点及结论：图灵的观点及结论：n 凡是能用算法方法解决的问题，也一定能凡是能用算法方法解决的问题，也一定能用图灵机解决；凡是图灵机解决不了的问用图灵机解决；凡是图灵机解决不了的问题，任何算法也解决不了。题，任何算法也解决不了。图灵机图灵机o b b 1 0 1 0 0 0 1 0 b b b 读 写 头

2、控 制 器 状 态 ql 图灵机图灵机o 写在带子上的符号为一个有穷字母表：写在带子上的符号为一个有穷字母表：o 由于由于“0”和和“1”只有形式的意义，因此，也只有形式的意义，因此，也可以将可以将0改称为改称为“白白”，1改称为改称为“黑黑”，甚至，还可以改称为甚至，还可以改称为“桌子桌子”和和“老虎老虎”，这样改称的目的在于割断与直觉的联系，并这样改称的目的在于割断与直觉的联系，并加深对布尔域中的值加深对布尔域中的值真，假真，假，以及二进制，以及二进制机器本质的理解。机器的控制状态表为：机器本质的理解。机器的控制状态表为：o 一个机器计算的结果是从机器停止时带子上的一个机器计算的结果是从机

3、器停止时带子上的信息得到的。容易看出，信息得到的。容易看出，1 1 2 2 2 23 3指令和指令和3 3 3 3 3 31 1指令如果同时出现在机器中，当机器处指令如果同时出现在机器中，当机器处于状态于状态1 1，第一条指令读入的是，第一条指令读入的是2 2，第二条指令，第二条指令读入的是读入的是3 3，那么机器会在两个方块之间无休止，那么机器会在两个方块之间无休止地工作。地工作。o 另外，如果另外，如果3 3 2 2 2 24 4和和3 3 2 2 4 46 6指令同时出现在指令同时出现在机器中，当机器处于状态机器中，当机器处于状态3 3并在带子上扫描到符并在带子上扫描到符号号2 2时，就

4、产生了二义性的问题，机器就无法判时，就产生了二义性的问题，机器就无法判定。定。例子：例子：表示空格，表示空格，1表示机器的初始状态，表示机器的初始状态， 4表示机器的表示机器的结束状态，设带子上的输入信息是结束状态，设带子上的输入信息是10100010，读入头，读入头位对准位对准最右边最右边第一个为第一个为0的方格，状态为初始状态的方格，状态为初始状态1。规则如下：规则如下： b b 1 0 1 0 0 0 1 0 b b b 读 写 头 控 制 器 状 态 ql 计算结果是10100011，即对给定的数加1。 b b 1 0 1 0 0 0 1 0 b b b 读 写 头 控 制 器 状 态

5、 ql 以上命令计算的是这样一个函数：s(x)x1。当没有输入时，即初始状态所指的方格为空格（b）时，不改变空格符，读写头不动并停机。 图灵机的计算能力图灵机的计算能力o 第一第一，把图灵机看作识别器，即判断带子上最，把图灵机看作识别器，即判断带子上最初的内容能否被图灵机所接受。假定图灵机从初的内容能否被图灵机所接受。假定图灵机从左向右扫描完带子上的内容后停机则为接受，左向右扫描完带子上的内容后停机则为接受，否则为不接受。否则为不接受。o 例例2 一台图灵机可以设计成识别下面的序列：一台图灵机可以设计成识别下面的序列： 1000110, 10011101, 010101011。图灵机的计算能力

6、图灵机的计算能力o 第二，第二，把图灵机看作生成器，对给定的输入集把图灵机看作生成器，对给定的输入集合，考察输出集合，并研究输入输出集合性质合，考察输出集合，并研究输入输出集合性质之间的关系，这就研究了图灵机的生成能力。之间的关系，这就研究了图灵机的生成能力。o 例例3 设一台图灵机的输入集合为设一台图灵机的输入集合为in1n0nnn，可设计一台图灵机，对给定的，可设计一台图灵机，对给定的输入集合输入集合in，得到输出集合，得到输出集合out0n1nnn。其中，。其中，n是全体自然数的集合。是全体自然数的集合。图灵机的计算能力图灵机的计算能力o 第三第三，把图灵机看作计算器，相当于一个函数。，

7、把图灵机看作计算器，相当于一个函数。图灵机的输入是函数的自变量的值，图灵机的图灵机的输入是函数的自变量的值，图灵机的输出是函数的值。输出是函数的值。 例例4 图灵机可以计算下列函数：图灵机可以计算下列函数： (1) s(x)x1； (2) o(x)0； (3) a(0，y)y1， a(x1，0)a(x，1)， a(x1，y1)a(x，a(x1，y)。图灵机的计算能力图灵机的计算能力o 第一和第二个函数读者不难从图灵机的定义出第一和第二个函数读者不难从图灵机的定义出发感悟到它们是图灵机可以计算的函数，而第发感悟到它们是图灵机可以计算的函数，而第三个函数就比较复杂，一时难于判断。顺便提三个函数就比

8、较复杂，一时难于判断。顺便提一下，第三个函数叫做一下，第三个函数叫做阿克曼函数阿克曼函数，它是阿克，它是阿克曼（曼（w.ackermann）在研究原始递归函数和）在研究原始递归函数和递归函数的关系时给出的。这个函数在计算理递归函数的关系时给出的。这个函数在计算理论中具有重要价值。论中具有重要价值。o 事实上，图灵机还可以计算形式上比第三个函事实上，图灵机还可以计算形式上比第三个函数更复杂的函数。数更复杂的函数。 图灵机的计算能力图灵机的计算能力o 图灵机可以计算图灵机可以计算4.1 计算模型与二进制计算模型与二进制4.1.2 二进制二进制计算机的数字系统计算机的数字系统o 计算机采用的是二进制

9、数字系统。计算机采用的是二进制数字系统。o 基本符号：基本符号：0 0、1 1o 进位原则：逢二进一进位原则：逢二进一o 优点：优点：n 易于物理实现易于物理实现n 二进制数运算简单二进制数运算简单n 机器可靠性高机器可靠性高n 通用性强通用性强o 缺点：对人来说可读性差缺点：对人来说可读性差十进制数的表示十进制数的表示各位数字与它的权相乘，其积相加。各位数字与它的权相乘，其积相加。例如例如:nn-110-1-m+1-m其中，其中，10称为十进制的基数称为十进制的基数,ki0,1,2,3,4,5,6,7,8 9，m，n为正整数。小数点的位置不言自明。为正整数。小数点的位置不言自明。计算机的数字

10、系统计算机的数字系统o 计算机采用的是二进制数字系统。二进制和十进计算机采用的是二进制数字系统。二进制和十进制一样，是一种数制，它用于表示数的符号（数制一样，是一种数制，它用于表示数的符号（数字）由于在书写中的位置不同而具有不同的值。字）由于在书写中的位置不同而具有不同的值。o 基本符号：基本符号：0 0、1 1o 进位原则：逢二进一进位原则：逢二进一o 优点：优点：n 易于物理实现易于物理实现n 二进制数运算简单二进制数运算简单n 机器可靠性高机器可靠性高n 通用性强通用性强o 缺点：对人来说可读性差缺点：对人来说可读性差二进制数二进制数 sknkn-1 k0. k-m kn2nkn-12n

11、-1k020k-m2-m -m ki2i in 其中，其中，2称为二进制的基数，称为二进制的基数，ki0,1,m,n为正整数。为正整数。 进一步，读者可从十进制数和二进制数的一般表示进一步，读者可从十进制数和二进制数的一般表示公式得到启发，将这种表示推广到更一般的任意进制，公式得到启发，将这种表示推广到更一般的任意进制，不同之处只是基数不一样。不同之处只是基数不一样。 二进制数二进制数 二进制的运算规则比十进制的运算规则简二进制的运算规则比十进制的运算规则简单得多。单得多。只要建立两种进制的数据之间的转换只要建立两种进制的数据之间的转换方法，那么，二进制将具有更多的优势。方法，那么，二进制将具

12、有更多的优势。计算计算机的理论基础是逻辑和代数。当二进制与同样机的理论基础是逻辑和代数。当二进制与同样只使用只使用“真真”和和“假假”两个值的逻辑代数建立两个值的逻辑代数建立了联系后，这就为计算机的逻辑设计提供了便了联系后，这就为计算机的逻辑设计提供了便利的工具。利的工具。不同进位计数制间的转换不同进位计数制间的转换 r 进制进制十进制十进制各位数字与它的权相乘，其积相加。各位数字与它的权相乘，其积相加。例如例如:二进制与十进制间的转换二进制与十进制间的转换 十进制十进制 二进制二进制十进制整数转换成二进制的整数十进制整数转换成二进制的整数二进制与十进制间的转换二进制与十进制间的转换十进制十进

13、制 二进制二进制十进制小数转换成二进制小数十进制小数转换成二进制小数不同进位计数制间的转换不同进位计数制间的转换二、八、十六进制的相互转换二、八、十六进制的相互转换o 每位八进制数相当于三位二进制数每位八进制数相当于三位二进制数o 每位十六进制数相当于四位二进制数每位十六进制数相当于四位二进制数信息的存储单位信息的存储单位o 位位(bit)：度量数据的最小单位，表示一位二：度量数据的最小单位，表示一位二进制信息。进制信息。o 字节字节(byte)：由八位二进制数字组成：由八位二进制数字组成(1 byte = 8 bit)。非数值信息的表示非数值信息的表示o 西文字符：西文字符：n ascii码

14、：用码：用7位二进制数表示一个字符，位二进制数表示一个字符，最多可以表示最多可以表示27=128个字符个字符n ebcdic码：用码：用8位二进制数表示一个字位二进制数表示一个字符，最多可以表示符，最多可以表示28=256个字符个字符4.2 存储程序式计算机的基本存储程序式计算机的基本结构与工作原理结构与工作原理4.2.1 冯冯诺依曼型计算机诺依曼型计算机 冯冯诺依曼型计算机诺依曼型计算机 图灵机的出现为现代计算机的发明提供了图灵机的出现为现代计算机的发明提供了重要的思想。图灵机的带子可以看成是计算机重要的思想。图灵机的带子可以看成是计算机的存储设备，数据可以存储在上面，也可以根的存储设备，数

15、据可以存储在上面，也可以根据需要擦去。图灵机的命令相当于一组事先设据需要擦去。图灵机的命令相当于一组事先设计、存储好了的程序，它们在控制器安排下，计、存储好了的程序，它们在控制器安排下，决定读写头的每一步操作。这样一种数学机器，决定读写头的每一步操作。这样一种数学机器，如果不考虑它的实用性，就思想和原理而言，如果不考虑它的实用性，就思想和原理而言，确实包含了确实包含了存储程序存储程序的重要思想。的重要思想。 冯冯诺依曼型计算机诺依曼型计算机o 计算机程序是指能够在计算机系统中运行的计算机程序是指能够在计算机系统中运行的程序。程序。o 现在的计算机全称为存储程序式通用电子数现在的计算机全称为存储

16、程序式通用电子数字计算机。其含义是：字计算机。其含义是：n 在计算机中各种信息用数字代码表示，如在计算机中各种信息用数字代码表示，如指令、数值型数据、字符、图像等。指令、数值型数据、字符、图像等。n 在物理机制上，数字代码以数字型信号出在物理机制上，数字代码以数字型信号出现。现。 o 信息表示数字化信息表示数字化-理解计算机工作原理的基理解计算机工作原理的基本出发点。本出发点。冯冯诺依曼型计算机诺依曼型计算机o 目前有两种电信号：目前有两种电信号：n 模拟信号：一种在时间上连续的信号，用模拟信号：一种在时间上连续的信号，用信号的某些参数（如幅值）去模拟信息。信号的某些参数（如幅值）去模拟信息。

17、n 数字信号：一种在时间上或空间上不连续数字信号：一种在时间上或空间上不连续（离散）的信号。（离散）的信号。 冯冯诺依曼型计算机诺依曼型计算机o 采用数字化方法表示信息的优点：采用数字化方法表示信息的优点：冯冯诺依曼型计算机诺依曼型计算机 o eniac的结构在很大程度上是依照机电系统的结构在很大程度上是依照机电系统设计的，还存在设计的，还存在重大的线路结构重大的线路结构等问题。等问题。o 在图灵等人工作的影响下，在图灵等人工作的影响下，1946年年6月，美国月，美国杰出的数学家冯杰出的数学家冯诺依曼（诺依曼（von neumann）及）及其同事完成了关于其同事完成了关于“电子计算装置逻辑结构

18、电子计算装置逻辑结构设计设计”的研究报告，的研究报告，n 具体介绍了制造电子计算机和程序设计的具体介绍了制造电子计算机和程序设计的新思想：新思想：存储程序、顺序控制存储程序、顺序控制n 至今为止，大多数计算机采用的仍然是至今为止，大多数计算机采用的仍然是冯冯诺依曼型计算机的组织结构，只是作了诺依曼型计算机的组织结构，只是作了一些改进而已。一些改进而已。因此，冯因此，冯诺依曼被人们誉诺依曼被人们誉为为“计算机器之父计算机器之父”。 冯冯诺依曼型计算机的组织结构诺依曼型计算机的组织结构 存 储 器 运 算 器 控 制 器 输入/输出设备 命令寄存器 输入设备和输出设备输入设备和输出设备输入设备和输

19、出设备o 作用：是将信息输入计算机和输出计算机。作用：是将信息输入计算机和输出计算机。o 常用的文字常用的文字输入设备输入设备是键盘（还有扫描仪、是键盘（还有扫描仪、穿孔卡片读入机和鼠标等专用输入设备）穿孔卡片读入机和鼠标等专用输入设备）n 当在键盘上按下一个键时，按下的键通过当在键盘上按下一个键时，按下的键通过编码变换成机器可读的数据形式，编码变换成机器可读的数据形式，n 如字符如字符“存储器存储器存储器存储器存储器运算器和控制器 register、控制单元、控制单元o 计算机中控制数据操作的电路并不与主存直计算机中控制数据操作的电路并不与主存直接相连接相连n 这些电路被封装在一起，即这些电

20、路被封装在一起，即cpu总线总线o 总线：总线：cpu与主存之间用总线连接，利用总与主存之间用总线连接，利用总线线n cpu通过提供存储单元目标地址以及读信通过提供存储单元目标地址以及读信号来选择、读取数据号来选择、读取数据n cpu通过提供存储单元目标地址以及写信通过提供存储单元目标地址以及写信号来放置、写入信号号来放置、写入信号cpu和主存储器通过总线相连和主存储器通过总线相连4.3 数字逻辑与集成电路数字逻辑与集成电路4.3.1 数字逻辑数字逻辑数字逻辑数字逻辑o 数字逻辑是数字电路逻辑设计的简称，其内数字逻辑是数字电路逻辑设计的简称，其内容是应用数字电路进行数字系统逻辑设计。容是应用数

21、字电路进行数字系统逻辑设计。o 组成计算机的逻辑部件可分为组合逻辑电路组成计算机的逻辑部件可分为组合逻辑电路和时序逻辑电路两种。和时序逻辑电路两种。 门电路门电路o “与与”门电路：两个以上的输入，一个输出。门电路：两个以上的输入，一个输出。仅当所有的输入为仅当所有的输入为1时，输出才为时，输出才为1。 p=a 门电路门电路 “与与”、“或或”、“非非”三种门电路示意图三种门电路示意图 p p p a b c a b c a （a） （b） （c） 4.4 机器指令与汇编语言机器指令与汇编语言4.4.1 机器指令机器指令机器指令o为了实现程序存储的概念，为了实现程序存储的概念，cpucpu要能

22、识要能识别二进制编码的指令别二进制编码的指令o机器语言机器语言指令集合以及编码系统指令集合以及编码系统机器指令机器指令o 用计算机求解一个问题，必须事先编制好程序。程用计算机求解一个问题，必须事先编制好程序。程序是由指令组成的。每一台计算机都设计规定了一序是由指令组成的。每一台计算机都设计规定了一组指令集合，称为机器指令系统。组指令集合，称为机器指令系统。o 机器指令的格式一般分为两部分，如下所示：机器指令的格式一般分为两部分，如下所示： 指令格式：指令格式： 操作码操作码 地址部分地址部分 其中，操作码指出运算的种类，如，其中，操作码指出运算的种类，如，跳转等，地址部分用来指示参与运算的数据

23、保，跳转等，地址部分用来指示参与运算的数据保存在什么地方，如存储器的某个地址或某个寄存器存在什么地方，如存储器的某个地址或某个寄存器等。操作码和地址部分都用二进制代码表示。等。操作码和地址部分都用二进制代码表示。机器指令机器指令o 机器指令一般可根据其功能划分为以下几类：机器指令一般可根据其功能划分为以下几类： (1)(1)控制指令；控制指令；(2)(2)算术运算指令；算术运算指令；(3)(3)逻辑逻辑运算指令；运算指令；(4)(4)移位操作指令；移位操作指令；(5)(5)传送操作传送操作指令；指令；(6)(6)输入输入/ /输出指令。输出指令。o 应当注意的是，不同的机器，其指令系统是应当注

24、意的是，不同的机器，其指令系统是不同的。不同的。o 指令系统的日渐增大虽然给用户的程序设计指令系统的日渐增大虽然给用户的程序设计带来了方便，但也带来了硬件设计复杂性的带来了方便，但也带来了硬件设计复杂性的增加和因译码、存储、寻址等开销的增大而增加和因译码、存储、寻址等开销的增大而使运算速度下降。研究发现，使运算速度下降。研究发现，指令系统存在指令系统存在着改进的必要和可能。着改进的必要和可能。 指令系统指令系统o cpu必须能够解码并执行的机器指令很少必须能够解码并执行的机器指令很少n 一旦计算机可以执行一些基本的而且是精一旦计算机可以执行一些基本的而且是精选的操作，加入额外的操作理论上是不会

25、选的操作，加入额外的操作理论上是不会改变计算机的能力的改变计算机的能力的cisco 最初人们采用的是进一步增强原有指令的功最初人们采用的是进一步增强原有指令的功能，并设置更为复杂的指令的方法能，并设置更为复杂的指令的方法o 采用这种设计思路的计算机被称为复杂指令采用这种设计思路的计算机被称为复杂指令系统计算机（系统计算机（cisco 80%的指令只在的指令只在20%的运行时间里用到；的运行时间里用到；o 一些指令非常繁杂，而执行效率甚至比用几一些指令非常繁杂，而执行效率甚至比用几条简单的基本指令组合的实现还要慢。条简单的基本指令组合的实现还要慢。o 庞杂的指令系统也给超大规模集成电路庞杂的指令

26、系统也给超大规模集成电路（vlsi）的设计带来了困难，）的设计带来了困难，n 它不但不利于设计自动化技术的应用，延它不但不利于设计自动化技术的应用，延长了设计周期，增加了成本，长了设计周期，增加了成本，n 容易增加设计中出现错误的机会，从而降容易增加设计中出现错误的机会，从而降低了系统的可靠性。低了系统的可靠性。 risco 思路主要是通过减少指令总数和简化指令的思路主要是通过减少指令总数和简化指令的功能来降低硬件设计的复杂度，从而提高指功能来降低硬件设计的复杂度，从而提高指令的执行速度。令的执行速度。o 优点优点:与与cisc技术相比技术相比n 简化了指令系统，适合超大规模集成电路简化了指令

27、系统，适合超大规模集成电路的实现；的实现；n 提高了机器执行的速度和效率；提高了机器执行的速度和效率；n 降低了设计成本，提高了系统的可靠性；降低了设计成本，提高了系统的可靠性；n 提供了直接支持高级语言的能力，简化了提供了直接支持高级语言的能力，简化了编译程序的设计。编译程序的设计。机器指令o 机器指令系统每台数字电子计算机在设计中，都规定了一组指令。o 机器语言用机器指令形式编写的程序。o 在裸机级，计算机语言关于算法的描述采用的是实际机器的机器指令，它的符号集是0，1，n 支撑实际机器的理论是图灵机等计算模型；n 在图灵机等计算模型理论的指导下，有关设计形态的主要成果有冯诺依曼型计算机等

28、具体实现思想和技术，以及各类数字电子计算机产品。计算机语言在裸机级所取得的主要成果计算机语言在裸机级所取得的主要成果计算机语言抽象理论设计裸机级的主要内容和成果 语言的符号集为：0，1；用机器指令对算法进行描述图灵机（过程语言的基础）、波斯特系统（字符串处理语言的基础）、-演算（函数式语言的基础）等计算模型冯 诺 依曼型计算机等实现技术；数字电子计算机产品4.4 机器指令与汇编语言机器指令与汇编语言4.4.2 汇编语言汇编语言汇编语言o 汇编语言实际上是由一组汇编指令构成的语汇编语言实际上是由一组汇编指令构成的语言。每一条汇编指令用某个西文字符串的缩言。每一条汇编指令用某个西文字符串的缩写来表

29、示其所代表的操作，用符号来代表数写来表示其所代表的操作，用符号来代表数据的二进制、八进制和十进制数字序列。大据的二进制、八进制和十进制数字序列。大多数情况下，一条汇编指令对应一条机器指多数情况下，一条汇编指令对应一条机器指令，少数对应几条机器指令。例如，下面是令，少数对应几条机器指令。例如，下面是几条汇编指令的操作符，右边中文是名称。几条汇编指令的操作符，右边中文是名称。 addadd 加法加法 idividiv 有符号除法有符号除法 mulmul 无符无符号乘法号乘法 negneg 求补求补 xchgxchg 交换交换 testtest 逻辑比较逻辑比较 jmpjmp 无条件转移无条件转移汇

30、编语言汇编语言o 采用字符和十进制数来代替二进制代码的思采用字符和十进制数来代替二进制代码的思想。想。o 汇编语言语句与特定的机器指令有一一对应汇编语言语句与特定的机器指令有一一对应的关系，但是它毕竟不同于由二进制组成的的关系，但是它毕竟不同于由二进制组成的机器指令，它还需要经汇编程序翻译为机器机器指令，它还需要经汇编程序翻译为机器指令后才能运行。指令后才能运行。o 汇编语言源程序经汇编程序翻译成机器指令，汇编语言源程序经汇编程序翻译成机器指令，再在实际的机器中执行。再在实际的机器中执行。汇编语言o 当然，汇编语言在可读性和编写程序时仍然当然，汇编语言在可读性和编写程序时仍然是不能令人满意的，

31、这导致进一步发展了高是不能令人满意的，这导致进一步发展了高级程序设计语言。不过，由于高级语言在使级程序设计语言。不过，由于高级语言在使用时通常还是要通过编译程序逐步将高级语用时通常还是要通过编译程序逐步将高级语言写的程序翻译成机器指令的程序，而这种言写的程序翻译成机器指令的程序，而这种翻译的结果往往不如机器指令或汇编语言写翻译的结果往往不如机器指令或汇编语言写的程序效率高，所以，直到今天，不少工程的程序效率高，所以，直到今天，不少工程师在系统软件的开发中还在使用机器指令和师在系统软件的开发中还在使用机器指令和汇编语言。汇编语言。4.5 算法、数据结构与程序算法、数据结构与程序 求解一个给定的问

32、题，不同的人常编写求解一个给定的问题，不同的人常编写出不同的然而都是正确的程序，这是为什么出不同的然而都是正确的程序，这是为什么呢？呢？ 这里存在两个层面的问题，一个是与计这里存在两个层面的问题，一个是与计算方法密切相关的算法问题，另一个是程序算方法密切相关的算法问题，另一个是程序设计的技术问题。设计的技术问题。4.5 算法、数据结构与程序算法、数据结构与程序4.5.1 算法算法算法的历史简介算法的历史简介 o 公元公元丢番图方程的可解性问题丢番图方程的可解性问题 o 古希腊数学家丢番图（古希腊数学家丢番图（一个未知数的线性丢番图方程的解一个未知数的线性丢番图方程的解= ，只要，只要 能整除能

33、整除 ，就可判定其有整，就可判定其有整数解，该整数解即数解，该整数解即 / 。两个未知数的线性丢番图方程两个未知数的线性丢番图方程 的解的解+ += = ，先求出，先求出 和和 的最大公因子的最大公因子 ，若，若 能能整除整除 ，则该方程有解（整数解）。，则该方程有解（整数解）。 o 问：方程问：方程1313 +26+26 =52=52有无整数解？有无整数解？n 答：答：1313和和2626的最大公因子是的最大公因子是1313，1313又可整又可整除除5252，故该方程有整数解（如，故该方程有整数解（如 =2=2， =1=1即即方程的解）。方程的解）。两个未知数的线性丢番图方程两个未知数的线性

34、丢番图方程 的解：的解：欧几里德算法欧几里德算法 o 给定两个正整数给定两个正整数例例4.3 算法如下算法如下o 不难想象，不同的求解方法将产生出不同的不难想象，不同的求解方法将产生出不同的算法，不同的算法将使我们设计出不同的程算法，不同的算法将使我们设计出不同的程序，而决定这个程序功能的本质是计算方法序，而决定这个程序功能的本质是计算方法及其算法。一般地说，对不同计算方法过程及其算法。一般地说，对不同计算方法过程的抽象描述就产生了相应的不同算法，但同的抽象描述就产生了相应的不同算法，但同一算法由不同的人来写程序则完全可能设计一算法由不同的人来写程序则完全可能设计出差别很大的程序。出差别很大的

35、程序。o 凭直觉想象给出的算法往往不是最好的算法。凭直觉想象给出的算法往往不是最好的算法。算法的定义和特征算法的定义和特征 算法算法被认为是计算科学的核心问题之一。被认为是计算科学的核心问题之一。 1o 定风定风1 1：给定问题和设备，一个算法是用该设备可：给定问题和设备，一个算法是用该设备可理解的语言表示的，解决这个问题的一种方法的精理解的语言表示的，解决这个问题的一种方法的精确刻划。特别，算法具有下列特征属性：确刻划。特别，算法具有下列特征属性： (1) (1) 算法应用于一个具体的输入集合或问题描述算法应用于一个具体的输入集合或问题描述将在有穷步动作序列之后得到结果；将在有穷步动作序列之

36、后得到结果； (2) (2) 该序列有一个唯一的初始动作；该序列有一个唯一的初始动作； (3) (3) 该序列中的每一个动作有一个唯一的后继动该序列中的每一个动作有一个唯一的后继动作；作； (4) (4) 该序列终止时或者得到这个问题的解，或者该序列终止时或者得到这个问题的解，或者因该问题不可解而获得不可解说明。因该问题不可解而获得不可解说明。1o 定风定风1 1：给定问题和设备，一个算法是用该设备可：给定问题和设备，一个算法是用该设备可理解的语言表示的，解决这个问题的一种方法的精理解的语言表示的，解决这个问题的一种方法的精确刻划。特别，算法具有下列特征属性：确刻划。特别，算法具有下列特征属性

37、： (1) (1) 算法应用于一个具体的输入集合或问题描述算法应用于一个具体的输入集合或问题描述将在有穷步动作序列之后得到结果；将在有穷步动作序列之后得到结果； (2) (2) 该序列有一个唯一的初始动作；该序列有一个唯一的初始动作； (3) (3) 该序列中的每一个动作有一个唯一的后继动该序列中的每一个动作有一个唯一的后继动作；作； (4) (4) 该序列终止时或者得到这个问题的解，或者该序列终止时或者得到这个问题的解，或者因该问题不可解而获得不可解说明。因该问题不可解而获得不可解说明。定义定义2（knuth算法定义）算法定义） 一个算法，就是一个有穷规则的集合，其中之规则一个算法，就是一个

38、有穷规则的集合，其中之规则确定了一个解决某一特定类型问题的运算序列。此外，确定了一个解决某一特定类型问题的运算序列。此外，算法的规则序列须满足如下五个重要条件（特性）：算法的规则序列须满足如下五个重要条件（特性）： (1) (1) 有穷性。算法必须总是在执行有穷步之后结束；有穷性。算法必须总是在执行有穷步之后结束； (2) (2) 确定性。算法的每一个步骤必须是确切地定义确定性。算法的每一个步骤必须是确切地定义的；的； (3) (3) 输入。算法有零个或多个输入；输入。算法有零个或多个输入； (4) (4) 输出。算法有一个或多个输出，即与输入有某输出。算法有一个或多个输出，即与输入有某个特定

39、关系的量；个特定关系的量； (5) (5) 能行性。算法中有待执行的运算和操作必须是能行性。算法中有待执行的运算和操作必须是相当基本的，即是说，它们原则上都是能够精确地进行相当基本的，即是说，它们原则上都是能够精确地进行的，而且用笔和纸做有穷次就可以完成。的，而且用笔和纸做有穷次就可以完成。2o 有穷性：一个算法在执行有穷步之后必须有穷性：一个算法在执行有穷步之后必须结束。结束。 如在欧几里德算法中，由于如在欧几里德算法中，由于m和和n均为均为正整数，在步骤（正整数，在步骤（1）之后，）之后，r必小于必小于n，若，若r0，下一次进行步骤（，下一次进行步骤（1）时，）时，n的值已经的值已经减小，

40、而正整数的递降序列最后必然要终减小，而正整数的递降序列最后必然要终止。因此，无论给定止。因此，无论给定m和和n的原始值有多大，的原始值有多大，步骤（步骤（1）的执行都是有穷次。）的执行都是有穷次。2o 确定性：算法的每一个步骤必须要确切地定义。确定性：算法的每一个步骤必须要确切地定义。即算法中所有有待执行的动作必须严格而不含即算法中所有有待执行的动作必须严格而不含混地进行规定，不能有歧义性。混地进行规定，不能有歧义性。 如欧几里德算法中，步骤（如欧几里德算法中，步骤（1）中明确规）中明确规定定“以以n除除m”，而不能有类似，而不能有类似“以以n除除m或以或以m除除n”这类有两种可能做法的规定。

41、这类有两种可能做法的规定。o 输入：算法有零个或多个的输入，即在算法开输入：算法有零个或多个的输入，即在算法开始之前，对算法最初给出的量。始之前，对算法最初给出的量。 如欧几里德算法中，有两个输入，即如欧几里德算法中，有两个输入，即m和和n。2o 输出：算法有一个或多个的输出，即与输入有输出：算法有一个或多个的输出，即与输入有某个特定关系的量，简单地说就是算法的最终某个特定关系的量，简单地说就是算法的最终结果。结果。 如在欧几里德算法中只有一个输出，即步如在欧几里德算法中只有一个输出，即步骤（骤（2）中的）中的n。o 能行性：算法中有待执行的运算和操作必须是能行性：算法中有待执行的运算和操作必

42、须是相当基本的。相当基本的。 如：欧几里德算法最终得出正确的结果。如：欧几里德算法最终得出正确的结果。 2o 输出：算法有一个或多个的输出，即与输入有输出：算法有一个或多个的输出，即与输入有某个特定关系的量，简单地说就是算法的最终某个特定关系的量，简单地说就是算法的最终结果。结果。 如在欧几里德算法中只有一个输出，即步如在欧几里德算法中只有一个输出，即步骤（骤（2）中的）中的n。o 能行性：算法中有待执行的运算和操作必须是能行性：算法中有待执行的运算和操作必须是相当基本的。相当基本的。 如：欧几里德算法最终得出正确的结果。如：欧几里德算法最终得出正确的结果。 2o 有穷性和能行性是算法最重要的

43、两个特征。对有穷性和能行性是算法最重要的两个特征。对有些问题来说，如果我们给出了一个类似于算有些问题来说，如果我们给出了一个类似于算法的有穷运算序列，而它对某些输入可能不停法的有穷运算序列，而它对某些输入可能不停机，那么，我们就称这样的运算序列为一个过机，那么，我们就称这样的运算序列为一个过程。算法和过程都满足能行性和确定性，唯一程。算法和过程都满足能行性和确定性，唯一的本质区别是算法的执行必须终止，而过程则的本质区别是算法的执行必须终止，而过程则不然，它可以永不停止。需要指出的是，高级不然，它可以永不停止。需要指出的是，高级程序设计语言中也有过程的概念，但与这里所程序设计语言中也有过程的概念

44、，但与这里所讲的过程不同，那里实际上指的是一种子程序。讲的过程不同，那里实际上指的是一种子程序。 3算法是一个四元组，即（算法是一个四元组，即（算法实例算法实例 例例设变量设变量例例4.5 设变量设变量nhn1312111 例例0 0，1 1，1 1，2 2，3 3，5 5，8 8，1313，2121，3434， （1 1）o 在序列（在序列（o 设变量设变量算法设计算法设计（算法的表示方法算法的表示方法原语原语o 一个算法的表达需要使用一些语言形式一个算法的表达需要使用一些语言形式n 自然语言自然语言“visiting grandchildren can be nerve-racking”,

45、可能即意味着孙子孙女导致了可能即意味着孙子孙女导致了很多问题，也表示去看他们可能会有问题很多问题，也表示去看他们可能会有问题n 图形语言：很少人能够根据折纸图给出的步图形语言：很少人能够根据折纸图给出的步骤成功地叠出一只鸟来，但一个专门学习过骤成功地叠出一只鸟来，但一个专门学习过折纸的学生可以轻松完成折纸的学生可以轻松完成o 当用来描述算法的语言并没有被准确定义或者当用来描述算法的语言并没有被准确定义或者没有给予足够信息的时候，交流就会产生问题没有给予足够信息的时候，交流就会产生问题原语原语o 通过建立一个可以描述算法的意义明确的基通过建立一个可以描述算法的意义明确的基本块（本块（原语原语）集

46、合，计算机科学即就可以解）集合，计算机科学即就可以解决上述的勾通问题决上述的勾通问题o 原语描述算法需要建立一个统一的细节描述原语描述算法需要建立一个统一的细节描述级别，原语连同一组表达了原语如何表达复级别，原语连同一组表达了原语如何表达复杂的想法的规定组成了一种程序设计语言杂的想法的规定组成了一种程序设计语言o 组成组成1o 缺点缺点2流程图流程图o 它 采 用 美 国 国 家 标 准 化 协 会它 采 用 美 国 国 家 标 准 化 协 会（1）求解例）求解例4.4的算法流程图的算法流程图 x=1 y=2 x=x+y y=y+1 y100 结 束 开 始 y n （2）求解例）求解例4.5

47、的算法流程图的算法流程图 开 始 x=0 i=1 x=x+1/i i=i+1 i=n 结 束 n y （3）求解例）求解例4.6的算法流程图的算法流程图 开 始 n = 0 x = 0 ， y = 1 p rin t x ， y i= 1 i n -1 z = x + y x = y y = z p rin t y i= i+ 1 结 束 y = 0 p rin t y y n y n 3伪代码伪代码（begin(算法开始算法开始) 1 x 2 ywhile（y=n)end（算法结束）（算法结束）（3）例）例4.6的伪代码算法描述：的伪代码算法描述：beginif n = =0 0 y pri

48、nt y else 4计算机程序设计语言计算机程序设计语言o 计算机程序设计语言描述的算法（程序）是计算机程序设计语言描述的算法（程序）是清晰的、简明的，最终也能由计算机处理的。清晰的、简明的，最终也能由计算机处理的。o 缺点：缺点：例例4.4的计算机程序设计语言（的计算机程序设计语言（c语言）的算法描述：语言）的算法描述：main() int x,y; x=1; y=2; while(y=100) x=x+y; y=y+1; ; printf(%d,x);例例4.5的计算机程序设计语言（的计算机程序设计语言（c语言）的算法描述语言）的算法描述main() int n; float x,i;

49、printf(please input n:); scanf(%d,&n); x=0; i=1; 算法分析算法分析o 在计算机科学研究中，事实上存在一条规律：在计算机科学研究中，事实上存在一条规律：一个问题，当它的描述及其求解方法或求解一个问题，当它的描述及其求解方法或求解过程可以用构造性数学描述，而且该问题所过程可以用构造性数学描述，而且该问题所涉及的论域为有穷，或虽为无穷但存在有穷涉及的论域为有穷，或虽为无穷但存在有穷表示时，那么，这个问题一定能用计算机来表示时，那么，这个问题一定能用计算机来求解；求解；o 反过来，凡是能用计算机求解的问题，也一反过来，凡是能用计算机求解的问题，也

50、一定能对该问题的求解过程数学化，而且这种定能对该问题的求解过程数学化，而且这种数学化是构造性的。数学化是构造性的。算法分析考虑的问题；算法分析考虑的问题； o 当一个问题的求解获得了计算方法和算法时，当一个问题的求解获得了计算方法和算法时，并不等于万事大吉了。并不等于万事大吉了。在许多情况下，找到在许多情况下，找到求解一个问题的算法只是走完了第一步。至求解一个问题的算法只是走完了第一步。至于现实是否可以计算，则取决于算法的存在于现实是否可以计算，则取决于算法的存在性和计算的复杂性，即取决于该问题是否存性和计算的复杂性，即取决于该问题是否存在求解算法，算法所需要的时间和空间在数在求解算法，算法所

51、需要的时间和空间在数量级上能否被接受。量级上能否被接受。o 要注意的是，有的问题虽然存在求解问题的要注意的是，有的问题虽然存在求解问题的计算方法，但是，不存在算法。计算方法，但是，不存在算法。原因有两种原因有两种可能：一是计算方法可能不是构造性的；二可能：一是计算方法可能不是构造性的；二是虽为构造性的，但计算方法不能保证计算是虽为构造性的，但计算方法不能保证计算过程在任何初值的情况下都能结束。过程在任何初值的情况下都能结束。算法分析考虑的问题；算法分析考虑的问题； o 解一个问题，往往有若干不同的算法，这些解一个问题，往往有若干不同的算法，这些算法决定着根据该算法编写的程序性能的好算法决定着根

52、据该算法编写的程序性能的好坏。那么，在保证算法正确性的前提下，如坏。那么，在保证算法正确性的前提下，如何确定算法的优劣就是一个值得研究的课题。何确定算法的优劣就是一个值得研究的课题。o 在算法的分析中，一般应考虑以下在算法的分析中，一般应考虑以下3个问题：个问题： （1）算法的时间复杂度；算法的时间复杂度； （2）算法的空间复杂度；）算法的空间复杂度； （3）算法是否便于阅读、修改和测试。）算法是否便于阅读、修改和测试。 算法分析考虑的问题；算法分析考虑的问题； o 使用计算机计算各种问题，需要存储空间、使用计算机计算各种问题，需要存储空间、计算时间。不同的算法计算所需要的时间和计算时间。不同

53、的算法计算所需要的时间和空间是不同的。所谓算法的复杂性就是对算空间是不同的。所谓算法的复杂性就是对算法计算所需要的时间和空间的一种度量。由法计算所需要的时间和空间的一种度量。由于不同的计算机千差万别，运算速度和字长于不同的计算机千差万别，运算速度和字长可以相差很大，因此，不可能用算法在某一可以相差很大，因此，不可能用算法在某一台计算机上计算所需要的实际的时间和存储台计算机上计算所需要的实际的时间和存储单元（空间）去衡量这个算法的复杂性。那单元（空间）去衡量这个算法的复杂性。那么，怎样才能准确刻划算法的计算复杂性呢？么，怎样才能准确刻划算法的计算复杂性呢？ 什么是算法的复杂性呢？什么是算法的复杂

54、性呢？o 科学家们采用了与问题规模大小相联系的一科学家们采用了与问题规模大小相联系的一个近似函数（个近似函数（称为渐近增长率称为渐近增长率）来刻画算法）来刻画算法的计算复杂度。该函数表示了算法随问题规的计算复杂度。该函数表示了算法随问题规模大小变化引起的算法中抽象的基本运算执模大小变化引起的算法中抽象的基本运算执行的次数或存储空间量的变化规律。行的次数或存储空间量的变化规律。o 例如，某个计算问题当输入规模分别为例如，某个计算问题当输入规模分别为1，2，3，n时，经分析算法中抽象的基本运算时，经分析算法中抽象的基本运算次数分别为次数分别为1，4，9，n2，那么，就可以，那么，就可以用函数用函数

55、n2来刻划这个算法的时间复杂性，并来刻划这个算法的时间复杂性，并称这个算法的时间复杂性度量为称这个算法的时间复杂性度量为 （1）算法的时间复杂度；）算法的时间复杂度； o 有了复杂性度量函数，一旦选定具体计算机，有了复杂性度量函数，一旦选定具体计算机，可以根据这台计算机对某个可以根据这台计算机对某个n值的实际运算速值的实际运算速度比较准确地估算出对其他的度比较准确地估算出对其他的n值完成计算所值完成计算所需要的时间。需要的时间。o 于是，对各种算法的复杂性进行分析的关键于是，对各种算法的复杂性进行分析的关键是要设法去找出这样的函数，它涉及到与数是要设法去找出这样的函数，它涉及到与数学密切相关的

56、算法的设计原理、思想和方法，学密切相关的算法的设计原理、思想和方法，算法分析是具有智力挑战性的研究课题。算法分析是具有智力挑战性的研究课题。（1）算法的时间复杂度；）算法的时间复杂度； o 用用（1）算法的时间复杂度；）算法的时间复杂度； （o 设设 ( )是一个关于正整数是一个关于正整数 的函数，若存在一的函数，若存在一个正整数个正整数0和一个常数和一个常数c，当，当0时，时， ( ) c ( ) 均成立，则称均成立，则称 ( )为为 ( )的同数量级的函数。的同数量级的函数。n 算法时间复杂度算法时间复杂度 ( )可表示为：可表示为： ( )=( ( )常见的大常见的大 在梵天塔问题中，需

57、要移动的盘子次数为在梵天塔问题中，需要移动的盘子次数为h(n)=2n-1，则该问题的算法时间复杂度表示，则该问题的算法时间复杂度表示为为 (2n)；例；例4.4的算法时间复杂度表示为的算法时间复杂度表示为 (1)；例例4.5的算法时间复杂度表示为的算法时间复杂度表示为 (n)；例；例4.6的的算法时间复杂度表示为算法时间复杂度表示为 (n)等等。等等。 一般而言，对于较复杂的算法，应将它分一般而言，对于较复杂的算法，应将它分成容易估算的几个部分，然后用成容易估算的几个部分，然后用 的求解原则的求解原则计算整个算法的时间复杂度，最好不要采用计算整个算法的时间复杂度，最好不要采用指数级和阶乘级的算

58、法，而应尽可能选用多指数级和阶乘级的算法，而应尽可能选用多项式级或线性级等时间复杂度较小的算法。项式级或线性级等时间复杂度较小的算法。另外，还要在算法最好、平均和最坏的情况另外，还要在算法最好、平均和最坏的情况下区别执行效率的不同。下区别执行效率的不同。 在阶乘级的算法中，如果问题规模在阶乘级的算法中，如果问题规模n为为10，则算法时间复杂度为则算法时间复杂度为10！（！（3，628，800）。）。若要检验若要检验10！种情况，设每种情况需要！种情况，设每种情况需要1毫秒毫秒的计算时间，则整个计算将需的计算时间，则整个计算将需1小时左右。一小时左右。一般来说，如果选用了阶乘级的算法，则当问般来

59、说，如果选用了阶乘级的算法，则当问题规模等于或者大于题规模等于或者大于10时，就要认真考虑算时，就要认真考虑算法的适用性问题。法的适用性问题。 算法的空间复杂度算法的空间复杂度o 指算法在执行过程中所占存储空间的大小，指算法在执行过程中所占存储空间的大小，o 用用算法的研究算法的研究算法算法o 算法：定义一项工作如何完成的步骤的集合算法：定义一项工作如何完成的步骤的集合n 在一台机器可以完成一个任务之前，必须在一台机器可以完成一个任务之前，必须找到完成这个任务的算法并且用与机器兼找到完成这个任务的算法并且用与机器兼容的方式来描述容的方式来描述n 一个与机器兼容的算法的描述一个与机器兼容的算法的

60、描述程序程序算法转化为智慧算法转化为智慧o 通过使用算法来得到并转化智慧，我们才可通过使用算法来得到并转化智慧，我们才可以构建起可以表现以构建起可以表现智慧行为的机器智慧行为的机器。n 机器表现的智能等级受到通过算法转化的机器表现的智能等级受到通过算法转化的智慧所限制智慧所限制n 如果没有解决问题的算法，意味着问题的如果没有解决问题的算法，意味着问题的解决方案超出了机器的能力范围解决方案超出了机器的能力范围计算机技术别用于复杂问题（大型软件系统）计算机技术别用于复杂问题（大型软件系统）o 不仅仅包括实现任务的单个算法的开发不仅仅包括实现任务的单个算法的开发n 还要求对组件之间的交互进行设计还要求对组件