资源描述
Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,*,单击以编辑母版标题样式,单击以编辑母版文本样式,第二级,第三级,第四级,第五级,*,欢迎学习算法设计与分析,算法设计与分析基础,主讲教师,：杨群生,计算机学院,绪论,为什么学习算法?对于一个即将从事计算机专业的人士来说,无论从理论还是从实践的角度,学习算法都是有必要的.从实践的角度来看,我们必须了解计算机领域中不同问题的一系列标准算法:此外,我们还要具备设计算法和分析效率的能力.从理论的角度来看,对算法的研究(有时称为“算法学”)已经被公认为是计算机科学的基石。,本章学习内容,1.1节介绍算法的概念,1.2节讲述算法问题求解,1.3节讨论几种问题类型,1.4节对基本的数据结构做了一番回顾,1.1 算法的概念,什么是,算法,？,算法是一系列解决问题的,清晰指令,，也就是说，能够对符合一定规范的,输入,，在有限时间内获得所要求的,输出,。,问题,算法,“computer”,输入,输出,图1.1 算法的概念,作为阐明算法概念的几个例子,本节会讨论3种方法,用于解决同一个问题:计算两个整数的最大约数。这些例子会帮助我们阐明几个要点：,算法的每一个步骤都必须,清晰,，,明确,，来不得半点含糊。,算法所处理的输入的值域必须仔细定义。,同样一种算法可以用几种不同的形式来描述。,可能存在几种解决相同问题的算法。,针对同一个问题的算法可能会基于完全不同的解题思路，而且解题目速度也会有显著不同。,欧几里得算法基于的方法是重复应用下列等式，直到m mod n等于0；,gcd(m,n)=gcd(n,m mod n)(m mod n 表于m除以n之后的余数),用于计算gcd(m,n)的,欧几里得算法,第一步,：如果n=0,返回m的值作为结果，同样过程结束；否则进入第二步。,第二步,：用n去除m，将,余数赋给r。,第三步,：将n的值赋给m，将r的值赋给n，返,回第一步。,用于计算gcd(m,n)连续整数检测算法,第一步,：将minm,n的值赋给t。,第二步,：m除以t，如,余数为0。进入第三步；否则，进入第四步。,第三步,：n,除以t，如果余数为0，返回t的值作为结果；否则，进入第四步。,第四步,：把t的值减1。返回第二步。,中学里计算gcd(m,n)过程,第一步,：找到m的所有质因数。,第二步,：找到n的所有质因数。,第三步,：从第一步和第二步求得的质因数分解式中找出所有的公因数（如果p是一个公因数，而且在m和n的质因数分解式分别出现过p,m,和p,n,次，那么应该将p重复minp,m,p,n,次,）。,第四步,：将第三步中找到质因数相乘，其结果作为给定数字的最大公约数。,1.2 算法问题求解基础,1.2.1 理解问题,从实践的观点来看，在设计一个算法前我们需要做的第一件事就是完全理解所给出的问题。仔细阅读问题的描述，如有任何疑惑就把疑问提出来，手工处理一些小例子，考虑一下特殊情况，有必要的话再继续提出疑问。,理解问题,决定；,计算方法；,精确和近似的解法；,数据结构；,算法设计技术,设计算法,正确性证明,分析算法,根据算法写代码,算法的设计和分析过程,1.2.2 了解计算设备的性能,一旦完全了了待处理的问题，我们就需要了解将要运行的计算机设备的性能。,1.2.3 在精确解法和近似解法间做先择,接下来主要讨论如何在精确的解法和近似的解法间做选择。前一种我们称之为精确算法，后一种则称为近似算法。,1.2.4 确定适当的数据结构,有些算法并不要求输入数据具有精巧的表现形式，但有些算法的确需要基于一些精心设计的数据结构。,1.2.5 算法设计技术,算法设计技术（也称为“策略”或者“范例”）是用算法解题的一般性方法，用于解决不同计算领域的多种问题。,1.2.6 详细表述算法的方法,我们一旦设计了一个算法，就需要用一定的方式对其进行详细描述。伪代码是自然语言和类编程语言组成的混合结构。伪代码往往比自然语言更精确，而且伪代码生成的算法描述往往会更简洁。,1.2.7 证明算法的正确性,一旦完成了以算法的描述，我们必须证明它的正确性。也就是说，我们必须证明对于每一个合法输入，该算法都会在有限的时间内输出一个满足要求的结果。,1.2.8 分析算法,我们常常希望我们的算法具有许多良好的特性。除正确性以外，最重要的特性就是“效率”了。实际上，算法有两种效率：时间效率和空间效率。时间效率显示了算法运行得有多快；而空间效率则显示了算法需要多额外的存储空间。,1.2.9 为算法写代码,绝大多数算法注定以计算机程序的形式实现。,1.3 重要的问题类型,在主算领域遇到的无数问题目中，有一些领域的问题吸引了研究人员的特殊关注。大体来讲，要么是问题具有实用上的重要性，要么是问题具有上些重要的特征，从而使它能够成为令人感兴趣的研究课题。幸运的是，在大多数情况下，这两种动因相互得到了强化。,本节，我们开始讲述最重要的问题类型：,排序,查找,串处理,图问题,组合问题,几何问题,数值问题,1.3.1 排序,排序问题要求我们按照升序重新排列给定列表中的数据项。当然，为了让这个问题有意义，列表中数据项的特性应该允许这种排列。,排序算法有两个特性特别值得一提。如果一个排序算法保留了实值无素在输入中的相对顺序，它被称为是稳定的。第二个特性是算法需要的额外储空间。如果一个算法除了个别存储单元以外，不需要额外存储空间，我们把它称为是在位的。,1.3.2 查找,查找问题涉及到从给定的集合（或者是多重集，它允许几个无素具有相同的值）中找寻一个给定的值，称为查找键。对于查找来说，也没有一种算法对于任何情况都是最适合的。有些算法速度比其他算法快，但却需要较多的存储空间；有些算法速度非常快，但仅适用于有序的数组，如此等等。,1.3.3 串处理,串是字母表中的符号所构成的序列。我们尤其关心文本串，它是由字母、数字以及特殊符号构成的。如何在文本中查找一个给定的词，这个特殊问题吸引了研究了研究者们的特别注意，他们称其为串匹配问题。,1.3.4 图问题,算法中最古老也是最令人感兴趣的领域是图算法。不必严格定义的话，可以认为图是由一些被称为顶点的点所构成的集合，其中某些顶点由一些称为边的线段相连。,基本的图算法包括图的遍历算法（如何能一次访问到网络中的所有节点）、最短路线算法（两个城市之间的最佳路线是哪条？）以及有向图的拓扑排序（一系列过程的前题条件是相互一致的还是自相矛盾的？）。,1.3.5 组合问题,从更抽象的角度来看，旅行商问题和图填色问题都是组合问题的特例。有一些问题要求（明确的或者含蓄的）寻找一个组合对象，比如一个排列、一个组合或者一个子集，这些对象能够满足特定的条件并具有我们想要的特性（例如：价值最大化或者成本最小化）。,一般说来，无论根据理论的观点还是实践的观点，组合问题都是计算领域中最难的问题。这是出于以下原因：第一，通常，随着问题规模的增大，组合对象的数量增长极快，即使是中等大小的实例，其组合的规模也会达不可思议的数量级。第二，还没有一种已知算法能在可接受的时间内，精确地解决绝大多数这类问题。,1.3.6 几何问题,几何算法处理类似于点、线、多面体这样的几何对象。本书只讨论两个经典的计算几何问题：最近对问题和凸包问题。,1.3.7 数值问题,数值问题，另一个广阔的具体应用领域，涉及具有连续性的数学对象问题：像解方程和方程组、计算定积分以及求函数的值等等。,1.4 基本数据结构,由于绝大多数算法关心的是对数据的操件，组织数据的特殊方法在算法的设计和分析中扮演了一至关重要的角色。我们可以将数据结构定义为相关的数据项进行组织的特殊方案。数据项的性质是由于手头的问题所决定的；它范围可以从基础的数据类型（例如，数字和字符号）到数据结构（例如，我们可以用以一维数组为元素的一维数组为元素的一维数组来实现矩阵）。,1.4.1 线性数据结构,两种最重要的基本数据结构是数组和链表。（一维）,数组,是n个相同数据类型的元素构成的序列，它们连续存储在计算机的存储器中，我们只要指定数组的下标就能够访问这些元素。,数据项n-1,数据项1,数据项0,图1.3 n个元素的数组,数组可以实现多种其他数据结构，其中比较突出的是串。吕是来自于字母表的字符序列，并以一个特殊字符来标识串的结束。由0和1组成的字符串称为二进制串或者比特串。,链表,是0个或者多称为节点的元素构成的序列，每个节包含两类信息：一些数据，以及一个或多个称为指针的链接，指向链表中其他元素（我们用一种称为null的特殊指针表明某个节点没有后继元素）。在单链表中，除了最后节点，每个节点都包含一个指向下一个元素的指针（图1.4）,数据项1,数据项0,数据项n-1,图1.4 n个元素的单链表,。,另一种扩展结构被称为,双链表,，其中除了第一个和最末一个节点，每一个节点都既包含指向前趋的指针又包含指向后继的指针（图1.5）,null,数据项n-1,数据项1,数据项0,null,图1.5 n个元素的双链表,另一种更抽象的数据结构叫做,线性列表,（或者简称列表），它的两种主要表现就是数组和链表。列表是由数据项构成的有限序列，即按照一定的线性顺序，排列而成的数据项的集合。在这种数据结构上进行的基本操作包括对元素的查找、插入和删除。,栈和队列,这两种特殊类型的列表，有着特殊的重要性。栈是一种插入和删除操作都只能在尾端进行的列表，这一端被称为栈顶。该结构按照一种“后进先出”（LIFO，last-in-first-out）的方式运转。,另一方面，,队列,也是一种列表，只是删除元素在列表的一头进行，称为队头（这种操作称为出队）；插入元素在表的另一头进行，称为队尾（这种操作称为入队）。因此队列是按照一种“先进先出”（FIFO，first-in-first-out）方式运行的。,优先队列是一个数据项的集合，这些数据项都来自于一些全序域（最常见的是整数或实数）。对优先队列的主要操作是找到最大元素、删除最大元素的插入一个新元素。,1.4.2 图,按照非正式定义，,图,可以认为是由平面上的顶点或者节点构成的集合。某些顶点称为边或者弧的线段连接。按照正式定义，一个图G=要由两个集合来定义：一个有限集合V，它的元素被称为顶点；另一个的限集合E，它的元素是由一对顶点，被称为边。如果每对顶点之间都没有顺序，也就是说，顶点对（u,v）和顶点（v,u）是相同的，我们说图G是无向的：否则，我们说边（u,v）的方向是从顶点u到顶点v，图本身被称为有向的。有向的图也称为有向图。,a,c,b,d,e,f,(a),a,c,b,d,e,f,(b),图1.6（a）无向图；(b)有向图,图1.6a包含6个顶点和7条边：,V=a,b,c,d,e,f E=(a,c),(a,d),(b,c),(b,f),(c,e),(d,e),(e,f)。,图1.6b包含6个顶点和8条的向边：,V=a,b,c,d,e,f E=(a,c),(b,c),(b,f),(c,e),(d,a),(d,e),(e,c),(e,f)。,任意两个顶点之间都有边相连的图称为完全图。如果完全图具有|V|个顶点，它的标准符号是K,|V|,。如果图中所缺的边数量相对较少，我们称它为稠密图；如果图中所缺的边数量相对较多，我们称为稀疏图。我们处理的是稀疏图还是稠密图，可能会影响图的表示方式，从而影响我们所设计或使用的算法的运行时间。,1.图的表示,计算机算法中,图主要可以用两种方法表示:邻接矩阵和邻接链表。n个顶点的邻接矩阵是一个n*n的布尔矩阵，图中每个顶点都用一行和一列来表示，如果从第i个顶点到第j个顶点之间有连接边，则矩阵中第i行第j列的元素等于1，如果没有这样的边，则等于0。例如，图1.6a所对应的邻接矩阵可以参见图1.7a。注意，一个无向图的邻接矩阵总是对称的（为什么？），也就是说，当i0，jn-1时，Ai,j=Aj,i。,
展开阅读全文