“2022级--学期安排 (第三学期)”的版本间的差异
来自问题求解
（→学习周历） |
（→学习周历） |
||
| 第39行： | 第39行： | ||
</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 知识图谱] | + | <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></td> | <td></td> | ||
</tr> | </tr> | ||
| 第166行： | 第166行： | ||
</ul> | </ul> | ||
</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>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></td> | ||
</tr> | </tr> | ||
2023年8月4日 (五) 17:41的版本
基本要求
- 掌握典型应用中抽象出来的重要算法问题的求解方法。
- 掌握复杂性理论的基本内容与问题规约方法。
- 理解解决“难”问题的主要方法、技术以及相关的重要理论。
注意：程序设计能力要求贯穿于整个课程，不再单列。
指定教材
- 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：图的基本概念 |
|
|
OT：图在计算机和人工智能研究中有很多应用，例如程序分析中的控制流图、信息检索中的网页链接图、知识表示中的知识图谱等，请调研至少2种应用（其中至多1种来自上述例子），描述应用场景，讨论用图建模的方式，形式化描述问题并概述现有解决方案。 | |
| 9.11-9.15 | 3-2：连通和遍历 |
|
|
OT：在DFS和BFS的基础上，形成了很多扩展的搜索算法，例如词典序BFS、双向搜索、最佳优先搜索等，请调研至少2种扩展搜索算法（其中至多1种来自上述例子），讨论适用场景，结合例子介绍算法的设计与分析，与DFS或BFS比较异同并分析优劣。 | |
| 9.18-9.22 | 3-3：圈和遍历 |
|
|
OT：请调研至少2篇介绍哈密尔顿路或哈密尔顿圈的存在性的必要条件或充分条件的论文，讨论条件的适用场景，并阐述证明过程。 | |
| 9.25-9.29 | 3-4：连通度 |
|
|
OT：请调研并阐述面向点连通度或边连通度的门格尔定理的至少2种证明方法。 | |
| 10.2-10.6 | 3-5：匹配 |
|
|
国庆放假 | 补周一 |
| 10.9-10.13 | 3-6：单源最短路 |
|
|
OT：请调研单源最短路问题的2种并行算法Δ-stepping和Radius Stepping，结合例子介绍算法的设计与分析，比较异同并分析优劣。 | OJ讲解 |
| 10.16-10.20 | 3-7：多源最短路 |
|
|
OT：请调研多源最短路问题的至少2种并行算法，结合例子介绍算法的设计与分析，比较异同并分析优劣。 | |
| 10.23-10.27 | 3-8：最小生成树 |
|
|
OT：最小生成树问题的相关问题有很多，例如Steiner tree、k-MST、MBST等，请调研至少2种问题（其中至多1种来自上述例子，欧氏最小生成树问题等仅限制最小生成树问题输入的相关问题不在调研范围内），讨论适用场景，形式化描述问题并概述现有解决方案。 | |
| 10.30-11.3 | 3-9：问题的形式化描述 |
|
|
OT：请调研教材中未介绍过的2种判定问题和2种优化问题（不能是相互对应版本，也不能是教材中介绍过的问题的对应版本），讨论适用场景，用教材中的方法形式化描述问题。 | |
| 11.6-11.10 | 3-10：NP完全理论初步 |
|
|
OT：请调研并介绍图灵机及其至少2种等价模型，讨论图灵机、P、NP之间的关系。 | OJ讲解 |
| 11.13-11.17 | 3-11：有向图和伪多项式时间算法 |
|
|
OT：除Ford-Fulkerson算法外，最大流问题还有很多其它算法，例如Edmonds-Karp算法、Dinitz算法、Push-Relabel算法等，请调研至少2种算法（其中至多1种来自上述例子），结合例子介绍算法的设计与分析，与Ford-Fulkerson算法比较异同并分析优劣。 | |
| 11.20-11.24 | 3-12：分支定界和局部搜索算法 |
|
|
OT：除MAX-SAT和TSP外，分支定界和局部搜索算法还可用于解决其它问题，请为每种算法调研至少2种NP难问题，结合例子介绍算法的设计与分析。 | |
| 11.27-12.1 | 3-13：松弛算法 |
|
|
OT：除IP外，广义的“松弛-修正”思想还可用于解决其它问题，例如TSP的松弛修正算法、最短超串问题的松弛修正算法等，请调研至少2种算法（其中至多1种来自上述例子），结合例子介绍算法的设计与分析，重点阐述其中的“松弛-修正”思想。 | |
| 12.4-12.8 | 3-14：近似算法的基本概念 |
|
|
OT：请调研至少2种近似算法（图上的优化问题不在调研范围内），结合例子介绍算法的设计与分析，重点阐述近似比的证明过程。 | |
| 12.11-12.15 | 3-15：独立、覆盖和支配 |
|
|
||
| 12.18-12.22 | 3-16：染色 |
|
|
OJ讲解 | |
| 12.25-12.29 | 3-17：平面 |
|
|
答疑 | |
| 寒假自学 | 3-18：背包问题 |
|
-- | -- | -- |
