授课内容【按照层次分】 设计理论 算法分析与设计 分析方法 实现技术 测试技术 应用范围 请华大学 宋斌恒 Contents【按照内容分】 教学目的 ■ Divide and conquer【分治】 理论分析能力培养:掌握算法分析与设计的基 ■ Dynamic Programming【动态规划】 本理论和方法,具有设计新算法和分析复杂性 ■ Greedy method【贪婪算法】 的能力 ■ Amortized Analysis【均摊分析法】 ■实践能力的培养:学会如何实现设计好的算 ■ Algorithms in Graphics【图论中算法】 法,如何测试其正确性和效率,应用与实际问 ■ NP-Completeness【NP完全问题,算法理 题 团队能力培养:和各种人员合作工作能力 ■ Selected Topics【专题讲座】 ■交流能力的培养:表达和接受能力 ■ Comprehensive Training【综合训练】 ■独立研究能力培养:具有独立开展研究的能力 上课的必要条件 基本要求 ■数据结构(没修过的请修过后再选) 上课不应迟到,迟到一次扣1分,自己申报,如果迟到 ■掌握一门对面向对象编程语言(C+十或 没有申报被发现扣10分 不得抄袭、剽窃。参考文献、著作、教材和包括其它 Java 同学的作业在内的所有资 ■文献、著作、教材类公开出版的参考资料,按照文献索 网络资料,除指出网络路徑URL,还应当提供资料电子 参考同学作业应当指出作业编号和提供原作业拷贝。多 人讨论的成果,应当在作业中反映 ■引用他人成果而没有指出出处的以抄袭论处。如有 次发现,总成绩减去该阶段分值 现,成绩记0分,并以考试作弊向上汇报。1 算法分析与设计 清华大学 宋斌恒 清华大学 宋斌恒 2 授课内容【按照层次分】 n 设计理论 n 分析方法 n 实现技术 n 测试技术 n 应用范围 清华大学 宋斌恒 3 Contents【按照内容分】 n Divide and conquer【分治】 n Dynamic Programming【动态规划】 n Greedy method【贪婪算法】 n Amortized Analysis【均摊分析法】 n Algorithms in Graphics【图论中算法】 n NP-Completeness【NP完全问题，算法理 论】 n Selected Topics【专题讲座】 n Comprehensive Training【综合训练】 清华大学 宋斌恒 4 教学目的 n 理论分析能力培养：掌握算法分析与设计的基 本理论和方法，具有设计新算法和分析复杂性 的能力 n 实践能力的培养：学会如何实现设计好的算 法，如何测试其正确性和效率，应用与实际问 题 n 团队能力培养：和各种人员合作工作能力 n 交流能力的培养：表达和接受能力 n 独立研究能力培养：具有独立开展研究的能力 清华大学 宋斌恒 5 上课的必要条件 n 数据结构（没修过的请修过后再选） n 掌握一门对面向对象编程语言（C＋＋或 Java） 清华大学 宋斌恒 6 基本要求 n 上课不应迟到，迟到一次扣1分，自己申报，如果迟到 没有申报被发现扣10分。 n 不得抄袭、剽窃。参考文献、著作、教材和包括其它 同学的作业在内的所有资料，必须指明出处。其中 n 文献、著作、教材类公开出版的参考资料，按照文献索 引方式引用。有可能的话最好提供电子拷贝。 n 网络资料，除指出网络路径URL，还应当提供资料电子 拷贝。 n 参考同学作业应当指出作业编号和提供原作业拷贝。多 人讨论的成果，应当在作业中反映。 n 引用他人成果而没有指出出处的以抄袭论处。如有抄 袭，第一次发现，总成绩减去该阶段分值，第二次发 现，成绩记0分，并以考试作弊向上汇报