跳到正文

CSCI3190

离散数学及算法导论

逻辑、集合与关系,计数与离散概率,数论与字符串算法,图算法、排序、算法设计及 NP 完全性。

11 章 · 29 节EN · 繁 · 简
我的课程笔记

你的进度

0/ 29 节已标记完成

下一节: 容斥原理与满射计数

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

这门课在网上

CSCI3190 笔记里的内容

定理卡
90
定义
70
反例
34
概念视角
17
思想史
1
证明透视
33

有思想史的节

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

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

在知识图谱中打开这门课

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

在网上定理卡 90 · 定义 70 · 反例 34 · 概念视角 17 · 思想史 1 · 证明透视 33

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

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

在知识图谱中打开这门课

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

第 1 章 · 5 节

计数

计数

定理 14 · 定义 11反例 4视角 2证明透视 5

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

  1. 1.1

    容斥原理与满射计数

    逐一追踪对象的贡献,处理互相重叠的例外。

  2. 1.2

    在对称下计算构型

    证明不动点数目的平均公式,并计算二进制循环字符串。

  3. 1.3

    函数计数、子集选取与递归树的阅读

    区分有序分配与子集,证明鸽巢原理,定义渐近界,并通过各层求和推导平衡递推式的代价。

  4. 1.4

    集合划分、满射与斯特林递推

    区分组的标签与元素归属,证明斯特林数和满射的计数公式,并用经过论证的动态规划计算精确答案。

  5. 1.5

    离散概率、期望与线性性

    定义有限概率空间、随机变量与期望,证明期望的线性性与 Markov 不等式,并用指示变量分析随机化算法。

第 3 章 · 2 节

算法设计

算法设计

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

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

  1. 3.1

    贪心选择、分治与动态规划

    以调度与归并排序比较算法设计原则。

  2. 3.2

    取整子问题与主递推界

    证明整数上取整与下取整递推的分治工作量界,计入叶子并区分几何级数的各种情形,并在恰为幂的输入上推导对数型代价的临界阈值。

第 4 章 · 5 节

图算法

生成树、连通性、最短游走及拓扑次序。

定理 16 · 定义 10反例 6证明透视 5

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

  1. 4.1

    Kruskal 算法与割的交换论证

    构造最小生成树,并证明每条贪心选边都可属于一棵最优树。

  2. 4.2

    Bellman–Ford 与可达负环

    推导边数受限的最短游走,并找出因负环而无下界的距离。

  3. 4.3

    拓扑次序与有向环证书

    证明用队列求拓扑次序的算法,并构造有向环见证。

  4. 4.4

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

    维护不断合并的连通分量,并用倍增证明对数界。

  5. 4.5

    图的遍历、最短路径与生成树

    通过前沿不变量证明 BFS 与 Dijkstra 算法的正确性,推导最小生成树的割性质,并区分三种不同的优化目标。

第 5 章 · 3 节

整数算术

整数算术

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

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

  1. 5.1

    最大公约数、模逆元与快速幂

    证明欧几里得算法、线性同余与重复平方法。

  2. 5.2

    通用哈希与固定键碰撞界

    证明一个有限域哈希族的碰撞界,并将其应用于链式哈希与随机化重试。

  3. 5.3

    傅里叶蝶形运算与多项式卷积

    推导离散傅里叶(Fourier)变换及其分治求值方法,并说明计算普通卷积所需的补零。

第 6 章 · 3 节

字符串算法

前缀回退与精确匹配。

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

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

  1. 6.1

    前缀函数与重叠字符串匹配

    推导 KMP 回退、证明线性扫描,并保留重叠出现的位置。

  2. 6.2

    编辑距离与最优对齐

    推导编辑距离的前缀动态规划,证明其正确性并重构最优编辑序列。

  3. 6.3

    以滚动多项式指纹搜索字符串

    推导滚动更新与有限域碰撞界,明确说明核对和输入假设。

第 8 章 · 2 节

排序算法

排序算法

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

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

  1. 8.1

    逆序对、随机化快速排序与稳定基数排序

    用逆序对分析插入排序,推导随机化快速排序的期望比较次数,并在明确的键模型下证明稳定计数排序与基数排序。

  2. 8.2

    二叉堆、线性建堆与堆排序

    证明下沉(sift-down)的正确性,通过对各结点高度求和证明自底向上建堆的线性时间界,并证明原地堆排序,同时区分堆序、稳定性与优先队列的内存分配代价。

第 9 章 · 1 节

数论算法

数论算法

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

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

  1. 9.1

    中国剩余定理与合数见证

    保持 CRT 合并不变量,证明试除法与强合数判据,并区分合数见证和未经证明的素数结论。

第 10 章 · 1 节

多项式算法

快速 Fourier 求值与系数卷积。

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

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

  1. 10.1

    FFT 与多项式卷积

    推导基二 Fourier 求值及反变换,并在没有循环混叠下相乘多项式。

第 11 章 · 1 节

欧几里得算法与同余

把欧几里得证书延伸至模方程及相容的非互素余数系统。

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

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

  1. 11.1

    欧几里得不变量与同余证书

    把欧几里得证书延伸至模方程及相容的非互素余数系统。

第 12 章 · 5 节

逻辑、集合与关系

逻辑、集合与关系

定理 18 · 定义 26反例 9视角 4证明透视 7

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

  1. 12.1

    命题等价、范式与归结

    构造有限布尔公式的范式,用归结消去变量,并区分等价与可满足性等价。

  2. 12.2

    谓词逻辑、见证的依赖与有限模型检验

    准确理解变量作用域,说明量词证明规则的条件,并区分给定有限结构上的求值与所有结构上的有效性。

  3. 12.3

    逻辑、计数与算法不变量

    运用量词语句、归纳法、双射与容斥原理证明离散命题,并验证一个计数算法。

  4. 12.4

    集合、像、原像与复合映射

    逐元素证明集合恒等式,区分像与原像,并在有限集及空集条件下正确构造逆映射。

  5. 12.5

    关系、等价类与偏序

    用划分理解等价关系,并用有限偏序描述依赖关系。

第 13 章 · 1 节

复杂度与 NP 完全性

复杂度与 NP 完全性

定理 3反例 1证明透视 1

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

  1. 13.1

    证书、归约与 NP 完全性

    定义带多项式见证长度界的高效验证,证明图问题之间的归约,并在两个逻辑方向上构造从子句到团的归约。

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

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

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

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

查看 Cookie 与存储详情