组合，概率与计算专栏

专栏简介

记录了一些与概率论结合的算法。本专栏难度较大，如有理解不精的地方，请多包涵~

专栏目录

专题：超图

注：本专题参考Morris讲义.定理即定义编号与讲义一致.

• 第一节：当你的一阶矩方法失效时，该怎么办？—随机图的无三角形子图问题
• 第二节：更一般的容器定理
• 第三节：容器定理应用进阶
• 工具：Chernoff不等式
• 第四节：用容器定理测试图的性质
  参考论文链接

专题：马尔科夫链与随机游走

注：本专题参考Michael Mitzenmacher书第七章，部分定理即定义沿用书中编号

• 第一节：Definitions and Representations
  • 应用案例1：2-SAT问题
  • 应用案例2：3-SAT问题
• 第二节： Classification of states & 第三节： Stationary Distributions
• 第四节：Random walks on Undirected Graphs

参考资料

• Probability and Computing by Michael Mitzenmacher & Eli Upfal