2018级--学期安排 (第一学期)

基本要求

• 理解计算思维最核心的概念，了解计算的基本方法与局限。
• 接受基本的形式化训练，掌握抽象数学证明的基本方法。

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

指定教材

• DH: David Harel et al.: Algorithmics - The Spirit of Computing, 3rd ed. Addison-Wesley, 2004
• UD: Ulrich Daepp et al.: Reading, Writing, and Proving - A Closer Look at Mathematics, 2nd ed. Springer-Verlag, 2011
• ES: Edward Scheinerman: Mathematics - A Discrete Introduction, 2nd ed. Brooks/Cole, 2005 (第24节：鸽巢原理)
• WS: Walter Savitch: Problem Solving with C++, 9th ed. Pearson, 2015

推荐课外读物

• Tony Hey et al.: The Computing Universe: A Journey Through a Revolution. Cambridge University Press, 2015

学习周历

注意：以下日期不是指上课时间，而是以“周”为单位的学习任务分配时间，特别是由于国庆节、元旦等假期影响，上课时间可能会有微调，但任务周期不受影响。

日期	论题	学习目的	阅读材料	引导要点
9.17-9.21	1-1：为什么计算机能解题	理解问题求解的基本过程 理解计算机中简单操作为什么能解决复杂问题	DH第1章第1-13页 UD第1章	简单操作能够解决各种复杂问题的关键是算法
9.24-9.28	1-2：什么样的推理是正确的	掌握命题逻辑与谓词逻辑的基本推导方法	UD第2、3、4章	计算机解题的关键是正确的推导 其正向是算法的设计，其反向是正确性证明
10.1-10.5	1-3：常用的证明方法	掌握逻辑正确的常用证明方法	UD第5、18章 ES第24节	为什么这些方法逻辑上是正确的
10.8-10.12	1-4：基本的算法结构	理解基本的算法结构：顺序、分支、循环、子程序、递归 理解程序最基本单元的正确性概念	DH第2章第1、2单元	基本结构的组合方式及其正确性
10.15-10.19	1-5：数据与数据结构	理解数据在计算机问题求解中的核心作用 通过例子理解几种常用的数据结构	DH第2章第3、4单元	有结构的数据对于计算以及算法设计的影响
10.22-10.26	1-6：算法的描述	理解程序设计语言的基本概念 了解程序在计算机中的执行方式	DH第3章第1单元	程序设计语言如何体现算法的基本要素与结构
10.29-11.2	1-7：不同的程序设计方法	了解不同的程序设计方法：函数式、命令式、对象式、逻辑式	DH第3章第2、3单元	为什么会出现不同的风范
11.5-11.9	1-8：集合及其运算	掌握集合的基本概念以及基本数学性质 进一步巩固数学证明能力	UD第6、7、8、9章	集合语言是形式化方法的基础，也是算法问题表述的基本手段
11.12-11.16	1-9：关系及其基本运算	掌握关系的概念与基本数学性质 理解等价关系与次序关系的数学性质 进一步巩固数学证明能力	UD第10、11章	对象及其相互之间的关系是所有数学建模的核心概念
11.19-11.23	1-10：函数	从问题求解的角度理解函数的概念及其重要的数学性质 熟悉函数表述方式	UD第14、15、16、17章	映射与计算机问题求解-从问题空间到解空间
11.26-11.30	1-11：算法方法	通过具体示例了解算法设计的基本策略	DH第4章第81-91页	理解复杂算法背后的简单原理
12.3-12.7	1-12：算法的正确性	理解并能够区分程序错误与算法错误 理解算法正确的概念及其证明方法	DH第5章第99-117页	算法正确性证明与一般数学定理证明的异同
12.10-12.14	1-13：有限与无限	理解无限集合的重要数学性质，理解可数与不可数的差别 理解有限过程与无限过程的概念与差别 理解由定义出发的数学证明的严谨性	UD第21、22、23章 UD第24章（选读）	如何比较无限集合的大小 对那些“显而易见”的结论，什么样的证明是数学上严谨的
12.17-12.21	1-14：算法的效率	理解算法的时间复杂性的概念与渐进表示方式	DH第6章第129-139页	从无限与有限的角度正确理解算法复杂度
12.24-12.28	1-15：问题的难度	理解问题固有难度的概念 了解NP-完全理论的基本内容	DH第7章第159-170页	区分问题的难度与算法的复杂性，特别是上下界的概念
寒假自学	1-16：基本计算模型与不可计算性		DH第9章第1、2、3单元第219-228页	基本计算模型有什么意义
寒假自学	1-17：并行与并发		DH第10章第257-263页	并发带来什么好处，又会带来什么问题
寒假自学	1-18：模算术与费马小定理		UD第27章 UD第28章（选读）	模算术与常规算术有什么异同