计算机科学导论第5章 算法与复杂性

1、、5章算法和复杂性、学习目标算法的概念和特性、算法的说明工具、评估、算法设计策略、分布式算法、可计算性理论基础、NP问题、机器人理论、加密算法、几何算法、并行算法等。掌握几种经典算法的基本思想。好的算法是编程的核心，本章首先介绍了算法的基本知识、常用算法和算法评价的基本知识，然后介绍了一些常用算法，为以后算法及其复杂性的进一步学习奠定了基础。5章算法和复杂性，5.1算法分析了基本5 . 1 . 1 . 1算法的概念，算法(Algorithm)是清晰有序的集合，可以执行在有限时间内结束和产生结果的步骤。算法是解决“做什么”和“怎么做”的问题。程序的工作语句实际上是算法的实现。算法也可以理解为由确

2、定的运算顺序组成的完整的故障诊断阶段。5.1.2算法的特性，算法反映了解决问题的方法和步骤，其他问题需要用其他算法解决，同一问题可以有多种不同的算法。5.1.2算法的特性，1 .有穷(终止可能性)的算法必须在有限的操作阶段内完成，并在合理的时间内完成。2.确定性算法的每个操作步骤都必须有明确的含义，不允许异议。3 .有效性(可行性)算法中描述的所有操作步骤都是可执行的，并且可以获得最终结果。算法的每个步骤都必须能够实现，例如算法不允许分母为零。必须实现预定的功能，以便执行算法的结果达到预定的目的。5.1.2算法的特性，4 .输入和输出数据要求算法必须包含零个或多个输入数据，一个或多个输出数据。

