2023级--学期安排 (第三学期)
来自问题求解
指定教材
- CH: 程龚: 图论与算法, 2023
- TC: Thomas Cormen: Introduction to Algorithms, 3rd ed. MIT, 2009
- TJ: Thomas Judson: Abstract Algebra - Theory and Applications, http://abstract.ups.edu/
- WS: Walter Savitch: Problem Solving with C++, 7th ed. Addison Wesley, 2008
学习周历
日期 | 论题 | 阅读材料 | 书面作业 | 周一小班(讲课) | 周二大班(OJ) | 周四大班(OT) |
---|---|---|---|---|---|---|
9.2-9.6 | 3-1:图的基本概念 |
|
|
|
【学号后3位 % 3 = 0的同学完成】 图在计算机和人工智能研究中有很多应用,例如程序分析中的控制流图、信息检索中的网页链接图、知识表示中的知识图谱等,请调研至少2种应用(其中至多1种来自上述例子),描述应用场景,讨论用图建模的方式,形式化描述问题并概述现有解决方案。 |
|
9.9-9.13 | 3-2:连通和遍历 |
|
|
【学号后3位 % 3 = 1的同学完成】 在DFS和BFS的基础上,形成了很多扩展的搜索算法,例如词典序BFS、双向搜索、最佳优先搜索等,请调研至少2种扩展搜索算法(其中至多1种来自上述例子),讨论适用场景,结合例子介绍算法的设计与分析,与DFS或BFS比较异同并分析优劣。 |
||
9.16-9.20 | 3-3:圈和遍历 |
|
|
中秋调休,本次课安排在9月14日 | 【学号后3位 % 3 = 2的同学完成】 请调研教材中未介绍过的至少2种哈密尔顿路或哈密尔顿圈的存在性的必要条件或充分条件,讨论条件的适用场景,并阐述证明过程。 |
|
9.23-9.27 | 3-4:连通度 |
|
|
【学号后3位 % 3 = 0的同学完成】 请调研并阐述面向点连通度或边连通度的门格尔定理的至少2种证明方法(其中至少1种来自论文原文);门格尔定理在图论中有很多应用,请调研至少2种应用,描述应用场景。 |
||
9.30-10.4 | 3-5:匹配 |
|
|
国庆放假 | 国庆放假 | |
10.7-10.11 | 3-6:单源最短路 |
|
|
国庆调休,本次课安排在10月12日 | 作业讲解 + OJ讲解 | |
10.14-10.18 | 3-7:多源最短路 |
|
|
【学号后3位 % 3 = 1的同学完成】单源最短路问题有很多并行算法,例如Δ-stepping算法、Radius Stepping算法等,请调研至少2种算法(其中至多1种来自上述例子),结合例子介绍算法的设计与分析,比较异同并分析优劣。 | ||
10.21-10.25 | 3-8:最小生成树 |
|
|
【学号后3位 % 3 = 2的同学完成】 距离索引(Distance Oracle)是一种用于查询精确或近似距离的数据结构,请调研至少1种精确距离索引和1种近似距离索引,讨论适用场景,结合例子介绍索引构造算法和距离查询算法的设计与分析。 |
||
10.28-11.1 | 3-9:有向图 |
|
|
【学号后3位 % 3 = 0的同学完成】 最小生成树问题有很多相关问题,例如Steiner tree、k-MST、MBST等,请调研至少2种问题(其中至多1种来自上述例子,欧氏最小生成树问题等仅限制原始问题输入的问题不在调研范围内),讨论适用场景,形式化描述问题并概述现有解决方案。 |
||
11.4-11.8 | 3-10:流网络和最大流 |
|
|
【学号后3位 % 3 = 1的同学完成】 |
||
11.11-11.15 | 3-11:独立、覆盖和支配 |
|
|
【学号后3位 % 3 = 2的同学完成】 除福特-法尔克森算法外,最大流问题还有很多其它算法,例如Edmonds-Karp算法、Dinitz算法、Push-Relabel算法等,请调研至少2种算法(其中至多1种来自上述例子),结合例子介绍算法的设计与分析,与福特-法尔克森算法比较异同并分析优劣。 |
||
11.18-11.22 | 3-12:染色 |
|
|
作业讲解 + OJ讲解 | ||
11.25-11.29 | 3-13:平面 |
|
|
【学号后3位 % 3 = 0的同学完成】 在独立、覆盖和支配的基础上,形成了很多扩展的优化问题,例如最小权完美匹配问题(Minimum-Weight Perfect Matching)、最小连通支配集问题等,请调研至少2种问题(其中至多1种来自上述例子,二分图最大匹配问题等仅限制原始问题输入的问题不在调研范围内),讨论适用场景,形式化描述问题,为每种问题结合例子介绍至少1种算法的设计与分析。 |
||
12.2-12.6 | 3-14:群和循环群 |
|
|
【学号后3位 % 3 = 1的同学完成】 |
||
12.9-12.13 | 3-15:置换群、陪集和拉格朗日定理 |
|
|
【学号后3位 % 3 = 2的同学完成】 |
||
12.16-12.20 | 3-16:代数编码 |
|
|
【学号后3位 % 3 = 0的同学完成】 |
||
12.23-12.27 | 3-17:群同构、正规子群和因子群 |
|
|
【学号后3位 % 3 = 1的同学完成】 |