高级算法

在大二下学期学习了yyt老师主讲的概率论与数理统计，作为拔尖班课程，yyt老师掺杂了很多有关随机算法，组合数学的私货，于是在大三上学期继续修读由yyt老师开设的高级算法。

课程网站：TCS Wiki

Min-cut

一个非常经典的图论模型与算法，笔者在大二上学习了最大流最小割定理，之后学习了解决该问题的随机算法Karger's Algorithm，原理十分简单，只需要有基本的图论与条件概率的知识即可。

这里是一篇讲义，读者可自行参考CS161Lecture16.pdf。

当我们找到了图G的最小割时，图的节点被分为两个互不相交的集合S和T，其中一条边若连接着分别属于这两个集合的顶点，那么这条边就属于当前划分的割。Karger算法将集合S,T视为两个super node。集合内部的边均可收缩，因为对最小割的寻找没有影响。

1
2
3

for (int i=1;i<=n-2;i++) {
	随机选择一条边，合并这两个节点
}

这个算法能够正确输出一个最小割的概率是多少？首先我们要承认以下事实：

[sparsest-cut.pdf]:首先我们参照第一篇讲义学习。实际上这个讲义懒得很…

本章介绍指纹技术，主要介绍随机算法

该算法帮助验证矩阵乘法的正确性

最朴素的方法即根据矩阵乘法的定义，在的时间复杂度内验证，但是通过随机化我们可以在的时间复杂度内验证，并且可以通过多次伯努利的方法实现高概率验证。

Alice有一个比特串记为,Bob有一个比特串记为,要验证两个比特串是否相等，可以将位比特串记为系数为01的多项式，多项式的度数为,在一个大素数的有限域内，随机挑选一个数，若两个多项式的值相等，则比特串有的概率相等。

该算法是单边错的蒙特卡洛算法，若比特串不相等，则多项式值相等当且仅当，度为的多项式至多有个根。

[CS 369M]:课程主页