跳到正文

CSCI3160

算法设计及分析

正确性与分治、摊还分析与随机化分析、动态规划、贪心算法与拟阵、最短路径、网络流与匹配,以及 NP 完全性。

9 章 · 45 节EN · 繁 · 简
我的课程笔记

你的进度

0/ 45 节已标记完成

下一节: 正确性、成本模型与分治

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

这门课在网上

CSCI3160 笔记里的内容

定理卡
111
定义
84
反例
61
概念视角
30
思想史
1
证明透视
53

有思想史的节

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

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

在知识图谱中打开这门课

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

在网上定理卡 111 · 定义 84 · 反例 61 · 概念视角 30 · 思想史 1 · 证明透视 53

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

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

在知识图谱中打开这门课

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

第 1 章 · 12 节

正确性与分治

正确性与分治

定理 25 · 定义 19反例 15视角 9证明透视 13

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

  1. 1.1

    正确性、成本模型与分治

    证明迭代及递归算法的正确性,分清输入大小与时间界,并推导合并排序的递推式。

  2. 1.2

    二进制计数器与摊还分析

    以总计数及势能证明操作序列上界,并处理循环溢出与混合操作的限制。

  3. 1.3

    用二分搜索定位可行性边界

    证明单调谓词的边界查找,再结合经证明的贪心判定,最小化连续分块的最大负载。

  4. 1.4

    带渐近代价项的主定理

    证明三种常见的递推情形,以及正则性条件的作用。

  5. 1.5

    分治递推式的递归树

    通过逐层求和,推导幂型附加代价递推式的三种情形。

  6. 1.6

    Karatsuba 乘法

    推导三次乘积的乘法,并分析取整后的递归规模。

  7. 1.7

    快速傅里叶变换与卷积

    推导基二蝶形运算、逆变换,以及用补零实现的多项式乘法。

  8. 1.8

    比较排序的下界

    证明决策树下界,并区分比较排序与计数排序。

  9. 1.9

    随机化快速排序的期望比较次数

    利用键对指示变量推导快速排序期望比较次数的精确值。

  10. 1.10

    最坏情况线性时间选择

    以五元组中位数选取主元,并证明线性比较次数上界。

  11. 1.11

    随机选择与期望线性工作量

    利用平衡主元阶段证明快速选择的期望线性界。

  12. 1.12

    动态数组的摊还分析

    用聚合论证与势能论证界定数组倍增的代价。

第 2 章 · 11 节

动态规划与贪心算法

动态规划与贪心算法

定理 24 · 定义 18反例 15视角 10证明透视 12

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

  1. 2.1

    最长公共子序列

    推导前缀动态规划,并重构一个最优公共子序列。

  2. 2.2

    矩阵链动态规划

    推导、计算并重构矩阵乘积的最优括号化方式。

  3. 2.3

    贪心选择与动态规划

    用交换论证证明区间调度,推导加权区间及背包递推式,并解释状态设计与解的重建。

  4. 2.4

    最长递增子序列:状态、末尾值与重构

    证明严格递增子序列的二次动态规划及二分搜索法,并重构真正的解。

  5. 2.5

    阅读加权调度的运算轨迹

    通过六个任务比较前驱前缀和回溯决策。

  6. 2.6

    单机调度与相邻交换

    推导按到期日和处理时间权重比排序的规则,理解为什么调度目标一变,贪心证明也必须改变。

  7. 2.7

    霍夫曼编码与贪心交换论证

    证明在二元前缀码中合并两个最小权重的做法是最优的。

  8. 2.8

    拟阵上的贪心优化

    利用扩充性质与基交换证明加权贪心定理。

  9. 2.9

    背包问题:分数贪心与零一动态规划

    证明分数背包的密度规则,推导零一背包状态,并恢复所选物品。

  10. 2.10

    编辑距离与动态规划

    推导编辑距离的递推式,并还原一个最优的编辑序列。

  11. 2.11

    最优二叉搜索树

    利用区间动态规划处理成功查找与失败查找的代价。

第 3 章 · 10 节

图与网络流

图与网络流

