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

基本要求

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

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

指定教材

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

推荐课外读物

• Gary Shelly et al.: Discovering Computers 2011 - Living in a Digital World. Course Technology, 2011

学习周历

</tr> </tr> </tr>

日期	论题	学习目的	阅读材料	引导要点	书面作业	编程任务
2015.9.22	计算思维导引
2015.9.24	1-1：为什么计算机能解题	理解问题求解的基本过程 理解计算机中简单操作为什么能解决复杂问题	DH第1章 UD第1章	简单操作能够解决各种复杂问题的关键是算法	UD第1章问题2、3、4、5、6、8 UD第27章项目1	WS第28页DISPLAY 1.10
2015.9.29	1-2：什么样的推理是正确的	掌握命题逻辑与谓词逻辑的基本推导方法	UD第2、3、4章	计算机解题的关键是正确的推导 其正向是算法的设计，其反向是正确性证明	UD第2章问题1、5、6、7、8、10、11 UD第3章问题2、6、7、8、9、10、11 UD第4章问题1、5、7、9、13	WS第2章项目3 WS第2章项目10
2015.10.08	1-3：常用的证明方法	掌握逻辑正确的常用证明方法	UD第5、17章 ES第24节	为什么这些方法逻辑上是正确的	UD第5章问题12、14 UD第17章问题11、13、14、16、18、19 ES第24节练习4、6、8 UD第27章项目3	WS第2章项目14 WS第3章项目1
2015.10.13	1-4：基本的算法结构 扩展阅读：Goto Statement is Harmful	理解基本的算法结构：顺序、分支、循环、子程序、递归 理解程序最基本单元的正确性概念	DH第2章第1、2单元	基本结构的组合方式及其正确性	DH第2章练习1、2、3、4、5、6、7、8	WS第3章项目10 WS第3章项目11
2015.10.27	1-5：数据与数据结构	理解数据在计算机问题求解中的核心作用 通过例子理解几种常用的数据结构	DH第2章第3、4单元	有结构的数据对于计算以及算法设计的影响	DH第2章练习10、11、12、13、14、15、16	WS第3章项目13
2015.10.30	1-6：如何将算法告诉计算机	理解程序设计语言的基本概念 了解程序在计算机中的执行方式	DH第3章第1单元	程序设计语言如何体现算法的基本要素与结构	写出你现在用的C++语言的算术表达式的完整严格的文法	WS第4章项目14 WS第4章项目15
2015.11.12	1-7：不同的程序设计方法	了解不同的程序设计方法：函数式、命令式、对象式、逻辑式	DH第3章第2、3单元	为什么会出现不同的风范	在网上查一下，什么是scripting language，它们和C++这样的程序设计语言有什么不同 有一个网站通过网络搜索方式评定程序设计语言的“流行程度”，你是否能找到这个网站，并了解最流行的是哪些语言？（排名限于“程序设计语言”，不包括“脚本语言”和“标记语言”）	WS第4章项目16
2015.11.5	1-8：集合及其运算	掌握集合的基本概念以及基本数学性质 进一步巩固数学证明能力	UD第6、7、8、9章	集合语言是形式化方法的基础，也是算法问题表述的基本手段	UD第6章问题7、16、17 UD第7章问题1、8、9、10、11 UD第8章问题1、4、7、8、9、11 UD第9章问题2、4、12、13、14、16	假设可能的元素个素最多64个，实现基本的集合运算 如果集合元素可能有任意有限多个，如何实现集合运算
2015.11.27	1-9：关系及其基本性质	掌握关系的概念与基本数学性质 理解等价关系与次序关系的数学性质 进一步巩固数学证明能力	UD第10、11、12章	对象及其相互之间的关系是所有数学建模的核心概念	UD第10章问题2、4、5、8 UD第11章问题3、7、8、9 UD第12章问题10、13b、16、20、22、23 UD第27章项目4 补充题	假设集合中元素个数最多64个，编一个程序判断该集合上任意给定的二元关系满足那些性质
2015.12.3	1-10：函数	从问题求解的角度理解函数的概念及其重要的数学性质 熟悉函数表述方式	UD第14、15、16章	映射与计算机问题求解-从问题空间到解空间	UD第13章问题3、4、5、11、13 UD第14章问题8、12、13、15 UD第15章问题1、6、7、11、12、13、14、15、20 UD第16章问题19、20、21、22 UD第27章项目6	WS第5章项目4 WS第5章项目5
2015.12.10	1-11：有限与无限	理解无限集合的重要数学性质，理解可数与不可数的差别 理解有限过程与无限过程的概念与差别 理解测度空间的基本概念	UD第20、21、22、23章	如何比较无限集合的大小	UD第20章问题4、8、9、10 UD第21章问题7、9、10、11、16、17、18、19 UD第22章问题1、2、3、6、9 UD第23章问题2、3、10	WS第6章项目13 WS第6章项目14
2015.12.17	1-12：偏序关系和格	理解集合上的序关系 理解格的基本概念 理解偏序集与格的联系与区别	SM第14章	如何定义集合中元素的“序”	SM第14章32、44、46、58、62、66、70、75	WS第6章项目13 WS第6章项目14
2015.12.31	1-13：布尔代数	理解布尔代数基本概念 理解布尔代数与格的联系与区别 布尔代数表达式的化简	SM第15章	布尔代数	证明布尔代数是有界有补分配格，有界有补分配格是布尔代数 证明SM定理15.6 证明等势的布尔代数均同构	WS第6章项目13 WS第6章项目14
	1-13：问题的难度	理解问题固有难度的概念 了解NP-完全理论的基本内容	DH第7章	区分问题的难度与算法的复杂性，特别是上下界的概念		WS第7章项目13
	1-14：基本计算模型与不可计算性		DH第8章第1、2、3、4单元 DH第9章第1、2、3单元	基本计算模型有什么意义
	1-15：并行与并发		DH第10章第1、2、3、4、5、6单元	并发带来什么好处，又会带来什么问题
	1-16：模算术与费马小定理		UD第25、26章 DH第12章第1单元	模算术与常规算术有什么异同