• 

  陈斌

  北京大学

• 

  陈旭

• 

  jingpinmooc

• 

  tomato8965

• 

  yichaopku

  北京大学

第一章：数理逻辑

1.1 命题演算：命题与联结词、重言式、范式、命题演算形式系统PC

1.2 谓词演算：个体谓词和量词、一阶谓词公式、谓词演算形式系统FC，自然推理系统ND

第二章：集合论

2.1 集合基本概念：集合定义、集合基本运算、归纳定义和归纳法证明

2.2 关系：关系基本概念、基本性质、等价关系、序关系

2.3 函数：函数定义、函数合成、基本函数类、逆函数

第三章：图论

3.1 图论基本概念：图定义、图的同构、路径回路、可达性和连通性、图的矩阵表示

3.2 特殊图：欧拉图、哈密顿图、二分图、平面图、树

第四章：抽象代数

4.1 代数结构的定义

4.2 代数结构中特殊元素

4.3 代数结构的同态与同构

第五章：形式语言与自动机

5.1 形式语言基本概念：形式语言定义、Chomsky分类体系、短语结构语法、语法和语言表示

5.2 有限状态自动机：定义和状态图、泵引理、机器同余和商机器、机器化简、有限状态机实现计算

5.3 图灵机和可计算理论：图灵机、哥德尔编码、通用图灵机、停机问题和哥德尔不完全性定理

离散数学是计算机科学的基础理论，离散结构的基础知识和逻辑思维的形式化是信息技术类学生的基本功，离散数学的基本概念是理科专业学生进行信息类课程学习的重要基础。

本课程介绍计算机科学和信息技术理论基础的概念和思想方法，介绍数理逻辑、集合论、图论、抽象代数和形式语言与自动机等各部分的基本概念，介绍离散数学基本概念和空间信息技术之间的联系与结合，培养学生理解和掌握离散数学基本概念，采用形式化方法分析问题，并能自觉运用逻辑分析、结构层次分析和同构类比等思想方法解决问题的能力。

1.[O158/75]计算机科学中的离散结构，王元元, 张桂芸编著，机械工业出版社 2004

2.[O158/60]离散数学导论，王元元, 张桂芸编著，科学出版社 2002

3.[O158/36]离散数学，王元元,李尚奋编著，科学出版社 1994

以上三本书实际上内容基本相同，选择其中一本即可，如果找不到，其它离散数学教材也没有问题。

先修知识

先修过《高等数学》《计算概论》《数据结构与算法》等理科基础课程最好，但这些先修课并不是必须的，有基本数理概念也可以选修本课程。

授课形式

本课程授课视频一般每段为6-9分钟左右，每段视频会有1-2个随堂测试，每周将安排1次作业，结课采用考试形式。

常见问题

Q：这是一门数学课么？

A：离散数学跟你在中学里学过的代数、几何，或者大学里学过的高等数学、线性代数都不一样，它研究推理过程如何变成公式演算，分立对象之间的关系以及把它们放在一起构成更复杂的系统。

Q：学了这门课会有什么收获？

A：离散数学是计算机科学的理论基础，所以对理科学生进一步学习程序设计、操作系统、数据库等等计算机类课程有很大帮助，你以后会在这些课程里反复用到离散数学的基本概念。如果你已经开始了IT行业的职业生涯，离散数学对提升你对工作的高度，拓宽行业视野也会有很大的帮助。

Q：课程介绍特别提了本课程面向“非”计算机软件专业，这意味着什么？

A：计算机软件专业对于离散数学教学的内容更为细致，要求更高，通常还会分成几门课程来讲述。本课程属于概论性质，主要是对基本概念的理解和掌握，综合性更强。

Q：课程介绍视频里还提到理解科幻作品？

A：在信息技术飞速发展的今天，人和机器的关系越来越被人们所重视，越来越多的小说、电影通过科幻的形式讨论未来技术发展对人类社会的影响。通过本课程的学习，你可以认识到机器的本质，理解科学知识体系的根基与边界。再看这些作品，你会有不同的眼界和体验。