“2022级--学期安排 (第三学期)”的版本间的差异
来自问题求解
（→学习周历） |
（→学习周历） |
||
| 第35行： | 第35行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li>CHENG练习1. | + | <li>CHENG练习1.1、1.2、1.3、1.4</li> |
| − | <li>CHENG练习1. | + | <li>CHENG练习1.7、1.8</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第52行： | 第52行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li>CHENG练习2. | + | <li>CHENG练习2.1、2.2、2.3</li> |
<li>CHENG练习2.8</li> | <li>CHENG练习2.8</li> | ||
| − | <li>CHENG练习2. | + | <li>CHENG练习2.11、2.12、2.13</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第70行： | 第70行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li>CHENG练习3. | + | <li>CHENG练习3.1、3.2、3.3、3.4、3.5、3.6、3.7</li> |
| − | <li>CHENG练习3. | + | <li>CHENG练习3.10、3.11、3.12、3.13</li> |
| − | <li>CHENG练习3. | + | <li>CHENG练习3.16、3.17、3.18、3.19</li> |
| − | <li>CHENG练习3. | + | <li>CHENG练习3.23、3.24</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第90行： | 第90行： | ||
<ul> | <ul> | ||
<li>CHENG练习4.1</li> | <li>CHENG练习4.1</li> | ||
| − | <li>CHENG练习4. | + | <li>CHENG练习4.4、4.5、4.6、4.7</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第107行： | 第107行： | ||
<ul> | <ul> | ||
<li>CHENG练习5.1</li> | <li>CHENG练习5.1</li> | ||
| − | <li>CHENG练习5. | + | <li>CHENG练习5.5、5.6</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第214行： | 第214行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li>CHENG练习7. | + | <li>CHENG练习7.1、7.2</li> |
| − | <li>CHENG练习7. | + | <li>CHENG练习7.4、7.5</li> |
| − | <li>CHENG练习7. | + | <li>CHENG练习7.17、7.18、7.19、7.20、7.21、7.22</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第264行： | 第264行： | ||
</ul> | </ul> | ||
</td> | </td> | ||
| − | <td></td> | + | <td> |
| + | <ul> | ||
| + | <li>JH练习4.2.1.4、4.2.1.5</li> | ||
| + | <li>JH练习4.3.3.5、4.3.3.6</li> | ||
| + | </ul> | ||
| + | </td> | ||
<td></td> | <td></td> | ||
<td></td> | <td></td> | ||
| 第278行： | 第283行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li>CHENG练习8. | + | <li>CHENG练习8.1、8.2</li> |
<li>CHENG练习8.5</li> | <li>CHENG练习8.5</li> | ||
</ul> | </ul> | ||
| 第295行： | 第300行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li>CHENG练习9. | + | <li>CHENG练习9.1、9.2</li> |
| − | <li>CHENG练习9. | + | <li>CHENG练习9.5、9.6</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第312行： | 第317行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li>CHENG练习10. | + | <li>CHENG练习10.1、10.2、10.3、10.4</li> |
</ul> | </ul> | ||
</td> | </td> | ||
2023年7月11日 (二) 14:49的版本
基本要求
- 掌握典型应用中抽象出来的重要算法问题的求解方法。
- 掌握复杂性理论的基本内容与问题规约方法。
- 理解解决“难”问题的主要方法、技术以及相关的重要理论。
注意：程序设计能力要求贯穿于整个课程，不再单列。
指定教材
- CHENG: 程龚: 图论与算法, 2023
- TC: Thomas Cormen: Introduction to Algorithms, 3rd ed. MIT, 2009
- JH: Juraj Hromkovic: Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, 2nd ed. Springer, 2004
- WS: Walter Savitch: Problem Solving with C++, 7th ed. Addison Wesley, 2008
学习周历
| 日期 | 论题 | 阅读材料 | 书面作业 | 周三小班 | 周四大班 |
|---|---|---|---|---|---|
| 9.4-9.8 | 3-1：图的基本概念 |
|
|
||
| 9.11-9.15 | 3-2：连通和遍历 |
|
|
||
| 9.18-9.22 | 3-3：圈和遍历 |
|
|
||
| 9.25-9.29 | 3-4：连通度 |
|
|
||
| 10.2-10.6 | 3-5：匹配 |
|
|
-- | -- |
| 10.9-10.13 | 3-6：单源最短路 |
|
|
||
| 10.16-10.20 | 3-7：多源最短路 |
|
|
||
| 10.23-10.27 | 3-8：最小生成树 |
|
|
||
| 10.30-11.3 | 3-9：问题的形式化描述 |
|
|
||
| 11.6-11.10 | 3-10：NP完全理论初步 |
|
|
||
| 11.13-11.17 | 3-11：有向图和伪多项式时间算法 |
|
|
||
| 11.20-11.24 | 3-12：分支定界和局部搜索算法 |
|
|
||
| 11.27-12.1 | 3-13：松弛算法 |
|
|
||
| 12.4-12.8 | 3-14：近似算法的基本概念 |
|
|
||
| 12.11-12.15 | 3-15：独立、覆盖和支配 |
|
|
||
| 12.18-12.22 | 3-16：染色 |
|
|
||
| 12.25-12.29 | 3-17：平面 |
|
|
||
| 寒假自学 | 3-18：背包问题 |
|
-- | -- | -- |
