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

来自问题求解
Majun讨论 | 贡献2022年2月8日 (二) 19:59的版本 指定教材

跳转至: 导航搜索

基本要求

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

考核方法

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

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

指定教材

推荐课外阅读材料

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

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

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

学习周历

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

2022-02-16

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

2022-03-05

2-2:算法的效率

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

2022-03-12

2-3:组合与计数

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

2022-03-19

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

2022-03-26

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

2022-04-02

  • 通过具体示例了解算法设计的基本策略
  • DH第4章
  • 理解复杂算法背后的简单原理

2022-04-09

  • 理解离散概率的基本概念
  • 掌握简单离散概率计算的基本方法
  • CS第5章: 5.1, 5.2, 5.3, 5.4 节
  • 正确理解“期望”的概念,为理解平均情况时间复杂度分析建立基础

2022-04-16

  • 理解概率在算法设计中的作用
  • 掌握基于概率的算法分析的基本方法
  • TC第5章
  • CS第5章: 5.6, 5.7节
  • 随机变量在算法分析中的意义

2022-04-23

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

2022-04-30

  • 掌握堆栈、队列、链表、指针、根树的概念、实现以及在算法设计中的应用
  • TC第10章
  • MA第2, 3章
  • 基本数据结构

2022-05-07

  • 理解并掌握堆的结构、实现以及算法应用
  • 通过堆的应用与实现理解抽象数据类型的基本概念以及分层抽象的思想
  • TC第6章
  • 从数据结构到抽象数据类型的思想发展

2022-05-14

  • 掌握Hashing方法的原理、处理冲突的方法以及分析方法
  • TC第11章
  • CS第5章第5节
  • Hashing方法中的冲突处理

2022-05-21

  • 掌握利用树结构存储与搜索数据的方法
  • MA 第4.1节
  • TC第12章
  • 搜索树的结构与操作

2022-05-28

  • 掌握 B 树的基本性质及其操作
  • TC第18章
  • 如何在经典数据结构的基础上,针对应用特征,优化设计,提高效率

2022-06-04

  • 掌握红黑树数据结构的基本性质及其操作
  • TC第13章
  • 红黑树的概念