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

基本要求

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

考核方法

（以下考核方法可能会有变动）

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

• 作业 (20%)
  • 必须订正，否则分数极低，订正后的分数被采纳
• Open topics (10%)
  • 每人至少做一次
  • 做多次报告，取最高分
  • 不做计 0 分
• OJ (20%)
• 期末笔试: (40%)
  • 难度不高于平时训练，及格成绩由课外作业构成，进阶成绩由同难度未见习题构成
• 期末机试（10%）

指定教材

• 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, 2010
• ES: Edward Scheinerman: Mathematics - A Discrete Introduction, 2nd ed. Brooks/Cole, 2005 (第24节：鸽巢原理)
• SM: Seymour Lipschutz and Marc Lipson: Theory and Problems of Discrete Mathematics, 3rd ed.

推荐参考资料与课外读物

- Walter Savitch-Problem Solving with C++-Addison Wesley (2014)

- Logicomix: An Epic Search for Truth, Apostolos Doxiadis, Christos Papadimitriou (2009 English Translation).

 《疯狂的罗素：逻辑学与数学的奇幻之旅》，张立英（译），中国人民大学出版社，2018。

- Engines of Logic: Mathematicians and the Origin of the Computer. Davis, Martin (2000). New York: Norton.

 《逻辑的引擎》，张卜天 (译)，湖南科学技术出版社，第一推动丛书，2005。

- 《三次数学危机与数学悖论》，韩雪涛，人民邮电出版社。

 第三部分：罗素悖论与第三次数学危机

Open Topics

Open Topics 见“小班讨论”页面

课件下载

[点击进入课件下载页面]

学习周历

日期	论题	学习目的	阅读材料	引导要点	书面作业
2023-09-14	1-1：为什么计算机能解题	理解问题求解的基本过程 理解计算机中简单操作为什么能解决复杂问题	DH第1章 UD第1章	简单操作能够解决各种复杂问题的关键是算法	1-why
2023-09-21	1-2：什么样的推理是正确的	掌握命题逻辑与谓词逻辑的基本推导方法	UD第2、3、4章	计算机解题的关键是正确的推导 其正向是算法的设计，其反向是正确性证明	1-2-reasoning
2023-09-28	1-3：常用证明方法及其逻辑正确性	掌握逻辑正确的常用证明方法	UD第5、18章 ES第24节	为什么这些方法在逻辑上是正确的？	1-3-proof
2023-10-12	1-4: 算法的基本结构	理解基本的算法结构：顺序、分支、循环、子程序、递归 理解程序最基本单元的正确性概念	DH第2章第 1、2 单元 Media:Go_To_Statement_Considered_Harmful_(Dijkstra_CACM_1968).pdf ‎| Go To Statement Considered Harmful (Dijkstra CACM 1968)	基本结构的组合方式及其正确性	1-4-algorithm
2023-10-19	1-5: 数据与数据结构	理解数据在计算机问题求解中的核心作用 通过例子理解几种常用的数据结构	DH第2章第 3、4 单元	有结构的数据对于计算以及算法设计的影响	1-5-data-structure
2023-10-26	1-6: 如何将算法告诉计算机	理解程序设计语言的基本概念 了解程序在计算机中的执行方式	DH第3章第1单元	程序设计语言如何体现算法的基本要素与结构	1-6-programming-language
2023-11-02	1-7: 不同的程序设计方法	了解不同的程序设计方法：函数式、命令式、对象式、逻辑式	DH第3章第2、3单元	为什么会出现不同的风范	1-7-programming-paradigm
2023-11-09	1-8 集合论 I: 公理与操作	掌握集合的基本概念以及基本数学性质 进一步巩固数学证明能力	UD第6、7、8、9章	集合语言是形式化方法的基础	1-8-set
2023-11-16	1-9 集合论 II: 关系	掌握关系的概念与基本数学性质 理解等价关系与次序关系的数学性质 进一步巩固数学证明能力	UD第10、11、12、13 (非重点)章	对象及其相互之间的关系是所有数学建模的核心概念	1-9-relation
2023-11-30	1-10 集合论 (III): 函数	从问题求解的角度理解函数的概念及其重要的数学性质 熟悉函数表述方式	UD第 14、15、16、17 章	映射与计算机问题求解 --- 从问题空间到解空间	1-10-function
2023-12-07	1-11 集合论 (IV): 无穷	理解无限集合的重要数学性质，理解可数与不可数的差别	UD第21、22、23、24（非重点）章	如何比较无限集合的大小	1-11-infinity
2023-12-14	1-12: 偏序关系和格	理解集合上的序关系 理解格的基本概念 理解偏序集与格的联系与区别	SM第14章	如何定义集合中元素的“序”	1-12-partial-lattice
2023-12-21	1-13: 算法方法与正确性	通过具体示例了解算法设计的基本策略 理解并能够区分算法错误与程序错误 理解算法正确性的概念及其证明方法	DH第4、5章	理解复杂算法背后的简单原理 循环不变式	1-13-algorithmic-method-and-correctness
2023-12-28	[1-14:算法的效率]	理解算法的时间复杂性的概念与渐近表示方式	DH第6章 TC 2.1节, 2.2节 TC 第3章	如何做算法复杂度分析	1-14-efficiency.zip]	}