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

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

ID:33926279

大小:42.06 KB

页数:9页

时间:2019-02-28

算法分析与设计2005春01 清华大学:算法分析与设计_第1页
算法分析与设计2005春01 清华大学:算法分析与设计_第2页
算法分析与设计2005春01 清华大学:算法分析与设计_第3页
算法分析与设计2005春01 清华大学:算法分析与设计_第4页
算法分析与设计2005春01 清华大学:算法分析与设计_第5页
资源描述:

《算法分析与设计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进一步我们需要回答:

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。