“2019级--学期安排 (第二学期)”的版本间的差异

2022年3月30日 (三) 09:52的最新版本

基本要求

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

考核方法

所有形式的考核,均不准抄袭。

考核形式	分值
作业	15
OT	10
OJ	15
机试	10
笔试	50

指定教材

DH: David Harel et al.: Algorithmics - The Spirit of Computing, 3rd ed. Addison-Wesley, 2004
CS: Clifford Stein et al.: Discrete Mathematics for Computer Scientists, 1st ed. Addison-Wesley, 2010
TC: Thomas Cormen et al.: Introduction to Algorithms, 3rd ed. MIT, 2009
MA: Manoochehr Azmoodeh. Abstract Data Types and Algorithms, Macmillan Education, UK, 1990

学习周历

日期	论题	学习目的	阅读材料	引导要点	书面作业 (非稳定版本作业@GitHub)	编程作业
2020-02-20	1-13: 布尔代数	理解布尔代数基本概念理解布尔代数与格的联系与区别布尔代数表达式的化简	SM第15章	布尔代数	1-13-boolean-algebra	[布尔代数与算法正确性]
2020-02-27	2-1: 算法的正确性	理解并能够区分算法错误与程序错误理解算法正确性的概念及其证明方法	DH第5章	循环不变式	2-1-correctness	[热身专题]
2020-03-05	2-2：算法的效率 2019-2-2-efficiency 2019-2-2-efficiency-handout	理解算法的时间复杂性的概念与渐近表示方式	DH第6章 TC 2.1节, 2.2节 TC 第3章	如何做算法复杂度分析	2-2-efficiency	[算法复杂度]
2020-03-12	2-3：组合与计数 2019-2-3-counting 2019-2-3-counting-handout	掌握在算法分析中常用的计数原理与方法	CS第1章	组合计数技巧与常见形式	2-3-counting	[组合与计数]
2020-03-19	2-4: 分治法与递归	掌握利用分治法设计算法的思路深入理解递归在算法设计中的作用	TC 第2.3节 TC 第4章	算法设计中的分治思想	2-4-recurrence	[分治法与递归]
2020-03-26	2019-2-5-linear-recurrences (马) 2019-2-5-linear-recurrences (魏) 2019-2-5-linear-recurrences-handout (魏)	进一步理解递归的数学基础更深入地掌握递归算法的分析方法	CS第4章 4.1-4.5 节	如何解递归式	2-5-solving-recurrence	[分治法与递归2]
2020-04-02	2-6: 算法方法	通过具体示例了解算法设计的基本策略	DH第4章	理解复杂算法背后的简单原理	2-6-algorithmic-methods	[算法方法]
2020-04-09	2-7: 离散概率基础	理解离散概率的基本概念掌握简单离散概率计算的基本方法	CS第5章: 5.1, 5.2, 5.3, 5.4 节	正确理解“期望”的概念，为理解平均情况时间复杂度分析建立基础	2-7-discrete-probability	[离散概率]
2020-04-16	2-8: 概率分析与随机算法	理解概率在算法设计中的作用掌握基于概率的算法分析的基本方法	TC第5章 CS第5章: 5.6, 5.7节	随机变量在算法分析中的意义	2-8-probabilistic-analysis	[随机算法]
2020-04-23	2019-2-9-sorting and selection.pdf 2019-2-9-sorting_and_selection(handout).pdf	深入理解快速排序算法的设计思想与分析方法通过排序理解问题复杂度的下界，并探索一些线性排序算法掌握以中位数为代表的统计算法	TC第7、8、9章	如何证明问题复杂度的下界	2-9-sorting-selection	[排序与选择]
2020-04-30	2-10: 基本数据结构	掌握堆栈、队列、链表、指针、根树的概念、实现以及在算法设计中的应用	TC第10章 MA第2, 3章	基本数据结构	2-10-data-structures	[基础数据结构-1]
2020-05-07	2019-2-11_Heap&HeapSort ‎	理解并掌握堆的结构、实现以及算法应用通过堆的应用与实现理解抽象数据类型的基本概念以及分层抽象的思想	TC第6章	从数据结构到抽象数据类型的思想发展	2-11-heapsort	[基础数据结构-2]
2020-05-14	2-12: Hashing方法	掌握Hashing方法的原理、处理冲突的方法以及分析方法	TC第11章 CS第5章第5节	Hashing方法中的冲突处理	2-12-hashing	[哈希]
2019-05-21	2-13：搜索树	掌握利用树结构存储与搜索数据的方法	MA 第4.1节 TC第12章	搜索树的结构与操作	2-13-bst	[搜索树]
2019-05-28	2-14：B 树	掌握 B 树的基本性质及其操作	TC第18章	如何在经典数据结构的基础上，针对应用特征，优化设计，提高效率	2-14-b-tree	[编程复习]
2019-06-04	2-15: 红黑树 (改为课堂练习)	掌握红黑树数据结构的基本性质及其操作	TC第13章	红黑树的概念	2-15-rb-tree
					2019-2-correction

