“2021级--学期安排（第二学期）”的版本间的差异
来自问题求解
（→学习周历） |
（→学习周历） |
||
| 第75行： | 第75行： | ||
* 布尔代数 | * 布尔代数 | ||
| | | | ||
| − | * [[ | 1-13-boolean-algebra]] | + | * [[Media: | 1-13-boolean-algebra]] |
| | | | ||
*[[http://oj.problemoverflow.top/2019-2/2/ 布尔代数与算法正确性]] | *[[http://oj.problemoverflow.top/2019-2/2/ 布尔代数与算法正确性]] | ||
| 第90行： | 第90行： | ||
* 循环不变式 | * 循环不变式 | ||
| style="width: 200px;" | | | style="width: 200px;" | | ||
| − | * [[ | 2-1-correctness]] | + | * [[Media: | 2-1-correctness]] |
| style="width: 200px;" | | | style="width: 200px;" | | ||
* | * | ||
| 第109行： | 第109行： | ||
* 如何做算法复杂度分析 | * 如何做算法复杂度分析 | ||
| | | | ||
| − | * [[ | 2-2-efficiency]] | + | * [[Media: | 2-2-efficiency]] |
| | | | ||
* | * | ||
| 第126行： | 第126行： | ||
* 组合计数技巧与常见形式 | * 组合计数技巧与常见形式 | ||
| | | | ||
| − | * [[ | 2-3-counting]] | + | * [[Media: | 2-3-counting]] |
| | | | ||
* | * | ||
| 第143行： | 第143行： | ||
* 算法设计中的分治思想 | * 算法设计中的分治思想 | ||
| | | | ||
| − | * [[ | 2-4-recurrence]] | + | * [[Media: | 2-4-recurrence]] |
| | | | ||
* | * | ||
| 第161行： | 第161行： | ||
* 如何解递归式 | * 如何解递归式 | ||
| | | | ||
| − | * [[ | 2-5-solving-recurrence]] | + | * [[Media: | 2-5-solving-recurrence]] |
| | | | ||
* | * | ||
| 第176行： | 第176行： | ||
* 理解复杂算法背后的简单原理 | * 理解复杂算法背后的简单原理 | ||
| | | | ||
| − | * [[ | 2-6-algorithmic-methods]] | + | * [[Media: | 2-6-algorithmic-methods]] |
| | | | ||
* | * | ||
| 第192行： | 第192行： | ||
* 正确理解“期望”的概念，为理解平均情况时间复杂度分析建立基础 | * 正确理解“期望”的概念，为理解平均情况时间复杂度分析建立基础 | ||
| | | | ||
| − | * [[ | 2-7-discrete-probability]] | + | * [[Media: | 2-7-discrete-probability]] |
| | | | ||
* | * | ||
| 第209行： | 第209行： | ||
* 随机变量在算法分析中的意义 | * 随机变量在算法分析中的意义 | ||
| | | | ||
| − | * [[ | 2-8-probabilistic-analysis]] | + | * [[Media: | 2-8-probabilistic-analysis]] |
| | | | ||
* | * | ||
| 第227行： | 第227行： | ||
* 如何证明问题复杂度的下界 | * 如何证明问题复杂度的下界 | ||
| | | | ||
| − | * [[ | 2-9-sorting-selection]] | + | * [[Media: | 2-9-sorting-selection]] |
| | | | ||
* | * | ||
| 第243行： | 第243行： | ||
* 基本数据结构 | * 基本数据结构 | ||
| | | | ||
| − | * [[ | 2-10-data-structures]] | + | * [[Media: | 2-10-data-structures]] |
| | | | ||
* | * | ||
| 第259行： | 第259行： | ||
* 从数据结构到抽象数据类型的思想发展 | * 从数据结构到抽象数据类型的思想发展 | ||
| | | | ||
| − | * [[ | 2-11-heapsort]] | + | * [[Media: | 2-11-heapsort]] |
| | | | ||
* | * | ||
| 第275行： | 第275行： | ||
* Hashing方法中的冲突处理 | * Hashing方法中的冲突处理 | ||
| | | | ||
| − | * [[ | 2-12-hashing]] | + | * [[Media: | 2-12-hashing]] |
| | | | ||
* | * | ||
| 第291行： | 第291行： | ||
* 搜索树的结构与操作 | * 搜索树的结构与操作 | ||
| | | | ||
| − | * [[ | 2-13-bst]] | + | * [[Media: | 2-13-bst]] |
| | | | ||
* | * | ||
| 第306行： | 第306行： | ||
* 如何在经典数据结构的基础上，针对应用特征，优化设计，提高效率 | * 如何在经典数据结构的基础上，针对应用特征，优化设计，提高效率 | ||
| | | | ||
| − | * [[ | 2-14-b-tree]] | + | * [[Media: | 2-14-b-tree]] |
| | | | ||
* | * | ||
| 第321行： | 第321行： | ||
* 红黑树的概念 | * 红黑树的概念 | ||
| | | | ||
| − | * [[ | 2-15-rb-tree]] | + | * [[Media: | 2-15-rb-tree]] |
| | | | ||
|- | |- | ||
2022年2月8日 (二) 17:06的版本
基本要求
- 理解数据抽象，理解并能够应用常用的数据结构
- 掌握重要算法设计策略以及算法分析的基本方法
- 理解并能够应用支持上述内容的离散数学工具与方法
- 程序设计能力
考核方法
所有形式的考核,均不准抄袭。
| 考核形式 | 分值 |
|---|---|
| 作业 | 20 |
| OT | 10 |
| OJ | 15 |
| 机试 | 15 |
| 笔试 | 40 |
指定教材
- 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
推荐课外阅读材料
(可参照习题课扩展材料部分所给出的阅读建议)
- Kenneth H. Rosen: Discrete Mathematics and Its Applications, 7th Edition. McGraw-Hill, 2011
- [TAOCP-4A] Donald E. Knuth: The Art of Computer Programming Vol4A: Combinatorial Algorithms Part 1, 2011
- [GKP] Ronald L. Graham, Donald E. Knuth, Oren Patashnik: Concrete Mathematics: A Foundation for Computer Science, 2nd Edition, 1994.
- [PP] Jon Bentley: Programming Pearls, 2nd Edition, 1999.
- [AoA] Robert Sedgewick, Philippe Flajolet: Book: An Introduction to the Analysis of Algorithms, 2nd Edition, 2012.
- [TheBook] Martin Aigner: Book: Proofs from THE BOOK, Fifth Edition, 2014.
- [MCS] Eric Lehman, F Thomson Leighton, Albert R Meyer: Mathematics for Computer Science, MIT, 2018.
更多阅读材料将随课堂进度添加。
学习周历
| 日期 | 论题 | 学习目的 | 阅读材料 | 引导要点 | 书面作业 | 编程作业 |
|---|---|---|---|---|---|---|
|
2022-02-16 |
|
|
|
|
||
| 2022-02-27 |
|
|
|
|
|
|
|
2022-03-05 |
2-2：算法的效率 |
|
|
|
|
|
|
2022-03-12 |
2-3：组合与计数 |
|
|
|
|
|
|
2022-03-19 |
|
|
|
|
| |
|
2022-03-26 |
|
|
|
|
| |
|
2022-04-02 |
|
|
|
|
| |
|
2022-04-09 |
|
|
|
|
| |
|
2022-04-16 |
|
|
|
|
| |
|
2022-04-23 |
|
|
|
|
| |
|
2022-04-30 |
|
|
|
|
| |
|
2022-05-07 |
|
|
|
|
| |
|
2022-05-14 |
|
|
|
|
| |
|
2022-05-21 |
|
|
|
|
| |
|
2022-05-28 |
|
|
|
|
| |
|
2022-06-04 |
|
|
|
|
|
|
|
|
|
|
|
|
|
