1、解释通用图灵机的设计思想，已知每一种图灵机识别一种语言，请问通用图灵机识别
的语言是什么？
2、什么是非确定图灵机？已知 N 是一个非确定图灵机，x 是输入，N（x）=1 代表什么
意思？N（x）=0 呢？
3、已知 SAT 问题是 NP 困难的，3SAT 问题是 SAT 的问题的特例，即每个子句中文字数
不超过 3，请证明 3SAT 问题是 NP 困难的。
4、证明马尔可夫不等式。
5、对于序列（1,2,…,n)进行置换，使得每个不同的序列出现的概率为 1/n！，给出多项
式算法并证明。
6、请解释延迟决策原理。
7、Markov Chain 的转移矩阵为
0 1 0
0 0 1
1 0 0
画出其状态转移图，并求其平稳分布。
8、设 φ = (x2∨ x3) ∧ (¬x2 ∨x3) ∧ (x1 ∨ ¬x3)，各个子句的权重依次是 1、1、3，
请用条件期望的方法来求出一个真值指派，使得总权重最大。
9、对于奖券收集问题，令 X 为收集全所有奖券需要购买的盒子数目，已知 E[X]=nH
n
,请
估计 X>2 nH
n
的概率。
10、最大割问题是指将图分成两部分，使得割开的边最多，一个随机算法如下：
1 设置顶点集 A、B，初始为空集
2 对于一个顶点，独立地以 1/2 的概率放入到集合 A，以 1/2 的概率放入到集合
B
3 返回 A 和 B
请证明此方法割开的边数至少是最优解的一半那么多。
--2020.12.28
附：第 5 题答案
评论0