你的进度
0/ 26 节已标记完成
下一节: 1.1 量词、归纳法与反例
完成记录保存在此浏览器中。
这门课在网上
MATH3250 笔记里的内容
数字只算这门课 26 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。
在网上定理卡 77 · 定义 39 · 反例 27 · 概念视角 25 · 思想史 1 · 证明透视 27
第 1 章 · 2 节
证明方法
翻译精确的陈述,否定量词,并通过最小反例论证普通归纳法与强归纳法。
- 1.1
量词、归纳法与反例
翻译精确的陈述,否定量词,并通过最小反例论证普通归纳法与强归纳法。
- 1.2
关系、等价类与良定义映射
证明等价关系与集合划分的对应,理解函数的纤维,并判断用代表元给出的公式能否定义商集上的函数。
第 2 章 · 11 节
计数
选择正确的计数模型,证明容斥原理,并计算错位排列与满射的个数。
- 2.1
双射、容斥原理与满射
选择正确的计数模型,证明容斥原理,并计算错位排列与满射的个数。
- 2.2
单调子序列与鸽巢原理
用成对的子序列长度证明精确的有限界。
- 2.3
依赖图与局部引理
通过条件回避界证明有限非对称局部引理,导出一个对称判据,并将其应用于稀疏重叠的超图着色与可满足性问题,同时点明其中的联合独立性假设。
- 2.4
计数中的选择、分类与原像纤维
从不相交分类与原像纤维推导加法和乘法法则,并区分选择过程与它所描述的对象。
- 2.5
二项式系数与组合恒等式
以子集计数定义二项式系数,证明阶乘公式、对称性、帕斯卡(Pascal)法则、交换环上的二项式定理及双重计数恒等式。
- 2.6
抽屉原理与单调子序列
证明尖锐的占用量界,用前缀和余数寻找可整除的连续段,并通过终点长度标记证明递增或递减子序列的精确保证。
- 2.7
集合划分、斯特林数与贝尔数总和
计数集合划分与置换的轮换,证明它们的递推式与生成函数,并解释幂与下降阶乘之间的斯特林逆变换。
- 2.8
反射法、投票路径与卡特兰结构
通过可逆的反射证明弱与严格投票路径的计数,推导卡特兰数的闭式及形式二次母函数,并构造有序树和多边形三角剖分的双射。
- 2.9
整数分拆、Ferrers 共轭与 Durfee 方阵
证明分拆的共轭、形式母函数乘积、奇部分拆与相异部分拆的等价性以及 Durfee 分解,并给出恰好若干部分的限制,以及一个有严格依据的系数表算法。
- 2.10
群作用、项链与本原周期
通过稳定子证明轨道计数公式,推导旋转与反射公式,并借助莫比乌斯反演把字的本原周期联系起来,而无需除以大小不一的轨道。
- 2.11
Ramsey 数及其基本界
用归纳法证明两色 Ramsey 定理,推出二项式上界,确定 R(3,3)=6,并证明对角 Ramsey 数的计数下界。
第 3 章 · 2 节
递推与生成函数
由组合分解推导递推关系,并用形式幂级数求解。
- 3.1
递推关系与形式生成函数
由组合分解推导递推关系,并用形式幂级数求解。
- 3.6
动态规划:选择、次序与重建
推导精确的 0–1 背包和最少硬币递推,证明计算次序并恢复解。
第 4 章 · 2 节
整数算法
证明两个整数算法的正确性与终止性,并将算术运算次数与比特复杂度区分开来。
- 4.1
欧几里得不变式与二进制幂运算
证明两个整数算法的正确性与终止性,并将算术运算次数与比特复杂度区分开来。
- 4.2
线性同余与相容的余数方程组
证明线性同余的完整解类、非互素情形下构造性的中国剩余定理合并方法以及两两相容判据,并给出精确的代表元、周期和模为一的边界情形。
第 5 章 · 5 节
图论方法
证明树的等价刻画,以及广度优先搜索在有限无权图上求最短路径的正确性。
- 5.1
树与广度优先搜索
证明树的等价刻画,以及广度优先搜索在有限无权图上求最短路径的正确性。
- 5.2
欧拉迹与万有循环词
证明有向欧拉(Euler)迹的判别准则,以及线性时间的图操作拼接算法,再通过重叠图构造最优的万有循环词与万有线性词,并给出精确的边界情形与输出规模条件。
- 5.3
顶点着色与贪心界
用合法着色表达冲突,证明贪心上界并识别二分图。
- 5.4
最小生成森林与贪心交换
证明割与圈交换规则、Kruskal 与 Prim 算法,以及可独立检查的最优性条件。
- 5.5
非负权最短路与距离证书
证明 Dijkstra 的最小标号定案原则,恢复最短路径,并用边不等式及无圈前驱证书独立核验距离。
第 6 章 · 3 节
偏序
整理有限偏序,对其下集上的求和进行反演,并由同一个关联代数论证导出布尔格反演与因数反演。
- 6.1
偏序、线性扩张与 Möbius 反演
整理有限偏序,对其下集上的求和进行反演,并由同一个关联代数论证导出布尔(Boole)格反演与因数反演。
- 6.2
链、反链与 Dilworth 定理
通过二分图匹配证明有限偏序集的链—反链划分定理,构造最优证书,并区分比较图与哈塞(Hasse)图。
- 6.3
Sperner 定理、LYM 不等式与子集上影
通过计数极大布尔(Boole)链证明 LYM 不等式与 Sperner 的最优反链上界,并分析上影以及中间层的取等情形。
第 8 章 · 1 节
算法设计
用交换论证和不变量证明算法选择的正确性。
- 8.1
贪心选择、交换与区间调度
通过交换及始终不落后的不变量证明最早结束区间调度,明确端点约定,并反驳其他看似合理的选择规则。