第5章 算法与复杂性

第5章算法与复杂性2计算机科学导论学习目标了解算法的概念和特性、算法的描述工具、评价、算法设计策略、分布式算法、可计算性理论基础、NP问题、自动机理论、加密算法、几何算法、并行算法等。掌握几种经典算法的基本思想。一个好的算法是程序设计的关键，本章首先介绍算法的基本知识、常用算法及算法评价的基础知识，然后介绍几种常用的算法，为今后进一步学习算法及其复杂性打好基础。第5章算法与复杂性3计算机科学导论5.1算法分析基础5.1.1算法的概念算法（Algorithm）是一组明确的、可以执行步骤的有序集合，在有限的时间内终止并产生结果。算法和数据结构之间存在密切联系，数据结构是算法的基础，数据结构不同，通常采用的算法也不同。4计算机科学导论5.1.2算法的特性算法反映了求解问题的方法和步骤，不同的问题需要用不同的算法来解决，同一个问题也可能有多种不同的算法。一个算法必须具有以下特性：1.有穷性(可终止性)一个算法必须在有限的操作步骤内以及合理的时间内执行完成。2.确定性算法中的每一个操作步骤都必须有明确的含义，不允许存在二义性。5计算机科学导论3.有效性(可行性)包括以下两个方面：①算法中每一个步骤必须能够实现，如在算法中不允许出现分母为0的情况。②算法执行的结果要能够达到预期的目的，实现预定的功能。4.输入数据与输出数据的要求一个算法应该有0个或多个输入数据、有1个或多个输出数据。5.1.2算法的特性6计算机科学导论5.2常用算法介绍•1.递归算法•如果一个过程（函数，子程序）直接或间接地调用它本身，则称该过程是递归的。7计算机科学导论5.2常用算法介绍•2.迭代算法•迭代是指重复执行一组指令或操作步骤，在每次执行这组指令时，都在原来的解的基础上推出一个新解，新的解比原来的解值更加接近真实的解。这个过程不断重复，直到最后计算得到的解与真实的解的误差满足实践的要求。8计算机科学导论5.2常用算法介绍•3.穷举算法•穷举算法亦称枚举算法，该算法首先根据问题的部分条件确定问题的大致范围，然后在此范围内对所有可能的情况逐一进行验证，直到全部情况验证完毕。•若某个情况使验证结果符合题目的条件，则为本题的一个答案，若全部情况验证完成后均不符合题目条件，则判定该问题无解。9计算机科学导论5.2常用算法介绍•4.贪婪算法•贪婪算法也称贪心算法，是通过一系列的选择，最终得到问题的解。算法做出的每一个选择都是在当前状态下的最优选择。10计算机科学导论5.3算法描述工具算法是要通过程序才能加以实现的。常用的算法描述方式:1.自然语言自然语言就是人们日常使用的语言，可以是中文、英文等。例如，求3个数中最大者的问题，可以描述为：①比较前两个数。②将①中较大的数与第三个数进行比较。③步骤②中较大的数即为所求。11计算机科学导论2.流程图流程图是用规定的一组图形符号、流程线和文字说明来描述算法的一种表示方法。(1)顺序结构。程序执行完A语句后接着执行B语句，如图所示。(2)选择结构。当条件P成立时，则执行A语句，否则执行B语句，如图所示。ABP成立AB不成立5.3算法描述工具12计算机科学导论(3)当型循环结构。当条件P成立时，则循环执行A语句，如图所示(4)直到型循环结构。循环执行A语句，直到条件P1成立为止，如图所示。A直到P1成立当P成立A5.3算法描述工具13计算机科学导论3.伪代码伪代码是用一种介于自然语言与计算机语言之间的文字和符号来描述算法，它比计算机语言形式灵活、格式紧凑，没有严格的语法。例如，求两个数的较大者，用伪代码描述算法如下：FindthebiggerInput:twonumbers:a,b1.if(thefirstnumberaisgreaterthanorequaltothesecondnumberb)then1.1returnaelse1.2returnbendifend5.3算法描述工具14计算机科学导论5.4算法的评价对于一个算法的评价，通常要从正确性、可理解性、健壮性、时间复杂度(TimeComplexity)及空间复杂度(SpaceComplexity)等多个方面加以衡量。1．算法的时间复杂度时间复杂度是度量时间的复杂性，即算法的时间效率的指标。2．算法的空间复杂度算法的空间复杂度是度量空间的复杂性，即执行算法的程序在计算机中运行时所占用空间的大小。15计算机科学导论5.5算法设计策略一个优秀的算法可以运行在比较慢的计算机上，但一个劣质的算法在一台性能很强的计算机上也不一定能满足应用的需要，因此，在计算机程序设计中，算法设计往往处于核心地位。要想充分理解算法并有效地应用于实际问题中，关键是对算法的分析。通常可以利用实验对比分析、数学方法来分析算法。16计算机科学导论5.6分布式算法分布式算法是用于解决多个互连处理器运行问题的算法。分布式算法的各部分并发和独立地运行，每一部分只承载有限的信息。即使处理器和通信信道以不同的速度运作，或即使某些构件出了故障，这些算法仍然能工作正常。应用：如今天的电话系统、航班订票系统、银行系统、全球信息系统、天气预报系统以及飞机和核电站控制系统都依赖于分布式算法。17计算机科学导论5.7可计算性理论基础研究计算的可行性和函数算法的理论，又称算法理论，是算法设计与分析的基础，也是计算机科学的理论基础。可计算性是函数的一个特性。18计算机科学导论5.8NP问题NP(Non-deterministicPolynomial)问题是非确定性多项式问题，是指算法无法直接计算出结果，只能通过进行一些有选择的“猜算”来得到结果。NP问题的研究结果有两种可能：一种是找到了求解问题的算法；另一种就是求解问题的算法是不存在的，那么就要从数学理论上证明它为什么不存在。19计算机科学导论5.9自动机理论数理语言学中研究抽象自动机的理论。抽象自动机是一种能够识别语言的抽象装置，它不是具有物理实体的机器，而是表示计算机运算方式的抽象的逻辑关系系统。美国语言学家N.Chomsky等人建立了形式文法和自动机之间的联系，证明语言的形式文法与自动机之间存在着以下的对应关系：①若某一语言能用图灵机来识别，则它就能用O形文法生成；反之亦然。②若某一语言能用线性有界自动机来识别，则它就能用上下文敏感文法生成；反之亦然。20计算机科学导论③若某一语言能用后进先出自动机来识别，则它就能用上下文自由文法生成；反之亦然。④若某一语言能用有限自动机来识别，则它就能用有限状态文法生成；反之亦然。这种关于形式文法与自动机的关系，反映了语言的生成过程与识别过程的内在联系，它已成为计算机科学的基石之一。5.9自动机理论21计算机科学导论5.10加密算法数据加密的基本过程就是对原来为明文的文件或数据按某种算法进行处理，使其成为不可读的一段代码，通常称为“密文”该过程的逆过程为解密，即将该编码信息转化为其原来数据的过程。加密技术通常分为“对称式”和“非对称式”两大类。对称式加密就是加密和解密使用同一个密钥，非对称式加密就是加密和解密所使用的不是同一个密钥，通常有两个密钥，称为“公钥”和“私钥”，它们两个必须配对使用，否则不能打开加密文件。22计算机科学导论常见加密算法有如下：(1)DES(DataEncryptionStandard)：数据加密标准，速度较快，适用于加密大量数据的场合。(2)3DES(TripleDES)：是基于DES，对一块数据用3个不同的密钥进行3次加密，强度更高；(3)RC2和RC4：用变长密钥对大量数据进行加密，比DES快。(4)IDEA(InternationalDataEncryptionAlgorithm)国际数据加密算法，使用128位密钥提供非常强的安全性。(5)RSA：由RSA公司发明，是一个支持变长密钥的公共密钥算法，需要加密的文件块的长度也是可变的。(6)DSA(DigitalSignatureAlgorithm)：数字签名算法，是一种标准的DSS(数字签名标准)。5.10加密算法23计算机科学导论5.11几何算法几何算法的内容不属于欧几里德的几何证明公理化范畴，而是属于欧几里德几何构造，即由算法和复杂性构成。在一个几何构造过程中，执行原始运算的总次数称为该过程的复杂性度量，这个概念对应于算法的时间复杂度。同样，还有对应于算法的空间复杂度的概念。这是欧几里德几何构造过程复杂性的定量测度。24计算机科学导论5.12并行算法并行算法是在给定并行模型下的一种具体、明确的计算方法和步骤，其有不同的分类方法。根据并行计算任务的大小分类，可以分为粗粒度并行算法、中粒度并行算法和细粒度并行算法3类。根据并行计算的基本对象可分为数值并行计算和非数值并行计算。根据并行计算进程间的依赖关系，可以分为同步并行算法和异步并行算法。一个高效的并行算法设计过程比较复杂。一般编程设计过程可以分为任务划分、通信分析、任务组合和处理器映射4步。25计算机科学导论5.13本章小结算法是计算机科学的重要组成部分，作为计算机科学中非正式的定义，算法是按部就班解决某个问题的方法。具体到计算机科学中，算法是有限的、有序的、有效的计算机指令集合。算法有输入、输出，虽然步骤有限，但每一步都是有效的。算法的迭代结构有顺序搜索法、循环控制和插入排序算法。算法可以用3种方式表示，即自然语言、流程图和伪代码。自然语言有定义明确的语言基本块集合；流程图是算法图形化的表示；伪代码是算法的符号和结构化的原语表示。对于一个算法的评价，通常要从正确性、可理解性、健壮性、时间复杂度及空间复杂度等多个方面加以衡量。