2022级--学期安排 (第三学期)

来自问题求解
Admin（讨论 | 贡献）2023年8月8日 (二) 22:57的版本 （→‎学习周历）

跳转至： 导航、 搜索

基本要求

  • 掌握典型应用中抽象出来的重要算法问题的求解方法。
  • 掌握复杂性理论的基本内容与问题规约方法。
  • 理解解决“难”问题的主要方法、技术以及相关的重要理论。

注意：程序设计能力要求贯穿于整个课程，不再单列。

指定教材

  • 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：图的基本概念
  • CHENG第1章
  • CHENG练习1.1、1.2、1.3、1.4
  • CHENG练习1.7、1.8
 OT：图在计算机和人工智能研究中有很多应用，例如程序分析中的控制流图、信息检索中的网页链接图、知识表示中的知识图谱等，请调研至少2种应用（其中至多1种来自上述例子），描述应用场景，讨论用图建模的方式，形式化描述问题并概述现有解决方案。
9.11-9.15 3-2：连通和遍历
  • CHENG第2章
  • CHENG练习2.1、2.2、2.3
  • CHENG练习2.8
  • CHENG练习2.11、2.12、2.13
 OT：在DFS和BFS的基础上，形成了很多扩展的搜索算法，例如词典序BFS、双向搜索、最佳优先搜索等，请调研至少2种扩展搜索算法（其中至多1种来自上述例子），讨论适用场景，结合例子介绍算法的设计与分析，与DFS或BFS比较异同并分析优劣。
9.18-9.22 3-3：圈和遍历
  • CHENG第3章
  • CHENG练习3.1、3.2、3.3、3.4、3.5、3.6、3.7
  • CHENG练习3.10、3.11、3.12、3.13
  • CHENG练习3.16、3.17、3.18、3.19
  • CHENG练习3.23、3.24
 OT：请调研至少2篇介绍哈密尔顿路或哈密尔顿圈的存在性的必要条件或充分条件的论文，讨论条件的适用场景，并阐述证明过程。
9.25-9.29 3-4：连通度
  • CHENG第4章
  • CHENG练习4.1
  • CHENG练习4.4、4.5、4.6、4.7
 OT：请调研并阐述面向点连通度或边连通度的门格尔定理的至少2种证明方法。
10.2-10.6 3-5：匹配
  • CHENG第5章
  • CHENG练习5.1
  • CHENG练习5.5、5.6
 国庆放假 补周一
10.9-10.13 3-6：单源最短路
  • CHENG第6.1节
  • TC第24章
  • TC练习24.1-2、3、4
  • TC练习24.2-2
  • TC练习24.3-2、4、7
  • TC练习24.5-2、5
  • TC问题24-2、3
 OT：请调研单源最短路问题的2种并行算法Δ-stepping和Radius Stepping，结合例子介绍算法的设计与分析，比较异同并分析优劣。 OJ讲解
10.16-10.20 3-7：多源最短路
  • TC第25章
  • TC练习25.1-4、5、6、9、10
  • TC练习25.2-2、4、6、8
  • TC练习25.3-2、3
  • TC问题25-2
 OT：请调研多源最短路问题的至少2种并行算法，结合例子介绍算法的设计与分析，比较异同并分析优劣。
10.23-10.27 3-8：最小生成树
  • CHENG第6.2节
  • CHENG练习6.3
 OT：最小生成树问题的相关问题有很多，例如Steiner tree、k-MST、MBST等，请调研至少2种问题（其中至多1种来自上述例子，欧氏最小生成树问题等仅限制原始问题输入的问题不在调研范围内），讨论适用场景，形式化描述问题并概述现有解决方案。
10.30-11.3 3-9：问题的形式化描述
  • JH第2.3.1、2.3.2节
  • JH练习2.3.1.7、2.3.1.8
 OT：请调研教材中未介绍过的2种判定问题和2种优化问题（不能是相互对应版本，也不能是教材中介绍过的问题的对应版本），讨论适用场景，用教材中的方法形式化描述问题。
