2012级--学期安排 (第四学期)

基本要求

• 掌握复杂性理论的基本内容与问题规约方法。
• 掌握解决“难”问题的主要方法，理解相关的重要理论结果。

注意：程序设计能力要求贯穿于整个课程，不再单列。

指定教材

• JH: Juraj Hromkovic: Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, 2nd ed. Springer, 2004
• TC: Thomas Cormen: Introduction to Algorithms, 3rd ed. MIT, 2009

学习周历

日期	论题	学习目的	阅读材料	引导要点	书面作业	编程任务
2.17--2.21	4-1：问题的形式化描述	熟悉以基于集合的形式化方式描述问题以及相关的对象，为严格的算法分析打下基础	JH第2.3节	如何有效地理解形式化描述？
2.24--2.28	4-2：NP完全理论初步	理解如何按照问题难度对问题进行分类 理解NPC的证明方法	TC第34章	规约在NPC理论中的意义