搜索
第5章算法与复杂性2计算机科学导论学习目标了解算法的概念和特性、算法的描述工具、评价、算法设计策略、分布式算法、可计算性理论基础、NP问题、自动机理论、加密算法、几何算法、并行算法等。掌握几种经典算法的基本思想。一个好的算法是程序设计的关键，本章首先介绍算法的基本知识、常用算法及算法评价的基础知识，然后介绍几种常用的算法，为今后进一步学习算法及其复杂性打好基础。第5章算法与复杂性3计算机科学导论5.1算法分析基础5.1.1算法的概念算法（Algorithm）是一组明确的、可以执行步骤的有序集合，在有限的时间内终止并产生结果。算法是解决“做什么”和“怎么做”的问题。程序中的操作语句，实际上就是算法的体现。算法也可以理解为是由规定的运算顺序所构成的完整的解题步骤。4计算机科学导论5.1.2算法的特性算法反映了求解问题的方法和步骤，不同的问题需要用不同的算法来解决，同一个问题也可能有多种不同的算法。5计算机科学导论5.1.2算法的特性1.有穷性(可终止性)一个算法必须在有限的操作步骤内以及合理的时间内执行完成。2.确定性算法中的每一个操作步骤都必须有明确的含义，不允许存在二义性。6计算机科学导论3.有效性(可行性)算法中描述的操作步骤都是可执行的，并能最终得到确定的结果。①算法中每一个步骤必须能够实现，如在算法中不允许出现分母为0的情况。②算法执行的结果要能够达到预期的目的，实现预定的功能。5.1.2算法的特性7计算机科学导论4.输入数据与输出数据的要求一个算法应该有0个或多个输入数据、有1个或多个输出数据。5.1.2算法的特性8计算机科学导论1.递归算法2.迭代算法3.穷举算法4.贪婪算法5.2常用算法介绍9计算机科学导论1.递归算法若一个算法直接地或间接地调用自己本身，则称这个算法是递归算法。例如：阶乘函数的定义1当n=0时n！=n*(n-1)！当n0时5.2常用算法介绍10计算机科学导论设计模拟汉诺塔问题求解过程的算法。汉诺塔问题的描述是：设有3根标号为A，B，C的柱子，在A柱上放着n个盘子，每一个都比下面的略小一点，要求把A柱上的盘子全部移到C柱上，移动的规则是：（1）一次只能移动一个盘子；（2）移动过程中大盘子不能放在小盘子上面；（3）在移动过程中盘子可以放在A，B，C的任意一个柱子上。问题分析：可以用递归方法求解n个盘子的汉诺塔问题。基本思想：1个盘子的汉诺塔问题可直接移动。n个盘子的汉诺塔问题可递归表示为，首先把上边的n-1个盘子从A柱移到B柱，然后把最下边的一个盘子从A柱移到C柱，最后把移到B柱的n-1个盘子再移到C柱。4个盘子汉诺塔问题的递归求解示意图如下图所示。11计算机科学导论•例：汉诺塔问题的递归求解过程2134ABC4ABC213ABC2134ABC2134(a)(b)(c)(d)12计算机科学导论5.3算法描述工具算法是要通过程序才能加以实现的。常用的算法描述方式有:1.自然语言2.流程图3.伪代码13计算机科学导论5.3算法描述工具1.自然语言自然语言就是人们日常使用的语言，可以是中文、英文等。14计算机科学导论•案例：判断2000～2500年中的每一年是否为闰年。•闰年的条件：•能被4整除，但不能被100整除的年份；•能被100整除，又能被400整除的年份；（如2004年就是闰年,1901年不是闰年，2000年是闰年，1900年不是闰年)5.3算法描述工具15计算机科学导论5.3算法描述工具16计算机科学导论自然语言S1：2000→y；S2：若y不能被4整除，则输出y“不是闰年”，然后转到S6；S3：若y能被4整除，不能被100整除，则输出y“是闰年”，然后转到S6；S4：若y能被100整除，又能被400整除，输出y“是闰年”，然后转到S6；S5：输出y“不是闰年”，然后转到S6；S6：y+1→y；S7：当y≤2500时,返回S2继续执行，否则结束。17计算机科学导论自然语言•使用自然语言描述算法的优缺点：•优点：•通俗易懂•缺点：•文字冗长•含义不太严格，容易出现歧义18计算机科学导论2.流程图流程图是用规定的一组图形符号、流程线和文字说明来描述算法的一种表示方法。5.3算法描述工具19计算机科学导论2.流程图(1)顺序结构。程序执行完A语句后接着执行B语句。5.3算法描述工具AB20计算机科学导论2.流程图(2)选择结构。当条件P成立时，则执行A语句，否则执行B语句。5.3算法描述工具PYNAB21计算机科学导论2.流程图(3)当型循环结构。当条件P成立时，则循环执行A语句。5.3算法描述工具当P成立A22计算机科学导论2.流程图(4)直到型循环结构。循环执行A语句，直到条件P成立为止。5.3算法描述工具A直到P成立23计算机科学导论•案例：判断2000～2500年中的每一年是否为闰年。•闰年的条件：•能被4整除，但不能被100整除的年份；•能被100整除，又能被400整除的年份；（如2004年就是闰年,1901年不是闰年，2000年是闰年，1900年不是闰年)5.3算法描述工具24计算机科学导论流程图y+1=y打印“非闰年”不为0否是25计算机科学导论流程图•优点：•直观易懂•缺点：•画起来比较麻烦，不易修改26计算机科学导论3.伪代码伪代码是用一种介于自然语言与计算机语言之间的文字和符号来描述算法，它比计算机语言形式灵活、格式紧凑，没有严格的语法。5.3算法描述工具27计算机科学导论伪代码BEGIN（算法开始）2000＝ywhiley=2500{ify能被4整除ify不被100整除printy：”是闰年”elseify能被400整除printy：”是闰年”elseprinty：”非闰年”endifendifelseprinty：”非闰年”endify＋1＝y}END(算法结束)28计算机科学导论5.3算法描述工具常用的算法描述方式有:1.自然语言2.流程图3.伪代码29计算机科学导论5.4算法的评价对于一个算法的评价，通常要从正确性、可理解性、健壮性、时间复杂度(TimeComplexity)及空间复杂度(SpaceComplexity)等多个方面加以衡量。1．算法的时间复杂度时间复杂度是度量时间的复杂性，即算法的时间效率的指标。2．算法的空间复杂度算法的空间复杂度是度量空间的复杂性，即执行算法的程序在计算机中运行时所占用空间的大小。30计算机科学导论算法的时间复杂度•时间复杂度：撇开与计算机硬件、软件有关的因素，可以认为一个特定算法“运行工作量”的大小，只依赖于问题的规模，或者说它是问题规模的函数。•常从算法中选取一种与求解问题相关的基本操作，以该基本操作的重复执行次数作为算法时间量度的依据，如时间复杂度在n级，n的平方级，n的立方级，n的指数级等。31计算机科学导论算法的空间复杂度•空间复杂度：作为算法所需存储空间的量度。存储空间指算法所处理的数据所需的存储空间与算法操作所需的辅助空间之和。•设n为问题规模的大小，f（n）为存储空间，空间复杂度是以f（n）为变量的函数。类似地，也有n级，n的平方级，n的立方级，n的指数级等区分。32计算机科学导论5.10加密算法数据加密的基本过程就是对原来为明文的文件或数据按某种算法进行处理，使其成为不可读的一段代码，通常称为“密文”该过程的逆过程为解密，即将该编码信息转化为其原来数据的过程。加密技术通常分为“对称式”和“非对称式”两大类。对称式加密就是加密和解密使用同一个密钥，非对称式加密就是加密和解密所使用的不是同一个密钥，通常有两个密钥，称为“公钥”和“私钥”，它们两个必须配对使用，否则不能打开加密文件。33计算机科学导论密码技术Thisisabook!@#$~%^~&~*()-Thisisabook!@#$~%^~&~*()-加密解密明文、密文、加密、解密、密钥对称密码技术、非对称密码技术34计算机科学导论对称密码技术•对称密码技术又叫传统密码算法，其特点是加密密钥和解密密钥相同，或者由其中一个可以很容易推算出另外一个。35计算机科学导论对称密码技术加密算法E密钥K明文M密钥K传输明文M发送方接收方密文C密文C解密算法D例如：明文M=abcdefg，密钥K=3，加密算法E为将明文字符的ascii和密钥相加，则密文C=(a+3)(b+3)(c+3)(d+3)(e+3)(f+3)(g+3)=defghij。同理，解密算法D为密文减去密钥，则明文M=(d-3)(e-3)(f-3)(g-3)(h-3)(i-3)(j-3)=abcdefg。36计算机科学导论对非称密码技术•非对称密码技术需要两个密钥，其中一个密钥完全公开，任何人都可以获得，称之为公钥，另一个密钥只有用户自己知道，称之为私钥。•公钥和私钥是相互关联的一对，但却不能由一个推导出另外一个，如果用公钥加密，则只能由相应的私钥进行解密。37计算机科学导论对非称密码技术加密算法EB的公钥明文MB的私钥传输明文M发送方A接收方B密文C密文C解密算法D38计算机科学导论常见加密算法有如下：(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加密算法