11.6-11.10 3-10：NP完全理论初步
  • TC第34章
  • TC练习34.2-3、4、6、11
  • TC练习34.3-2
  • TC练习34.5-6
 OT：请调研并介绍图灵机及其至少2种等价模型，讨论图灵机、P、NP之间的关系。 OJ讲解
11.13-11.17 3-11：有向图和伪多项式时间算法
  • CHENG第7章
  • JH第3.2.1、3.2.3节
  • CHENG练习7.1、7.2
  • CHENG练习7.4、7.5
  • CHENG练习7.17、7.18、7.19、7.20、7.21、7.22
 OT：除福特-法尔克森算法外，最大流问题还有很多其它算法，例如Edmonds-Karp算法、Dinitz算法、Push-Relabel算法等，请调研至少2种算法（其中至多1种来自上述例子），结合例子介绍算法的设计与分析，与福特-法尔克森算法比较异同并分析优劣。
11.20-11.24 3-12：分支定界和局部搜索算法
  • JH第3.4、3.6节
  • JH练习3.4.2.1、3.4.2.2
  • JH练习3.6.1.3
 OT：除MAX-SAT和TSP外，分支定界和局部搜索算法还可用于解决其它问题，请为每种算法调研至少2种可以解决的问题，结合例子介绍算法的设计与分析。
11.27-12.1 3-13：松弛算法
  • JH第3.7节
  • JH练习3.7.2.1、3.7.2.4、3.7.2.5
  • JH练习3.7.4.4、3.7.4.12、3.7.4.16
 OT：除IP外，广义的“松弛-修正”思想还可用于解决其它问题，例如TSP的松弛修正算法、最短超串问题的松弛修正算法等，请调研至少2种算法（其中至多1种来自上述例子），结合例子介绍算法的设计与分析，重点阐述其中的“松弛-修正”思想。
12.4-12.8 3-14：近似算法的基本概念
  • JH第4.2.1、4.2.2、4.3.3节
  • JH练习4.2.1.4、4.2.1.5
  • JH练习4.3.3.5、4.3.3.6
 OT：除MS和MAX-CUT外，近似算法还可用于解决其它问题，例如SCP（JH算法4.3.2.11）、SKP（JH算法4.3.4.1和4.3.4.2）等，请调研至少2种近似算法（其中至多1种来自上述例子，图上的优化问题不在调研范围内），结合例子介绍算法的设计与分析，重点阐述近似比的证明过程。
12.11-12.15 3-15：独立、覆盖和支配
  • CHENG第8章
  • CHENG练习8.1、8.2
  • CHENG练习8.5
 OT：在独立、覆盖和支配的基础上，形成了很多扩展的优化问题，例如最小权完美匹配问题（Minimum-Weight Perfect Matching）、最小连通支配集问题等，请调研至少2种问题（其中至多1种来自上述例子，二分图最大匹配问题等仅限制原始问题输入的问题不在调研范围内），讨论适用场景，形式化描述问题，为每种问题结合例子介绍至少1种算法的设计与分析。
12.18-12.22 3-16：染色
  • CHENG第9章
  • CHENG练习9.1、9.2
  • CHENG练习9.5、9.6
 OT：除米什拉-格赖斯算法和贪心算法外，边染色和点染色问题还有很多其它算法，请为每种问题调研至少1种精确算法（暴力算法不在调研范围内），结合例子介绍算法的设计与分析。 OJ讲解
12.25-12.29 3-17：平面
  • CHENG第10章
  • CHENG练习10.1、10.2、10.3、10.4
 OT：除DMP算法外，可平面图的判定问题还有很多其它算法，请调研至少2种算法，结合例子介绍算法的设计与分析，与DMP算法比较异同并分析优劣。 答疑
寒假自学 3-18：背包问题
  • JH第4.3.4节
 -- -- --
取自“http://cslabcms.nju.edu.cn/problem_solving/index.php?title=2022级--学期安排_(第三学期)&oldid=5148”