《计算机导论3》由会员分享，可在线阅读，更多相关《计算机导论3（34页珍藏版）》请在金锄头文库上搜索。
1、第四章 算法, 4.0 导言,问题求解的过程： 抽象把问题抽象为一个带有一般性的数学问题。 建模确定问题的数据模型。 描述将非形式化自然语言表达的算法转变为一种程序设计语言表达的算法。 调试、测试得到所要求的结果。,问题是否可解取决于算法的存在性和计算的复杂性。, 4.1 算法的概念,算法是程序设计的精髓，程序设计的实质就是构造解决问题的算法，将其解释为计算机语言。,算法是对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。,算法的规则序列必须满足的五个重要条件： (1)有穷性算法必须总是在执行有穷步后结束 (2)确定性算法的每一步骤必须被确定地定义 (3)输入
2、算法有零个或多个输入 (4)输出算法有一个或多个输出 (5)能行性算法中有待执行的运算和操作必须是相当基本的，即它们原则上都是能够精确地进行的，而且用笔和纸做有穷次就可以完成。,非形式化定义, 4.1 算法的概念,算法的形式化定义： 算法是四元组，即(Q,I,O,F)。其中： Q表示计算的状态 I表示计算的输入集合 O表示计算的输出集合 F表示计算的规则, 4.2 算法的表示,算法是一个描述性的内容。,常用的算法描述工具有：自然语言、流程图、决策表以及算法描述语言。,1.自然语言的优点：通俗易懂 自然语言的缺点：(1)歧义性(2)描述过长(3)串行性不适合描述循环和多分支情况(4)不能被计算机
3、接受, 4.2 算法的表示,2.流程图：用图形工具描述算法或程序结构。 优点：(1)可以方便表示顺序选择和循环结构。(2)不依赖于任何具体的计算机和计算机程序设计语言,处理或过程,起点或终点,判断或决策,输入输出,数据流程, 4.2 算法的表示,Begin,Read (m ,n),r:=mod (m ,n),m:=n,n:=r,r=0?,Write (m),否,是,(1)读入整数m和n read m,n,(2)求m和n的余数r r:=mod(m,n),(3)用n的值取代m，用r的值取代n。 m:=n n:=r,(4)判断r的值是否为零，如果r=0， 则m为最大公因子，否则返回2 循环,(5)输
4、出m的值,使用欧几里得算法求解两个整数m和n的最大公因子。,End, 4.2 算法的表示,3.决策表又称为判断表，列出了对于所有可能的条件应该采取的动作。比较适用于描述一个复杂的判断过程。,4.算法描述语言，是一种把自然语言与程序语言相结合起来的算法描述工具。与计算机程序非常相似，但是又不是正式的程序。,Procedure Euclids algorithm; BeginRead(m,n);Repeat;r:=mod(m,n);m:=n;n:=r;Until r=0Write(m) End, 4.2 算法的表示,Fibonacci(斐波那契)数列,第三个月,第四个月,第五个月,问：一年后有多少
5、只兔子？, 4.2 算法的表示,分析可得Fibonacci数列：1，1，2，3，5，8，13，21，34，,F(n)= 1 n=01 n=1F(n-1)+F(n-2) n1,注意：这是一个递归定义。,Procedure Fibonacci; Beginn0:=1n1:=1n2:=0Write(n0,n1);While n2n-1?,Z:=X+Y,X:=Y,Y:=Z,输出Y,I:=I+1,算法结束,Y,N,N,Y,F0=1 F1=1 Fn+2=Fn+1+FnI：计数器,当I的数值小于等于n-1的时候，前两个Fibonacci(n-1,n-2)数相加和为第n个Fibonacci数, 4.3 算法的
6、表示,4.3.3 分治法,分治法的设计思想是将一个规模为n的问题分解成为K个规模较小的子问题，这些子问题相互独立并且与原问题相同。递归地解这些问题，然后将各子问题的解合并得到原问题的解。,分治与递归是一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。, 4.3 算法的表示,分治算法的典型例子：二分搜索算法的基本思想是将n个元素分成个数大致相同的两半，取an/2与x作比较。如果x=an/2，则找到x，算法终止。如果xan/2，则我们只要在数组a的右半部继续搜索x。见图示：,Y,Y,Y,Y, 4.4 并行算法,所谓并行算法是指一次可执行多个操作的算法。,并行算法将用一种流行的理论模
7、型即并行随机存取计算机（PRAM:parallel random access Machine）来描述。,误区：顺序算法解决不了的问题完全可以用并行算法来解决；并行计算机系统求解问题的速度将随着处理器数目的不断增加而不断提高，从而解决难题。, 4.4 并行算法,1. PRAM模型右图说明了PRAM的基本结构。其中有n个普通的串行处理器p0,p1,.,pn-1共享一个全局存储器。所有处理器都可以“并行地”(同时)从全局存储器读出信息或向全局存储器写入信息。各处理器也可以并行地执行各种算术和逻辑操作。,并行算法的运行时间既依赖于执行算法的处理器数目，也依赖于输入问题本身的规模。一般来说，在分析PR
8、AM算法时我们必须同时讨论其时间和处理器数目。, 4.4 并行算法,2.并行存储器存取方式与互斥存储器存取方式,并发读算法：指在算法执行过程中多处理器可以同时对共享存储器的同一位置进行读操作的一种PRAM算法。互斥读算法：指在算法执行中任何两个处理器都不能同时对共享存储器的同一位置进行读操作的一种PRAM算法。,EREW：互斥读且互斥写 CREW：并发读且互斥写 ERCW：互斥读且并发写 CRCW：并发读且并发写,同步与控制PRAM算法必须高度同步以保证其正确执行。如何获得这一同步特征？另外，PRAM算法中的处理器常常必须测试循环的终止条件，而这一终止条件又往往取决于所有处理器的状态。如何实现这种控制功能？, 4.4 并行算法,一个好的正确的算法，衡量它是否优劣要综合考虑它的时间复杂度、空间复杂度和可理解性。, 4.5 算法的评价,
