算法分析与设计2004春.课件.第01讲

《算法分析与设计2004春.课件.第01讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、算法分析与设计清华大学宋斌恒授课内容【按照层次分】¢设计理论¢分析方法¢实现技术¢测试技术¢应用范围清华大学宋斌恒21Contents【按照内容分】¢Divideandconquer【分治】¢DynamicProgramming【动态规划】¢Greedymethod【贪婪算法】¢AmortizedAnalysis【均摊分析发】¢AlgorithmsinGraphics【图论中算法】¢NP-Completeness【NP完全问题，算法理论】¢SelectedTopics【专题讲座】¢ComprehensiveTraining【综合训

2、练】清华大学宋斌恒3教学目的¢理论分析能力培养：掌握算法分析与设计的基本理论和方法，具有设计新算法和分析复杂性的能力。¢实践能力的培养：学会如何实现设计好的算法，如何测试其正确性和效率，应用与实际问题。¢团队合作能力培养：和各种能力人员合作工作能力。¢交流能力的培养：表达和接受能力。¢独立研究能力培养：具有独立开展研究的能力清华大学宋斌恒42上课的必要条件¢数据结构（没修过的请修过后再选）¢掌握一门对面向对象编程语言（C＋＋或Java）清华大学宋斌恒5基本要求¢上课不应迟到，迟到一次扣1分，自己申报，如果迟到没有申报被发现扣10分

3、。¢不得抄袭、剽窃。参考文献、著作、教材和包括其它同学的作业在内的所有资料，必须指明出处。其中¢文献、著作、教材类公开出版的参考资料，按照文献索引方式引用。有可能的话最好提供电子拷贝。¢网络资料，除指出网络路径URL，还应当提供资料电子拷贝。¢参考同学作业应当指出作业编号和提供原作业拷贝。多人讨论的成果，应当在作业中反映。¢引用他人成果而没有指出出处的以抄袭论处。如有抄袭，第一次发现，总成绩减去该阶段分值，第二次发现，成绩记0分，并以考试作弊向上汇报。清华大学宋斌恒63鼓励¢创新¢提出问题¢讨论¢根据平时情况，可以得到加分。清华大

4、学宋斌恒7教学网站¢清华大学网络学堂清华大学宋斌恒84主要参考书¢Introductiontoalgorithms,ThomasH.Cormen,etc.,secondedition,TheMITPress.¢TheArtofComputerProgramming,DonaldE.Knuth.Volume1-3,SecondEdition.¢DataStructures,Algorithms,andApplicationsinC++(Part3)SartajSahni,ChinaMachinePress¢算法设计与分析，王晓东，清

5、华大学出版社清华大学宋斌恒9综合训练报告框架和要求1.问题表述2.该问题的研究历史综述【与参考资料关系】1.该问题的最新算法【如果有比上述典型算法效率更好的算法】介绍3.该问题的典型算法介绍：1.该算法主要思想2.算法描述3.算法正确性说明或者证明4.算法复杂度理论分析5.*涉及到的理论方法总结和推广4.算法的实现与测试【分别用Java和C＋＋】：1.算法接口设计2.算法使用说明3.典型算法的实现，包括异常处理和性能估计4.典型算法实现的测试分析报告：1.结果是否正确？2.不同规模输入情况下的效率分析，是否与理论分析一致，如果不一

6、致，为什么？5.该问题的应用介绍：1.应用背景，使用条件等等2.*部分典型算法的演示软件。6.*提出该问题自己的算法7.参考资料清华大学宋斌恒105综合训练问题集¢排序（Sorting）¢大整数运算¢密码支撑运算：随机数生成、素数生成、大整数模运算、Hash运算、各类标准加密算法¢字符串【模式】匹配¢字符串相似度理论【字符串距离编辑等】¢索引与查找¢图文排版优化¢网络任务调度清华大学宋斌恒11综合练习问题集【续】¢图的所有点最短距离问题¢应用：纹理合成中的缝合法。¢图的单源最短路径¢贪婪算法理论：Matroid、Greedoid、

7、GreedSet¢旅行商问题【精确解、近似解】¢背包问题【同上】¢自选清华大学宋斌恒126课程安排介绍¢前面以介绍设计方法为主¢后面以解决问题为主清华大学宋斌恒13DivideandConquer¢DivideandConquerisamethod¢Applyingcases:¢Abigproblem,howtosolveit?¢Wecansolvesmallproblems!¢Divideitintoseveralsmallproblems,¢Solvethesesmallsub-problems!¢Next,whatshall

8、wedo?¢Combinethesub-solutiontogetthesolutionoftheoriginalproblem.清华大学宋斌恒147ExampleofaDivideandConquer¢Problem:sorting{12,3,4