ch1算法设计与分析基础.ppt

《ch1算法设计与分析基础.ppt》由会员分享，可在线阅读，更多相关《ch1算法设计与分析基础.ppt（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、广东工业大学广东工业大学计算机学院计算机学院算法设计算法设计与分析与分析 The The Design and Analysis of Algorithms凌 捷广东工业大学计算机学院 2023/1/42023/1/41 1LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院本课程的安排本课程的安排平时成绩30%(设计、作业、考勤、提问等）期末考试70%第15周周四随堂考试（考查）学习建议：1、注重算法的编程实现 2、大部分内容是了解（36学时）2023/1/42023/1/42 2LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学

2、计算机学院计算机学院第第1章章 绪绪 论论主要内容：1.1 算法的概念 1.2 算法问题求解的基础 1.3 重要问题类型 1.4 基本数据结构2023/1/42023/1/43 3LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院1.1 算法的概念1 1、算法概念、算法概念没有一个统一的严谨的定义。一般而言，对于计没有一个统一的严谨的定义。一般而言，对于计算机算法的概念是这样描述的：算法是在有限步算机算法的概念是这样描述的：算法是在有限步骤内求解某一问题所使用的一组定义明确的指令。骤内求解某一问题所使用的一组定义明确的指令。本书采用的定义：本书采用的定

3、义：An An algorithmalgorithm is a sequence of is a sequence of unambiguous instructions for solving a unambiguous instructions for solving a problem=problem=算法是求解某一问题所使用的一系列清算法是求解某一问题所使用的一系列清晰的指令。晰的指令。2023/1/42023/1/44 4LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院2、算法的概念图、算法的概念图注意：计算机发明以前也有算法问题问题算法算

4、法“计算机计算机”输出输出输入输入2023/1/42023/1/45 5LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院3、算法的三个要素、算法的三个要素 1).数据:运算序列中作为运算对象和结果的数据.2).运算:运算序列中的各种运算:赋值,算术和逻辑运算 3).控制和转移:运算序列中的控制和转移.2023/1/42023/1/46 6LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院4、算法的一般特征、算法的一般特征 1).1).有穷性有穷性 finitenessfiniteness 算法必须在执行有穷步

5、后终止算法必须在执行有穷步后终止,且每一步均在有且每一步均在有限时间内完成限时间内完成 2).2).确定性确定性 definiteness definiteness 算法的每个步骤必须有明确的意义算法的每个步骤必须有明确的意义,对每种可能对每种可能的情况的情况,算法都要给出确定的操作算法都要给出确定的操作.3).3).能行性能行性effectivenesseffectiveness 算法中的每个步骤是能够实现的算法中的每个步骤是能够实现的,算法执行结果算法执行结果要达到预期目的要达到预期目的 4).4).有有0 0个或多个输入项个或多个输入项,至少有一个输出项至少有一个输出项.2023/1/4

6、2023/1/47 7LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院举例举例举例举例:计算最大公约数的欧几里德算法计算最大公约数的欧几里德算法计算最大公约数的欧几里德算法计算最大公约数的欧几里德算法ALGORITHM EuclidALGORITHM Euclid（mm，n n）/计算两个整数计算两个整数mm、n n的最大公约数的最大公约数gcdgcd（mm，n n）/输入：非负整数输入：非负整数mm，n n，其中，其中mm，n n不同时为零不同时为零/输出：输出：mm，n n的最大公约数的最大公约数while n 0 dowhile n 0 dor

