你的进度
0/ 29 节已标记完成
下一节: 容斥原理与满射计数
完成记录保存在此浏览器中。
这门课在网上
CSCI3190 笔记里的内容
数字只算这门课 29 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。
在网上定理卡 90 · 定义 70 · 反例 34 · 概念视角 17 · 思想史 1 · 证明透视 33
第 1 章 · 5 节
计数
计数
- 1.1
容斥原理与满射计数
逐一追踪对象的贡献,处理互相重叠的例外。
- 1.2
在对称下计算构型
证明不动点数目的平均公式,并计算二进制循环字符串。
- 1.3
函数计数、子集选取与递归树的阅读
区分有序分配与子集,证明鸽巢原理,定义渐近界,并通过各层求和推导平衡递推式的代价。
- 1.4
集合划分、满射与斯特林递推
区分组的标签与元素归属,证明斯特林数和满射的计数公式,并用经过论证的动态规划计算精确答案。
- 1.5
离散概率、期望与线性性
定义有限概率空间、随机变量与期望,证明期望的线性性与 Markov 不等式,并用指示变量分析随机化算法。
第 3 章 · 2 节
算法设计
算法设计
- 3.1
贪心选择、分治与动态规划
以调度与归并排序比较算法设计原则。
- 3.2
取整子问题与主递推界
证明整数上取整与下取整递推的分治工作量界,计入叶子并区分几何级数的各种情形,并在恰为幂的输入上推导对数型代价的临界阈值。
第 4 章 · 5 节
图算法
生成树、连通性、最短游走及拓扑次序。
- 4.1
Kruskal 算法与割的交换论证
构造最小生成树,并证明每条贪心选边都可属于一棵最优树。
- 4.2
Bellman–Ford 与可达负环
推导边数受限的最短游走,并找出因负环而无下界的距离。
- 4.3
拓扑次序与有向环证书
证明用队列求拓扑次序的算法,并构造有向环见证。
- 4.4
不相交集合森林与按大小合并
维护不断合并的连通分量,并用倍增证明对数界。
- 4.5
图的遍历、最短路径与生成树
通过前沿不变量证明 BFS 与 Dijkstra 算法的正确性,推导最小生成树的割性质,并区分三种不同的优化目标。
第 5 章 · 3 节
整数算术
整数算术
- 5.1
最大公约数、模逆元与快速幂
证明欧几里得算法、线性同余与重复平方法。
- 5.2
通用哈希与固定键碰撞界
证明一个有限域哈希族的碰撞界,并将其应用于链式哈希与随机化重试。
- 5.3
傅里叶蝶形运算与多项式卷积
推导离散傅里叶(Fourier)变换及其分治求值方法,并说明计算普通卷积所需的补零。
第 6 章 · 3 节
字符串算法
前缀回退与精确匹配。
- 6.1
前缀函数与重叠字符串匹配
推导 KMP 回退、证明线性扫描,并保留重叠出现的位置。
- 6.2
编辑距离与最优对齐
推导编辑距离的前缀动态规划,证明其正确性并重构最优编辑序列。
- 6.3
以滚动多项式指纹搜索字符串
推导滚动更新与有限域碰撞界,明确说明核对和输入假设。
第 8 章 · 2 节
排序算法
排序算法
- 8.1
逆序对、随机化快速排序与稳定基数排序
用逆序对分析插入排序,推导随机化快速排序的期望比较次数,并在明确的键模型下证明稳定计数排序与基数排序。
- 8.2
二叉堆、线性建堆与堆排序
证明下沉(sift-down)的正确性,通过对各结点高度求和证明自底向上建堆的线性时间界,并证明原地堆排序,同时区分堆序、稳定性与优先队列的内存分配代价。
第 9 章 · 1 节
数论算法
数论算法
- 9.1
中国剩余定理与合数见证
保持 CRT 合并不变量,证明试除法与强合数判据,并区分合数见证和未经证明的素数结论。
第 10 章 · 1 节
多项式算法
快速 Fourier 求值与系数卷积。
- 10.1
FFT 与多项式卷积
推导基二 Fourier 求值及反变换,并在没有循环混叠下相乘多项式。
第 11 章 · 1 节
欧几里得算法与同余
把欧几里得证书延伸至模方程及相容的非互素余数系统。
- 11.1
欧几里得不变量与同余证书
把欧几里得证书延伸至模方程及相容的非互素余数系统。
第 12 章 · 5 节
逻辑、集合与关系
逻辑、集合与关系
- 12.1
命题等价、范式与归结
构造有限布尔公式的范式,用归结消去变量,并区分等价与可满足性等价。
- 12.2
谓词逻辑、见证的依赖与有限模型检验
准确理解变量作用域,说明量词证明规则的条件,并区分给定有限结构上的求值与所有结构上的有效性。
- 12.3
逻辑、计数与算法不变量
运用量词语句、归纳法、双射与容斥原理证明离散命题,并验证一个计数算法。
- 12.4
集合、像、原像与复合映射
逐元素证明集合恒等式,区分像与原像,并在有限集及空集条件下正确构造逆映射。
- 12.5
关系、等价类与偏序
用划分理解等价关系,并用有限偏序描述依赖关系。
第 13 章 · 1 节
复杂度与 NP 完全性
复杂度与 NP 完全性
- 13.1
证书、归约与 NP 完全性
定义带多项式见证长度界的高效验证,证明图问题之间的归约,并在两个逻辑方向上构造从子句到团的归约。