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

来自问题求解
跳转至： 导航、 搜索
（→‎学习周历）
Whf（讨论 | 贡献）
（→‎推荐课外阅读材料）
第37行： 第37行：
 
* 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: [[Media:Discrete_Mathematics_and_Its_Applications_(7th_Edition).pdf ‎| Discrete Mathematics and Its Applications]], 7th Edition. McGraw-Hill, 2011
  
−
* Donald E. Knuth: [[Media:The_Art_of_Computer_Programmin_Volume4A_Combinatorial_Algorithms.pdf | The Art of Computer Programming Vol4A: Combinatorial Algorithms Part 1]], 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
  
−
* Ronald L. Graham, Donald E. Knuth, Oren Patashnik: [[Media: Concrete_Mathematics_-_R._Graham,_D._Knuth,_O._Patashnik.pdf | Concrete Mathematics: A Foundation for Computer Science]], 2nd Edition, 1994.
+
* '''[GKP]''' Ronald L. Graham, Donald E. Knuth, Oren Patashnik: [[Media: Concrete_Mathematics_-_R._Graham,_D._Knuth,_O._Patashnik.pdf | Concrete Mathematics: A Foundation for Computer Science]], 2nd Edition, 1994.
  
−
* Jon Bentley: [[Media:Programming_Pearls_(Second_Edition_Jon_Bentley).pdf | Programming Pearls]], 2nd Edition, 1999.
+
* '''[PP]''' Jon Bentley: [[Media:Programming_Pearls_(Second_Edition_Jon_Bentley).pdf | Programming Pearls]], 2nd Edition, 1999.
  
−
* Robert Sedgewick, Philippe Flajolet: [[Media:An_Introduction_to_the_Analysis_of_Algorithms_(2nd_Edition_Robert_Sedgewick,_Philippe_Flajolet).pdf | Book: An Introduction to the Analysis of Algorithms]], 2nd Edition, 2012.
+
* '''[AoA]''' Robert Sedgewick, Philippe Flajolet: [[Media:An_Introduction_to_the_Analysis_of_Algorithms_(2nd_Edition_Robert_Sedgewick,_Philippe_Flajolet).pdf | Book: An Introduction to the Analysis of Algorithms]], 2nd Edition, 2012.
  
−
* Martin Aigner: [[Media:Proofs_from_THE_BOOK_(Fifth_Edition_2014).pdf | Book: Proofs from THE BOOK]], Fifth Edition, 2014.
+
* '''[TheBook]''' Martin Aigner: [[Media:Proofs_from_THE_BOOK_(Fifth_Edition_2014).pdf | Book: Proofs from THE BOOK]], Fifth Edition, 2014.
 +
 
 +
* '''[MCS]''' Eric Lehman, F Thomson Leighton, Albert R Meyer: [[Media:Mathematics for Computer Science (MCS; MIT, 2018).pdf | Mathematics for Computer Science]], MIT, 2018.
  
 
更多阅读材料将随课堂进度添加。
 
更多阅读材料将随课堂进度添加。
 +
 
== 学习周历 ==
 
== 学习周历 ==
  

2020年3月20日 (五) 21:20的版本

基本要求

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

考核方法

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

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

指定教材

推荐课外阅读材料

(可参照习题课扩展材料部分所给出的阅读建议)

更多阅读材料将随课堂进度添加。

学习周历

日期 论题 学习目的 阅读材料 引导要点 书面作业

(非稳定版本作业@GitHub)

编程作业

2020-02-20

  • 理解布尔代数基本概念
  • 理解布尔代数与格的联系与区别
  • 布尔代数表达式的化简
  • SM第15章
  • 布尔代数
2020-02-27
  • 理解并能够区分算法错误与程序错误
  • 理解算法正确性的概念及其证明方法
  • DH第5章
  • 循环不变式

2020-03-05

