“2014级--学期安排 (第四学期)”的版本间的差异
来自问题求解
（→学习周历） |
（→学习周历） |
||
| （未显示同一用户的8个中间版本） | |||
| 第201行： | 第201行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li>JH第3章练习3. | + | <li>JH第3章练习3.7.2.1、3.7.2.4、3.7.2.5、3.7.4.4、3.7.4.12、3.7.4.16</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第231行： | 第231行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li></li> | + | <li>JH第4章练习4.2.1.4、4.2.1.5、4.2.3.3、4.2.3.4、4.2.3.5</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第260行： | 第260行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li></li> | + | <li>JH第4章练习4.3.2.3、4.3.2.6、4.3.2.9、4.3.3.5、4.3.3.6</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第289行： | 第289行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li></li> | + | <li>完整地写出MOD-SKP是解KP_delta的PTAS的证明</li> |
| + | <li>JH第4章练习4.3.4.9、4.3.4.13</li> | ||
</ul> | </ul> | ||
</td> | </td> | ||
| 第319行： | 第320行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li></li> | + | <li>设计一个找最小完美匹配的算法</li> |
| + | <li>JH第4章练习4.3.5.6、4.3.5.11、4.3.5.13</li> | ||
</ul> | </ul> | ||
</td> | </td> | ||
| 第348行： | 第350行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li></li> | + | <li>JH第4章练习4.3.6.6</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第378行： | 第380行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li></li> | + | <li>JH第5章练习5.2.2.7、5.2.2.8</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第408行： | 第410行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li></li> | + | <li>JH第5章练习5.3.2.5、5.3.3.2、5.3.3.9、5.3.3.10</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第437行： | 第439行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li></li> | + | <li>JH第2章练习2.2.3.21、2.2.3.22</li> |
| + | <li>JH第5章练习5.3.4.12</li> | ||
</ul> | </ul> | ||
</td> | </td> | ||
2016年5月23日 (一) 09:38的最新版本
基本要求
- 掌握复杂性理论的基本内容与问题规约方法。
- 掌握解决“难”问题的主要方法，理解相关的重要理论结果。
注意：程序设计能力要求贯穿于整个课程，不再单列。
指定教材
- 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
推荐课外读物
- Richard Lipton: The P=NP Question and Gödel's Lost Letter. Springer, 2010
学习周历
| 日期 | 论题 | 学习目的 | 阅读材料 | 引导要点 | 书面作业 | 编程任务 |
|---|---|---|---|---|---|---|
| 2.22--2.26 | 4-1：问题的形式化描述 |
|
|
|
|
|
| 2.29--3.4 | 4-2：NP完全理论初步 |
|
|
|
|
|
| 3.7--3.11 | 4-3：伪多项式算法 |
|
|
|
|
|
| 3.14--3.18 | 4-4：分支-界限算法 |
|
|
|
|
|
| 3.21--3.25 | 4-5：局部搜索算法 |
|
|
|
|
|
| 3.28--4.1 | 4-6：松弛算法 |
|
|
|
|
|
| 4.4--4.8 | 4-7：近似算法的基本概念 |
|
|
|
|
|
| 4.11--4.15 | 4-8：覆盖问题与最大割集问题 |
|
|
|
|
|
| 4.18--4.22 | 4-9：背包问题 |
|
|
|
|
|
| 4.25--4.29 | 4-10：旅行推销商问题 |
|
|
|
|
|
| 5.2--5.6 | 4-11：Bin-Packing问题 |
|
|
|
|
|
| 5.9--5.13 | 4-12：随机算法的概念 |
|
|
|
|
|
| 5.16--5.20 | 4-13：Random Sampling和Abundance of Witnesses |
|
|
|
|
|
| 5.23--5.27 | 4-14：等价测试问题 |
|
|
|
|
|
| 5.30--6.3 | 4-15：最小割集问题 |
|
|
|
|
|
| 6.6--6.10 | 4-16：不同方法结合使用 |
|
|
|
|
|
| 6.13--6.17 | 4-17：去随机方法 |
|
|
|
|
|
| 暑假自学 | 4-18：启发式算法 |
|
|
|
|
|
