2020级--学期安排 (第二学期)

基本要求

• 理解数据抽象，理解并能够应用常用的数据结构。
• 掌握重要算法设计策略以及算法设计与分析的基本方法。
• 理解并能够应用支持上述内容的离散数学工具与方法。

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

指定教材

• CS: Cliff Stein et al.: Discrete Mathematics for Computer Scientists, 1st ed. Addison-Wesley, 2010
• GC: Gary Chartrand et al.: A First Course in Graph Theory, 1st ed. Dover, 2012
• SB: Sara Baase et al.: Computer Algorithms - Introduction to Design and Analysis, 3rd ed. Addison-Wesley, 1999 (第2章：抽象数据类型)
• TC: Thomas Cormen: Introduction to Algorithms, 3rd ed. MIT, 2009
• WS: Walter Savitch: Problem Solving with C++, 7th ed. Addison Wesley, 2008

推荐课外读物

• Kenneth H. Rosen: Discrete Mathematics and Its Applications, 7th ed. McGraw-Hill, 2011

学习周历

日期	论题	学习目的	阅读材料	引导要点
3.1-3.5	2-1：算法问题与解题的算法 课件1 课件2	理解计算机算法的相关概念 掌握算法复杂性的基本度量方法	TC第1、2、3章	算法设计与算法分析是计算机问题求解不可互却的两个方面
3.8-3.12	2-2：组合与计数	掌握在算法分析中常用的计数原理与方法	CS第1章	为什么算法分析中需要计数
3.15-3.19	2-3：分治法与递归	掌握利用分治法设计算法的思路 深入理解递归在算法设计中的作用	TC第4章	策略在计算机算法设计中的意义
3.22-3.26	2-4：递归及其数学基础	进一步理解递归的数学基础 更深入地掌握递归算法的分析方法	CS第4章第1、2、3、4节	如何解递归式
3.29-4.2	2-5：离散概率基础	理解离散概率的基本概念 掌握简单离散概率计算的基本方法	CS第5章第1、2、3、4节	正确理解期望值，由此建立算法分析中期望效率理解的基础
4.5-4.9	2-6：概率分析与随机算法	理解概率在算法设计中的作用 掌握基于概率的算法分析的基本方法	TC第5章 CS第5章第6、7节	随机变量在算法分析中的意义
4.12-4.16	2-7：排序与选择	深入理解快速排序算法的设计思想与分析方法 通过排序理解问题复杂度的下限，并探索一些线性排序算法 掌握以中位数为代表的统计算法	TC第7、8、9章	如何证明问题复杂度的下限
4.19-4.23	2-8：基本数据结构	掌握堆栈、队列、链表、指针、根树的概念、实现以及在算法设计中的应用	TC第10章	数据结构的算法支撑与实现效率的平衡
4.26-4.30	2-9：堆与堆排序	理解并掌握堆的结构、实现以及算法应用 通过堆的应用与实现理解抽象数据类型的基本概念以及分层抽象的思想	TC第6章 SB第2章	从数据结构到抽象数据类型的思想发展
5.3-5.7	2-10：Hashing方法	掌握Hashing方法的原理、处理冲突的方法以及分析方法	TC第11章 CS第5章第5节	Hashing方法中的冲突处理
5.10-5.14	2-11：搜索树	掌握利用树结构存储与搜索数据的方法	TC第12、13章	树的平衡与搜索效率的关系
5.17-5.21	2-12：动态规划	通过实例掌握动态规划的基本思想与算法设计方法	TC第15章	以空间换时间的关键是存储效率 动态规划与指数时间的有效降低
5.24-5.28	2-13：贪心算法	掌握利用贪心策略设计算法的思路与方法 掌握用分摊进行算法分析的思想与方法	TC第16章第1、2、3节 TC第17章	贪心算法的正确性证明
5.31-6.4	2-14：用于动态等价关系的数据结构	理解动态等价关系的概念以及在问题求解中的意义 掌握以union-find为代表的相应数据结构 进一步理解抽象数据类型的意义	TC第21章 SB第2章	算法分析的困难性
6.7-6.11	2-15：图的基本概念	掌握图的基本概念以及图论的基本证明方式	GC第1章 GC第2章第1、2节 GC第3章第1节	图论应用的广泛性以及图论证明方法的独特性 理解图与关系的联系
6.14-6.18	2-16：图的计算机表示以及遍历	掌握在计算机中表示图的方式 掌握图的深度优先与广度优先遍历方法	TC第22章	图表示中形式与效率的关系 不同遍历方法的算法意义
暑假自学	2-17：树	理解树的基本数学性质 掌握用加权树建立数学模型的方法	GC第4章第1、2、3节	树的数学性质在计算机问题求解中的意义
暑假自学	2-18：最小生成树算法	理解贪心算法在最小生成树问题中的应用	TC第23章	如何评价同一问题的不同算法