2-2：算法的效率

  • 理解算法的时间复杂性的概念与渐近表示方式
  • DH第6章
  • TC 2.1节, 2.2节
  • TC 第3章
  • 如何做算法复杂度分析

2020-03-12

2-3：组合与计数

  • 掌握在算法分析中常用的计数原理与方法
  • CS第1章
  • 组合计数技巧与常见形式

2019-03-19

  • 掌握利用分治法设计算法的思路
  • 深入理解递归在算法设计中的作用
  • TC 第2.3节
  • TC 第4章
  • 算法设计中的分治思想

2019-03-26

  • 进一步理解递归的数学基础
  • 更深入地掌握递归算法的分析方法
  • CS第4章
  • 如何解递归式
  • 整理中

2019-xx-xx

  • 通过具体示例了解算法设计的基本策略
  • DH第4章
  • 理解复杂算法背后的简单原理
  • DH 第4章练习 1, 8, 9, 12, 14

2019-xx-xx

  • 理解离散概率的基本概念
  • 掌握简单离散概率计算的基本方法
  • CS第5章: 5.1, 5.2, 5.3, 5.4 节
  • 正确理解“期望”的概念，为理解平均情况时间复杂度分析建立基础
  • CS第5.1节问题 10, 12
  • CS第5.2节问题 4, 10
  • CS第5.3节问题 2, 6, 12
  • CS第5.4节问题 4, 10, 12 ("Solve Problem 10" 改为 "Solve Problem 11"), 15

2019-xx-xx

  • 理解概率在算法设计中的作用
  • 掌握基于概率的算法分析的基本方法
  • TC第5章
  • CS第5章: 5.6, 5.7节
  • 随机变量在算法分析中的意义
  • CS第5.6节问题 4, 8
  • CS第5.7节问题 2, 4, 6, 12
  • TC第5.2节练习 4, 5
  • TC第5.3节练习 2, 3, 4

2019-xx-xx

  • 深入理解快速排序算法的设计思想与分析方法
  • 通过排序理解问题复杂度的下界，并探索一些线性排序算法
  • 掌握以中位数为代表的统计算法
  • TC第7、8、9章
  • 如何证明问题复杂度的下界
  • TC 第七章:
    • 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

2019-xx-xx

  • 掌握堆栈、队列、链表、指针、根树的概念、实现以及在算法设计中的应用
  • TC第10章
  • MA第2, 3章
  • 数据结构的算法支撑(???)与实现效率的平衡
  • MA 2.6 (只要求考察 Push 操作)
  • 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

2019-xx-xx

  • 理解并掌握堆的结构、实现以及算法应用
  • 通过堆的应用与实现理解抽象数据类型的基本概念以及分层抽象的思想
  • TC第6章
  • 从数据结构到抽象数据类型的思想发展
  • TC第6.1节练习 2、4、7
  • TC第6.2节练习 2、5、6
  • TC第6.3节练习 3
  • TC第6.4节练习 2、4
  • TC第6.5节练习 5、7、9

2019-xx-xx

  • 掌握Hashing方法的原理、处理冲突的方法以及分析方法
  • TC第11章
  • CS第5章第5节
  • Hashing方法中的冲突处理
  • CS第5.5节问题 8、14
  • TC第11.2节练习 3、6
  • TC第11.3节练习 3、4
  • TC第11.4节练习 2、3
  • TC第11章问题 1、2

2019-xx-xx

  • 掌握利用树结构存储与搜索数据的方法
  • TC第12、13章
  • 树的平衡与搜索效率的关系
  • TC第12.1节练习 2、5
  • 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

2019-xx-xx

  • 掌握 B 树的基本性质及其操作
  • TC第18章
  • 如何在经典数据结构的基础上，针对应用特征，优化设计，提高效率
  • TC 练习 18.1.1,18.1.4
  • TC 练习 18.2.3,18.2.4
  • TC 练习 18.3.1
取自“http://cslabcms.nju.edu.cn/problem_solving/index.php?title=2019级--学期安排_(第二学期)&oldid=3759”