“2022级--学期安排 (第三学期)”的版本间的差异
来自问题求解
(→学习周历) |
(→学习周历) |
||
第40行: | 第40行: | ||
</td> | </td> | ||
<td></td> | <td></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> |
</tr> | </tr> | ||
<tr> | <tr> | ||
第58行: | 第58行: | ||
</td> | </td> | ||
<td></td> | <td></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> |
</tr> | </tr> | ||
<tr> | <tr> |
2023年7月16日 (日) 18:37的版本
基本要求
- 掌握典型应用中抽象出来的重要算法问题的求解方法。
- 掌握复杂性理论的基本内容与问题规约方法。
- 理解解决“难”问题的主要方法、技术以及相关的重要理论。
注意:程序设计能力要求贯穿于整个课程,不再单列。
指定教材
- 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:圈和遍历 |
|
|
||
9.25-9.29 | 3-4:连通度 |
|
|
||
10.2-10.6 | 3-5:匹配 |
|
|
-- | -- |
10.9-10.13 | 3-6:单源最短路 |
|
|
OJ讲解 | |
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完全理论初步 |
|
|
OJ讲解 | |
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:染色 |
|
|
OJ讲解 | |
12.25-12.29 | 3-17:平面 |
|
|
答疑 | |
寒假自学 | 3-18:背包问题 |
|
-- | -- | -- |