“2019级--学期安排 (第二学期)”的版本间的差异

2022年3月30日 (三) 09:52的最新版本

目录

基本要求

考核方法

指定教材

推荐课外阅读材料

学习周历

导航菜单

个人工具

命名空间

变种

视图

更多

搜索

导航

工具

@@ 第35行： / 第35行： @@
 '''''(可参照习题课扩展材料部分所给出的阅读建议)'''''
-* Kenneth H. Rosen: [[Media:Discrete_Mathematics_and_Its_Applications_(7th_Edition).pdf ‎| Discrete Mathematics and Its Applications]], 7th Edition. McGraw-Hill, 2011
+* Kenneth H. Rosen: Discrete Mathematics and Its Applications, 7th Edition. McGraw-Hill, 2011
 * '''[TAOCP-4A]''' Donald E. Knuth: [[Media:The_Art_of_Computer_Programmin_Volume4A_Combinatorial_Algorithms.pdf | The Art of Computer Programming Vol4A: Combinatorial Algorithms Part 1]], 2011
@@ 第132行： / 第132行： @@
 |-
 |
 -03-19
 |
 * [[Media:2-4-计算机问题求解-2020-03-19-分治法与递归.pptx | 2-4: 分治法与递归]]
@@ 第149行： / 第149行： @@
 |-
 |
 -03-26
 |
-* [[Media:2-5-递归及其数学基础-2018-4-4.pptx | 2-5: 递归及其数学基础 (OLD)]]
+* [[Media:2-5-递归及其数学基础(part-1).pptx |2019-2-5-linear-recurrences (马)]]
+* [[Media:2019-2-5-linear-recurrences.pdf | 2019-2-5-linear-recurrences (魏)]]
+* [[Media:2019-2-5-linear-recurrences-handout.pdf | 2019-2-5-linear-recurrences-handout (魏)]]
 |
 * 进一步理解递归的数学基础
@@ 第162行： / 第164行： @@
 * [[Media:2-5-solving-recurrence.zip | 2-5-solving-recurrence]]
 |
