唐常杰翻译的计算理论导引.ppt

该【唐常杰翻译的计算理论导引 】是由【明月清风】上传分享，文档一共【59】页，该文档可以免费在线阅读，需要了解更多关于【唐常杰翻译的计算理论导引 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。Chap 10 复杂性理论中的高级专题 (同学报告）
可以从下列文件获得ＰPT素材：
13_10-复杂理论高级专题-
本章提纲
1 近似算法、
2 概率算法
3 交错式
4 交互证明，
5 并行计算
6 密码学
Chap 10 复杂性理论中的高级专题 (同学报告）
可根据 提供的ＰPT素材+参考以前同学的报告， 修改成为有自己见解的讨论报告建议： 底色用浅色（象牙白， 浅黄， 白色等） 适合色盲 色弱 观众 字体颜色选择余地大 在投影机 效果差时 也还能能看见
近似算法
3
在最优化问题中，通常试图在可行解中寻找最好的解，即最优解。
在实践中，可能并不一定非要最优解不可，一个接近最优的解可能是足够好的，而且可能更容易找到。
近似算法是为了求近似最优解而设计的。
02
03
01
2025/1/23
顶点覆盖问题
4
若G是无向图，则G的顶点覆盖是节点的一个子集，使得G的每条边都与子集中的节点之一相关联。
2025/1/23
最小顶点覆盖的一个近似算法
5
下述多项式时间算法近似地解这个最优化问题，它给出一个顶点覆盖，其大小不超过最小顶点覆盖的大小的2倍。
A＝ “对于输入<G>，这里G是一个无向图：
重复下述操作直至G中所有的边都与有标记的边相邻。
在G中找一条不与任何有标记的边相邻的边。
给这条边作标记。
输出所有有标记边的顶点。 ”
2025/1/23

6
：A是一个多项式时间算法，它给出G的一个顶点覆盖，其大小不超过最小顶点覆盖的大小的2倍。
证明思路:
A的运行时间显然是多项式界限的。
设X是它输出的顶点集合，H是有标记的边的集合。因为G的每一条边要么属于H，要么与H中的一条边相邻，因此X与G的所有边关联，因此X是一个顶点覆盖。
证明X的大小不超过最小顶点覆盖Y的大小的2倍。
X的大小是H的2倍
H不大于Y
2025/1/23
k-优算法
7
如果一个最小化问题的近似算法总能找到不超过最优解k倍的可行解，则称这个算法是k-优的。
对于最大化问题，一个k-优近似算法总能找到不小于最优解大小的1/k的可行解。
2025/1/23
最大割集的近似算法
8
把顶点集V划分成两个不相交的子集S和T，称为无向图中的割。顶点分别在两个子集 中的边称为割边，割边的数目称为割的大小。
B＝ “对于输入<G>，这里G是顶点集为V的无向图：
令S＝Ø和T＝V。
如果把一个顶点从S移到T或者从T移到S，使割的大小变大，则做这样的移动，并且重复这一步。
如果不存在这样的顶点，则输出当前的割并且停止。”
2025/1/23

9
：B是最大割集的2-优的多项式近似算法。
证明：
割的大小不超过G的边数，故B是多项式时间的。
证明B输出的割X至少包含G中的所有边的一半。
X的每个顶点的割边>=非割边。
X的所有顶点的割边数和＝ X的割边总数×2。
X的所有顶点的非割边数和＝ X的非割边总数×2。
X的割边数和>= X的非割边数和
X的割边数 >= G的所有边数/2
G的所有边数>=最大割边数
2025/1/23
概率算法
10
概率算法使用随机过程的结果。典型包含一条“扔硬币”的指令，并且扔硬币的结果可能影响算法后面的执行和输出。
01
BPP类
02
素数性
03
只读一次的分支程序
04
2025/1/23