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

第4章 计算学科中的基本概念,李陶深 tshligxu.edu.cn,4.1 计算模型与二进制,4.1.1 计算模型与图灵机,计算模型与图灵机,计算模型： 刻画计算这一概念的一种抽象的形式系统或数学系统。 在计算科学中，是指具有状态转换特征，能够对所处理的对象的数据或信息进行表示、加工、变化、接收、输出的数学机器。 计算模型的层次： 计算某个（类）具体问题的计算方法； 按照计算方法对应的程序完成某类问题特定计算所需要的平台。 在计算能力上具有某种等价性的形式系统。 计算模型的模型（一切计算模型所内含的机理）,计算模型与图灵机,图灵的观点及结论： 凡是能用算法方法解决的问题，也一定能用图灵机解决；凡是图灵机解决不了的问题，任何算法也解决不了。 与图灵机等价的计算模型： 递归函数 -演算 POST规范系统 图灵机是从过程这一角度来刻画计算的本质，其结构简单、操作运算规则也较少，从而为更多的人所理解。,图灵机,图灵机由一条两端可无限延长的带子、一个读写头以及一组控制读写头工作的命令组成，,图灵机,写在带子上的符号为一个有穷字母表：S0，S1，S2，Sp。 可以认为这个有穷字母表仅有S0、S1两个字符， 其中S0可以看作是“0”，S1可以看作是“1”， 由 “0”和“1”组成的字母表可以表示任何一个数。,由于“0”和“1”只有形式的意义，因此，也可以将S0改称为“白”，S1改称为“黑”，甚至，还可以改称为“桌子”和“老虎”，这样改称的目的在于割断与直觉的联系，并加深对布尔域中的值真，假，以及二进制机器本质的理解。机器的控制状态表为：q1，q2，qm。 将一个图灵机的初始状态设为q1，在每一个具体的图灵机中还要确定一个结束状态qw。,一个给定机器的“程序”,机器内的五元组（qiSjSkR（或L或N）ql）形式的指令集，五元组定义了机器在一个特定状态下读入一个特定字符时所采取的动作。5个元素的含义如下： qi表示机器目前所处的状态； Sj表示机器从方格中读入的符号； Sk表示机器用来代替Sj写入方格中的符号； R、L、N分别表示向右移一格、向左移一格、不移动； ql表示下一步机器的状态。,一个机器计算的结果是从机器停止时带子上的信息得到的。容易看出，q1S2S2Rq3指令和q3S3S3Lq1指令如果同时出现在机器中，当机器处于状态q1，第一条指令读入的是S2，第二条指令读入的是S3，那么机器会在两个方块之间无休止地工作。 另外，如果q3S2S2Rq4和q3S2S4Lq6指令同时出现在机器中，当机器处于状态q3并在带子上扫描到符号S2时，就产生了二义性的问题，机器就无法判定。,例子：,b表示空格，q1表示机器的初始状态， q4表示机器的结束状态，设带子上的输入信息是10100010，读入头位对准最右边第一个为0的方格，状态为初始状态q1。规则如下： q1 0 1 L q2 q1 1 0 L q3 q1 b b N q4 q2 0 0 L q2 q2 1 1 L q2 q2 b b N q4 q3 0 1 L q2 q3 1 0 L q3 q3 b b N q4,计算结果是10100011，即对给定的数加1。,以上命令计算的是这样一个函数：S(x)x1。当没有输入时，即初始状态所指的方格为空格（b）时，不改变空格符，读写头不动并停机。,图灵机的计算能力,第一，把图灵机看作识别器，即判断带子上最初的内容能否被图灵机所接受。假定图灵机从左向右扫描完带子上的内容后停机则为接受，否则为不接受。 例2 一台图灵机可以设计成识别下面的序列： 1000110, 10011101, 010101011。,图灵机的计算能力,第二，把图灵机看作生成器，对给定的输入集合，考察输出集合，并研究输入输出集合性质之间的关系，这就研究了图灵机的生成能力。 例3 设一台图灵机的输入集合为In1n0nnN，可设计一台图灵机，对给定的输入集合In，得到输出集合Out0n1nnN。其中，N是全体自然数的集合。,图灵机的计算能力,第三，把图灵机看作计算器，相当于一个函数。图灵机的输入是函数的自变量的值，图灵机的输出是函数的值。 例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)。,图灵机的计算能力,第一和第二个函数读者不难从图灵机的定义出发感悟到它们是图灵机可以计算的函数，而第三个函数就比较复杂，一时难于判断。顺便提一下，第三个函数叫做阿克曼函数，它是阿克曼（W.Ackermann）在研究原始递归函数和递归函数的关系时给出的。这个函数在计算理论中具有重要价值。 事实上，图灵机还可以计算形式上比第三个函数更复杂的函数。,图灵机的计算能力,图灵机可以计算 S(x)x1（后继函数）， N(x)0（零函数）， Ui(n)(x1，x2，xn)xi，1in（投影函数） 上述3个函数的任意组合。 从递归论中，我们知道这3个函数属于初始递归函数， 任何原始递归函数都是从这3个初始递归函数经有限次的复合、递归和极小化操作得到的。 从可计算理论可知每一个原始递归函数都是图灵机可计算的。,4.1 计算模型与二进制,4.1.2 二进制,计算机的数字系统,计算机采用的是二进制数字系统。 基本符号：0、1 进位原则：逢二进一 优点： 易于物理实现 二进制数运算简单 机器可靠性高 通用性强 缺点：对人来说可读性差,十进制数的表示,各位数字与它的权相乘，其积相加。 例如: 27997.63=21*104+ 7*103 + 9* 102 +9* 101 + 7* 100 + 6* 10-1 +3* 10-2 对于任意的十进制数： S=kn*10n +kn-1*10n-1 +k1*101 + k0*100 +k-1*10-1 + k-m+1*10-m+1 + k-m*10-m (n1, m1) 其中，10称为十进制的基数,ki0,1,2,3,4,5,6,7,8 9，m，n为正整数。小数点的位置不言自明。,计算机的数字系统,计算机采用的是二进制数字系统。二进制和十进制一样，是一种数制，它用于表示数的符号（数字）由于在书写中的位置不同而具有不同的值。 基本符号：0、1 进位原则：逢二进一 优点： 易于物理实现 二进制数运算简单 机器可靠性高 通用性强 缺点：对人来说可读性差,二进制数,Sknkn-1 k0. k-m kn×2nkn-1×2n-1k0×20k-m×2-m -m ki×2i in 其中，2称为二进制的基数，ki0,1,m,n为正整数。 进一步，读者可从十进制数和二进制数的一般表示公式得到启发，将这种表示推广到更一般的任意进制，不同之处只是基数不一样。,二进制数,二进制的运算规则比十进制的运算规则简单得多。只要建立两种进制的数据之间的转换方法，那么，二进制将具有更多的优势。计算机的理论基础是逻辑和代数。当二进制与同样只使用“真”和“假”两个值的逻辑代数建立了联系后，这就为计算机的逻辑设计提供了便利的工具。,不同进位计数制间的转换 R 进制十进制,各位数字与它的权相乘，其积相加。 例如: (11111111.11)2=1*27 + 1*26 + 1* 25 +1* 24 + 1* 23 + 1* 22 +1* 21+ 1* 20+1*2-1+1*2-2 =(255.75)10 (3506.2)8=3*83 + 5*82 + 0*81 + 6*80 +2*8-1 =(1862.25)10 (0.2A)16=2*16-1 +10*16-2=(0.1640625)10,二进制与十进制间的转换 十进制 二进制,十进制整数转换成二进制的整数 “除R取余”法，例如： 2 68 余 数 2 34 0 低位 2 17 0 2 8 1 2 4 0 2 2 0 2 1 0 0 1 高位 所以 681010001002,二进制与十进制间的转换十进制 二进制,十进制小数转换成二进制小数 “乘 R 取整”法，例如： 高位 0.3125×2 = 0 .625 0.625 ×2 = 1 .25 0.25 ×2 = 0 .5 0.5 ×2 = 1 .0 所以 0.312510 = 0.01012,不同进位计数制间的转换二、八、十六进制的相互转换,每位八进制数相当于三位二进制数 每位十六进制数相当于四位二进制数 (1011010.10)2=(001 011 010 .100)2 =(132.4)8 (1011010.10)2=(0101 1010 .1000)2 =(5A.8)16 (F7)16(1111 0111)2(11110111)2,信息的存储单位,位(bit)：度量数据的最小单位，表示一位二进制信息。 字节(byte)：由八位二进制数字组成(1 byte = 8 bit)。 K 字节 1 K = 1024 byte M 字节 1 M = 1024 K G 字节 1 G = 1024 M T字节 1T=1024G,非数值信息的表示,西文字符： ASCII码：用7位二进制数表示一个字符，最多可以表示27=128个字符 EBCDIC码：用8位二进制数表示一个字符，最多可以表示28=256个字符 汉字： 应用较为广泛的是“国家标准信息交换用汉字编码“(GB2312-80标准)，简称国标码。是二字节码，用二个七位二进制数编码表示一个汉字。,4.2 存储程序式计算机的基本结构与工作原理,4.2.1 冯·诺依曼型计算机,冯·诺依曼型计算机,图灵机的出现为现代计算机的发明提供了重要的思想。图灵机的带子可以看成是计算机的存储设备，数据可以存储在上面，也可以根据需要擦去。图灵机的命令相当于一组事先设计、存储好了的程序，它们在控制器安排下，决定读写头的每一步操作。这样一种数学机器，如果不考虑它的实用性，就思想和原理而言，确实包含了存储程序的重要思想。,冯·诺依曼型计算机,计算机程序是指能够在计算机系统中运行的程序。 现在的计算机全称为存储程序式通用电子数字计算机。其含义是： 在计算机中各种信息用数字代码表示，如指令、数值型数据、字符、图像等。 在物理机制上，数字代码以数字型信号出现。 信息表示数字化-理解计算机工作原理的基本出发点。,冯·诺依曼型计算机,目前有两种电信号： 模拟信号：一种在时间上连续的信号，用信号的某些参数（如幅值）去模拟信息。 数字信号：一种在时间上或空间上不连续（离散）的信号。,冯·诺依曼型计算机,采用数字化方法表示信息的优点： 抗干扰能力强，可靠性高。 位数增多则数的表示范围扩大，可以表示更精确的数字。 物理上容易实现，并可存储。 表示信息的类型和范围极其广泛。 能用逻辑代数等数字逻辑技术进行处理。,冯·诺依曼型计算机,ENIAC的结构在很大程度上是依照机电系统设计的，还存在重大的线路结构等问题。 在图灵等人工作的影响下，1946年6月，美国杰出的数学家冯·诺依曼（Von Neumann）及其同事完成了关于“电子计算装置逻辑结构设计”的研究报告， 具体介绍了制造电子计算机和程序设计的新思想：存储程序、顺序控制 至今为止，大多数计算机采用的仍然是冯·诺依曼型计算机的组织结构，只是作了一些改进而已。因此，冯·诺依曼被人们誉为“计算机器之父”。,冯·诺依曼型计算机的组织结构,输入设备和输出设备,输入设备和输出设备,作用：是将信息输入计算机和输出计算机。 常用的文字输入设备是键盘（还有扫描仪、穿孔卡片读入机和鼠标等专用输入设备） 当在键盘上按下一个键时，按下的键通过编码变换成机器可读的数据形式， 如字符“A”变换成ASCII码“1000001”，该编码数据随即存入存储器等待处理， 通过与“1000001”对应的字符点阵数据在屏幕上显示一个字符“A”。 输出设备有打印机、显示器、绘图仪、磁记录设备等。,存储器,存储器,存储器是一种数据或信息的存储部件，它分成很多存储单元，并按照一定的方式进行排列。每个单元都编了号，称为存储地址。指令和数据存放在存储器中,而且对指令和数据同等对待，都不加区别地送到运算器中运算。指令在存储器中基本上是按执行顺序存储的，由指令计数器指明要执行的指令在存储器中的地址。,存储器,存储器一般分为内存储器与外存储器两大类。内存一般安装在主机板上，根据材料和工作原理的不同，内存可分为随机存储器（RAM）和只读存储器（ROM）两种。控制器和运算器只能接受在内存中存放的指令和数据。 外存一般安装在主机板之外，例如磁盘就是一种常用的外存。外存上面的信息可长久保存，但这些信息必须读入内存之后才能被控制器和运算器所利用。磁盘按其材料的不同，又可分为软盘和硬盘两种。,CPU(运算器和控制器 ),central processing unit,Register、控制单元,计算机中控制数据操作的电路并不与主存直接相连 这些电路被封装在一起，即CPU CPU含有自己的存储单元（register） Register作为临时空间来存储CPU所操作的数，保存算术逻辑单元的输入与输出数据 控制单元负责将主存中的数据移到register，然后通知算术逻辑单元所需要的数据在哪个register,总线,总线：CPU与主存之间用总线连接，利用总线 CPU通过提供存储单元目标地址以及读信号来选择、读取数据 CPU通过提供存储单元目标地址以及写信号来放置、写入信号 谁发明了什么 程序存储的概念：由宾西法尼亚大学Moore电子工程学院的J.P.Echert提出，John von Neumann只是先发表了程序存储的概念,CPU和主存储器通过总线相连,4.3 数字逻辑与集成电路,4.3.1 数字逻辑,数字逻辑,数字逻辑是数字电路逻辑设计的简称，其内容是应用数字电路进行数字系统逻辑设计。 组成计算机的逻辑部件可分为组合逻辑电路和时序逻辑电路两种。 组合逻辑电路：由与门、或门和非门等门电路组合而成的逻辑电路。 时序逻辑电路：由触发器和门电路组成的具有记忆能力的逻辑电路。,门电路,“与”门电路：两个以上的输入，一个输出。仅当所有的输入为1时，输出才为1。 P=A · B · C “或”门电路：两个以上的输入，一个输出。仅当有一个输入为1时，输出就为1。 P=A + B + C “非”门电路：一个输入，一个输出。当输入为1时，输出为0；输入为0时，输出为1。,门电路,“与”、“或”、“非”三种门电路示意图 P P P · A B C A B C A （a） （b） （c）,4.4 机器指令与汇编语言,4.4.1 机器指令,机器指令,为了实现程序存储的概念，CPU要能识别二进制编码的指令 机器语言指令集合以及编码系统,机器指令,用计算机求解一个问题，必须事先编制好程序。程序是由指令组成的。每一台计算机都设计规定了一组指令集合，称为机器指令系统。 机器指令的格式一般分为两部分，如下所示： 指令格式： 操作码 地址部分 其中，操作码指出运算的种类，如，×，÷，跳转等，地址部分用来指示参与运算的数据保存在什么地方，如存储器的某个地址或某个寄存器等。操作码和地址部分都用二进制代码表示。,机器指令,机器指令一般可根据其功能划分为以下几类： (1)控制指令；(2)算术运算指令；(3)逻辑运算指令；(4)移位操作指令；(5)传送操作指令；(6)输入/输出指令。 应当注意的是，不同的机器，其指令系统是不同的。 指令系统的日渐增大虽然给用户的程序设计带来了方便，但也带来了硬件设计复杂性的增加和因译码、存储、寻址等开销的增大而使运算速度下降。研究发现，指令系统存在着改进的必要和可能。,指令系统,CPU必须能够解码并执行的机器指令很少 一旦计算机可以执行一些基本的而且是精选的操作，加入额外的操作理论上是不会改变计算机的能力的 是否充分利用这种特性导致了两种不同的计算机设计： CISC(complex instruction set computer) RISC(reduced instruction set computer),CISC,最初人们采用的是进一步增强原有指令的功能，并设置更为复杂的指令的方法 采用这种设计思路的计算机被称为复杂指令系统计算机（CISC）。 CISC的思路是由IBM公司提出的，并以1964年IBM研制的IBM 360系统为代表。,CISC缺点,80%的指令只在20%的运行时间里用到； 一些指令非常繁杂，而执行效率甚至比用几条简单的基本指令组合的实现还要慢。 庞杂的指令系统也给超大规模集成电路（VLSI）的设计带来了困难， 它不但不利于设计自动化技术的应用，延长了设计周期，增加了成本， 容易增加设计中出现错误的机会，从而降低了系统的可靠性。,RISC,思路主要是通过减少指令总数和简化指令的功能来降低硬件设计的复杂度，从而提高指令的执行速度。 优点:与CISC技术相比 简化了指令系统，适合超大规模集成电路的实现； 提高了机器执行的速度和效率； 降低了设计成本，提高了系统的可靠性； 提供了直接支持高级语言的能力，简化了编译程序的设计。,机器指令,机器指令系统每台数字电子计算机在设计中，都规定了一组指令。 机器语言用机器指令形式编写的程序。 在裸机级，计算机语言关于算法的描述采用的是实际机器的机器指令，它的符号集是0，1， 支撑实际机器的理论是图灵机等计算模型； 在图灵机等计算模型理论的指导下，有关设计形态的主要成果有冯·诺依曼型计算机等具体实现思想和技术，以及各类数字电子计算机产品。,计算机语言在裸机级所取得的主要成果,4.4 机器指令与汇编语言,4.4.2 汇编语言,汇编语言,汇编语言实际上是由一组汇编指令构成的语言。每一条汇编指令用某个西文字符串的缩写来表示其所代表的操作，用符号来代表数据的二进制、八进制和十进制数字序列。大多数情况下，一条汇编指令对应一条机器指令，少数对应几条机器指令。例如，下面是几条汇编指令的操作符，右边中文是名称。 add 加法 idiv 有符号除法 mul 无符号乘法 neg 求补 xchg 交换 test 逻辑比较 jmp 无条件转移,汇编语言,采用字符和十进制数来代替二进制代码的思想。 例3.10 对2+6进行计算的算法描述 用机器指令对“2+6”进行计算的算法描述： 1011000000000110 0000010000000010 101000100101000000000000 汇编语言对“2+6”进行计算的算法描述： MOV AL，6 ADD AL，2 MOV VC，AL,汇编语言语句与特定的机器指令有一一对应的关系，但是它毕竟不同于由二进制组成的机器指令，它还需要经汇编程序翻译为机器指令后才能运行。 汇编语言源程序经汇编程序翻译成机器指令，再在实际的机器中执行。 就汇编语言的用户而言，该机器是可以直接识别汇编语言的，从而产生了一个属于抽象形态的重要概念，即虚拟机的概念。 一般说来，汇编程序被看成是系统软件的一部分。,汇编语言,当然，汇编语言在可读性和编写程序时仍然是不能令人满意的，这导致进一步发展了高级程序设计语言。不过，由于高级语言在使用时通常还是要通过编译程序逐步将高级语言写的程序翻译成机器指令的程序，而这种翻译的结果往往不如机器指令或汇编语言写的程序效率高，所以，直到今天，不少工程师在系统软件的开发中还在使用机器指令和汇编语言。,4.5 算法、数据结构与程序,求解一个给定的问题，不同的人常编写出不同的然而都是正确的程序，这是为什么呢？ 这里存在两个层面的问题，一个是与计算方法密切相关的算法问题，另一个是程序设计的技术问题。,4.5 算法、数据结构与程序,4.5.1 算法,算法的历史简介,公元825年，阿拉伯数学家阿科瓦里茨米（AlKhowarizmi）写了著名的波斯教科书（Persian Textbook），书中概括了进行四则算术运算的法则。 “算法”（Algorithm）一词就来源于这位数学家的名字。 后来，韦氏新世界词典将其定义为“解某种问题的任何专门的方法”。 而据考古学家发现，古巴比伦人在求解代数方程时，就已经采用了“算法”的思想。,丢番图方程的可解性问题,古希腊数学家丢番图（Diophantus）：代数学之父 在算术（Arithmetica）一书中提出了有关两个或多个变量整数系数方程的有理数解问题。 对于具有整数系数的不定方程，如果只考虑其整数解，这类方程就叫做丢番图方程。 “丢番图方程可解性问题”的实质为：能否写出一个可以判定任意丢番图方程是否可解的算法？,一个未知数的线性丢番图方程的解,ax=b，只要a能整除b，就可判定其有整数解，该整数解即b/a。,两个未知数的线性丢番图方程 的解,ax+by=c，先求出a和b的最大公因子d，若d能整除c，则该方程有解（整数解）。 问：方程13x+26y=52有无整数解？ 答：13和26的最大公因子是13，13又可整除52，故该方程有整数解（如x=2，y=1即方程的解）。 例4.2 问：方程2x+4y=15有无整数解？ 答：2和4的最大公因子是2，2不能整除15，故该方程无整数解。,两个未知数的线性丢番图方程 的解：欧几里德算法,给定两个正整数m和n，求它们的最大公因子，即能同时整除m和n的最大正整数。 步骤如下： （1）以n除m，并令所得余数为r（r必小于n）； （2）若r=0，算法结束，输出结果n；否则，继续步骤（3）； （3）将n置换为m，r置换为n，并返回步骤（1）继续进行。,例4.3 设m=56，n=32，求m、n的最大公因子,算法如下: （1）32除56余数为24； （2）24除32余数为8； （3）8除24余数为0，算法结束，输出结果8。 答：m、n的最大公因子为8。 欧几里德算法既表述了一个数的求解过程， 又表述了一个判定过程，该过程可以判定“m和n是互质的”（即除1以外，m和n没有公因子）这个命题的真假。,不难想象，不同的求解方法将产生出不同的算法，不同的算法将使我们设计出不同的程序，而决定这个程序功能的本质是计算方法及其算法。一般地说，对不同计算方法过程的抽象描述就产生了相应的不同算法，但同一算法由不同的人来写程序则完全可能设计出差别很大的程序。 凭直觉想象给出的算法往往不是最好的算法。,算法,算法的定义和特征,算法的定义和特征,算法被认为是计算科学的核心问题之一。 有关算法的定义不少，其内涵基本上是一致的，其中最为著名的是计算机科学家克努特在其经典巨著计算机程序设计的艺术（The Art of Computer Programming）第一卷中对算法的定义和特性所作的有关描述。,1算法的一些定义,定风1：给定问题和设备，一个算法是用该设备可理解的语言表示的，解决这个问题的一种方法的精确刻划。特别，算法具有下列特征属性： (1) 算法应用于一个具体的输入集合或问题描述将在有穷步动作序列之后得到结果； (2) 该序列有一个唯一的初始动作； (3) 该序列中的每一个动作有一个唯一的后继动作； (4) 该序列终止时或者得到这个问题的解，或者因该问题不可解而获得不可解说明。,算法的定义和特征,1算法的一些定义,定风1：给定问题和设备，一个算法是用该设备可理解的语言表示的，解决这个问题的一种方法的精确刻划。特别，算法具有下列特征属性： (1) 算法应用于一个具体的输入集合或问题描述将在有穷步动作序列之后得到结果； (2) 该序列有一个唯一的初始动作； (3) 该序列中的每一个动作有一个唯一的后继动作； (4) 该序列终止时或者得到这个问题的解，或者因该问题不可解而获得不可解说明。,算法的定义和特征,定义2（Knuth算法定义）,一个算法，就是一个有穷规则的集合，其中之规则确定了一个解决某一特定类型问题的运算序列。此外，算法的规则序列须满足如下五个重要条件（特性）： (1) 有穷性。算法必须总是在执行有穷步之后结束； (2) 确定性。算法的每一个步骤必须是确切地定义的； (3) 输入。算法有零个或多个输入； (4) 输出。算法有一个或多个输出，即与输入有某个特定关系的量； (5) 能行性。算法中有待执行的运算和操作必须是相当基本的，即是说，它们原则上都是能够精确地进行的，而且用笔和纸做有穷次就可以完成。,2算法的重要特性,有穷性：一个算法在执行有穷步之后必须结束。 如在欧几里德算法中，由于m和n均为正整数，在步骤（1）之后，r必小于n，若r0，下一次进行步骤（1）时，n的值已经减小，而正整数的递降序列最后必然要终止。因此，无论给定m和n的原始值有多大，步骤（1）的执行都是有穷次。,2算法的重要特性,确定性：算法的每一个步骤必须要确切地定义。即算法中所有有待执行的动作必须严格而不含混地进行规定，不能有歧义性。 如欧几里德算法中，步骤（1）中明确规定“以n除m”，而不能有类似“以n除m或以m除n”这类有两种可能做法的规定。 输入：算法有零个或多个的输入，即在算法开始之前，对算法最初给出的量。 如欧几里德算法中，有两个输入，即m和n。,2算法的重要特性,输出：算法有一个或多个的输出，即与输入有某个特定关系的量，简单地说就是算法的最终结果。 如在欧几里德算法中只有一个输出，即步骤（2）中的n。 能行性：算法中有待执行的运算和操作必须是相当基本的。 如：欧几里德算法最终得出正确的结果。,2算法的重要特性,输出：算法有一个或多个的输出，即与输入有某个特定关系的量，简单地说就是算法的最终结果。 如在欧几里德算法中只有一个输出，即步骤（2）中的n。 能行性：算法中有待执行的运算和操作必须是相当基本的。 如：欧几里德算法最终得出正确的结果。,2算法的重要特性,有穷性和能行性是算法最重要的两个特征。对有些问题来说，如果我们给出了一个类似于算法的有穷运算序列，而它对某些输入可能不停机，那么，我们就称这样的运算序列为一个过程。算法和过程都满足能行性和确定性，唯一的本质区别是算法的执行必须终止，而过程则不然，它可以永不停止。需要指出的是，高级程序设计语言中也有过程的概念，但与这里所讲的过程不同，那里实际上指的是一种子程序。,3算法的形式化定义,算法是一个四元组，即（Q，I，F）。 其中： （1）Q是一个包含子集I和的集合，它表示计算的状态； （2）I表示计算的输入集合； （3）表示计算的输出集合； （4）F表示计算的规则，它是一个由Q到它自身的函数，且具有自反性，即对于任何一个元素qQ，有F(q)=q。,算法,算法实例,例4.4 求1+2+3+100,设变量X表示加数，Y表示被加数，用自然语言将算法描述如下： （1）将1赋值给X； （2）将2赋值给Y； （3）将X与Y相加，结果存放在X中； （4）将Y加1，结果存放在Y中； （5）若Y小于或等于100，转到步骤（3）继续执行；否则，算法结束，结果为X。,例4.5 求解调和级数,设变量X表示累加和，变量I表示循环的次数，自然语言描述算法如下： （1）将0赋值给X； （2）将1赋值给I； （3）将X与1/I相加，然后把结果存入X； （4）将I加1； （5）若I大于等于N，算法结束，结果为X；否则转到步骤（3）继续执行。,例4.6 求解斐波那契数,0，1，1，2，3，5，8，13，21，34， （1） 来源于1202年意大利数学家斐波那契（L.P.Fibonacci）在其珠算之书（Liber Abaci）中提出的一个“兔子问题”： 假设一对刚出生的兔子一个月后就能长大，再过一个月就能生下一对兔子，并且此后每个月都能生一对兔子，且新生的兔子在第二个月后也是每个月生一对兔子。 问：一对兔子一年内可繁殖成多少对兔子？,在序列（1）中，每个数都是它的前两个数之和，Fn表示这个序列的第n个数，该序列可以形式化的定义为： F0=0，F1=1，Fn+2=Fn+1+Fn，n0 斐波那契数列还是一个关于加法算法的典型实例。,设变量X表示前一个数的值，即定义中的Fn，变量Y表示当前数的值，即定义中的Fn+1，变量Z表示后一个数的值，即定义中的Fn+2。那么求解问题的自然语言描述如下：,算法设计,（1）如果=0，那么将0赋值给Y，并输出Y，转步骤（11）继续执行； （2）将0赋给X，将1赋值给Y； （3）输出X、Y； （4）将1赋值给I； （5）如果I大于-1，则转到步骤（11），否则继续执行； （6）将X和Y的和赋值给Z； （7）将Y赋值给X； （8）将Z赋值给Y； （9）将Y输出； （10）将I加1，转步骤（5）继续执行； （11）算法结束。,算法,算法的表示方法,原语,一个算法的表达需要使用一些语言形式 自然语言“Visiting grandchildren can be nerve-racking”,可能即意味着孙子孙女导致了很多问题，也表示去看他们可能会有问题 图形语言：很少人能够根据折纸图给出的步骤成功地叠出一只鸟来，但一个专门学习过折纸的学生可以轻松完成 当用来描述算法的语言并没有被准确定义或者没有给予足够信息的时候，交流就会产生问题,原语,通过建立一个可以描述算法的意义明确的基本块（原语）集合，计算机科学即就可以解决上述的勾通问题 原语描述算法需要建立一个统一的细节描述级别，原语连同一组表达了原语如何表达复杂的想法的规定组成了一种程序设计语言 组成 语法：原语的符号表示 语义：表达了原语的意义,1自然语言,缺点 由于自然语言的歧义性，容易导致算法执行的不确定性； 自然语言的语句一般太长，从而导致了用自然语言描述的算法太长； 由于自然语言表示的串行性，因此，当一个算法中循环和分支较多时就很难清晰地表示出来； 自然语言表示的算法不便翻译成计算机程序设计语言理解的语言。,2流程图,它采用美国国家标准化协会ANSI（American National Standard Institute）规定的一组图形符号来表示算法。 流程图可以很方便地表示顺序、选择和循环结构，而任何程序的逻辑结构都可以用顺序、选择和循环结构来表示， 流程图可以表示任何程序的逻辑结构。 用流程图表示的算法不依赖于任何具体的计算机和计算机程序设计语言，,（1）求解例4.4的算法流程图,（2）求解例4.5的算法流程图,（3）求解例4.6的算法流程图,3伪代码（1）求解例4.4的伪代码算法描述：,BEGIN(算法开始) 1 X 2 Y while（Y=100） X+Y X Y+1 Y Print X END（算法结束）,（2）求解例4.5的伪代码算法描述：,BEGIN（算法开始） 0 X 1 I do X+1/I X I+1 I while(I=n) END（算法结束）,（3）例4.6的伪代码算法描述：,BEGIN if n = =0 0 Y Print Y else ,0 X 1 Y Print X，Y for(i=1;i=n-1;i+) X+YZ YX ZY Print Y END,4计算机程序设计语言,计算机程序设计语言描述的算法（程序）是清晰的、简明的，最终也能由计算机处理的。 缺点： 算法的基本逻辑流程难于遵循。与自然语言一样，程序设计语言也是基于串行的 用特定程序设计语言编写的算法限制了与他人的交流，不利于问题的解决； 要花费大量的时间去熟悉和掌握某种特定的程序设计语言； 要求描述计算步骤的细节，而忽视算法的本质。,例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; printf(“Please input n:“); scanf(“%d“,do X=X+1/I; I=I+1; while(I=n); printf(“n%f“,X); ,算法,算法分析,在计算机科学研究中，事实上存在一条规律：一个问题，当它的描述及其求解方法或求解过程可以用构造性数学描述，而且该问题所涉及的论域为有穷，或虽为无穷但存在有穷表示时，那么，这个问题一定能用计算机来求解； 反过来，凡是能用计算机求解的问题，也一定能对该问题的求解过程数学化，而且这种数学化是构造性的。,算法分析考虑的问题；,当一个问题的求解获得了计算方法和算法时，并不等于万事大吉了。在许多情况下，找到求解一个问题的算法只是走完了第一步。至于现实是否可以计算，则取决于算法的存在性和计算的复杂性，即取决于该问题是否存在求解算法，算法所需要的时间和空间在数量级上能否被接受。 要注意的是，有的问题虽然存在求解问题的计算方法，但是，不存在算法。原因有两种可能：一是计算方法可能不是构造性的；二是虽为构造性的，但计算方法不能保证计算过程在任何初值的情况下都能结束。,算法分析考虑的问题；,解一个问题，往往有若干不同的算法，这些算法决定着根据该算法编写的程序性能的好坏。那么，在保证算法正确性的前提下，如何确定算法的优劣就是一个值得研究的课题。 在算法的分析中，一般应考虑以下3个问题： （1）算法的时间复杂度； （2）算法的空间复杂度； （3）算法是否便于阅读、修改和测试。,算法分析考虑的问题；,使用计算机计算各种问题，需要存储空间、计算时间。不同的算法计算所需要的时间和空间是不同的。所谓算法的复杂性就是对算法计算所需要的时间和空间的一种度量。由于不同的计算机千差万别，运算速度和字长可以相差很大，因此，不可能用算法在某一台计算机上计算所需要的实际的时间和存储单元（空间）去衡量这个算法的复杂性。那么，怎样才能准确刻划算法的计算复杂性呢？,什么是算法的复杂性呢？,科学家们采用了与问题规模大小相联系的一个近似函数（称为渐近增长率）来刻画算法的计算复杂度。该函数表示了算法随问题规模大小变化引起的算法中抽象的基本运算执行的次数或存储空间量的变化规律。 例如，某个计算问题当输入规模分别为1，2，3，n时，经分析算法中抽象的基本运算次数分别为1，4，9，n2，那么，就可以用函数n2来刻划这个算法的时间复杂性，并称这个算法的时间复杂性度量为(n2)级。,（1）算法的时间复杂度；,有了复杂性度量函数，一旦选定具体计算机，可以根据这台计算机对某个n值的实际运算速度比较准确地估算出对其他的n值完成计算所需要的时间。 于是，对各种算法的复杂性进行分析的关键是要设法去找出这样的函数，它涉及到与数学密切相关的算法的设计原理、思想和方法，算法分析是具有智力挑战性的研究课题。,（1）算法的时间复杂度；,用T(n)表示，n表示问题规模的大小。 使用一个记号 Order（数量级）的第一个字母， 允许使用“=”代替“”。如n2+n+1=(n2),（1）算法的时间复杂度；,（1）算法的时间复杂度；,设f(n)是一个关于