“2022级--学期安排 (第三学期)”的版本间的差异
来自问题求解
（→学习周历） |
（→学习周历） |
||
| （未显示同一用户的72个中间版本） | |||
| 第9行： | 第9行： | ||
==指定教材== | ==指定教材== | ||
<ul> | <ul> | ||
| − | <li>''' | + | <li>'''CH''': 程龚: 图论与算法, 2023</li> |
<li>'''TC''': Thomas Cormen: Introduction to Algorithms, 3rd ed. MIT, 2009</li> | <li>'''TC''': Thomas Cormen: Introduction to Algorithms, 3rd ed. MIT, 2009</li> | ||
<li>'''JH''': Juraj Hromkovic: Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, 2nd ed. Springer, 2004</li> | <li>'''JH''': Juraj Hromkovic: Algorithmics for Hard Problems - Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics, 2nd ed. Springer, 2004</li> | ||
| 第27行： | 第27行： | ||
<tr> | <tr> | ||
<td>9.4-9.8</td> | <td>9.4-9.8</td> | ||
| − | <td>3-1：图的基本概念</td> | + | <td>[[媒体文件:大班课件-22级-第3学期-第1次课.pdf|3-1：图的基本概念]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>CH第1章</li> |
</ul> | </ul> | ||
</td> | </td> | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>CH练习1.1、1.2、1.3、1.4</li> |
| − | <li> | + | <li>CH练习1.7、1.8</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| − | + | <td>OT：图在计算机和人工智能研究中有很多应用，例如程序分析中的[https://en.m.wikipedia.org/wiki/Control-flow_graph 控制流图]、信息检索中的[https://en.wikipedia.org/wiki/Webgraph 网页链接图]、知识表示中的[https://en.wikipedia.org/wiki/Knowledge_graph 知识图谱]等，请调研至少2种应用（其中至多1种来自上述例子），描述应用场景，讨论用图建模的方式，形式化描述问题并概述现有解决方案。</td> | |
| − | <td>OT：图在计算机和人工智能研究中有很多应用，例如程序分析中的[https://en.m.wikipedia.org/wiki/Control-flow_graph 控制流图]、信息检索中的[https://en.wikipedia.org/wiki/Webgraph 网页链接图]、知识表示中的[https://en.wikipedia.org/wiki/Knowledge_graph 知识图谱] | + | <td>第1次OJ</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>9.11-9.15</td> | <td>9.11-9.15</td> | ||
| − | <td>3-2：连通和遍历</td> | + | <td>[[媒体文件:大班课件-22级-第3学期-第2次课.pdf|3-2：连通和遍历]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>CH第2章</li> |
</ul> | </ul> | ||
</td> | </td> | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>CH练习2.1、2.2、2.3</li> |
| − | <li> | + | <li>CH练习2.8</li> |
| − | <li> | + | <li>CH练习2.11、2.12、2.13</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| − | + | <td>OT：在DFS和BFS的基础上，形成了很多扩展的搜索算法，例如[https://en.wikipedia.org/wiki/Lexicographic_breadth-first_search 词典序BFS]、[https://en.wikipedia.org/wiki/Bidirectional_search 双向搜索]、[https://en.wikipedia.org/wiki/Best-first_search 最佳优先搜索]等，请调研至少2种扩展搜索算法（其中至多1种来自上述例子），讨论适用场景，结合例子介绍算法的设计与分析，与DFS或BFS比较异同并分析优劣。</td> | |
| − | <td>OT：在DFS和BFS的基础上，形成了很多扩展的搜索算法，例如[https://en.wikipedia.org/wiki/Lexicographic_breadth-first_search 词典序BFS]、[https://en.wikipedia.org/wiki/Bidirectional_search 双向搜索]、[https://en.wikipedia.org/wiki/Best-first_search 最佳优先搜索] | + | <td>第2次OJ</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>9.18-9.22</td> | <td>9.18-9.22</td> | ||
| − | <td>3-3：圈和遍历</td> | + | <td>[[媒体文件:大班课件-22级-第3学期-第3次课.pdf|3-3：圈和遍历]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>CH第3章</li> |
</ul> | </ul> | ||
</td> | </td> | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>CH练习3.1、3.2、3.3、3.4、3.5、3.6、3.7</li> |
| − | <li> | + | <li>CH练习3.10、3.11、3.12、3.13</li> |
| − | <li> | + | <li>CH练习3.16、3.17、3.18、3.19</li> |
| − | <li> | + | <li>CH练习3.23、3.24</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| − | <td></td> | + | <td>OT：请调研教材中未介绍过的至少2种哈密尔顿路或哈密尔顿圈的存在性的必要条件或充分条件，讨论条件的适用场景，并阐述证明过程。</td> |
| − | <td></td> | + | <td>第3次OJ</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>9.25-9.29</td> | <td>9.25-9.29</td> | ||
| − | <td>3-4：连通度</td> | + | <td>[[媒体文件:大班课件-22级-第3学期-第4次课.pdf|3-4：连通度]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>CH第4章</li> |
</ul> | </ul> | ||
</td> | </td> | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>CH练习4.1</li> |
| − | <li> | + | <li>CH练习4.4、4.5、4.6、4.7</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| − | <td></td> | + | <td>OT：请调研并阐述面向点连通度或边连通度的门格尔定理的至少2种证明方法（其中至少1种来自论文原文）；门格尔定理在图论中有很多应用，请调研至少2种应用，描述应用场景。</td> |
| − | <td></td> | + | <td>第4次OJ</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>10.2-10.6</td> | <td>10.2-10.6</td> | ||
| − | <td>3-5：匹配</td> | + | <td>[[媒体文件:大班课件-22级-第3学期-第5次课.pdf|3-5：匹配]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>CH第5章</li> |
</ul> | </ul> | ||
</td> | </td> | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>CH练习5.1</li> |
| − | <li> | + | <li>CH练习5.5、5.6</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| − | <td> | + | <td>国庆放假</td> |
| − | <td> | + | <td>补周一</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>10.9-10.13</td> | <td>10.9-10.13</td> | ||
| − | <td>3-6：单源最短路</td> | + | <td>[[媒体文件:大班课件-22级-第3学期-第6次课.pdf|3-6：单源最短路]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>CH第6.1节</li> |
<li>TC第24章</li> | <li>TC第24章</li> | ||
</ul> | </ul> | ||
| 第131行： | 第131行： | ||
</ul> | </ul> | ||
</td> | </td> | ||
| − | <td></td> | + | <td>OT：单源最短路问题有很多并行算法，例如[https://doi.org/10.1016/S0196-6774(03)00076-2 Δ-stepping算法]、[https://doi.org/10.1145/2935764.2935765 Radius Stepping算法]等，请调研至少2种算法（其中至多1种来自上述例子），结合例子介绍算法的设计与分析，比较异同并分析优劣。</td> |
| − | <td>OJ讲解</td> | + | <td>作业讲解+OJ讲解</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>10.16-10.20</td> | <td>10.16-10.20</td> | ||
| − | <td>3-7：多源最短路</td> | + | <td>[[媒体文件:大班课件-22级-第3学期-第7次课.pdf|3-7：多源最短路]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| 第150行： | 第150行： | ||
</ul> | </ul> | ||
</td> | </td> | ||
| − | <td></td> | + | <td>OT：[https://doi.org/10.1145/2530531 距离索引]（Distance Oracle）是一种用于查询精确或近似距离的数据结构，请调研至少1种精确距离索引和1种近似距离索引，讨论适用场景，结合例子介绍索引构造算法和距离查询算法的设计与分析。</td> |
| − | <td></td> | + | <td>第5次OJ</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>10.23-10.27</td> | <td>10.23-10.27</td> | ||
| − | <td>3-8：最小生成树</td> | + | <td>[[媒体文件:大班课件-22级-第3学期-第8次课.pdf|3-8：最小生成树]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>CH第6.2节</li> |
</ul> | </ul> | ||
</td> | </td> | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>CH练习6.3</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| − | <td></td> | + | <td>OT：最小生成树问题有很多[https://en.wikipedia.org/wiki/Minimum_spanning_tree#Related_problems 相关问题]，例如[https://en.wikipedia.org/wiki/Steiner_tree Steiner tree]、[https://en.wikipedia.org/wiki/K-minimum_spanning_tree k-MST]、[https://en.wikipedia.org/wiki/Minimum_bottleneck_spanning_tree MBST]等，请调研至少2种问题（其中至多1种来自上述例子，[https://en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree 欧氏最小生成树问题]等仅限制原始问题输入的问题不在调研范围内），讨论适用场景，形式化描述问题并概述现有解决方案。</td> |
| − | <td></td> | + | <td>第6次OJ</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>10.30-11.3</td> | <td>10.30-11.3</td> | ||
| − | <td>3-9：问题的形式化描述</td> | + | <td>[[媒体文件:大班课件-22级-第3学期-第9次课.pdf|3-9：问题的形式化描述]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| 第182行： | 第182行： | ||
</ul> | </ul> | ||
</td> | </td> | ||
| − | <td></td> | + | <td>OT：请调研教材中未介绍过的至少2种判定问题和2种优化问题（不能是相互对应版本，也不能是教材中介绍过的问题的对应版本），讨论适用场景，用教材中的方法形式化描述问题。</td> |
| − | <td></td> | + | <td>第7次OJ</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>11.6-11.10</td> | <td>11.6-11.10</td> | ||
| − | <td>3-10：NP完全理论初步</td> | + | <td>[[媒体文件:大班课件-22级-第3学期-第10次课.pdf|3-10：NP完全理论初步]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| 第200行： | 第200行： | ||
</ul> | </ul> | ||
</td> | </td> | ||
| − | <td></td> | + | <td>OT：请调研并介绍图灵机及其至少2种[https://en.wikipedia.org/wiki/Turing_machine_equivalents 等价模型]，讨论图灵机、P、NP之间的关系。</td> |
| − | <td> | + | <td>第8次OJ</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>11.13-11.17</td> | <td>11.13-11.17</td> | ||
| − | <td>3-11：有向图和伪多项式时间算法</td> | + | <td>[[媒体文件:大班课件-22级-第3学期-第11次课.pdf|3-11：有向图和伪多项式时间算法]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>CH第7章</li> |
<li>JH第3.2.1、3.2.3节</li> | <li>JH第3.2.1、3.2.3节</li> | ||
</ul> | </ul> | ||
| 第214行： | 第214行： | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>CH练习7.1、7.2</li> |
| − | <li> | + | <li>CH练习7.4、7.5</li> |
| − | <li> | + | <li>CH练习7.17、7.18、7.19、7.20、7.21、7.22</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| − | <td></td> | + | <td>OT：除福特-法尔克森算法外，最大流问题还有很多其它算法，例如[https://doi.org/10.1145/321694.321699 Edmonds-Karp算法]、[https://doi.org/10.1007/11685654_10 Dinitz算法]、[https://doi.org/10.1145/48014.61051 Push-Relabel算法]等，请调研至少2种算法（其中至多1种来自上述例子），结合例子介绍算法的设计与分析，与福特-法尔克森算法比较异同并分析优劣。</td> |
| − | <td></td> | + | <td>第9次OJ</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>11.20-11.24</td> | <td>11.20-11.24</td> | ||
| − | <td>3-12：分支定界和局部搜索算法</td> | + | <td>[[媒体文件:大班课件-22级-第3学期-第12次课.pdf|3-12：分支定界和局部搜索算法]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li>JH第3.4、3. | + | <li>JH第3.4、3.6.1、3.6.2节</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第236行： | 第236行： | ||
</ul> | </ul> | ||
</td> | </td> | ||
| − | <td></td> | + | <td>OT：除MAX-SAT和TSP外，分支定界和局部搜索算法还可用于解决其它问题，请为每种算法调研至少1种可以解决的问题，结合例子介绍算法的设计与分析。</td> |
| − | <td></td> | + | <td>作业讲解+OJ讲解</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>11.27-12.1</td> | <td>11.27-12.1</td> | ||
| − | <td>3-13：松弛算法</td> | + | <td>[[媒体文件:大班课件-22级-第3学期-第13次课.pdf|3-13：松弛算法]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li>JH第3. | + | <li>JH第3.7.1、3.7.2、3.7.4节（不含练习3.7.4.12之后的内容）</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| 第250行： | 第250行： | ||
<ul> | <ul> | ||
<li>JH练习3.7.2.1、3.7.2.4、3.7.2.5</li> | <li>JH练习3.7.2.1、3.7.2.4、3.7.2.5</li> | ||
| − | <li>JH练习3.7.4.4、3.7.4. | + | <li>JH练习3.7.4.4、3.7.4.12</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| − | <td></td> | + | <td>OT：除IP外，广义的“松弛-修正”思想还可用于解决其它问题，例如[https://doi.org/10.1007/s43069-021-00101-z TSP的松弛修正算法]、[https://doi.org/10.1145/179812.179818 最短超串问题的松弛修正算法]等，请调研至少2种算法（其中至多1种来自上述例子），结合例子介绍算法的设计与分析，重点阐述其中的“松弛-修正”思想。</td> |
| − | <td></td> | + | <td>第10次OJ</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>12.4-12.8</td> | <td>12.4-12.8</td> | ||
| − | <td>3-14：近似算法的基本概念</td> | + | <td>[[媒体文件:大班课件-22级-第3学期-第14次课.pdf|3-14：近似算法的基本概念]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li>JH第4.2.1、4.2.2、4.3.3节</li> | + | <li>JH第4.2.1、4.2.2、4.2.3、4.3.3节</li> |
</ul> | </ul> | ||
</td> | </td> | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li>JH练习4.2.1.4、4.2.1. | + | <li>JH练习4.2.1.4、4.2.1.5、4.2.3.3</li> |
<li>JH练习4.3.3.5、4.3.3.6</li> | <li>JH练习4.3.3.5、4.3.3.6</li> | ||
</ul> | </ul> | ||
</td> | </td> | ||
| − | <td></td> | + | <td>OT：除MS和MAX-CUT外，近似算法还可用于解决其它问题，例如SCP（JH算法4.3.2.11）、SKP（JH算法4.3.4.1和4.3.4.2）等，请调研至少2种近似算法（其中至多1种来自上述例子，图上的优化问题不在调研范围内），结合例子介绍算法的设计与分析，重点阐述近似比的证明过程。</td> |
| − | <td></td> | + | <td>第11次OJ</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>12.11-12.15</td> | <td>12.11-12.15</td> | ||
| − | <td>3-15：独立、覆盖和支配</td> | + | <td>[[媒体文件:大班课件-22级-第3学期-第15次课.pdf|3-15：独立、覆盖和支配]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>CH第8章</li> |
</ul> | </ul> | ||
</td> | </td> | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>CH练习8.1、8.2</li> |
| − | <li> | + | <li>CH练习8.5</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| − | <td></td> | + | <td>OT：在独立、覆盖和支配的基础上，形成了很多扩展的优化问题，例如最小权完美匹配问题（Minimum-Weight Perfect Matching）、[https://en.wikipedia.org/wiki/Connected_dominating_set 最小连通支配集问题]等，请调研至少2种问题（其中至多1种来自上述例子，二分图最大匹配问题等仅限制原始问题输入的问题不在调研范围内），讨论适用场景，形式化描述问题，为每种问题结合例子介绍至少1种算法的设计与分析。</td> |
| − | <td></td> | + | <td>第12次OJ</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>12.18-12.22</td> | <td>12.18-12.22</td> | ||
| − | <td>3-16：染色</td> | + | <td>[[媒体文件:大班课件-22级-第3学期-第16次课.pdf|3-16：染色]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>CH第9章</li> |
</ul> | </ul> | ||
</td> | </td> | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>CH练习9.1、9.2</li> |
| − | <li> | + | <li>CH练习9.5、9.6</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| − | <td></td> | + | <td>OT：除米什拉-格赖斯算法和贪心算法外，边染色和点染色问题还有很多其它算法，请为每种问题调研至少1种精确算法（暴力算法不在调研范围内），结合例子介绍算法的设计与分析。</td> |
| − | <td> | + | <td>第13次OJ</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
<td>12.25-12.29</td> | <td>12.25-12.29</td> | ||
| − | <td>3-17：平面</td> | + | <td>[[媒体文件:大班课件-22级-第3学期-第17次课.pdf|3-17：平面]]</td> |
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>CH第10章</li> |
</ul> | </ul> | ||
</td> | </td> | ||
<td> | <td> | ||
<ul> | <ul> | ||
| − | <li> | + | <li>CH练习10.1、10.2、10.3、10.4</li> |
</ul> | </ul> | ||
</td> | </td> | ||
| − | <td></td> | + | <td>OT：除DMP算法外，可平面图的判定问题还有很多其它算法，请调研至少2种算法，结合例子介绍算法的设计与分析，与DMP算法比较异同并分析优劣。</td> |
| − | <td> | + | <td>作业讲解+OJ讲解</td> |
</tr> | </tr> | ||
<tr> | <tr> | ||
2024年2月1日 (四) 09:52的最新版本
基本要求
- 掌握典型应用中抽象出来的重要算法问题的求解方法。
- 掌握复杂性理论的基本内容与问题规约方法。
- 理解解决“难”问题的主要方法、技术以及相关的重要理论。
注意：程序设计能力要求贯穿于整个课程，不再单列。
指定教材
- CH: 程龚: 图论与算法, 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：图的基本概念 |
|
|
OT：图在计算机和人工智能研究中有很多应用，例如程序分析中的控制流图、信息检索中的网页链接图、知识表示中的知识图谱等，请调研至少2种应用（其中至多1种来自上述例子），描述应用场景，讨论用图建模的方式，形式化描述问题并概述现有解决方案。 | 第1次OJ |
| 9.11-9.15 | 3-2：连通和遍历 |
|
|
OT：在DFS和BFS的基础上，形成了很多扩展的搜索算法，例如词典序BFS、双向搜索、最佳优先搜索等，请调研至少2种扩展搜索算法（其中至多1种来自上述例子），讨论适用场景，结合例子介绍算法的设计与分析，与DFS或BFS比较异同并分析优劣。 | 第2次OJ |
| 9.18-9.22 | 3-3：圈和遍历 |
|
|
OT：请调研教材中未介绍过的至少2种哈密尔顿路或哈密尔顿圈的存在性的必要条件或充分条件，讨论条件的适用场景，并阐述证明过程。 | 第3次OJ |
| 9.25-9.29 | 3-4：连通度 |
|
|
OT：请调研并阐述面向点连通度或边连通度的门格尔定理的至少2种证明方法（其中至少1种来自论文原文）；门格尔定理在图论中有很多应用，请调研至少2种应用，描述应用场景。 | 第4次OJ |
| 10.2-10.6 | 3-5：匹配 |
|
|
国庆放假 | 补周一 |
| 10.9-10.13 | 3-6：单源最短路 |
|
|
OT：单源最短路问题有很多并行算法，例如Δ-stepping算法、Radius Stepping算法等，请调研至少2种算法（其中至多1种来自上述例子），结合例子介绍算法的设计与分析，比较异同并分析优劣。 | 作业讲解+OJ讲解 |
| 10.16-10.20 | 3-7：多源最短路 |
|
|
OT：距离索引（Distance Oracle）是一种用于查询精确或近似距离的数据结构，请调研至少1种精确距离索引和1种近似距离索引，讨论适用场景，结合例子介绍索引构造算法和距离查询算法的设计与分析。 | 第5次OJ |
| 10.23-10.27 | 3-8：最小生成树 |
|
|
OT：最小生成树问题有很多相关问题，例如Steiner tree、k-MST、MBST等，请调研至少2种问题（其中至多1种来自上述例子，欧氏最小生成树问题等仅限制原始问题输入的问题不在调研范围内），讨论适用场景，形式化描述问题并概述现有解决方案。 | 第6次OJ |
| 10.30-11.3 | 3-9：问题的形式化描述 |
|
|
OT：请调研教材中未介绍过的至少2种判定问题和2种优化问题（不能是相互对应版本，也不能是教材中介绍过的问题的对应版本），讨论适用场景，用教材中的方法形式化描述问题。 | 第7次OJ |
| 11.6-11.10 | 3-10：NP完全理论初步 |
|
|
OT：请调研并介绍图灵机及其至少2种等价模型，讨论图灵机、P、NP之间的关系。 | 第8次OJ |
| 11.13-11.17 | 3-11：有向图和伪多项式时间算法 |
|
|
OT：除福特-法尔克森算法外，最大流问题还有很多其它算法，例如Edmonds-Karp算法、Dinitz算法、Push-Relabel算法等，请调研至少2种算法（其中至多1种来自上述例子），结合例子介绍算法的设计与分析，与福特-法尔克森算法比较异同并分析优劣。 | 第9次OJ |
| 11.20-11.24 | 3-12：分支定界和局部搜索算法 |
|
|
OT：除MAX-SAT和TSP外，分支定界和局部搜索算法还可用于解决其它问题，请为每种算法调研至少1种可以解决的问题，结合例子介绍算法的设计与分析。 | 作业讲解+OJ讲解 |
| 11.27-12.1 | 3-13：松弛算法 |
|
|
OT：除IP外，广义的“松弛-修正”思想还可用于解决其它问题，例如TSP的松弛修正算法、最短超串问题的松弛修正算法等，请调研至少2种算法（其中至多1种来自上述例子），结合例子介绍算法的设计与分析，重点阐述其中的“松弛-修正”思想。 | 第10次OJ |
| 12.4-12.8 | 3-14：近似算法的基本概念 |
|
|
OT：除MS和MAX-CUT外，近似算法还可用于解决其它问题，例如SCP（JH算法4.3.2.11）、SKP（JH算法4.3.4.1和4.3.4.2）等，请调研至少2种近似算法（其中至多1种来自上述例子，图上的优化问题不在调研范围内），结合例子介绍算法的设计与分析，重点阐述近似比的证明过程。 | 第11次OJ |
| 12.11-12.15 | 3-15：独立、覆盖和支配 |
|
|
OT：在独立、覆盖和支配的基础上，形成了很多扩展的优化问题，例如最小权完美匹配问题（Minimum-Weight Perfect Matching）、最小连通支配集问题等，请调研至少2种问题（其中至多1种来自上述例子，二分图最大匹配问题等仅限制原始问题输入的问题不在调研范围内），讨论适用场景，形式化描述问题，为每种问题结合例子介绍至少1种算法的设计与分析。 | 第12次OJ |
| 12.18-12.22 | 3-16：染色 |
|
|
OT：除米什拉-格赖斯算法和贪心算法外，边染色和点染色问题还有很多其它算法，请为每种问题调研至少1种精确算法（暴力算法不在调研范围内），结合例子介绍算法的设计与分析。 | 第13次OJ |
| 12.25-12.29 | 3-17：平面 |
|
|
OT：除DMP算法外，可平面图的判定问题还有很多其它算法，请调研至少2种算法，结合例子介绍算法的设计与分析，与DMP算法比较异同并分析优劣。 | 作业讲解+OJ讲解 |
| 寒假自学 | 3-18：背包问题 |
|
-- | -- | -- |
