“2012级--学期安排 (第四学期)”的版本间的差异

来自问题求解
跳转至: 导航搜索
第52行: 第52行:
 
     </td>
 
     </td>
 
   </tr>
 
   </tr>
 +
  <tr>
 
     <td>2.24--2.28</td>
 
     <td>2.24--2.28</td>
 
     <td>4-2:NP完全理论初步</td>
 
     <td>4-2:NP完全理论初步</td>

2014年2月16日 (日) 10:45的版本

基本要求

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

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

指定教材

  • 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理论中的意义