“2017级--学期安排 (第三学期)”的版本间的差异
来自问题求解
(→学习周历) |
(→学习周历) |
||
(未显示3个用户的52个中间版本) | |||
第28行: | 第28行: | ||
* '''TC''': Thomas Cormen et al.: [[Media:CLRS_Introduction_to_Algorithms_(3rd_Edition,_2009).pdf | Introduction to Algorithms]], 3rd ed. MIT, 2009 | * '''TC''': Thomas Cormen et al.: [[Media:CLRS_Introduction_to_Algorithms_(3rd_Edition,_2009).pdf | Introduction to Algorithms]], 3rd ed. MIT, 2009 | ||
− | *'''CZ''': Gary Chartrand, Ping Zhang: | + | *'''CZ''': Gary Chartrand, Ping Zhang: A First Course in Graph Theory |
== 推荐课外阅读材料 == | == 推荐课外阅读材料 == | ||
'''''(可参照习题课扩展材料部分所给出的阅读建议)''''' | '''''(可参照习题课扩展材料部分所给出的阅读建议)''''' | ||
+ | |||
+ | Jon Kleinberg, Eva Tardos. "Algorithm Design". | ||
更多阅读材料将随课堂进度添加。 | 更多阅读材料将随课堂进度添加。 | ||
第138行: | 第140行: | ||
2018-10-09 | 2018-10-09 | ||
| | | | ||
− | * [[ | 3-4:用于动态等价关系的数据结构]] | + | * [[Media:计算机问题求解-动态等价关系.pptx| 3-4:用于动态等价关系的数据结构]] |
| | | | ||
* 理解动态等价关系的概念以及在问题求解中的意义 | * 理解动态等价关系的概念以及在问题求解中的意义 | ||
第153行: | 第155行: | ||
* TC第21章问题1 | * TC第21章问题1 | ||
| | | | ||
− | * | + | * LCA |
+ | # 杜星亮 | ||
+ | # 彭翔宇 | ||
+ | * Partition Refinement | ||
+ | # 袁彦 | ||
+ | # 马常风 | ||
+ | |- | ||
+ | | | ||
+ | 2018-10-16 | ||
+ | | | ||
+ | * [[Media:3-5-计算机问题求解-2018-10-16-树.pptx | 3-5: 树]] | ||
+ | | | ||
+ | * 理解树的基本数学性质 | ||
+ | * 掌握用带权树建立数学模型的方法 | ||
+ | * 最小生成树算法 | ||
+ | | | ||
+ | * CZ 第4章 | ||
+ | | style="width: 140px;" | | ||
+ | * 树的数学性质在计算机问题求解中的意义 | ||
+ | * 理解贪心算法策略在最小生成树问题上的应用 | ||
+ | | | ||
+ | * 练习 4.4、4.8、4.14、4.22、4.26、4.28、4.30、4.36 | ||
+ | | | ||
+ | * Kruskal 算法和 Prim 算法的实现及其效率 | ||
+ | # 谢乃容 | ||
+ | # 刘恩萌 | ||
+ | * 使用矩阵表示实现最小生成树算法 | ||
+ | # 何润雨 | ||
+ | # 殷兆恒 | ||
+ | |- | ||
+ | | | ||
+ | 2018-10-25 | ||
+ | | | ||
+ | * [[Media:计算机问题求解-2018-10-25图的计算机表示及其遍历.pptx| 3-6: 图的计算机表示以及遍历]] | ||
+ | | | ||
+ | * 掌握在计算机中表示图的方式 | ||
+ | * 掌握图的深度优先与广度优先遍历方法 | ||
+ | | | ||
+ | * TC第22章 | ||
+ | | style="width: 140px;" | | ||
+ | * 图表示中形式与效率的关系 | ||
+ | * 不同遍历方法的算法意义 | ||
+ | | | ||
+ | * TC第22.1节练习 3、8 | ||
+ | * TC第22.2节练习 3 ("lines 5 and 14" 修改为 "line 18")、4、5 | ||
+ | * TC第22.3节练习 6、7、8、9、12 | ||
+ | * TC第22.4节练习 2、3 | ||
+ | * TC第22.5节练习 5、7 | ||
+ | | | ||
+ | * DFS算法及其正确性 | ||
+ | # 桑百惠 | ||
+ | # 梁宇方 | ||
+ | * SCC算法正确性 | ||
+ | # 王腾 | ||
+ | # 郑奘巍 | ||
+ | |- | ||
+ | | | ||
+ | 2018-10-30 | ||
+ | | | ||
+ | * [[Media:计算机问题求解-2018-10-30-单源最短通路算法.pptx | 3-7: 单源最短路径算法]] | ||
+ | | | ||
+ | * 掌握单源最短路径问题的解决方法 | ||
+ | * 理解最短路径的数学性质并理解其在算法正确性证明中的作用 | ||
+ | | | ||
+ | * TC第24章 | ||
+ | | style="width: 140px;" | | ||
+ | * 贪心策略在不同算法中的不同体现 | ||
+ | | | ||
+ | * 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 | ||
+ | | | ||
+ | * Bellman-Ford 算法输出负权环 | ||
+ | # 张天昀 | ||
+ | # 丁保荣 | ||
+ | * 使用 Fibonacci Heap 的 Dijkstra 算法的复杂度分析 | ||
+ | # 毛一鸣 | ||
+ | # 李顶为 | ||
+ | |- | ||
+ | | | ||
+ | 2018-11-06 | ||
+ | | | ||
+ | * [[Media:计算机问题求解-2018-11-6-多源最短通路算法.pptx | 3-8: 多源最短路径算法]] | ||
+ | | | ||
+ | * 掌握多源最短路径问题的解决方法 | ||
+ | | | ||
+ | * TC第25章 | ||
+ | | style="width: 140px;" | | ||
+ | * 不同领域表面上完全不同的问题如何归结为同一个模型上的问题 | ||
+ | | | ||
+ | * TC第25.1节练习 4、5、6、9、10 | ||
+ | * TC第25.2节练习 2、4、6、8 | ||
+ | * TC第25.3节练习 2、3 | ||
+ | * TC第25章问题 2 | ||
+ | | | ||
+ | * Floyd-Warshall 算法输出最短路径 | ||
+ | # 周海波 | ||
+ | # 李凯旭 | ||
+ | * 炼钢厂选址 | ||
+ | # 徐臣 | ||
+ | # 匡舒磊 | ||
+ | |- | ||
+ | | | ||
+ | 2018-11-13 | ||
+ | | | ||
+ | * [[Media:计算机问题求解-2018-11-13-图的连通度.pptx | 3-9: 图的连通度]] | ||
+ | | | ||
+ | * 理解图的连通度的概念与相关理论 | ||
+ | | | ||
+ | * CZ 5.1-5.4 | ||
+ | * CZ 12.1, 12.2 | ||
+ | | style="width: 140px;" | | ||
+ | * 连通性的度量方式及其等效性 | ||
+ | | | ||
+ | * CZ: 5.4、5.8 | ||
+ | * CZ: 5.10、5.12 | ||
+ | * CZ: 5.18、5.22、5.26 | ||
+ | * CZ: 5.34 | ||
+ | | | ||
+ | * Block 算法 | ||
+ | # | ||
+ | # 毕秋宇 | ||
+ | * 证明 Harary 图是r-连通的。 | ||
+ | # 黄秉焜 | ||
# | # | ||
− | # | + | |- |
− | * | + | | |
+ | 2018-11-20 | ||
+ | | | ||
+ | * [[Media:计算机问题求解-2018-11-20图上的旅行.pptx | 3-10: 旅行问题]] | ||
+ | | | ||
+ | * 哈密尔顿回路问题、TSP问题 | ||
+ | | | ||
+ | * CZ第6章 | ||
+ | | style="width: 140px;" | | ||
+ | * 如何针对具体问题建立图模型,并利用图上的“旅行”概念对问题的解进行描述 | ||
+ | | | ||
+ | * CZ: 6.4、6.6、6.10、6.12、6.20 | ||
+ | | | ||
+ | * 竞赛图 | ||
+ | # 何伟 | ||
+ | # 殷天润 | ||
+ | * 循环赛排名方法 | ||
+ | # 孙旭东 | ||
+ | # 李博文 | ||
+ | |- | ||
+ | | | ||
+ | 2018-11-29 | ||
+ | | | ||
+ | * [[Media:计算机问题求解-2018-11-29-匹配与因子分解.pptx | 3-11: 图中的匹配与覆盖]] | ||
+ | | | ||
+ | * 掌握图中匹配与覆盖的概念、关键问题与算法 | ||
+ | | | ||
+ | * CZ第8章 | ||
+ | | style="width: 140px;" | | ||
+ | * 点与边、匹配与覆盖的对称性 | ||
+ | | | ||
+ | * CZ 8.3、8.5、8.14、8.16、8.18、8.21、8.24 | ||
+ | | | ||
+ | * 点独立与点覆盖 | ||
+ | # 刘寒 | ||
+ | # 韩博 | ||
+ | * 点独立与点覆盖 | ||
+ | # 杨欣然 | ||
# | # | ||
− | # | + | |- |
+ | | | ||
+ | 2018-12-04 | ||
+ | | | ||
+ | * [[Media:计算机问题求解-2018-12-04最大流算法.pptx | 3-12: 最大流算法]] | ||
+ | | | ||
+ | * 掌握网络最大流问题的算法 | ||
+ | | | ||
+ | * TC第26章 | ||
+ | | style="width: 140px;" | | ||
+ | * 最大流与最小割集的关系在算法正确性证明中的影响 | ||
+ | * 叠加式算法及其分析 | ||
+ | | | ||
+ | * TC 第26.1节练习 1、2、6、7 | ||
+ | * TC 第26.2节练习 2、6、8、10、12、13 | ||
+ | * TC 第26.3节练习 3 | ||
+ | * TC 第26章问题 1、2 | ||
+ | | | ||
+ | * Ford-Fulkerson's Labeling Algorithm | ||
+ | # 张梓悦 | ||
+ | # 周涛 | ||
+ | * 利用最大流算法证明 Hall 定理 | ||
+ | # 裴一凡 | ||
+ | # 董杨静 | ||
+ | |- | ||
+ | | | ||
+ | 2018-12-11 | ||
+ | | | ||
+ | * [[Media:计算机问题求解-2018-12-11-平面图和图着色基础.pptx | 3-13: 平面图与图着色]] | ||
+ | | | ||
+ | * 理解图论中一些著名的问题以及它们在计算机问题求解中的地位,包括图顶点着色问题、平面图等 | ||
+ | | | ||
+ | * CZ 9.1 | ||
+ | * CZ 10.1、10.2 | ||
+ | (注: Theorem 10.10 证明有误) | ||
+ | | style="width: 140px;" | | ||
+ | * 图模型应用的广泛性 | ||
+ | | | ||
+ | * CZ 9.3、9.5、9.7、9.8 | ||
+ | * CZ 10.2、10.3、10.4、10.5 | ||
+ | | | ||
+ | * Brooks 定理 | ||
+ | # 张廷昊、裴明亮 | ||
+ | # 高天朗、邱凯 | ||
+ | * Martin Gardner | ||
+ | # 赵新榆 | ||
+ | # 兰兆炜 | ||
+ | |- | ||
+ | | | ||
+ | 2018-12-18 | ||
+ | | | ||
+ | * [[Media: 计算机问题求解-2018-12-20-矩阵计算.pptx| 3-14: 矩阵计算]] | ||
+ | | | ||
+ | * 掌握矩阵计算中一些基本问题的算法以及其在线性系统中的应用 | ||
+ | | | ||
+ | * TC 第28章 | ||
+ | | style="width: 140px;" | | ||
+ | * 线性系统及其在问题求解中的重要性 | ||
+ | | | ||
+ | * TC 第28.1节练习 2、3、6、7 | ||
+ | * TC 第28.2节练习 1、2、3 | ||
+ | * TC 第28.3节练习 1、3 | ||
+ | * TC 第28章问题 1 | ||
+ | | | ||
+ | * LUP 分解算法的正确性 | ||
+ | # 廖玺然 | ||
+ | # 陶绍诚 | ||
+ | * LUP 分解求矩阵的行列式 | ||
+ | # 张扬播 | ||
+ | # 顾宬 | ||
+ | |- | ||
+ | | | ||
+ | 2018-12-25 | ||
+ | | | ||
+ | * | ||
+ | | | ||
+ | * | ||
+ | | | ||
+ | * | ||
+ | | | ||
+ | * | ||
+ | | | ||
+ | * | ||
+ | | | ||
+ | * CZ 9.8、CZ 10.5 | ||
+ | # 戴若石 | ||
+ | * CZ Theorem 10.10 | ||
+ | # 陈昱名 | ||
+ | * Dilworth Theorem | ||
+ | # 殷兆恒 | ||
+ | # 张博乔 (取消) | ||
|- | |- | ||
|} | |} |
2019年1月20日 (日) 14:21的最新版本
基本要求
- 掌握典型应用中抽象出来的重要算法问题的求解方法
- 理解并能够应用支持上述内容的离散数学工具与方法
- 面向对象程序设计
考核方法
所有形式的考核,均不准抄袭。
- 作业 (10%)
- A: 10
- A-: 9
- B: 8
- B-: 7
- C: 6
- OJ (10%)
- Open topics (10%)
- 成绩: A (10), B (8), C (6) 三档
- 每人至少做一次
- 做多次报告,取最高分
- 不做计 0 分
- 期末: (70%)
- 机试 (20%)
- 笔试 (50%)
指定教材
- TC: Thomas Cormen et al.: Introduction to Algorithms, 3rd ed. MIT, 2009
- CZ: Gary Chartrand, Ping Zhang: A First Course in Graph Theory
推荐课外阅读材料
(可参照习题课扩展材料部分所给出的阅读建议)
Jon Kleinberg, Eva Tardos. "Algorithm Design".
更多阅读材料将随课堂进度添加。
学习周历
日期 | 论题 | 学习目的 | 阅读材料 | 引导要点 | 书面作业 | Open Topics |
---|---|---|---|---|---|---|
2018-09-04 |
|
|
|
|
| |
2018-09-11 |
|
|
|
|
| |
2018-09-18 |
|
|
|
|
| |
2018-09-25 |
|
|
|
|
| |
2018-10-09 |
|
|
|
|
| |
2018-10-16 |
|
|
|
|
| |
2018-10-25 |
|
|
|
|
| |
2018-10-30 |
|
|
|
|
| |
2018-11-06 |
|
|
|
|
| |
2018-11-13 |
|
|
|
|
| |
2018-11-20 |
|
|
|
|
| |
2018-11-29 |
|
|
|
|
| |
2018-12-04 |
|
|
|
|
| |
2018-12-11 |
|
(注: Theorem 10.10 证明有误) |
|
|
| |
2018-12-18 |
|
|
|
|
| |
2018-12-25 |
|
|
|
|
|
|