跳到正文

CSCI4240

进阶算法:随机与近似

集中不等式、随机舍入与线性规划松弛、随机游走、局部搜索、零和博弈、数据流与哈希,以及半正定规划。

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

你的进度

0/ 34 节已标记完成

下一节: 最大割的局部搜索

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

这门课在网上

CSCI4240 笔记里的内容

定理卡
74
定义
52
反例
36
概念视角
17
思想史
0
证明透视
40

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

在知识图谱中打开这门课

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

在网上定理卡 74 · 定义 52 · 反例 36 · 概念视角 17 · 证明透视 40

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

在知识图谱中打开这门课

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

第 2 章 · 2 节

零和博弈

混合策略与最优性证书。

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

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

  1. 2.1

    有限零和博弈中的混合策略

    利用线性规划对偶解释有限博弈中的最优随机化。

  2. 2.2

    多人博弈中的无遗憾策略

    利用完全信息乘性权重法构造近似粗相关均衡。

第 3 章 · 4 节

集中不等式

独立指示变量的乘法尾界。

定理 9反例 5视角 2证明透视 6

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

  1. 3.1

    独立指示变量的 Chernoff 界

    推导乘性尾界,并将其应用于抽样与稀疏计数。

  2. 3.2

    集中不等式与独立重复

    证明马尔可夫和切比雪夫不等式,并分析独立重复。

  3. 3.3

    球入箱问题中的最大负载

    利用一阶矩与二阶矩证明最大负载的上界与下界。

  4. 3.4

    生日碰撞与二阶矩

    分析碰撞概率,以及其背后的独立性假设。

第 4 章 · 5 节

随机舍入

集合覆盖的随机舍入与修补。

定理 12 · 定义 8反例 5视角 4证明透视 6

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

  1. 4.1

    集合覆盖的随机舍入

    把分数覆盖转化为可行覆盖,并界定其期望代价。

  2. 4.2

    为什么线性规划对偶是精确的

    通过投影不等式并追踪非负证书来证明强对偶性。

  3. 4.3

    集合覆盖:收费、线性松弛与原始—对偶证书

    证明调和贪心与频率舍入保证,并在构造覆盖时同步建立可行对偶下界。

  4. 4.4

    度量旅行商问题的近似算法

    利用生成树、欧拉(Euler)回路与度量捷径(shortcutting)来界定巡回路线的代价。

  5. 4.5

    背包问题的完全多项式时间近似方案

    对利润进行缩放,并求解最小重量动态规划,从而得到明确的近似保证。

第 5 章 · 4 节

随机游走

利用谱界放大成功概率。

定理 10 · 定义 8反例 4视角 2证明透视 5

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

  1. 5.1

    随机游走放大

    利用绝对谱界限控制对坏集合的重复访问概率。

  2. 5.2

    随机游走与谱混合

    利用正则图的特征值界定随机游走的收敛速度。

  3. 5.3

    2-SAT 的随机游走搜索

    利用距离势函数,界定随机化可满足赋值搜索的期望时间。

  4. 5.4

    平稳分布与懒惰游走

    证明有限马尔可夫(Markov)链平稳分布的存在性,以及基于耦合的收敛结果。

第 6 章 · 7 节

条件期望

以条件期望去随机化 Max-2SAT 保证。

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

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

  1. 6.1

    Max-2SAT 与条件期望

    把随机赋值的期望转化为确定性保证。

  2. 6.2

    最小割的随机收缩算法

    证明随机收缩算法的成功概率,并通过重复运行放大该概率。

  3. 6.3

    通过随机取值进行多项式恒等检验

    证明 Schwartz–Zippel 界,并将其应用于二部图完美匹配。

  4. 6.4

    矩阵乘积的随机化验证

    利用随机向量以单侧错误验证矩阵乘积。

  5. 6.5

    Lovász 局部引理

    证明局部引理,并利用稀疏的依赖关系说明所有坏事件可以同时被避免。

  6. 6.6

    随机割与条件期望

    用随机划分证明好割存在,并以条件期望去随机化。

  7. 6.7

    随机赋值与 MAX-SAT 近似

    分析带权子句的满足情况,并用条件期望法将随机算法去随机化。

第 7 章 · 6 节

在线决策

滑雪租赁的竞争分析。

定理 14 · 定义 17反例 7证明透视 7

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

  1. 7.1

    在线决策与租滑雪装备问题

    证明确定性竞争保证及与之匹配的下界。

  2. 7.2

    在线租买:竞争比与随机购买阈值

    比较离散模型与连续时间竞争比,并提供附解练习。

  3. 7.3

    在线分页与竞争分析

    分析分页问题中的标记阶段与对抗性请求。

  4. 7.4

    LRU 分页的精确竞争界

    利用按访问新近程度加权的势函数,证明最近最少使用(LRU)分页算法是 k-竞争的。

  5. 7.5

    在线分页的随机化标记算法

    利用调和和,在不经意对手下界定随机分页算法的期望代价。

  6. 7.6

    同构机器上的列表调度

    利用负载下界与最长作业下界,证明一个紧的完工时间保证。

第 8 章 · 1 节

随机覆盖

期望等待时间与高概率覆盖。

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

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

  1. 8.1

    集齐种类:期望与尾部界

    分析随机停止时间与覆盖尾部界。

第 9 章 · 1 节

数据流抽样

均匀水塘抽样与有限总体估计。

定理 1反例 1证明透视 1

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

  1. 9.1

    水塘抽样与估计数据流比例

    证明未知长度数据流的均匀抽样不变式,并推导有限总体误差界。

第 10 章 · 2 节

哈希与草图

哈希与草图

定理 4反例 2视角 2证明透视 2

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

  1. 10.1

    两两独立的二元哈希

    构造一个仿射哈希族,并分析基于碰撞的保证。

  2. 10.2

    用于频率估计的 Count–Min 草图

    利用两两独立哈希与独立重复来界定碰撞误差。

第 11 章 · 1 节

半正定规划

半正定规划

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

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

  1. 11.1

    最大割向量与随机超平面

    推导半正定松弛,证明角度分离概率,并得到精确的期望近似常数。

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

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

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

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

查看 Cookie 与存储详情