3、5.1.2算法的特性，1 .递归算法2。迭代算法3。彻底的算法4。贪心算法，5.2常用算法说明，如果一种算法直接或间接调用自身，则它是递归算法。例如：阶乘函数的定义1 n=0点n！=n*(n-1)！N0到5.2介绍了设计模拟汉诺威问题解决过程的算法的一般算法。汉诺塔问题的说明如下。标有a、b、c的三根柱子在a列上放上n个板，每个板比下面的板小一点，a列上的板都要移到c列上的规则是(1)一次只能移动一个板；(2)移动的时候，大碟子不能放在小碟子上。(。(3)移动时，盘子可以放在a，b，c的任何柱子上。问题分析：可以递归解决n个板块的汉诺威问题。基本想法：一盘汉诺塔问题可以直接移动。有n个盘子的h

4、anota问题可以递归表示：首先将顶部的n-1板从a柱移动到b柱，然后将底部板从a柱移动回c柱，再将b-柱的n-1板移动回c柱，依此类推。四板汉诺塔问题的递归解法如下图所示。例如，hanota问题的递归解决过程，5.3算法描述了通过程序实现算法的工具。常用算法为： 1。自然语言2。流程图3 .伪代码，5.3算法描述工具，1 .自然语言自然语言是人们每天使用的语言，可以是汉语、英语等。方案：确定2002500年是否为闰年。闰年的条件：可以被4整除，但不能被100整除的年；可分为100和400的一年；(如果2004年是闰年，1901年不是闰年，2000年是闰年，1900年不是闰年)，5.3算法说明

5、工具，5.3算法说明工具，自然语言，S1:2000y；S2:如果y不能除以4，则y输出“不是闰年”，然后转至S6。S3:如果y可除以4，不能除以100，则y输出为“闰年”，并转至S6。S4:如果y可除以100，可除以400，则y输出为“闰年”，并转至S6。S5:输出y“不是闰年”，然后转到S6；S6:y 1y；S7:如果是y2500，请返回S2继续。否则，将退出。说明使用自然语言、自然语言的算法的优缺点：优点：通俗易懂的缺点：字的长义不太严格，容易产生歧义，2 .流程图流程图用一系列规定的图形符号、流线和文字说明说明了算法的一种表示方法。5.3算法描述工具，2 .流程图顺序结构。程序执行a语句

6、后执行b语句。5.3算法描述工具，2 .流程图(2)选择结构。如果条件p为真，则执行a语句，否则执行b语句。5.3算法描述工具，2 .流程图(3)循环结构。如果设置了条件p，则a语句将循环。5.3算法描述工具，2 .流程图(4)为基础的回路结构。循环执行a语句，直到设置了条件p。5.3算法说明工具，案例：确定2002500年的年份是否为闰年。闰年的条件：可以被4整除，但不能被100整除的年；可分为100和400的一年；2004年是闰年，1901年不是闰年，2000年是闰年，1900年不是闰年，5.3算法是工具，流程图，y 1=y，“非闰年”打印，0，否，是，流程图打印，优点：直观易懂的缺点伪代

7、码伪代码用自然语言和计算机语言之间的字符和符号描述算法，没有比计算机语言格式更灵活、更紧凑、更严格的语法。5.3算法描述工具，伪代码，启动算法2000y while YY END，5.3算法描述工具， 1。自然语言2。流程图3 .伪代码、5.4算法的评估、算法评估通常在准确性、理解力、健壮性、时间复杂性、空间复杂性等方面进行测量。1算法的时间复杂性时间复杂性是衡量时间复杂性的指标，即算法的时间效率。2算法的空间复杂性算法的空间复杂性是测量空间的复杂性，即运行算法的程序在计算机上运行时占用的空间量。算法的时间复杂性，时间复杂性：除计算机硬件、软件相关因素外，可以根据问题的大小将特定算法视为“工作

8、量执行”的大小或问题的大小函数。在频繁算法中，选择与故障排除相关的默认操作。使用此基本任务的迭代执行次数作为算法时间测量的基准(例如，时间复杂性为n，n的平方，n的立方，n的指数等)。算法的空间复杂性，空间复杂性：算法所需存储空间的测量。存储空间是算法处理的数据所需的存储空间和算法操作所需的辅助空间的总和。将n设置为问题大小，f(n)作为存储空间，空间复杂性将f(n)设置为变量函数。同样，它分为n个级别、n的平方级别、n的立方级别、n的指数级别等。5.10加密算法，数据加密的基本过程是将原始纯文本文件或数据变成无法读取的代码片段的算法。通常称为“密文”的过程的反向过程是解密，即转换为原始数据的

9、过程。加密技术一般分为两类：“对称”和“不对称”。对称加密是对加密和解密使用相同的密钥；不对称加密不是对加密和解密使用相同的密钥，而是通常有两个密钥(称为“公钥”和“私钥”)，两者必须成对使用。否则，无法打开加密文件。密码技术、明文、密文、加密、解密、密钥、对称密码技术、对称密码技术、对称密码技术(也称为传统密码算法)的特点是加密密钥和解密密钥相同，或者可以很容易地找出其中的一个。对称密码技术，如明文M=abcdefg，密钥K=3，加密算法e将明文字符的ascii和密钥相加时的密文c=(a 3)(b 3)(c 3)(d 3)(e 3)(e 3)同样，解密算法d在密文中减去密钥时，会显示以下信息

10、：明文m=(d-3)(e-3)(f-3)(g-3)(h-3)(I-3)(j-3)=，对于不对称密码技术，不对称密码技术需要两个密钥，其中一个密钥完全公开，任何人都可以获得，这称为公钥，另一个密钥只有用户自己知道，称为私钥。公钥和私钥是相互关联的对，但是不能从一对派生另一对，如果用公钥加密，则只能用该私钥解密。典型的加密算法包括：(1)数据加密标准(DES):数据加密标准，速度快，非常适合加密大量数据。(2)3DES(三重DES):基于DES，使用三个不同的密钥对一个数据加密三次，从而提供更高的强度。(3)RC2和RC4:使用比DES更快的可变长度密钥加密大量数据。(4)国际数据加密算法(internatio