算法分析与设计2005春01 清华大学：算法分析与设计

《算法分析与设计2005春01 清华大学：算法分析与设计》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、授课内容【按照层次分】n设计理论算法分析与设计n分析方法n实现技术n测试技术n应用范围清华大学宋斌恒清华大学宋斌恒2Contents【按照内容分】教学目的nDivideandconquer【分治】n理论分析能力培养：掌握算法分析与设计的基nDynamicProgramming【动态规划】本理论和方法，具有设计新算法和分析复杂性nGreedymethod【贪婪算法】的能力nAmortizedAnalysis【均摊分析法】n实践能力的培养：学会如何实现设计好的算nAlgorithmsinGraphics【图论中算法】法，

2、如何测试其正确性和效率，应用与实际问nNP-Completeness【NP完全问题，算法理题论】n团队能力培养：和各种人员合作工作能力nSelectedTopics【专题讲座】n交流能力的培养：表达和接受能力nComprehensiveTraining【综合训练】n独立研究能力培养：具有独立开展研究的能力清华大学宋斌恒3清华大学宋斌恒4上课的必要条件基本要求n数据结构（没修过的请修过后再选）n上课不应迟到，迟到一次扣1分，自己申报，如果迟到没有申报被发现扣10分。n掌握一门对面向对象编程语言（C＋＋或n不得抄袭、剽窃

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

4、出问题n讨论n根据平时情况，可以得到加分。清华大学宋斌恒7清华大学宋斌恒8主要参考书综合训练报告框架和要求1.问题表述nIntroductiontoalgorithms,ThomasH.Cormen,2.该问题的研究历史综述【该问题与参考资料的关系】1.该问题的最新算法【如果有比上述典型算法效率更好的算法】介绍etc.,secondedition,TheMITPress.3.该问题的典型算法介绍：1.该算法主要思想nTheArtofComputerProgramming,DonaldE.2.算法描述3.算法正确性说明

5、或者证明Knuth.Volume1-3,SecondEdition.4.算法复杂度理论分析5.*涉及到的理论方法总结和推广4.算法的实现与测试【分别用Java和C＋＋】：nDataStructures,Algorithms,andApplications1.算法接口设计inC++(Part3)SartajSahni,ChinaMachine2.算法使用说明3.典型算法的实现，包括异常处理和性能估计Press4.典型算法实现的测试分析报告：1.结果是否正确？2.不同规模输入情况下的效率分析，是否与理论分析一致，如果不一

6、致，为什么？n算法设计与分析，王晓东，清华大学出版社5.该问题的应用介绍：1.应用背景，使用条件等等2.*部分典型算法的演示软件。6.*提出该问题自己的算法7.参考资料清华大学宋斌恒9清华大学宋斌恒10综合训练问题集综合练习问题集【续】n大整数运算【大整数表示、加法、减法、乘法、除n字符串【模式】匹配法、密指数，及其模运算下的上述运算】n字符串相似度理论【字符串距离编辑等】n密码支撑运算1【随机数生成】n索引与查找n密码支撑运算2【素数生成算法】n密码支撑运算3【标准和经典文献算法5个左右Hash运n图文排版优化算】

7、n网络任务调度n对称加密算法【标准和经典文献算法5个左右对称加密算法】n非对称加密算法【标准和经典文献算法5个左右非对称加密算法】清华大学宋斌恒11清华大学宋斌恒122综合练习问题集【续2】课程安排介绍n图的所有点最短距离问题n前面以介绍设计方法为主n应用：纹理合成中的缝合法。n后面以解决问题为主n图的单源最短路径n贪婪算法理论：Matroid、Greedoid、GreedSetn旅行商问题【精确解、近似解】n背包问题【同上】n自选清华大学宋斌恒13清华大学宋斌恒14算法简介本课程要回答算法的几个基本问题n什么是算法

8、：算法是一个定义好的用来计算，或者更n它会停下来吗？加一般地说，是用于把一定的输入转换成需要的输出的过程。大家最熟悉不过的算法就是算术中的加法和n它的结果正确吗？乘法。下面我们通过一个二进制的加法来说明问题：n10011011101n它运算快吗？n＋111011010001n它使用了多少内存？n＝1001110101110n进一步我们需要回答：