你的进度
0/ 45 节已标记完成
下一节: 正确性、成本模型与分治
完成记录保存在此浏览器中。
这门课在网上
CSCI3160 笔记里的内容
数字只算这门课 45 节公开笔记里写了什么,不是网上已记录的关系。目前其中 0 节已细致地记录到网上。
在网上定理卡 111 · 定义 84 · 反例 61 · 概念视角 30 · 思想史 1 · 证明透视 53
第 1 章 · 12 节
正确性与分治
正确性与分治
- 1.1
正确性、成本模型与分治
证明迭代及递归算法的正确性,分清输入大小与时间界,并推导合并排序的递推式。
- 1.2
二进制计数器与摊还分析
以总计数及势能证明操作序列上界,并处理循环溢出与混合操作的限制。
- 1.3
用二分搜索定位可行性边界
证明单调谓词的边界查找,再结合经证明的贪心判定,最小化连续分块的最大负载。
- 1.4
带渐近代价项的主定理
证明三种常见的递推情形,以及正则性条件的作用。
- 1.5
分治递推式的递归树
通过逐层求和,推导幂型附加代价递推式的三种情形。
- 1.6
Karatsuba 乘法
推导三次乘积的乘法,并分析取整后的递归规模。
- 1.7
快速傅里叶变换与卷积
推导基二蝶形运算、逆变换,以及用补零实现的多项式乘法。
- 1.8
比较排序的下界
证明决策树下界,并区分比较排序与计数排序。
- 1.9
随机化快速排序的期望比较次数
利用键对指示变量推导快速排序期望比较次数的精确值。
- 1.10
最坏情况线性时间选择
以五元组中位数选取主元,并证明线性比较次数上界。
- 1.11
随机选择与期望线性工作量
利用平衡主元阶段证明快速选择的期望线性界。
- 1.12
动态数组的摊还分析
用聚合论证与势能论证界定数组倍增的代价。
第 2 章 · 11 节
动态规划与贪心算法
动态规划与贪心算法
- 2.1
最长公共子序列
推导前缀动态规划,并重构一个最优公共子序列。
- 2.2
矩阵链动态规划
推导、计算并重构矩阵乘积的最优括号化方式。
- 2.3
贪心选择与动态规划
用交换论证证明区间调度,推导加权区间及背包递推式,并解释状态设计与解的重建。
- 2.4
最长递增子序列:状态、末尾值与重构
证明严格递增子序列的二次动态规划及二分搜索法,并重构真正的解。
- 2.5
阅读加权调度的运算轨迹
通过六个任务比较前驱前缀和回溯决策。
- 2.6
单机调度与相邻交换
推导按到期日和处理时间权重比排序的规则,理解为什么调度目标一变,贪心证明也必须改变。
- 2.7
霍夫曼编码与贪心交换论证
证明在二元前缀码中合并两个最小权重的做法是最优的。
- 2.8
拟阵上的贪心优化
利用扩充性质与基交换证明加权贪心定理。
- 2.9
背包问题:分数贪心与零一动态规划
证明分数背包的密度规则,推导零一背包状态,并恢复所选物品。
- 2.10
编辑距离与动态规划
推导编辑距离的递推式,并还原一个最优的编辑序列。
- 2.11
最优二叉搜索树
利用区间动态规划处理成功查找与失败查找的代价。
第 3 章 · 10 节
图与网络流
图与网络流
- 3.1
最大流与最小割
利用残量网络证明最优性并计算最大流。
- 3.2
从不变量理解图算法
明确图、权重与数据结构假设,证明遍历、生成树及最短路径算法。
- 3.3
二分图匹配、Hall 条件与顶点覆盖证书
利用交替路径构造最优性证书,并证明 Hall 定理。
- 3.4
有向无环图中的拓扑序与最短路径
证明拓扑排序,以及无环图中允许负边权的线性时间最短路径算法。
- 3.5
强连通分量
证明两遍扫描分量算法背后的完成时间顺序。
- 3.6
基于动态规划的全源最短路径
在明确的假设下推导 Floyd–Warshall 递推式及其原地更新。
- 3.7
Prim 最小生成树算法
证明不断生长的树的不变量,并核算二叉堆操作的代价。
- 3.8
不相交集合森林与按大小合并
证明按大小合并的树高为对数级,并将该结构应用于 Kruskal 算法。
- 3.9
最短增广路径与多项式时间网络流
利用残量距离证明 Edmonds–Karp 增广次数上界。
- 3.10
二分图匹配与 Hall 证书
寻找增广路,并推导匹配证书、覆盖证书与 Hall 证书。
第 4 章 · 6 节
归约与 NP 完全性
归约与 NP 完全性
- 4.1
多项式归约与 NP 完全性
区分验证与搜索,证明归约方向,并完整构造从 3-SAT 到团及顶点覆盖的归约。
- 4.2
从布尔公式到 3-SAT
构造逻辑门子句与长子句链,证明精确的赋值扩张性质,并从明确声明的 SAT 起点推导 3-SAT 完全性。
- 4.3
从 3-SAT 到三着色的归约
构造并验证三着色问题的显式子句构件。
- 4.4
从 3-SAT 到子集和问题的归约
用无进位的十进制数位列编码变量选择与子句满足性。
- 4.5
哈密顿路径、哈密顿圈与旅行商归约
在不同图模型之间变换哈密顿见证,并比较度量旅行商与任意代价旅行商的巡回代价。
- 4.6
近似算法:顶点覆盖与集合覆盖
定义近似比,证明极大匹配给出顶点覆盖的二近似,并证明贪心集合覆盖的调和数保证。
第 5 章 · 1 节
前缀码
贪心合并与最优带权二元码。
- 5.1
霍夫曼编码与贪心交换
证明二元前缀码的最小两权重合并法则。
第 6 章 · 1 节
拟阵与贪心算法
以增广性证明加权贪心定理。
- 6.1
为什么加权贪心法适用于拟阵的基
利用前缀秩证明最大权基定理,并区分基与任意独立集。
第 7 章 · 2 节
最短路径
以边数上限证明松弛,并识别相关的负环。
- 7.1
Bellman–Ford:松弛、边数上限与负环
由限制边数的递推式推导最短路径松弛,证明原地更新算法,并分清可达负环与不影响查询的负环。
- 7.2
Dijkstra 算法:已确定顶点与惰性优先队列
证明非负边权下的贪心步骤,处理堆中过时的记录和零权重平局,并在有向多重图中用边编号重建路径。
第 8 章 · 1 节
动态规划:重构
重构最长公共子序列,并明确计算时间与空间开销。
- 8.1
最长公共子序列:前缀不变量与节省空间的重建
证明 LCS 递推、重建最优序列、维持滚动行不变量,并以明确内存成本推导分治重建。
第 9 章 · 1 节
分治应用
几何分治与排序不变量。
- 9.1
最近点对:条带中的点数界、纵坐标顺序与精确距离平方
证明合并步骤只需检查后续七个点,在递归中维持纵坐标顺序,并在不使用浮点距离比较的情况下返回可核对的最近点对。