搜索
海南大学信息科学技术学院CollegeofInformationScienceandTechnology,HainanUniversity算法设计与分析—本科生课程DesignandAnalysisofAlgorithm第1章算法绪论1.1算法的基本概念1.2为什么要学习和研究算法1.3重要的问题类型2020/9/10AlgorithmIntroduction2算法理论的两大论题：1.算法设计（解决问题）2.算法分析（评价，改进）本章主要知识点：1.1算法的基本概念算法及其重要特性算法的描述方法算法设计的一般过程2020/9/10AlgorithmIntroduction3算法及其重要特性算法（Algorithm）?定义1.1算法是解某一特定问题的一组有穷规则的集合。即，对特定问题求解步骤的一种描述，是指令的有限序列，有以下五大特性：输入：一个算法有零个或多个外部量作为算法的输入。输出：一个算法会产生至少一个量作为输出。有穷性：一个算法必须总是在执行有穷步之后结束，且每一步都在有穷时间内完成。确定性：算法中的每一条指令必须有确切的含义，对于相同的输入只能得到相同的输出。可行性：算法描述的操作可以通过已经实现的基本操作执行有限次来实现。2020/9/10AlgorithmIntroduction4算法及其重要特性例1.1求两个自然数的最大公约数（直观的方法）第1步：找出m的所有质因子；第2步：找出n的所有质因子；第3步：从第上述两步所得到的质因子中找出所有公因子；第4步：将所有公因子相乘，即为m和n的最大公约数2020/9/10AlgorithmIntroduction5这是算法吗？为什么？算法及其重要特性程序?是算法用某种程序设计语言的具体实现。程序可以不满足算法的性质(3)，即有穷性。“好算法”的重要特性：（1）正确性：合法的输入，都会得出正确的结果（2）健壮性：非法的输入，应能识别并处理（3）可理解性：可读性，易理解（4）抽象分级：通过抽象分级减少求解步骤（5）高效性：时间和空间效率2020/9/10AlgorithmIntroduction61.1算法的基本概念算法及其重要特性算法的描述方法算法设计的一般过程重要的问题类型2020/9/10AlgorithmIntroduction7算法的描述方法2020/9/10AlgorithmIntroduction8为了清楚准确地将算法求解的步骤记录下来，必须要描述算法，常用的方法：自然语言、流程图、程序设计语言和伪代码等⑴自然语言优点：容易理解缺点：冗长、二义性、过于抽象难于转换为程序使用方法：粗线条描述算法思想注意事项：避免写成自然段算法的描述方法2020/9/10AlgorithmIntroduction9①输入m和n；②求m除以n的余数r；③若r等于0，则n为最大公约数，算法结束；否则执行第④步；④将n的值放在m中，将r的值放在n中；⑤重新执行第②步。欧几里德算法(自然语言描述)算法的描述方法2020/9/10AlgorithmIntroduction10⑵流程图优点：流程直观缺点：严密性不及程序设计语言、灵活性不如自然语言使用方法：描述简单算法注意事项：注意抽象层次算法的描述方法2020/9/10AlgorithmIntroduction11N开始输入m和nr=m%nr=0m=n；n=r输出m结束Y欧几里德算法流程图算法的描述方法2020/9/10AlgorithmIntroduction12⑶程序设计语言优点：能由计算机执行缺点：抽象性差，对语言要求高使用方法：算法需要验证注意事项：将算法写成子函数算法的描述方法2020/9/10AlgorithmIntroduction13#includeiostream.hintCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnm;}voidmain(){coutCommonFactor(63,54)endl;}欧几里德算法算法的描述方法2020/9/10AlgorithmIntroduction14⑷伪代码——算法语言伪代码（Pseudocode）：介于自然语言和程序设计语言之间的方法，它采用某一程序设计语言的基本语法、操作指令，再结合自然语言来设计。优点：表达能力强，抽象性强，容易理解使用方法：算法语言算法的描述方法2020/9/10AlgorithmIntroduction15欧几里德算法（C++语法的伪代码表达）1.r=m%n;2.循环直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.输出n;1.1算法的基本概念为什么要学习算法算法及其重要特性算法的描述方法算法设计的一般过程重要的问题类型2020/9/10AlgorithmIntroduction16算法设计的一般过程2020/9/10AlgorithmIntroduction171．理解问题（输入、目标、输出以及用适当的数据结构来描述，在精确解和近似解间做选择）2.选择算法设计技术（蛮力法、分治法等）3．设计并描述算法4．手工运行跟踪算法（发现逻辑错误）5．分析算法的效率（时间和空间效率）6．实现算法（根据算法编写代码）1.2为什么要学习和研究算法算法在问题求解中的地位算法训练能够提高计算思维能力算法研究是推动计算机技术发展的关键2020/9/10AlgorithmIntroduction18算法在问题求解中的地位程序是蓝色的诗，算法是程序的灵魂问题的求解过程：分析问题→设计算法→编写程序→整理结果程序设计研究的四个层次：算法→方法学→语言→工具2020/9/10AlgorithmIntroduction19算法在问题求解中的地位相同问题不同的解决方案产生不同的算法，不同的算法设计出不同的程序，程序的解题思路、复杂程序、效率也不相同。例1.2求两个自然数的最大公约数[想法1]用短除法找出两个数的公因子，再相乘就是最大公约数。[算法1]找两个数的公因子目前只能用蛮力法逐个尝试，用2－min(m,n)进行枚举尝试。2020/9/10AlgorithmIntroduction20算法在问题求解中的地位算法1.1：CommFactorl（伪代码）输入：两个自然数m和n输出：m和n的最大公约数1.factor=1;2.循环变量i从2~min(m,n),执行下述操作；2.1如果i是m和n的公因子，则执行下述操作；2.1.1factor=factor*i;2.1.2m=m/i;n=n/i;2.2如果i不是m和n的公因子，则i=i+1;3.输出factor;2020/9/10AlgorithmIntroduction21算法在问题求解中的地位intCommFactorl(intm,intn){inti,factor=1;for(i=2;i=m&&i=n;i++){while(m%i==0&&n%i==0){factor=factor*i;m=m/i;n=n/i;}}returnfactor;}2020/9/10AlgorithmIntroduction22算法在问题求解中的地位[想法2]欧几里得算法效率更高。将两个数辗转相除直到余数为0。[算法2]欧几里得算法的伪代码描述。算法1.2CommFactor2输入：两个自然数m和n输出：m和n的最大公约数1.r=m%n;2.循环直到r等于02.1m=n;2.2n=r;2.3r=m%n;3.输出n;2020/9/10AlgorithmIntroduction23算法在问题求解中的地位[算法实现2]欧几里得算法的C++语言描述。intCommonFactor(intm,intn){intr=m%n;while(r!=0){m=n;n=r;r=m%n;}returnm;}2020/9/10AlgorithmIntroduction24算法在问题求解中的地位[算法比较]算法1的时间主要耗费在求余操作m%i==0&&n%i==0算法2的时间主要耗费在求余操作r=m%n但两者求余运算次数差别较大，如以求48和36最大公约数为例，算法1要进行10次求余，算法2只需两次求余。光写出一个可以正确运行的算法还不够，特别是规模较大的数据上运行的算法，效率就成为一个重要的问题。2020/9/10AlgorithmIntroduction25算法训练能够提高计算思维能力ACM/IEEE－CS提交的CC2005将计算机专业的基本学科能力归纳为：计算思维能力、算法设计与分析能力、程序设计与实现能力和系统能力。计算思维主要包括形式化、模型化、抽象思维与逻辑思维，可以从算法的角度来看，计算思维就是将人的想法抽象为算法，算法设计过程是计算思维的具体运用。算法训练就像一种思维体操，锻炼我们的思维。2020/9/10AlgorithmIntroduction26算法研究是推动计算机技术发展的关键现代计算机在计算能力和存储容量上的革命，并不会终结算法的研究，因为现实世界的复杂性远远超出计算机技术的运算能力，光靠硬件，没有“好”的算法，是难于想像的。2020/9/10AlgorithmIntroduction272020/9/10AlgorithmIntroduction281.3重要的问题类型1.查找问题2.排序问题3.图问题4.组合问题5.几何问题2020/9/10AlgorithmIntroduction291.3重要的问题类型1.查找问题在一个数据集合中查找满足给定条件的记录。没有十全十美的查找算法搜索引擎2020/9/10AlgorithmIntroduction301.3重要的问题类型2.排序问题将一个记录的无序序列调整为一个有序序列的过程。排序的主要目的是为了快速查找。同样没有十全十美的排序算法2020/9/10AlgorithmIntroduction311.3重要的问题类型3.图问题最古老最令人感兴趣。很多纷乱复杂的现实问题抽象出的数据模型都是图结构，如分子结构、排课问题、任务分配等。TSP（TravelingSalemanProblem）问题：旅行n城市回到起点，每个城市只经历一次且总路程最短。10城市180000个可能解20城市6*1016个可能解50城市1062个可能解2020/9/10AlgorithmIntroduction321.3重要的问题类型4.组合问题一般都是最优化问题，即寻找一个组合对象，能够满足特定的约束条件并使得某个目标函数取得极值。组合问题算是计算领域最难解的问题，因为：（1）随着问题规模增大，组合对象数量极快增长（爆炸）（2）绝大多数组合问题尚未找到有效算法在可接受的时间内得到正确的解。0/1背包问题：给定n个重量为{w1,w2,…,wn}、价值为{v1,v2,…,vn}的物品和一个容量为C的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。2n个可能解2020/9/10AlgorithmIntroduction331.3重要的问题类型5.几何问题处理类似于点、线、面、体等几何对象。难于符号化造成计算机难于处理。最近对问题（closestpairproblem）：在给定平台上的n个点中，求距离最近的两个点。凸包问题（convexhullproblem）:找出一个能把给定集合中的所有点都包含在里面的最小凸边形。