“2016级--学期安排 (第四学期)”的版本间的差异
来自问题求解
(未显示同一用户的11个中间版本) | |||
第141行: | 第141行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
+ | <li>JH第3章练习3.4.2.1、3.4.2.2</li> | ||
+ | <li>采用branch-and-bound方法解背包问题,并分别给出对你的方法有利与不利的输入</li> | ||
</ul> | </ul> | ||
</td> | </td> | ||
第169行: | 第171行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
+ | <li>JH第3章练习3.6.1.3</li> | ||
+ | <li>如果一个局部搜索算法给出的解一定是全局最优解,则这个算法称为“精确局部搜索算法”:(1)证明解TSP的2-exchange不是精确的。(2)证明解TSP的(n-1)-exchange是精确的。</li> | ||
+ | <li>考虑带权图的最大边割集问题……(参见课件)</li> | ||
</ul> | </ul> | ||
</td> | </td> | ||
第197行: | 第202行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
+ | <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> | ||
第226行: | 第232行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
+ | <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> | ||
第254行: | 第261行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
+ | <li>JH第4章练习4.3.2.3、4.3.2.6、4.3.2.9</li> | ||
</ul> | </ul> | ||
</td> | </td> | ||
第282行: | 第290行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
+ | <li>JH第4章练习4.3.4.9、4.3.4.13</li> | ||
</ul> | </ul> | ||
</td> | </td> | ||
第311行: | 第320行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
+ | <li>设计一个找最小完美匹配的算法</li> | ||
+ | <li>JH第4章练习4.3.5.6、4.3.5.11、4.3.5.13</li> | ||
</ul> | </ul> | ||
</td> | </td> | ||
第339行: | 第350行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
+ | <li>JH第4章练习4.3.6.6</li> | ||
</ul> | </ul> | ||
</td> | </td> | ||
第368行: | 第380行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
+ | <li>JH第5章练习5.2.2.7、5.2.2.8</li> | ||
</ul> | </ul> | ||
</td> | </td> | ||
第397行: | 第410行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
+ | <li>JH第5章练习5.3.2.5、5.3.3.2、5.3.3.9、5.3.3.10</li> | ||
</ul> | </ul> | ||
</td> | </td> | ||
第425行: | 第439行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
+ | <li>JH第2章练习2.2.3.21、2.2.3.22</li> | ||
+ | <li>JH第5章练习5.3.4.12</li> | ||
</ul> | </ul> | ||
</td> | </td> | ||
第453行: | 第469行: | ||
<td> | <td> | ||
<ul> | <ul> | ||
+ | <li>JH第5章练习5.3.5.9、5.3.5.10</li> | ||
</ul> | </ul> | ||
</td> | </td> |
2018年6月11日 (一) 09:52的最新版本
基本要求
- 掌握复杂性理论的基本内容与问题规约方法。
- 掌握解决“难”问题的主要方法,理解相关的重要理论结果。
注意:程序设计能力要求贯穿于整个课程,不再单列。
指定教材
- 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
学习周历
日期 | 论题 | 学习目的 | 阅读材料 | 引导要点 | 书面作业 | 编程任务 |
---|---|---|---|---|---|---|
3.5--3.9 | 4-1:问题的形式化描述 |
|
|
|
|
|
3.12--3.16 | 4-2:NP完全理论初步 |
|
|
|
|
|
3.19--3.23 | 4-3:伪多项式算法 |
|
|
|
|
|
3.26--3.30 | 4-4:分支-界限算法 |
|
|
|
|
|
4.2--4.6 | 4-5:局部搜索算法 |
|
|
|
|
|
4.9--4.13 | 4-6:松弛算法 |
|
|
|
|
|
4.16--4.20 | 4-7:近似算法的基本概念 |
|
|
|
|
|
4.23--4.27 | 4-8:覆盖问题与最大割集问题 |
|
|
|
|
|
4.30--5.4 | 4-9:背包问题 |
|
|
|
|
|
5.7--5.11 | 4-10:旅行推销商问题 |
|
|
|
|
|
5.14--5.18 | 4-11:Bin-Packing问题 |
|
|
|
|
|
5.21--5.25 | 4-12:随机算法的概念 |
|
|
|
|
|
5.28--6.1 | 4-13:Random Sampling和Abundance of Witnesses |
|
|
|
|
|
6.4--6.8 | 4-14:等价测试问题 |
|
|
|
|
|
6.11--6.15 | 4-15:最小割集问题 |
|
|
|
|
|
6.18--6.22 | 4-16:不同方法结合使用 |
|
|
|
|
|
暑假自学 | 4-17:去随机方法 |
|
|
|
|
|
暑假自学 | 4-18:启发式算法 |
|
|
|
|
|