返回：本科课程：疾风计划

1、课程定位

离散数学是疾风计划第一阶段的基础课之一，主要用来补齐计算机专业后续课程需要的数学表达能力。它不只是背定义，而是训练四件事：把问题写成集合语言，把对象之间的联系写成关系和函数，把结构抽象成图或代数系统，把计数和推理过程写成可检查的证明。

项目 内容
课程 离散数学
资料来源 北大公开课为主，清华资料与 Auto_Tutor 整理资料作补充
授课教师 刘田、屈婉玲、王捍贫、马昱春
学习定位 专业基础课，服务数据结构、算法、数据库、编译原理、网络安全和后续证明类复盘
笔记范围 0101~0124，对应 Chap 1 到 Chap 24

这组笔记已经按章节拆开，0100 只作为总目录。后续复盘时从这里进入对应章节，避免总览页和逐章页混在一起。

2、学习主线

部分 章节 核心问题 后续连接
集合论基础 Chap 1-5 如何用集合、关系、函数和自然数描述离散对象 数据结构、数据库关系模型、算法证明
图论 Chap 6-13 如何用顶点和边描述连接、路径、匹配、着色和优化问题 图算法、网络拓扑、调度与路径问题
代数结构 Chap 14-18 集合上定义运算后，会形成怎样的抽象结构 密码学、编码理论、形式化结构
组合数学 Chap 19-22 如何计数、递推、处理对称性和包含排斥 算法分析、概率统计、数学建模
数理逻辑 Chap 23-24 如何形式化命题、谓词、推理、证明和语义 编译原理、程序验证、形式化方法

3、章节索引

3.1 集合论基础

编号 Chap 主题 复盘重点 笔记
0101 1 集合论课程引言、预备知识与集合基本概念 命题逻辑、一阶谓词逻辑、集合运算、集合恒等式 查看
0102 2 关系、有序对、闭包、等价关系与序关系 关系性质、关系矩阵、闭包、等价类、偏序和哈斯图 查看
0103 3 函数与集合论习题课 函数、单射、满射、双射、复合、反函数和集合论综合题 查看
0104 4 自然数的定义与性质 Peano 系统、后继、归纳法、递归定义、自然数运算 查看
0105 5 等势、基数、序数与集合论公理 双射、Cantor 定理、可数集、基数比较、ZFC 公理 查看

3.2 图论

编号 Chap 主题 复盘重点 笔记
0106 6 图的基本概念、通路回路与连通性 度数列、握手定理、连通性、点割集、边割集、Menger 定理 查看
0107 7 欧拉图与哈密顿图 欧拉判定、Fleury 算法、哈密顿必要条件、Ore 与 Dirac 定理 查看
0108 8 树 树的等价定义、树叶、生成树、基本回路、基本割集、Cayley 公式 查看
0109 9 图的矩阵表示 关联矩阵、邻接矩阵、矩阵幂通路计数、可达矩阵、连通矩阵 查看
0110 10 平面图 欧拉公式、极大平面图、非平面判定、Kuratowski 定理、对偶图 查看
0111 11 图着色 点着色、色多项式、平面图着色、面着色、边着色 查看
0112 12 支配、覆盖、独立与匹配 支配集、点覆盖、点独立、边覆盖、匹配、Hall 定理 查看
0113 13 图论应用、习题课与课程总结 中国邮递员问题、货郎担问题、近似算法、图论综合题 查看

3.3 代数结构

编号 Chap 主题 复盘重点 笔记
0114 14 代数结构基础：二元运算、代数系统与同态 封闭性、运算性质、子代数、积代数、同态、同构、商代数 查看
0115 15 半群与独异点 半群、独异点、单位元、子半群、生成子半群、同态 查看
0116 16 群论基础 群、子群、循环群、置换群、陪集、正规子群、商群、群同态 查看
0117 17 环与域 环、整环、域、零因子、理想、商环、环同态、有限域 查看
0118 18 格与布尔代数 格、模格、分配格、有补格、布尔代数、理想、格同态 查看

3.4 组合数学

编号 Chap 主题 复盘重点 笔记
0119 19 组合数学引言、鸽巢原理与 Ramsey 定理 一一对应、归纳、鸽巢原理、Ramsey 数、相异代表系 查看
0120 20 计数原则、排列组合与组合恒等式 加法/乘法法则、排列组合、多重集、二项式定理、非降路径 查看
0121 21 递推方程与生成函数 常系数递推、普通生成函数、指数生成函数、Catalan 数、Stirling 数 查看
0122 22 包含排斥、Burnside 引理与 Polya 定理 包含排斥、错位排列、棋盘多项式、Burnside、Polya、轮换指数 查看

3.5 数理逻辑

编号 Chap 主题 复盘重点 笔记
0123 23 命题逻辑 联结词、真值表、完全集、自然推演 N、形式系统 P、范式、可靠性 查看
0124 24 一阶谓词逻辑 项、公式、自由变元、NL、KL、解释与赋值、可靠性和完备性 查看

4、复盘顺序

场景 建议顺序
快速补基础 0101 -> 0102 -> 0103 -> 0106 -> 0108 -> 0119 -> 0120 -> 0123
数据结构前置 0106 -> 0107 -> 0108 -> 0109 -> 0110 -> 0111 -> 0112 -> 0113
考研数学表达 0101 -> 0102 -> 0103 -> 0104 -> 0105 -> 0119 -> 0120 -> 0121 -> 0122
网络安全/密码学方向 0114 -> 0115 -> 0116 -> 0117 -> 0118 -> 0123 -> 0124
证明能力训练 每章先看“核心概念”，再做“习题与答案”，最后对照“复盘清单”查缺口

5、颜色标注规则

颜色 用法
粉色 主线必掌握、考试或复盘优先级最高的结论
蓝色 核心概念、术语、定义名
橙色 易错边界、定义适用条件、容易混淆的地方
绿色 解释、类比、和后续课程的连接

6、整理口径

每章保留同一套结构：学习目标、知识主线、核心概念、易错点、习题与答案、复盘清单。习题不只列题目，而是尽量补出答案和思路；如果原始资料里的公式或图片不完整，后续复盘时再对照课件或截图校正。

这门课后面会经常回看，尤其是图论、组合数学和逻辑部分。先不用追求一次背完，重点是让每一章都能快速定位到“定义是什么、常见题怎么做、容易错在哪里”。