1算法分析与设计.ppt
算法分析与设计Analysis and Design of Computer Algorithms 杨春明Yang Chunming西南科学技大学计算机学院 School of Computer Science and Technology,SWUST 2009年8月http:/ of Computer Science and Technology,SWUST 2Who is Yang Chunming?Instructor of SWUSTTel:6089357 13881194177Office:东6E401QQ:4879687Email:教学主页：http:/ Online平台完成。课程报告：课程结束后开始。出勤：上课的出勤情况，缺席一次扣2分，扣完为止。http:/ of Computer Science and Technology,SWUST 3课程教学方案（续）l课程考核算法设计与实现每次时间为一周到两周，完成后判断代码雷同，如果雷同率超过85%，则视为抄袭，作0分处理。http:/ of Computer Science and Technology,SWUST 4顺顺序序时间时间覆盖内容覆盖内容分分值值题题目目难难度度第一次第一次第二第二三周三周第一至三章中的第一至三章中的经经典算法典算法15分分35容易容易第二次第二次第五第五六周六周分治策略、减治法、分治策略、减治法、变变治法治法20分分58容易，中等容易，中等第三次第三次第八第八九周九周时时空空权权衡衡、动态规动态规划划15分分35中等中等，难难第四次第四次第十第十十一周十一周贪贪心策略心策略、回溯、回溯20分分46中等，中等，难难http:/ of Computer Science and Technology,SWUST 5课程教学方案（续）http:/:8080/JudgeOnline/登陆Online Judge注册http:/ of Computer Science and Technology,SWUST 6程序雷同判断http:/ of Computer Science and Technology,SWUST 7执行效果2007年：实践考核40%，分5次进行，期末考试60%，共计93人作业一作业二作业三作业四作业五提交人数6653554339完成总数3371961997172平均/人5.11 3.70 3.62 1.65 1.85 2008年：课程考核由过程（70%）、课程报告（20%）、出勤（10%）三部分组成。过程考核共计4次，共计20题，其中11题选做。51人。提交比例雷同满分比列考核14384.31%223466.67%考核24588.24%63262.75%考核33976.47%303670.59%考核43874.51%63160.78%执行情况2009年：考核方式与2008年相同，82人。过程考核统计表http:/ of Computer Science and Technology,SWUST 8提交比例雷同比例满分比列考核17793.90%22.60%7192.21%考核27692.68%56.58%6686.84%考核37793.90%1012.99%6483.12%考核47895.12%56.41%6076.92%分数段6060697079808990100人数3771550比例3.66%8.54%8.54%18.29%60.98%http:/ of Computer Science and Technology,SWUST 9About Algorithm l课程主要介绍计算机算法分析算法分析、算法设计算法设计及复杂复杂性理论性理论的基本概念、基本的算法分析方法和常用的算法设计方法。l目标：掌握计算机算法分析的基本方法及常见算法设计方法训练逻辑思维利用常见的算法设计方法解决软件开发中的实际问题l先修课程：离散数学、数据结构、高级程序设计语言。http:/ of Computer Science and Technology,SWUST 10为什么要学习算法？l算法不仅是计算机科学的一个分支，它更是计算机科学的核心，而且，可以毫不夸张地说，它和绝大多数的科学、商业和技术都是相关的。David Harel算法：计算的灵魂l程序=数据结构+算法l开发人们的分析能力l作为一种技术的算法一个人只有把知识教给“计算机”，才能“真正”掌握它。算法可以解决哪些问题l找出人类DNA中所有100000中基因，确定构成人类DNA的30亿种化学基对的各种序列。l快速地访问和检索互联网数据l电子商务活动中各种信息的加密及签名l制造业中各种资源的有效分配l确定地图中两地之间的最短路径l各种数学、几何计算（矩阵、方程、集合）http:/ of Computer Science and Technology,SWUST 11http:/ of Computer Science and Technology,SWUST 12Contents of Algorithml算法基础(Foundations)算法基本概念算法效率分析基础l算法设计及分析技巧蛮力法分治法(Divide and Conquer)减治法变治法时空权衡动态规划(Dynamic Programming)贪婪技术(Greedy Algorithm)回溯法(Back Tracking)http:/ of Computer Science and Technology,SWUST 13Referencesl1 算法设计与分析基础(第2版).（美）Anany Levitin 著，潘彦译.北京：清华大学出版社.2007年1月l2Thomas H.Cormen等著，潘金贵等译.算法导论（第二版）.机械工业出版社.2006年9月l3 C算法（第二卷 图算法）（第三版）（中文版）人民邮电出版社 2004年4月l4卢开澄（2000），计算机算法导引，清华大学出版社l5算法设计与分析.王晓东.清华大学出版社.2003年1月http:/ of Computer Science and Technology,SWUST 14How to Study Algorithm？“Sometimes we have experiences,and sometimes not.Therefore,the better way is to learn more.http:/ of Computer Science and Technology,SWUST 15Chapter 1 Introduction to AlgorithmslWhats an Algorithm?算法算法是一系列解决问题的清晰清晰清晰清晰指令，也就是说，能够对一定规范规范规范规范的输入输入输入输入，在有限有限有限有限时间内获得所要求的输出输出输出输出。AlgorithmQuestionhttp:/ of Computer Science and Technology,SWUST 16算法的几个要点l算法的每一个步骤都必须清晰、明确。l算法所处理的输入的值域必须仔细定义。l同样的一个算法可以用几种不同的形式来描述。l可能存在几种解决相同问题的算法。l针对同一个问题的算法可能会基于完全不同的解题思路，而且解题的速度也会有明显区别。http:/ of Computer Science and Technology,SWUST 17Examplel求两个正整数m,n的最大公约数gcd(m,n)l欧几里得算法基于的方法是重复应用下列式子，直到欧几里得算法基于的方法是重复应用下列式子，直到m mod n=0lgcd(m,n)=gcd(n,m mod n)gcd(m,n)的欧几里得算法的欧几里得算法第一步：如果n=0，返回m的值作为结果，结束；否则进入第二步第二步：用n去除m，将余数赋给r。第三步：将n的值赋给m，将r的值赋给n，回第一步。算法算法 Euclid(m,n)/使用欧几里得算法计算gcd(m,n)/输入：两个不全为0的非负整数m,n/输出：m，n的最大公约数While n!=0 do rm mod n mn nrReturn m同一个算法有不同的表达方式http:/ of Computer Science and Technology,SWUST 18Examplegcd(m,n)的连续整数检测算法的连续整数检测算法第一步：将minm,n的值赋给t。第二步：m除以t，如果余数为0，则进入第三步；否则，进入第四步。第三步：n除以t，如果余数为0，则返回t值作为结果；否则，进入第四步。第四步：把t的值减1。返回第二步。gcd(m,n)的中学计算算法的中学计算算法第一步：找到m的所有质因数。第二步：找到n的所有质因数第三步：从第一步和第二步中求得的质因数分解式找出所有的公因数第四步：将第三步中找的质因数相乘，其结果作为给定数字的最大公因数。同一个问题有不同的解决方法http:/ of Computer Science and Technology,SWUST 19算法问题求解基础l算法是问题的程序化解决方案解决方案。理解问题决定：计算方法；精确和近似的解法；数据结构；算法设计技术；设计算法正确性证明分析算法根据算法写代码http:/ of Computer Science and Technology,SWUST 20算法问题求解基础l理解问题设计算法前做的第一件事情仔细阅读问题的描述提出疑问手工处理一些实例考虑特殊情况确定输入抽象出问题，用数学表达式描述抽象出问题，用数学表达式描述http:/ of Computer Science and Technology,SWUST 21算法问题求解基础l了解计算设备的性能确定计算方法RAM结构下的顺序算法并行算法l选择精确解和近似解某些重要的问题无法求得精确解某些问题利用精确解速度慢，无法接受http:/ of Computer Science and Technology,SWUST 22算法问题求解基础l确定适当的数据结构算法+数据结构=程序l算法设计技术使用算法解题的一般性方法，用于解决计算领域的多种问题。l详细表述算法的方法自然语言伪代码流程图http:/ of Computer Science and Technology,SWUST 23算法问题求解基础l证明算法的正确性证明对于每一个合法的输入，该算法都会在有限的时间内输出一个满足要求的结果。一般方法：数学归纳法证明算法的正确性与不正确哪一个更容易？l分析算法算法有两种效率：时间效率和空间效率算法的另外两个特性：简单性和一般性http:/ of Computer Science and Technology,SWUST 24算法问题求解基础l为算法写代码用计算机程序实现算法在把算法转变为程序的过程中，可能会发生错误或者效率非常低作为一种规律，一个好的算法是反复努力和重新修正的结果算法是一个最优性最优性最优性最优性问题：对于给定的问题需要花费多少力气（资源）？是不是每个问题都能够用算法的方法来解决？发明或者发现算法是一个非常有创造性和非常值得付出的过程！发明或者发现算法是一个非常有创造性和非常值得付出的过程！发明或者发现算法是一个非常有创造性和非常值得付出的过程！发明或者发现算法是一个非常有创造性和非常值得付出的过程！http:/ of Computer Science and Technology,SWUST 25重要的问题类型l排序(Sorting)l查找(Search)l串处理(String)l图问题(Graph)l组合问题(Combination)l几何问题(Geometry)l数值问题岛岛河岸桥七桥问题Icosian游戏http:/ of Computer Science and Technology,SWUST 26基本数据结构l线性数据结构数组，串，单（双）链表，栈，队列l图有向图，无向图，加权图l树自由树，有根树l有序树l集合与字典http:/ of Computer Science and Technology,SWUST 27小结l“算法”是在有限时间内，对问题求解的一个清晰的指令序列。l算法可以用自然语言或伪代码描述，也可用计算机语言来描述。l对算法的分类主要有两种方法：按照求解问题的类型对算法分类按照其内在的设计技术对算法分类l重要的问题类型：排序、查找、串处理、图问题、组合问题、几何问题和数值问题。l“算法设计技术”是用算法解题的一般性方法，适用于解决不同计算领域的多种问题。l一个好的算法常常是不懈努力和反复修正的结果。l解决同一个问题的算法常常有好几种。