定理 24 · 定义 23反例 15视角 4证明透视 13

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

  1. 3.1

    最大流与最小割

    利用残量网络证明最优性并计算最大流。

  2. 3.2

    从不变量理解图算法

    明确图、权重与数据结构假设,证明遍历、生成树及最短路径算法。

  3. 3.3

    二分图匹配、Hall 条件与顶点覆盖证书

    利用交替路径构造最优性证书,并证明 Hall 定理。

  4. 3.4

    有向无环图中的拓扑序与最短路径

    证明拓扑排序,以及无环图中允许负边权的线性时间最短路径算法。

  5. 3.5

    强连通分量

    证明两遍扫描分量算法背后的完成时间顺序。

  6. 3.6

    基于动态规划的全源最短路径

    在明确的假设下推导 Floyd–Warshall 递推式及其原地更新。

  7. 3.7

    Prim 最小生成树算法

    证明不断生长的树的不变量,并核算二叉堆操作的代价。

  8. 3.8

    不相交集合森林与按大小合并

    证明按大小合并的树高为对数级,并将该结构应用于 Kruskal 算法。

  9. 3.9

    最短增广路径与多项式时间网络流

    利用残量距离证明 Edmonds–Karp 增广次数上界。

  10. 3.10

    二分图匹配与 Hall 证书

    寻找增广路,并推导匹配证书、覆盖证书与 Hall 证书。

第 4 章 · 6 节

归约与 NP 完全性

归约与 NP 完全性

定理 13 · 定义 15反例 6视角 5思想史 1证明透视 7

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

  1. 4.1

    多项式归约与 NP 完全性

    区分验证与搜索,证明归约方向,并完整构造从 3-SAT 到团及顶点覆盖的归约。

  2. 4.2

    从布尔公式到 3-SAT

    构造逻辑门子句与长子句链,证明精确的赋值扩张性质,并从明确声明的 SAT 起点推导 3-SAT 完全性。

  3. 4.3

    从 3-SAT 到三着色的归约

    构造并验证三着色问题的显式子句构件。

  4. 4.4

    从 3-SAT 到子集和问题的归约

    用无进位的十进制数位列编码变量选择与子句满足性。

  5. 4.5

    哈密顿路径、哈密顿圈与旅行商归约

    在不同图模型之间变换哈密顿见证,并比较度量旅行商与任意代价旅行商的巡回代价。

  6. 4.6

    近似算法:顶点覆盖与集合覆盖

    定义近似比,证明极大匹配给出顶点覆盖的二近似,并证明贪心集合覆盖的调和数保证。

第 5 章 · 1 节

前缀码

贪心合并与最优带权二元码。

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

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

  1. 5.1

    霍夫曼编码与贪心交换

    证明二元前缀码的最小两权重合并法则。

第 6 章 · 1 节

拟阵与贪心算法

以增广性证明加权贪心定理。

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

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

  1. 6.1

    为什么加权贪心法适用于拟阵的基

    利用前缀秩证明最大权基定理,并区分基与任意独立集。

第 7 章 · 2 节

最短路径

以边数上限证明松弛,并识别相关的负环。

定理 10 · 定义 4反例 3证明透视 3

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

  1. 7.1

    Bellman–Ford:松弛、边数上限与负环

    由限制边数的递推式推导最短路径松弛,证明原地更新算法,并分清可达负环与不影响查询的负环。

  2. 7.2

    Dijkstra 算法:已确定顶点与惰性优先队列

    证明非负边权下的贪心步骤,处理堆中过时的记录和零权重平局,并在有向多重图中用边编号重建路径。

第 8 章 · 1 节

动态规划:重构

重构最长公共子序列,并明确计算时间与空间开销。

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

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

  1. 8.1

    最长公共子序列:前缀不变量与节省空间的重建

    证明 LCS 递推、重建最优序列、维持滚动行不变量,并以明确内存成本推导分治重建。

第 9 章 · 1 节

分治应用

几何分治与排序不变量。

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

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

  1. 9.1

    最近点对:条带中的点数界、纵坐标顺序与精确距离平方

    证明合并步骤只需检查后续七个点,在递归中维持纵坐标顺序,并在不使用浮点距离比较的情况下返回可核对的最近点对。

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

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

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

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

查看 Cookie 与存储详情