“2012级--学期安排 (第四学期)”的版本间的差异
来自问题求解
(→学习周历) |
(→学习周历) |
||
(未显示同一用户的6个中间版本) | |||
第296行: | 第296行: | ||
<tr> | <tr> | ||
<td>4.21--4.25</td> | <td>4.21--4.25</td> | ||
− | <td>4-10:旅行推销商问题</td> | + | <td>[http://cslab.nju.edu.cn/problem_solving/images/c/c5/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-04-22-%E6%97%85%E8%A1%8C%E6%8E%A8%E9%94%80%E5%95%86%E9%97%AE%E9%A2%98.pdf 4-10:旅行推销商问题]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
第326行: | 第326行: | ||
<tr> | <tr> | ||
<td>4.28--5.2</td> | <td>4.28--5.2</td> | ||
− | <td>4-11:Bin-Packing问题</td> | + | <td>[http://cslab.nju.edu.cn/problem_solving/images/9/99/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-04-29-Bin-Packing%E9%97%AE%E9%A2%98.pdf 4-11:Bin-Packing问题]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
第355行: | 第355行: | ||
<tr> | <tr> | ||
<td>5.5--5.9</td> | <td>5.5--5.9</td> | ||
− | <td>4-12:随机算法的概念</td> | + | <td>[http://cslab.nju.edu.cn/problem_solving/images/5/5f/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-05-06-%E9%9A%8F%E6%9C%BA%E7%AE%97%E6%B3%95%E7%9A%84%E6%A6%82%E5%BF%B5.pdf 4-12:随机算法的概念]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
第385行: | 第385行: | ||
<tr> | <tr> | ||
<td>5.12--5.16</td> | <td>5.12--5.16</td> | ||
− | <td>4-13:Random Sampling和Abundance of Witnesses</td> | + | <td>[http://cslab.nju.edu.cn/problem_solving/images/b/bc/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-05-13-Random_Sampling%E5%92%8Cabundance_of_witnesses.pdf 4-13:Random Sampling和Abundance of Witnesses]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
第398行: | 第398行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
+ | <li>为什么“乱猜”也是一种算法设计方法</li> | ||
<li>如何利用数学知识减少false witness</li> | <li>如何利用数学知识减少false witness</li> | ||
</ul> | </ul> | ||
第414行: | 第415行: | ||
<tr> | <tr> | ||
<td>5.19--5.23</td> | <td>5.19--5.23</td> | ||
− | <td>4-14:等价测试问题</td> | + | <td>[http://cslab.nju.edu.cn/problem_solving/images/b/b3/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-05-20-%E7%AD%89%E4%BB%B7%E6%B5%8B%E8%AF%95%E9%97%AE%E9%A2%98.pdf 4-14:等价测试问题]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
第432行: | 第433行: | ||
<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> | ||
第443行: | 第445行: | ||
<tr> | <tr> | ||
<td>5.26--5.30</td> | <td>5.26--5.30</td> | ||
− | <td>4-15:最小割集问题</td> | + | <td>[http://cslab.nju.edu.cn/problem_solving/images/1/12/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-05-27-%E6%9C%80%E5%B0%8F%E5%89%B2%E9%9B%86%E9%97%AE%E9%A2%98.pdf 4-15:最小割集问题]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
第461行: | 第463行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
− | <li></li> | + | <li>JH第5章练习5.3.5.9、5.3.5.10</li> |
</ul> | </ul> | ||
</td> | </td> | ||
第472行: | 第474行: | ||
<tr> | <tr> | ||
<td>6.2--6.6</td> | <td>6.2--6.6</td> | ||
− | <td>4-16:不同方法结合使用</td> | + | <td>[http://cslab.nju.edu.cn/problem_solving/images/8/8f/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-06-03-%E4%B8%8D%E5%90%8C%E6%96%B9%E6%B3%95%E7%9A%84%E7%BB%93%E5%90%88%E4%BD%BF%E7%94%A8.pdf 4-16:不同方法结合使用]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
第502行: | 第504行: | ||
<tr> | <tr> | ||
<td>6.9--6.13</td> | <td>6.9--6.13</td> | ||
− | <td>4-17:去随机方法</td> | + | <td>[http://cslab.nju.edu.cn/problem_solving/images/d/de/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-06-10-%E5%8E%BB%E9%9A%8F%E6%9C%BA%E6%96%B9%E6%B3%95.pdf 4-17:去随机方法]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
第520行: | 第522行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
− | <li></li> | + | <li>JH第5章练习5.4.2.3、5.4.2.4、5.4.3.2、5.4.3.3</li> |
</ul> | </ul> | ||
</td> | </td> | ||
第531行: | 第533行: | ||
<tr> | <tr> | ||
<td>6.16--6.20</td> | <td>6.16--6.20</td> | ||
− | <td>4-18:启发式算法</td> | + | <td>[http://cslab.nju.edu.cn/problem_solving/images/1/1d/%E8%AE%A1%E7%AE%97%E6%9C%BA%E9%97%AE%E9%A2%98%E6%B1%82%E8%A7%A3-2014-06-17-%E5%90%AF%E5%8F%91%E5%BC%8F%E7%AE%97%E6%B3%95.pdf 4-18:启发式算法]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
第550行: | 第552行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
− | <li></li> | + | <li>列出这学期讨论的典型“难题”,在每个题目下列出可能采用的解法,并比较解的质量与代价。</li> |
</ul> | </ul> | ||
</td> | </td> |
2014年6月21日 (六) 16:27的最新版本
基本要求
- 掌握复杂性理论的基本内容与问题规约方法。
- 掌握解决“难”问题的主要方法,理解相关的重要理论结果。
注意:程序设计能力要求贯穿于整个课程,不再单列。
指定教材
- 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:Random Sampling和Abundance of Witnesses |
|
|
|
|
|
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:启发式算法 |
|
|
|
|
|