“2012级--学期安排 (第四学期)”的版本间的差异
来自问题求解
（→学习周历） |
（→学习周历） |
||
| 第48行： | 第48行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li></li> | + | <li>附录A.01</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第78行： | 第78行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li></li> | + | <li>附录A.02</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第107行： | 第107行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li></li> | + | <li>附录A.03</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第136行： | 第136行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li></li> | + | <li>附录A.04</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第165行： | 第165行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li></li> | + | <li>附录A.05</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第194行： | 第194行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li></li> | + | <li>附录A.06</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第203行： | 第203行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>理解近似算法相关的基本概念</li> |
<li>理解近似算法的基本评价方法</li> | <li>理解近似算法的基本评价方法</li> | ||
</ul> | </ul> | ||
| 第224行： | 第224行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li></li> | + | <li>附录A.07</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第253行： | 第253行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li></li> | + | <li>附录A.08</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第282行： | 第282行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li></li> | + | <li>附录A.09</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第308行： | 第308行： | ||
<ul> | <ul> | ||
<li></li> | <li></li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>附录A.10</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | </tr> | ||
| + | <tr> | ||
| + | <td>4.28--5.2</td> | ||
| + | <td>4-11：Bin-Packing问题</td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>以Bin-Packing问题为例，理解对偶近似方法</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>JH第4章第3节第6小节</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>理解对偶在算法设计中的意义与效果</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li></li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>附录A.11</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | </tr> | ||
| + | <tr> | ||
| + | <td>5.5--5.9</td> | ||
| + | <td>4-12：随机算法的概念</td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>理解与随机算法相关的基本概念</li> | ||
| + | <li>理解随机算法的基本评价方法</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>JH第5章第1、2节</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>正确性的概念与期望正确率的概念</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li></li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>附录A.12</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | </tr> | ||
| + | <tr> | ||
| + | <td>5.12--5.16</td> | ||
| + | <td>4-13：素性判定问题</td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>理解单边错Monte Carlo方法在随机算法设计中的应用</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>JH第5章第3节第1、2、3小节</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>如何利用数学知识减少false witness</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li></li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>附录A.13</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | </tr> | ||
| + | <tr> | ||
| + | <td>5.19--5.23</td> | ||
| + | <td>4-14：等价测试问题</td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>以多项式等价测试为例理解随机算法设计中的指纹方法</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>JH第5章第3节第4小节</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>问题的转移</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li></li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>附录A.14</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | </tr> | ||
| + | <tr> | ||
| + | <td>5.26--5.30</td> | ||
| + | <td>4-15：最小割集问题</td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>以最小割集为例理解如何用随机算法解优化问题</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>JH第5章第3节第5小节</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>随机算法用于优化问题与用于判定问题的差别</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li></li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>附录A.15</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | </tr> | ||
| + | <tr> | ||
| + | <td>6.2--6.6</td> | ||
| + | <td>4-16：可满足问题</td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>通过Max-Sat问题理解如何将随机算法和优化算法很好地结合起来，以达到效率与解质量的权衡</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>JH第5章第3节第6、7小节</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>多种方法的结合使用</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li></li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>附录A.16</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | </tr> | ||
| + | <tr> | ||
| + | <td>6.9--6.13</td> | ||
| + | <td>4-17：去随机方法</td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>理解并掌握去随机的基本方法，结合应用场景，可能可以在输入空间的一个子集上将随机算法改为确定算法</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>JH第5章第4节</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>如何找合适的输入子集合</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li></li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>附录A.17</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | </tr> | ||
| + | <tr> | ||
| + | <td>6.16--6.20</td> | ||
| + | <td>4-18：启发式算法</td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>通过典型的模拟淬火算法，理解启发式算法的基本概念、其价值以及局限性</li> | ||
| + | <li>理解遗传算法的基本思想及其适用性</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>JH第6章</li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>如何从自然界获得灵感，以非常简单的思路改造算法</li> | ||
</ul> | </ul> | ||
</td> | </td> | ||
| 第313行： | 第542行： | ||
<ul> | <ul> | ||
<li></li> | <li></li> | ||
| + | </ul> | ||
| + | </td> | ||
| + | <td> | ||
| + | <ul> | ||
| + | <li>附录A.18</li> | ||
</ul> | </ul> | ||
</td> | </td> | ||
</tr> | </tr> | ||
</table> | </table> | ||
2014年2月16日 (日) 20:17的版本
基本要求
- 掌握复杂性理论的基本内容与问题规约方法。
- 掌握解决“难”问题的主要方法，理解相关的重要理论结果。
注意：程序设计能力要求贯穿于整个课程，不再单列。
指定教材
- 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：局部搜索算法 |
|
|
|
|
|
| 3.24--3.28 | 4-6：松弛算法 |
|
|
|
|
|
| 3.31--4.4 | 4-7：近似算法的基本概念 |
|
|
|
|
|
| 4.7--4.11 | 4-8：覆盖问题与最大割集问题 |
|
|
|
|
|
| 4.14--4.18 | 4-9：背包问题 |
|
|
|
|
|
| 4.21--4.25 | 4-10：旅行推销商问题 |
|
|
|
|
|
| 4.28--5.2 | 4-11：Bin-Packing问题 |
|
|
|
|
|
| 5.5--5.9 | 4-12：随机算法的概念 |
|
|
|
|
|
| 5.12--5.16 | 4-13：素性判定问题 |
|
|
|
|
|
| 5.19--5.23 | 4-14：等价测试问题 |
|
|
|
|
|
| 5.26--5.30 | 4-15：最小割集问题 |
|
|
|
|
|
| 6.2--6.6 | 4-16：可满足问题 |
|
|
|
|
|
| 6.9--6.13 | 4-17：去随机方法 |
|
|
|
|
|
| 6.16--6.20 | 4-18：启发式算法 |
|
|
|
|
|
