“2022级--学期安排 (第三学期)”的版本间的差异
来自问题求解
（→学习周历） |
|||
| 第258行： | 第258行： | ||
<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> | ||
2023年12月6日 (三) 12:16的版本
基本要求
- 掌握典型应用中抽象出来的重要算法问题的求解方法。
- 掌握复杂性理论的基本内容与问题规约方法。
- 理解解决“难”问题的主要方法、技术以及相关的重要理论。
注意：程序设计能力要求贯穿于整个课程，不再单列。
指定教材
- 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：背包问题 |
|
-- | -- | -- |
