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

基本要求

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

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

指定教材

• CHENG: 程龚: 图论与算法
• GC: Gary Chartrand et al.: Introduction to Graph Theory, 1st ed. McGraw-Hill, 2004
• 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章
9.11-9.15	3-2：连通和遍历	CHENG第2章
9.18-9.22	3-3：圈和遍历	CHENG第3章
9.25-9.29	3-4：连通度	CHENG第4章
10.2-10.6	3-5：匹配	CHENG第5章
10.9-10.13	3-6：单源最短路	CHENG第6.1节 TC第24章
10.16-10.20	3-7：多源最短路	TC第25章
10.23-10.27	3-8：最小生成树	CHENG第6.2节
10.30-11.3	3-9：有向图	CHENG第7章 JH第3.2.1、3.2.3节
4.24-4.28	2-10：堆与堆排序	TC第6章
5.1-5.5	2-11：Hashing方法	TC第11章 CS第5章第5节		习题课
5.8-5.12	2-12：搜索树	TC第12、13章
5.15-5.19	2-13：动态规划	TC第15章		OT
5.22-5.26	2-14：贪心算法	TC第16章
5.29-6.2	2-15：用于动态等价关系的数据结构与均摊分析	TC第17章 TC第21章		OT
6.5-6.9	2-16：线性规划	TC第29章		习题课
暑假自学	2-17：矩阵计算	TC第28章
暑假自学	2-18：串匹配	TC第32章