基本要求
- 掌握典型应用中抽象出来的重要算法问题的求解方法
- 理解并能够应用支持上述内容的离散数学工具与方法
- 面向对象程序设计
考核方法
所有形式的考核,均不准抄袭。
考核形式 |
分值
|
作业 |
15
|
OT |
10
|
OJ(作业) |
15
|
OJ(测试) |
5
|
机试 |
10
|
笔试 |
45
|
指定教材
- 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
|
2020-09-02
|
|
|
|
|
|
|
TBD
|
|
|
|
|
- TC第15.1节练习1、3
- TC第15.2节练习2、4
- TC第15.3节练习3、5、6
- TC第15.4节练习3、5
- TC第15.5节练习1
- TC第15章问题4
|
|
TBD
|
|
- 掌握利用贪心策略设计算法的思路与方法
- 掌握用分摊进行算法分析的思想与方法
|
|
|
- TC第16.1节练习2、3
- TC第16.2节练习1、2
- TC第16.3节练习2、5、8
- TC第16章问题1
- TC第17.1节练习3
- TC第17.2节练习2
- TC第17.4节练习1
|
|
TBD
|
|
|
- CZ第一章
- CZ第二章2.1;2.2;2.3
- CZ第三章3.1
|
- 图论应用的广泛性以及图论证明方法的独特性
- 理解图与关系的联系
|
- CZ 练习1.2、1.3、1.11、1.12、1.24
- CZ 练习2.1、2.19、2.31
- CZ 练习3.1、3.2
|
|
TBD
|
|
- 理解动态等价关系的概念以及在问题求解中的意义
- 掌握以union-find为代表的相应数据结构
- 进一步理解抽象数据类型的意义
|
|
|
- TC第21.1节练习2、3
- TC第21.2节练习1、3、6
- TC第21.3节练习1、2、3
- TC第21章问题1
|
|
TBD
|
|
- 理解树的基本数学性质
- 掌握用带权树建立数学模型的方法
- 最小生成树算法
|
|
- 树的数学性质在计算机问题求解中的意义
- 理解贪心算法策略在最小生成树问题上的应用
|
- 练习 4.4、4.8、4.14、4.22、4.26、4.28、4.30、4.36
|
|
TBD
|
|
- 掌握在计算机中表示图的方式
- 掌握图的深度优先与广度优先遍历方法
|
|
|
- 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
|
|
TBD
|
|
- 掌握单源最短路径问题的解决方法
- 理解最短路径的数学性质并理解其在算法正确性证明中的作用
|
|
|
- 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
|
|
TBD
|
|
|
|
- 不同领域表面上完全不同的问题如何归结为同一个模型上的问题
|
- TC第25.1节练习 4、5、6、9、10
- TC第25.2节练习 2、4、6、8
- TC第25.3节练习 2、3
- TC第25章问题 2
|
|
TBD
|
|
|
|
|
- CZ: 5.4、5.8
- CZ: 5.10、5.12
- CZ: 5.18、5.22、5.26
- CZ: 5.34
|
|
TBD
|
|
|
|
- 如何针对具体问题建立图模型,并利用图上的“旅行”概念对问题的解进行描述
|
- CZ: 6.4、6.6、6.10、6.12、6.20
|
|
TBD
|
|
|
|
|
- CZ 8.3、8.5、8.14、8.16、8.18、8.21、8.24
|
|
TBD
|
|
|
|
- 最大流与最小割集的关系在算法正确性证明中的影响
- 叠加式算法及其分析
|
- TC 第26.1节练习 1、2、6、7
- TC 第26.2节练习 2、6、8、10、12、13
- TC 第26.3节练习 3
- TC 第26章问题 1、2
|
|
TBD
|
|
- 理解图论中一些著名的问题以及它们在计算机问题求解中的地位,包括图顶点着色问题、平面图等
|
(注: Theorem 10.10 证明有误)
|
|
- CZ 9.3、9.5、9.7、9.8
- CZ 10.2、10.3、10.4、10.5
|
|
TBD
|
|
- 掌握矩阵计算中一些基本问题的算法以及其在线性系统中的应用
|
|
|
- TC 第28.1节练习 2、3、6、7
- TC 第28.2节练习 1、2、3
- TC 第28.3节练习 1、3
- TC 第28章问题 1
|
|
TBD
|
|
|
|
|
|
- 戴若石
- 陈昱名
- 殷兆恒
- 张博乔 (取消)
|