7、 r m mod n m mod nmm n nn n r rreturn mreturn m2023/1/42023/1/48 8LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院求求求求gcd(m,ngcd(m,n)的原理：的原理：的原理：的原理：（结构化的描述）（结构化的描述）第一步：如果第一步：如果n=0,n=0,返回返回mm的值作为结果，结束；否则进入的值作为结果，结束；否则进入 第二步。第二步。第二步：用第二步：用n n除除m,m,余数赋值给余数赋值给r r，进入第三步。，进入第三步。第三步：将第三步：将n n的值赋给的值赋给mm，将，将r

8、 r的值赋给的值赋给n n，返回第一步。，返回第一步。例：例：gcd(60,24)=?gcd(60,24)=?1-1 1-1、m=60,n=24m=60,n=24 1-2 1-2、60 mod 24=12,r=12,60 mod 24=12,r=12,1-3 1-3、m=24,n=12m=24,n=12 2-1 2-1、24 mod 12=0,r=024 mod 12=0,r=0 2-2 2-2、m=12,n=0m=12,n=0 2-32-3、条件、条件“n=0”n=0”满足，返回满足，返回gcd(mgcd(m,n)=m=12,n)=m=122023/1/42023/1/49 9LingJie

9、/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院求求求求gcd(m,ngcd(m,n)的其他算法的其他算法的其他算法的其他算法算法二：连续整数检测法算法二：连续整数检测法第一步：将第一步：将minm,nminm,n 赋值给赋值给t t。第二步：第二步：mm除以除以t t，如果余数为，如果余数为0 0，进入第三步，否则进入第四步。，进入第三步，否则进入第四步。第三步：第三步：n n除以除以t t，如果余数为，如果余数为0 0，返回，返回t t的值；否则进入第四步。的值；否则进入第四步。第四步：把第四步：把t t的值减的值减1 1，返回第三步。，返回第三步。例：例：g

10、cd(60,24)gcd(60,24)t=min60,24=24,m=60,n=24t=min60,24=24,m=60,n=24 60mod24=120,60mod24=120,t=23,24 mod 23=1 0t=23,24 mod 23=1 0t=22,24 mod 22=2 0t=22,24 mod 22=2 0t=21,24 mod 21=3 0t=21,24 mod 21=3 0.t=12,24 mod 12=0,t=12,24 mod 12=0,返回返回gcd(mgcd(m,n)=t=12,n)=t=122023/1/42023/1/41010LingJie/GDUTLingJ

11、ie/GDUT广东工业大学广东工业大学计算机学院计算机学院算法三：质因数分解法算法三：质因数分解法第一步：找出第一步：找出mm的所有质因数。的所有质因数。第二步：找出第二步：找出n n的所有质因数。的所有质因数。第三步：从第一步求得的第三步：从第一步求得的mm的质因数分解式和第二步求得的的质因数分解式和第二步求得的n n 的质因数分解式中，找出所有公因数。的质因数分解式中，找出所有公因数。第四步：将第三步找到的公因数相乘，结果为所求的第四步：将第三步找到的公因数相乘，结果为所求的 gcd(m,ngcd(m,n)例：例：m=60=m=60=22322355 n=24=2 n=24=2223223

12、 公因数为公因数为 223223 结果为结果为 gcd(m,ngcd(m,n)=12)=12存在问题：如何求所有的质因数存在问题：如何求所有的质因数/素因子？素因子？2023/1/42023/1/41111LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院求连续素数序列的筛法求连续素数序列的筛法求连续素数序列的筛法求连续素数序列的筛法-2 23 34 45 56 67 78 89 910101111 12121313141415151616 17171818191920202121 2222232324242525问题：问题：求不大于n=25的质数 序

13、列。筛法：1、取 p=2，消去p的倍数。2、取 p=3，消去p的倍数。直至 p=?结束2023/1/42023/1/41212LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院-2*2*3 34 45 56 67 78 89 91010111112121313141415151616171718181919202021212222232324242525-2 23*3*5 57 79 911111313151517171919212123232525-2 23 35*5*7 7111113131717191923232525-2 23 35 57 71

14、11113131717191923232023/1/42023/1/41313LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院求连续素数序列的筛法求连续素数序列的筛法求连续素数序列的筛法求连续素数序列的筛法Sieve(nSieve(n)For p=2 to n do /For p=2 to n do /设立数组设立数组A2AnA2An ApAp=p=pFor p=2 to do /For p=2 to do /if Ap0,j=p*p if Ap0,j=p*p while j=n do while j=n do AjAj=0=0 j=j=j+pj+p

15、i=0 /i=0 /将将A A中剩余的元素复制到数组中剩余的元素复制到数组L L供连续输出供连续输出For p=2 to n doFor p=2 to n do if Ap0,if Ap0,LiLi=ApAp i=i+1 i=i+1Return L Return L 2023/1/42023/1/41414LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院5、算法的分类、算法的分类从解法上分：从解法上分：优化算法优化算法:算法中的基本运算为逻辑运算。算法中的基本运算为逻辑运算。数值算法数值算法:算法中的基本运算为算术运算。算法中的基本运算为算术运算。从

16、处理方式上分：从处理方式上分：串行算法串行算法:串行计算机上执行的算法。串行计算机上执行的算法。并行算法并行算法:并行计算机上执行的算法。并行计算机上执行的算法。2023/1/42023/1/41515LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院1.2 算法问题求解基础 观点观点:算法是问题的程序化解决方案算法是问题的程序化解决方案 算法设计与分析过程的典型步骤算法设计与分析过程的典型步骤:1 1、了解问题的内容、了解问题的内容 2 2、了解计算设备的性能、了解计算设备的性能 3 3、在精确解法和近似解法之间选择、在精确解法和近似解法之间选择 4

17、 4、确定适当的数据结构、确定适当的数据结构 5 5、算法设计技术、算法设计技术 6 6、详细表述算法的方法、详细表述算法的方法 7 7、证明算法的正确性、证明算法的正确性 8 8、分析算法、分析算法 9 9、为算法写代码、为算法写代码2023/1/42023/1/41616LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院图图1.2 1.2 算法设计与分析的过程算法设计与分析的过程2023/1/42023/1/41717LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院1.2.1 了解问题的内容当遇到一个问题

18、时，首先要清楚这个问题的所当遇到一个问题时，首先要清楚这个问题的所有内容。如果这个问题已经给出了明显的要求，有内容。如果这个问题已经给出了明显的要求，如对成绩排序，那么只需要看看它是属于那一如对成绩排序，那么只需要看看它是属于那一类的问题，然后参考相关的资料。类的问题，然后参考相关的资料。了解问题内容这个步骤是十分重要的，因为只了解问题内容这个步骤是十分重要的，因为只有知道了问题具有什么样的输入，需要得到什有知道了问题具有什么样的输入，需要得到什么样的输出，问题的解决才可能进行下去。理么样的输出，问题的解决才可能进行下去。理解了问题是问题求解的关键。解了问题是问题求解的关键。2023/1/42

19、023/1/41818LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院1.2.2 了解计算设备的能力 在清楚了解了问题的内容之后，下一步是确定在清楚了解了问题的内容之后，下一步是确定用于解决问题的设备的能力。目前一般使用的用于解决问题的设备的能力。目前一般使用的计算机都是冯诺依曼（计算机都是冯诺依曼（von Neumannvon Neumann）体系架）体系架构的。它的一个最重要假设是，程序指令的执构的。它的一个最重要假设是，程序指令的执行是顺序的。针对这一类计算机设计的算法被行是顺序的。针对这一类计算机设计的算法被称为串行算法（称为串行算法（seq

20、uential algorithmssequential algorithms）。与）。与之相区别的是所谓的并行计算机以及并行算法之相区别的是所谓的并行计算机以及并行算法（parallel algorithmsparallel algorithms）。指令能够并行的执行，）。指令能够并行的执行，效率当然会大大提高，额外需要考虑的则是指效率当然会大大提高，额外需要考虑的则是指令执行顺序以及同步等问题。并行算法的设计令执行顺序以及同步等问题。并行算法的设计有相应的理论，这里仅考虑串行算法。有相应的理论，这里仅考虑串行算法。2023/1/42023/1/41919LingJie/GDUTLingJi

21、e/GDUT广东工业大学广东工业大学计算机学院计算机学院1.2.3 选择精确或者近似的算法 解决问题下一步要考虑的是使用精确的还是近解决问题下一步要考虑的是使用精确的还是近似的算法。并不是每一个可解的问题都有精确似的算法。并不是每一个可解的问题都有精确的算法，例如求一个数的平方根，求非线性方的算法，例如求一个数的平方根，求非线性方程的解等。有时候一个问题有精确的解法但是程的解等。有时候一个问题有精确的解法但是算法的执行效率很差，例如旅行家问题。因此算法的执行效率很差，例如旅行家问题。因此如果待处理的问题涉及到上述那些方面，则要如果待处理的问题涉及到上述那些方面，则要考虑是选择精确的还是近似的算

22、法。考虑是选择精确的还是近似的算法。2023/1/42023/1/42020LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院1.2.4 确定合适的数据结构 许多程序设计的教程都提到：程序设计算法许多程序设计的教程都提到：程序设计算法数据结构（数据结构（Programs=Algorithms+Data Programs=Algorithms+Data StructuresStructures），由此可以看出数据结构对算法），由此可以看出数据结构对算法的重要性。例如在处理搜索问题时，对于仅仅的重要性。例如在处理搜索问题时，对于仅仅进行搜索的算法只需要用到

23、简单的数组即可，进行搜索的算法只需要用到简单的数组即可，如果搜索后伴随着插入删除操作时，那么用链如果搜索后伴随着插入删除操作时，那么用链表以及堆等复杂的数据结构的算法更加可取。表以及堆等复杂的数据结构的算法更加可取。2023/1/42023/1/42121LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院1.2.5 选择算法设计技术 算法设计技术（算法设计技术（algorithm design techniquealgorithm design technique）或者算法设计策略（或者算法设计策略（strategystrategy）指的是解决一）指的

24、是解决一系列不同问题的通用设计思想。常用的设计技系列不同问题的通用设计思想。常用的设计技术包括分治法（术包括分治法（Divide and ConquerDivide and Conquer），贪婪），贪婪法（法（Greedy TechniqueGreedy Technique），动态规划），动态规划（Dynamic ProgrammingDynamic Programming），回溯法），回溯法（BacktrackingBacktracking），分支限定法（），分支限定法（Branch and Branch and BoundBound）等。）等。2023/1/42023/1/42222Li

25、ngJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院1.2.6 详细表述该算法的方法 可以用到的工具有自然语言（可以用到的工具有自然语言（nature nature languagelanguage）、伪代码（）、伪代码（pseudocodepseudocode）以及程序）以及程序流程图（流程图（flow chartflow chart）等。）等。当对一个问题有了概要的理解后，下面的工作当对一个问题有了概要的理解后，下面的工作就是把这个问题的想法进行细化。所谓的细化就是把这个问题的想法进行细化。所谓的细化就是把它们表示成算法的步骤。就是把它们表示成算法的步骤

26、。2023/1/42023/1/42323LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院1.2.7 确认算法的正确性 当给算法一个合法输入，而该算法给出一个错当给算法一个合法输入，而该算法给出一个错误的结果时，可以证明这个算法是错误的。但误的结果时，可以证明这个算法是错误的。但如果证明一个算法是正确，情况就不是那样地如果证明一个算法是正确，情况就不是那样地简单。算法的测试有一套完整的理论，这里不简单。算法的测试有一套完整的理论，这里不作详细叙述。作详细叙述。特别需要提出的是，所谓算法的正确性指的是：特别需要提出的是，所谓算法的正确性指的是：对于任意

27、合法的输入在有限时间内都能得到正对于任意合法的输入在有限时间内都能得到正确的结果。如果算法是一个近似算法，那么正确的结果。如果算法是一个近似算法，那么正确性则是指输出结果与理论结果之间的误差在确性则是指输出结果与理论结果之间的误差在一个可以接受的范围内。一个可以接受的范围内。2023/1/42023/1/42424LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院1.2.8 对算法的分析 时空的观点时空的观点 发展的观点：算法的适应性（发展的观点：算法的适应性（generalitygenerality）最强）最强 设计的观点：算法的设计时间最少设计的观

28、点：算法的设计时间最少 交流的观点：算法最容易理解（交流的观点：算法最容易理解（simplicitysimplicity）2023/1/42023/1/42525LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院1.2.9 为算法写代码目前而言，大部分的算法最后还是需要通过程目前而言，大部分的算法最后还是需要通过程序语言进行实现。针对不同的问题，还需要考序语言进行实现。针对不同的问题，还需要考虑什么样的程序语言才是最适合的，这与个人虑什么样的程序语言才是最适合的，这与个人的知识组成以及程序语言本身的特性等有关。的知识组成以及程序语言本身的特性等有关。部

29、分的程序语言可能需要对算法进行修改以适部分的程序语言可能需要对算法进行修改以适应这种语言本身。例如广泛用于科学计算的应这种语言本身。例如广泛用于科学计算的MatlabMatlab语言，它是基于矩阵的语言，提供了大语言，它是基于矩阵的语言，提供了大量数值计算的函数，然而它的循环计算能力相量数值计算的函数，然而它的循环计算能力相对较弱，所以如果把算法中涉及循环的过程通对较弱，所以如果把算法中涉及循环的过程通过向量的形式进行，那么最终的效率将能得到过向量的形式进行，那么最终的效率将能得到很大的提高。很大的提高。2023/1/42023/1/42626LingJie/GDUTLingJie/GDUT广

30、东工业大学广东工业大学计算机学院计算机学院1.3 重要问题的类型排序问题（排序问题（SortingSorting）查找查找/搜索问题（搜索问题（SearchingSearching）串处理问题（串处理问题（String problemsString problems）图论问题（图论问题（Graph problemsGraph problems）组合问题（组合问题（Combinatorial problemsCombinatorial problems）几何问题（几何问题（Geometric problemsGeometric problems）数值计算问题（数值计算问题（Numerical p

31、roblemsNumerical problems）加密问题（加密问题（EncrpytionEncrpytion problems problems）2023/1/42023/1/42727LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院1.3.1 排序问题 所谓的所谓的“排序排序”就是把一组杂乱的数据按照一就是把一组杂乱的数据按照一定的规律顺次排列起来。排序是很重要的，因定的规律顺次排列起来。排序是很重要的，因为它可以使得以后的工作更加地容易。目前，为它可以使得以后的工作更加地容易。目前，计算机科学家发明了很多的排序算法，然而这计算机科学家发明了很

32、多的排序算法，然而这些排序算法中并不存在一种算法是绝对最优的。些排序算法中并不存在一种算法是绝对最优的。这里介绍几个与这里介绍几个与“排序排序”相关的重要概念：数相关的重要概念：数据表据表 、关键字、关键字 、主关键字、主关键字 、排序的稳定性、排序的稳定性 、内排序与外排序内排序与外排序 。2023/1/42023/1/42828LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院1.3.2 查找/搜索问题 所所谓谓查查找找/搜搜索索，就就是是在在数数据据集集合合中中寻寻找找满满足足某某种种条条件件的的数数据据对对象象。一一般般的的形形式式是是先先给给

33、出出一一个个特特定定值值，然然后后在在数数据据集集合合中中找找出出关关键键字字等等于于该该特特定定值值的的对对象象。对对于于搜搜索索问问题题，通通常常需需要要返返回回的的结结果果可可能能有有两两种种。一一种种是是简简单单的的搜搜索索成成功功或或者者失失败败的的信信息息；另另一一种种是是返返回回满满足足搜搜索索条条件件的的对象所在位置，如果找不到则返回不存在信息。对象所在位置，如果找不到则返回不存在信息。2023/1/42023/1/42929LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院1.3.3 串处理问题 对对于于字字符符串串处处理理的的问问题

34、题，这这里里只只是是对对其其中中一一类类特特殊殊的的问问题题进进行行讨讨论论，即即字字符符串串模模式式匹匹配配问问题题（string string matchingmatching）。问问题题是是这这样样表表述述的的：在在一一篇篇文文章章或或文文章章的的一一部部分分中中找找出出单单词词第第一一次次出出现现的的位位置置。本本书书把把字字符符串串匹匹配配问问题题作作为为一一种种特特殊殊的的搜搜索索问问题题考考虑虑，因因为为两两者者是是有有相相似似之之处处的的。最最大大的的区区别别在在于于，一一般般搜搜索索问问题题是是单单一一的的关关键键字字的的搜搜索索，而而字字符符串串匹匹配配可可以以看看作作是是

35、几几个个关关键键字字组组成成一一种种模模式式的的搜搜索索过过程程，因因此此对对模模式式的的分分析有助于算法效率的提高。析有助于算法效率的提高。2023/1/42023/1/43030LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院1.3.4 图论问题 图论问题主要是与图或树相关的问题。这里所图论问题主要是与图或树相关的问题。这里所谓的谓的“图图”指的是一些顶点（指的是一些顶点（VertexVertex）与边）与边（EdgeEdge）的集合。图有着非常重要与丰富的实）的集合。图有着非常重要与丰富的实际应用，如通信网络，交通网络，工程计划等。际应用，如通

36、信网络，交通网络，工程计划等。本书所涉及到的图论问题主要包括了图的遍历本书所涉及到的图论问题主要包括了图的遍历问题（问题（Graph TraversalGraph Traversal），最短路径问题以及），最短路径问题以及图的特例图的特例树结构的排序、搜索中的应用问树结构的排序、搜索中的应用问题。题。2023/1/42023/1/43131LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院1.3.5 组合问题现代的组合数学所涉及的领域更加广阔，其中现代的组合数学所涉及的领域更加广阔，其中的问题出自抽象代数、拓扑学、数学基础、图的问题出自抽象代数、拓扑学

37、、数学基础、图论、博弈论、线性规划以及其他许多领域。值论、博弈论、线性规划以及其他许多领域。值得注意的是，这些来源不同的问题不能在一个得注意的是，这些来源不同的问题不能在一个统一的理论体系中得到有效的解决，而且随着统一的理论体系中得到有效的解决，而且随着问题的输入量的增加，问题的规模急剧增长至问题的输入量的增加，问题的规模急剧增长至计算机的处理能力的极限，所以可以说组合数计算机的处理能力的极限，所以可以说组合数学问题是最难的一类问题。学问题是最难的一类问题。2023/1/42023/1/43232LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院1.3

38、.6 几何问题几何问题是几何数学上与点、线、多边形相关几何问题是几何数学上与点、线、多边形相关的问题。当然，这不是一本几何学的书，所以的问题。当然，这不是一本几何学的书，所以这里只会涉及如直线段的表示、相交判断等基这里只会涉及如直线段的表示、相交判断等基本问题。同时还会给出最近邻点问题与凸包问本问题。同时还会给出最近邻点问题与凸包问题这两个重要问题的介绍。它们都有穷举法与题这两个重要问题的介绍。它们都有穷举法与分治法的算法版本，通过比较，可以深入体会分治法的算法版本，通过比较，可以深入体会到其中所用到的算法设计思想。到其中所用到的算法设计思想。2023/1/42023/1/43333LingJ

39、ie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院1.3.7 数值问题 数值计算问题是另一大类问题，它要解决的问数值计算问题是另一大类问题，它要解决的问题包括：求解方程或者方程组，求数值积分等。题包括：求解方程或者方程组，求数值积分等。这些问题常常只能给出一个近似的结果，而不这些问题常常只能给出一个近似的结果，而不是精确的解析解。并且这些问题常涉及到具体是精确的解析解。并且这些问题常涉及到具体的数据，由于计算机对数字表示的精度问题，的数据，由于计算机对数字表示的精度问题，所以还需要考虑可能带来的误差以及这些误差所以还需要考虑可能带来的误差以及这些误差对算法稳定性

40、的影响。对算法稳定性的影响。2023/1/42023/1/43434LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院1.3.8 加密问题加密问题是信息安全的基础，它要解决的问题加密问题是信息安全的基础，它要解决的问题包括：通信双方的相互鉴定，消息完整性的确包括：通信双方的相互鉴定，消息完整性的确定以及公开密钥的分发等。这些安全问题的解定以及公开密钥的分发等。这些安全问题的解决方案依赖于加密算法的发展，如决方案依赖于加密算法的发展，如DESDES算法、算法、RSARSA算法以及算法以及MD5MD5算法都是目前广泛使用的加算法都是目前广泛使用的加密算法。

41、密算法。2023/1/42023/1/43535LingJie/GDUTLingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院算法设计分析经典题目举例递归序列的求解递归序列的求解 约瑟夫问题约瑟夫问题 黑白棋黑白棋猜数字游戏猜数字游戏 天平称球问题天平称球问题 项链问题项链问题MD5MD5加密加密 网络搜索引擎网络搜索引擎 2023/1/42023/1/43636LingJie/GDUTLingJie/GDUT计算机算法研究的两个方向v优化优化优化优化寻找更好的算法寻找更好的算法寻找更好的算法寻找更好的算法设计技巧设计技巧设计技巧设计技巧一个新的算法（上界）一个新的算法（上界）一个新的算法（上界）一个新的算法（上界）v可能性可能性可能性可能性说明难以得到更好的算法说明难以得到更好的算法说明难以得到更好的算法说明难以得到更好的算法证明技巧证明技巧证明技巧证明技巧对问题的更好认识（下界）对问题的更好认识（下界）对问题的更好认识（下界）对问题的更好认识（下界）37LingJie/GDUT广东工业大学广东工业大学计算机学院计算机学院谢谢 谢谢!2023/1/42023/1/43838LingJie/GDUTLingJie/GDUT