“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:启发式算法 |
|
|
|
|
|