“2012级--学期安排 (第四学期)”的版本间的差异
来自问题求解
(→学习周历) |
|||
第33行: | 第33行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
− | <li> | + | <li>JH第2章第3节</li> |
</ul> | </ul> | ||
</td> | </td> | ||
第69行: | 第69行: | ||
<ul> | <ul> | ||
<li>规约在NPC理论中的意义</li> | <li>规约在NPC理论中的意义</li> | ||
+ | </ul> | ||
+ | </td> | ||
+ | <td> | ||
+ | <ul> | ||
+ | <li></li> | ||
+ | </ul> | ||
+ | </td> | ||
+ | <td> | ||
+ | <ul> | ||
+ | <li></li> | ||
+ | </ul> | ||
+ | </td> | ||
+ | </tr> | ||
+ | <tr> | ||
+ | <td>3.3--3.7</td> | ||
+ | <td>4-3:伪多项式算法</td> | ||
+ | <td> | ||
+ | <ul> | ||
+ | <li>理解为什么若输入满足一定条件,则此条件有可能被利用来降低算法的复杂性</li> | ||
+ | </ul> | ||
+ | </td> | ||
+ | <td> | ||
+ | <ul> | ||
+ | <li>JH第3章第2、3节</li> | ||
+ | </ul> | ||
+ | </td> | ||
+ | <td> | ||
+ | <ul> | ||
+ | <li>如何识别一个可利用的输入子集条件</li> | ||
+ | </ul> | ||
+ | </td> | ||
+ | <td> | ||
+ | <ul> | ||
+ | <li></li> | ||
+ | </ul> | ||
+ | </td> | ||
+ | <td> | ||
+ | <ul> | ||
+ | <li></li> | ||
+ | </ul> | ||
+ | </td> | ||
+ | </tr> | ||
+ | <tr> | ||
+ | <td>3.10--3.14</td> | ||
+ | <td>4-4:分支-界限算法</td> | ||
+ | <td> | ||
+ | <ul> | ||
+ | <li>理解如何加快解空间搜索的速度,以至于算法复杂度得以降低</li> | ||
+ | </ul> | ||
+ | </td> | ||
+ | <td> | ||
+ | <ul> | ||
+ | <li>JH第3章第4、5节</li> | ||
+ | </ul> | ||
+ | </td> | ||
+ | <td> | ||
+ | <ul> | ||
+ | <li>如何判断可以剪枝的条件</li> | ||
+ | </ul> | ||
+ | </td> | ||
+ | <td> | ||
+ | <ul> | ||
+ | <li></li> | ||
+ | </ul> | ||
+ | </td> | ||
+ | <td> | ||
+ | <ul> | ||
+ | <li></li> | ||
+ | </ul> | ||
+ | </td> | ||
+ | </tr> | ||
+ | <tr> | ||
+ | <td>3.17--3.21</td> | ||
+ | <td>4-5:局部搜索算法</td> | ||
+ | <td> | ||
+ | <ul> | ||
+ | <li>掌握通过局部搜索试图获得最优解的方法</li> | ||
+ | </ul> | ||
+ | </td> | ||
+ | <td> | ||
+ | <ul> | ||
+ | <li>JH第3章第6节</li> | ||
+ | </ul> | ||
+ | </td> | ||
+ | <td> | ||
+ | <ul> | ||
+ | <li>如何合理定义邻集</li> | ||
</ul> | </ul> | ||
</td> | </td> |
2014年2月16日 (日) 10:49的版本
基本要求
- 掌握复杂性理论的基本内容与问题规约方法。
- 掌握解决“难”问题的主要方法,理解相关的重要理论结果。
注意:程序设计能力要求贯穿于整个课程,不再单列。
指定教材
- 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:问题的形式化描述 |
|
|
|
|
|
2.24--2.28 | 4-2:NP完全理论初步 |
|
|
|
|
|
3.3--3.7 | 4-3:伪多项式算法 |
|
|
|
|
|
3.10--3.14 | 4-4:分支-界限算法 |
|
|
|
|
|
3.17--3.21 | 4-5:局部搜索算法 |
|
|
|
|
|