+*[[http://oj.problemoverflow.top/2019-2/6/ 分治法与递归2]]
 |-
 |
--xx-xx
+-04-02
 |
-* [[Media:2-6-算法方法-2017-04-09.pptx | 2-6: 算法方法]]
+* [[Media:计算机问题求解-2022-03-30-算法方法.pptx | 2-6: 算法方法]]
 |
 * 通过具体示例了解算法设计的基本策略
@@ 第174行： / 第177行： @@
 * 理解复杂算法背后的简单原理
 |
-* DH 第4章练习 1, 8, 9, 12, 14
+* [[Media:2-6-algorithmic-methods.zip | 2-6-algorithmic-methods]]
 |
+*[[http://oj.problemoverflow.top/2019-2/7/ 算法方法]]
 |-
 |
--xx-xx
+-04-09
 |
-* [[Media:2-7-离散概率基础-2018-04-18.pptx | 2-7: 离散概率基础]]
+* [[Media:2-7-计算机问题求解-2020-04-09-离散概率基础.pptx | 2-7: 离散概率基础]]
 |
 * 理解离散概率的基本概念
@@ 第190行： / 第193行： @@
 * 正确理解“期望”的概念，为理解平均情况时间复杂度分析建立基础
 |
-* CS第5.1节问题 10, 12
+* [[Media:2-7-discrete-probability.zip | 2-7-discrete-probability]]
-* CS第5.2节问题 4, 10
-* CS第5.3节问题 2, 6, 12
-* CS第5.4节问题 4, 10, 12 ("Solve Problem 10" 改为 "Solve Problem 11"), 15
 |
+*[[http://oj.problemoverflow.top/2019-2/8/ 离散概率]]
 |-
 |
--xx-xx
+-04-16
 |
-* [[Media:2-8-概率分析与随机算法-2018-04-24.pptx | 2-8: 概率分析与随机算法]]
+* [[Media:2-8-计算机问题求解-2020-04-16概率和随机算法.pptx | 2-8: 概率分析与随机算法]]
 |
 * 理解概率在算法设计中的作用
@@ 第210行： / 第210行： @@
 * 随机变量在算法分析中的意义
 |
-* CS第5.6节问题 4, 8
+* [[Media:2-8-probabilistic-analysis.zip | 2-8-probabilistic-analysis]]
-* CS第5.7节问题 2, 4, 6, 12
-* TC第5.2节练习 4, 5
-* TC第5.3节练习 2, 3, 4
 |
+*[[http://oj.problemoverflow.top/2019-2/9/ 随机算法]]
 |-
 |
--xx-xx
+-04-23
 |
-* [[Media:2-9-排序与选择-2018-05-02.pptx | 2-9: 排序与选择]]
+* [[Media:2-9-sorting and selection.pdf | 2019-2-9-sorting and selection.pdf]]
+*[[media:2-9-sorting_and_selection(handout).pdf|2019-2-9-sorting_and_selection(handout).pdf]]
 |
 * 深入理解快速排序算法的设计思想与分析方法
@@ 第230行： / 第228行： @@
 * 如何证明问题复杂度的下界
 |
-* TC 第七章:
+* [[Media:2-9-sorting-selection.zip | 2-9-sorting-selection]]
-** Exercises: 7.1-3, 7.2-4, 7.3-2, 7.4-2
-** Problem: 7.5
-* TC 第八章:
-** Exercises: 8.1-4, 8.2-4, 8.3-4, 8.4-2
-** Problem: 8.2
-* TC 第九章
-** Exercises: 9.1-1, 9.3-7
 |
+*[[http://oj.problemoverflow.top/2019-2/10/ 排序与选择]]
 |-
 |
--xx-xx
+-04-30
 |
-* [[Media:2-10-基本的数据结构-2018-05-9.pptx | 2-10: 基本数据结构]]
+* [[Media:2-10-计算机问题求解-2020-04-30-基本数据结构.pptx | 2-10: 基本数据结构]]
 |
 * 掌握堆栈、队列、链表、指针、根树的概念、实现以及在算法设计中的应用
@@ 第251行： / 第242行： @@
 * MA第2, 3章
 |
-* 数据结构的算法支撑(???)与实现效率的平衡
+* 基本数据结构
 |
-* MA 2.6 (只要求考察 Push 操作)
+* [[Media:2-10-data-structures.zip | 2-10-data-structures]]
-* TC第10.1节练习 4、5、6
-* TC第10.2节练习 1、2、3、6
-* TC第10.3节练习 4、5
-* TC第10.4节练习 2、3、4
-* TC第10章问题 3
 |
+*[[http://oj.problemoverflow.top/2019-2/11/ 基础数据结构-1]]
 |-
 |
--xx-xx
+-05-07
 |
-* [[Media:2-11-堆与堆排序-2018-05-13.pptx | 2-11: 堆与堆排序]]
+* [[Media:2-11_Heap&HeapSort.pdf ‎ | 2019-2-11_Heap&HeapSort ‎]]
 |
 * 理解并掌握堆的结构、实现以及算法应用
@@ 第274行： / 第260行： @@
 * 从数据结构到抽象数据类型的思想发展
 |
-* TC第6.1节练习 2、4、7
+* [[Media:2-11-heapsort.zip | 2-11-heapsort]]
-* TC第6.2节练习 2、5、6
-* TC第6.3节练习 3
-* TC第6.4节练习 2、4
-* TC第6.5节练习 5、7、9
 |
+*[[http://oj.problemoverflow.top/2019-2/12/ 基础数据结构-2]]
 |-
 |
--xx-xx
+-05-14
 |
-* [[media:Hashing方法-2018-05-23.pptx|2-12: Hashing方法]]
+* [[media:2019-2-12_Hashing.pdf |2-12: Hashing方法]]
 |
 * 掌握Hashing方法的原理、处理冲突的方法以及分析方法
@@ 第294行： / 第276行： @@
 * Hashing方法中的冲突处理
 |
-* CS第5.5节问题 8、14
+* [[Media:2-12-hashing.zip | 2-12-hashing]]
-* TC第11.2节练习 3、6
-* TC第11.3节练习 3、4
-* TC第11.4节练习 2、3
-* TC第11章问题 1、2
 |
+*[[http://oj.problemoverflow.top/2019-2/13/ 哈希]]
 |-
 |
--xx-xx
+-05-21
 |
-* [[Media:2-13-搜索树-2018-06-04.pptx | 2-13：搜索树]]
+* [[Media:2-13-搜索树-2020-05-21.pptx | 2-13：搜索树]]
 |
 * 掌握利用树结构存储与搜索数据的方法
 |
-* TC第12、13章
+* MA 第4.1节
+* TC第12章
 |
-* 树的平衡与搜索效率的关系
+* 搜索树的结构与操作
 |
-* TC第12.1节练习 2、5
+* [[Media:2-13-bst.zip | 2-13-bst]]
-* TC第12.2节练习 5、9
-* TC第12.3节练习 5
-* TC第13.1节练习 5、7
-* TC第13.2节练习 2
-* TC第13.3节练习 1、5
-* TC第13.4节练习 1、7
 |
+*[[http://oj.problemoverflow.top/2019-2/14/ 搜索树]]
 |-
 |
--xx-xx
+-05-28
 |
-* [[media:B树 2018-6-10.pptx|2-14：B 树]]
+* [[media:计算机问题求解-2020-05-28-B树.pptx | 2-14：B 树]]
 |
 * 掌握 B 树的基本性质及其操作
@@ 第334行： / 第307行： @@
 * 如何在经典数据结构的基础上，针对应用特征，优化设计，提高效率
 |
-* TC 练习 18.1.1,18.1.4
+* [[Media:2-14-b-tree.zip | 2-14-b-tree]]
-* TC 练习 18.2.3,18.2.4
+|
-* TC 练习 18.3.1
+*[[http://oj.problemoverflow.top/2019-2/15/ 编程复习]]
+|-
+|
+-06-04
+|
+* [[Media:红黑树.pptx | 2-15: 红黑树]] (改为课堂练习)
+|
+* 掌握红黑树数据结构的基本性质及其操作
+|
+* TC第13章
+|
+* 红黑树的概念
+|
+* [[Media:2-15-rb-tree.zip | 2-15-rb-tree]]
+|
+|-
+|
+*
+|
+*
+|
+*
+|
+*
+|
+*
+|
+* [[Media: 2-correction.zip | 2019-2-correction]]
 |
 |}