离散数学

国家级

北京大学的离散数学课程建设获得过北京市教学成果奖一等奖,出版了多部国家级规划教材、北京市精品教材和教育部高等教育精品教材,教师团队中有2名教育部高等学校师资培训离散数学课程的主讲教师。本课程按照144学时设计,面向创新人才培养计划,具有鲜明的特色和丰富的资源。

课程介绍

课程介绍 离散数学(Discrete Mathematics)是计算机科学与技术专业的一门重要的专业基础课,也是该专业的核心课程之一。教育部高等学校计算机科学与技术教学指导委员会在2006年出版的《高等学校计算机科学与技术专业发展战略研究报告暨专业规范(试行)》中提到:“离散结构是计算机科学的基础内容,可以为计算机系统提供其处理对象的状态及其变换的有效描述。所以,计算机科学与技术有关的许多领...

教学单元
  • 第1讲 集合(教材第一章)
    • 01-01

      引言

    • 01-02

      预备知识(命题逻辑)

    • 01-03

      预备知识(一阶逻辑)

    • 01-04

      集合的概念和集合之间的关系

    • 01-05

      集合的运算

    • 01-06

      基本的集合恒等式

  • 第2讲 二元关系(教材第二章)
    • 02-01

      有序对与卡氏积

    • 02-02

      二元关系

    • 02-03

      关系的表示和关系的性质

    • 02-04

      关系的幂运算和闭包

    • 02-05

      等价关系和划分

    • 02-06

      序关系

  • 第3讲 函数(教材第三章)
    • 03-01

      函数的基本概念、性质、合成、反函数

  • 第4讲 自然数(教材第四章)
    • 04-01

      自然数的定义

    • 04-02

      自然数的性质

  • 第5讲 基数(教材第五章)
    • 05-01

      集合的等势、有穷集合与无穷集合

    • 05-02

      基数和基数的比较与运算

    • 05-03

      习题课

  • 第6讲 图(教材第七章)
    • 06-01

      图的基本概念

    • 06-02

      通路与回路

    • 06-03

      无向图和有向图的连通性

    • 06-04

      无向图的连通度

  • 第7讲 欧拉图与哈密顿图(教材第八章)
    • 07-01

      欧拉图

    • 07-02

      哈密顿图

  • 第8讲 树(教材第九章)
    • 08-01

  • 第9讲 图的矩阵表示(教材第十章)
    • 09-01

      图的矩阵表示

  • 第10讲 平面图(教材第十一章)
    • 10-01

      平面图的基本概念

    • 10-02

      欧拉公式与平面图的判断

    • 10-03

      平面图的对偶图与外平面图

    • 10-04

      平面图与哈密顿图

    • 10-05

      习题课

  • 第11讲 图的着色(教材第十二章)
    • 11-01

      点着色和色多项式

    • 11-02

      平面图着色和边着色

  • 第12讲 支配集、覆盖集、独立集与匹配(教材第十三章)
    • 12-01

      支配集、点覆盖集、点独立集

    • 12-02

      边覆盖数与匹配

    • 12-03

      二部图中的匹配

  • 第13讲 带权图及其应用(教材第十四章)
    • 13-01

      中国邮递员问题和货郎问题

    • 13-02

      图论12-14章习题课

    • 13-03

      课程总结

  • 第14讲 离散数学(1)期末考试
  • 第15讲 代数系统(教材第十五章)
    • 15-01

      引言

    • 15-02

      二元运算及其性质

    • 15-03

      代数系统、子代数和积代数

    • 15-04

      代数系统的同态与同构

    • 15-05

      同余关系与商代数

  • 第16讲 半群与独异点(教材第十六章)
    • 16-01

      半群与独异点

  • 第17讲 群(教材第十七章)
    • 17-01

      群的定义和性质、子群

    • 17-02

      习题课

    • 17-03

      循环群、变换群与置换群

    • 17-04

      群的分解、正规子群与商群、群的同态与同构

    • 17-05

      习题课、小测验

  • 第18讲 环与域(教材第十八章)
    • 18-01

      环与域

  • 第19讲 格与布尔代数(教材第十九章)
    • 19-01

      格的定义和性质、子格、格同态与直积

    • 19-02

      模格、分配格、有补格与布尔代数

  • 第20讲 组合存在性定理(教材第二十章)
    • 20-01

      鸽巢原理和Ramsey定理

  • 第21讲 基本的计数公式(教材第二十一章)
    • 21-01

      两个计数原则、排列组合

    • 21-02

      二项式定理与组合恒等式

    • 21-03

      多项式定理

  • 第22讲 组合计数方法(教材第二十二章)
    • 22-01

      递推方程的公式解法

    • 22-02

      递推方程的其他求解方法

    • 22-03

      生成函数的定义和性质

    • 22-04

      生成函数、指数生成函数及应用

    • 22-05

      Catalan数与Stirling数

    • 22-06

      小测验

  • 第23讲 组合计数定理(教材第二十三章)
    • 23-01

      包含排斥原理与对称筛公式

    • 23-02

      Burnside引理与Polya定理

    • 23-03

      课程总结

  • 第24讲 离散数学(2)期末考试
  • 第25讲 命题逻辑(教材第二十六章)
    • 25-01

      引言

    • 25-02

      命题与联结词

    • 25-03

      命题形式和真值表

    • 25-04

      联结词的完全集

    • 25-05

      推理形式

    • 25-06

      命题演算的自然推理系统N

    • 25-07

      命题演算形式系统P

    • 25-08

      N与P的等价性

    • 25-09

      赋值与等值演算

    • 25-10

      命题范式

    • 25-11

      可靠性、和谐性与完备性

    • 25-12

      期中考试

  • 第26讲 一阶谓词逻辑(教材第二十七章)
    • 26-01

      一阶谓词演算的符号化

    • 26-02

      一阶语言

    • 26-03

      一阶谓词演算的自然推演形式系统NL

    • 26-04

      一阶谓词演算的形式系统KL

    • 26-05

      NL与KL的等价性

    • 26-06

      KL的解释与赋值

    • 26-07

      KL的可靠性与和谐性

    • 26-08

      习题课

  • 第27讲 离散数学(3)期末考试
教材
  • 主教材
    离散数学教程
    ISBN:

    978-7-301-05366-9

    主编:

    耿素云 屈婉玲 王捍贫

    北京大学出版社
  • 辅助教材
    离散数学习题解析
    ISBN:

    978-7-301-09801-1

    主编:

    屈婉玲 耿素云 王捍贫 刘田

    北京大学出版社
课程信息
课程类型:

理论课

课程属性:

专业基础课/技术基础课

课程学时:

144.0

学校:

北京大学

学科门类:

工学

专业大类:

计算机类

专业类:

计算机科学与技术

适用专业:

计算机科学与技术

教学团队
  • 王捍贫

    课程负责人

    教授、博导

  • 刘田

    主讲教师

    副教授

  • 曹永知

    主讲教师

    教授

  • 屈婉玲

    主讲教师

    教授,博导

  • 张立昂

    主讲教师

    教授 博导