跳到正文

MATH3250

离散数学

证明方法、计数、递推与生成函数、整数算法、图论方法、偏序及算法设计,附证明、例题及习题解答。

7 章 · 26 节EN · 繁 · 简
我的课程笔记

你的进度

0/ 26 节已标记完成

下一节: 1.1 量词、归纳法与反例

完成记录保存在此浏览器中。

这门课在网上

MATH3250 笔记里的内容

定理卡
77
定义
39
反例
27
概念视角
25
思想史
1
证明透视
27

有思想史的节

这些思想史还没有放上时间线。

这门课的概念视角还没有记录到网上。

在知识图谱中打开这门课

数字只算这门课 26 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。

在网上定理卡 77 · 定义 39 · 反例 27 · 概念视角 25 · 思想史 1 · 证明透视 27

这些思想史还没有放上时间线。

这门课的概念视角还没有记录到网上。

在知识图谱中打开这门课

数字只算这门课 26 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。

第 1 章 · 2 节

证明方法

翻译精确的陈述,否定量词,并通过最小反例论证普通归纳法与强归纳法。

定理 5 · 定义 3反例 2视角 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 1.1

    量词、归纳法与反例

    翻译精确的陈述,否定量词,并通过最小反例论证普通归纳法与强归纳法。

  2. 1.2

    关系、等价类与良定义映射

    证明等价关系与集合划分的对应,理解函数的纤维,并判断用代表元给出的公式能否定义商集上的函数。

第 2 章 · 11 节

计数

选择正确的计数模型,证明容斥原理,并计算错位排列与满射的个数。

定理 37 · 定义 15反例 13视角 11证明透视 11

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 2.1

    双射、容斥原理与满射

    选择正确的计数模型,证明容斥原理,并计算错位排列与满射的个数。

  2. 2.2

    单调子序列与鸽巢原理

    用成对的子序列长度证明精确的有限界。

  3. 2.3

    依赖图与局部引理

    通过条件回避界证明有限非对称局部引理,导出一个对称判据,并将其应用于稀疏重叠的超图着色与可满足性问题,同时点明其中的联合独立性假设。

  4. 2.4

    计数中的选择、分类与原像纤维

    从不相交分类与原像纤维推导加法和乘法法则,并区分选择过程与它所描述的对象。

  5. 2.5

    二项式系数与组合恒等式

    以子集计数定义二项式系数,证明阶乘公式、对称性、帕斯卡(Pascal)法则、交换环上的二项式定理及双重计数恒等式。

  6. 2.6

    抽屉原理与单调子序列

    证明尖锐的占用量界,用前缀和余数寻找可整除的连续段,并通过终点长度标记证明递增或递减子序列的精确保证。

  7. 2.7

    集合划分、斯特林数与贝尔数总和

    计数集合划分与置换的轮换,证明它们的递推式与生成函数,并解释幂与下降阶乘之间的斯特林逆变换。

  8. 2.8

    反射法、投票路径与卡特兰结构

    通过可逆的反射证明弱与严格投票路径的计数,推导卡特兰数的闭式及形式二次母函数,并构造有序树和多边形三角剖分的双射。

  9. 2.9

    整数分拆、Ferrers 共轭与 Durfee 方阵

    证明分拆的共轭、形式母函数乘积、奇部分拆与相异部分拆的等价性以及 Durfee 分解,并给出恰好若干部分的限制,以及一个有严格依据的系数表算法。

  10. 2.10

    群作用、项链与本原周期

    通过稳定子证明轨道计数公式,推导旋转与反射公式,并借助莫比乌斯反演把字的本原周期联系起来,而无需除以大小不一的轨道。

  11. 2.11

    Ramsey 数及其基本界

    用归纳法证明两色 Ramsey 定理,推出二项式上界,确定 R(3,3)=6,并证明对角 Ramsey 数的计数下界。

第 3 章 · 2 节

递推与生成函数

由组合分解推导递推关系,并用形式幂级数求解。

定理 5 · 定义 3反例 2视角 2证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 3.1

    递推关系与形式生成函数

    由组合分解推导递推关系,并用形式幂级数求解。

  2. 3.6

    动态规划:选择、次序与重建

    推导精确的 0–1 背包和最少硬币递推,证明计算次序并恢复解。

第 4 章 · 2 节

整数算法

证明两个整数算法的正确性与终止性,并将算术运算次数与比特复杂度区分开来。

定理 5 · 定义 3反例 2视角 2思想史 1证明透视 2

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 4.1

    欧几里得不变式与二进制幂运算

    证明两个整数算法的正确性与终止性,并将算术运算次数与比特复杂度区分开来。

  2. 4.2

    线性同余与相容的余数方程组

    证明线性同余的完整解类、非互素情形下构造性的中国剩余定理合并方法以及两两相容判据,并给出精确的代表元、周期和模为一的边界情形。

第 5 章 · 5 节

图论方法

证明树的等价刻画,以及广度优先搜索在有限无权图上求最短路径的正确性。

定理 14 · 定义 8反例 4视角 5证明透视 6

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 5.1

    树与广度优先搜索

    证明树的等价刻画,以及广度优先搜索在有限无权图上求最短路径的正确性。

  2. 5.2

    欧拉迹与万有循环词

    证明有向欧拉(Euler)迹的判别准则,以及线性时间的图操作拼接算法,再通过重叠图构造最优的万有循环词与万有线性词,并给出精确的边界情形与输出规模条件。

  3. 5.3

    顶点着色与贪心界

    用合法着色表达冲突,证明贪心上界并识别二分图。

  4. 5.4

    最小生成森林与贪心交换

    证明割与圈交换规则、Kruskal 与 Prim 算法,以及可独立检查的最优性条件。

  5. 5.5

    非负权最短路与距离证书

    证明 Dijkstra 的最小标号定案原则,恢复最短路径,并用边不等式及无圈前驱证书独立核验距离。

第 6 章 · 3 节

偏序

整理有限偏序,对其下集上的求和进行反演,并由同一个关联代数论证导出布尔格反演与因数反演。

定理 8 · 定义 6反例 3视角 3证明透视 3

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 6.1

    偏序、线性扩张与 Möbius 反演

    整理有限偏序,对其下集上的求和进行反演,并由同一个关联代数论证导出布尔(Boole)格反演与因数反演。

  2. 6.2

    链、反链与 Dilworth 定理

    通过二分图匹配证明有限偏序集的链—反链划分定理,构造最优证书,并区分比较图与哈塞(Hasse)图。

  3. 6.3

    Sperner 定理、LYM 不等式与子集上影

    通过计数极大布尔(Boole)链证明 LYM 不等式与 Sperner 的最优反链上界,并分析上影以及中间层的取等情形。

第 8 章 · 1 节

算法设计

用交换论证和不变量证明算法选择的正确性。

定理 3 · 定义 1反例 1视角 1证明透视 1

本章骨架 →在网上看本章 →本章还没有记录到网上

  1. 8.1

    贪心选择、交换与区间调度

    通过交换及始终不落后的不变量证明最早结束区间调度,明确端点约定,并反驳其他看似合理的选择规则。

Vercel 访问统计与公开页面性能测量分别征求同意,均非使用网站的必要条件。

网站功能存储(按需使用)

安全、登录和你选择的偏好会按需使用存储,与可选统计分开处理。

撤回会停止后续统计;需要卸载已加载的统计程序时,页面会刷新。已发送的数据不会因此删除。

查看 Cookie 与存储详情