山东大学软件学院2020年硕士随机算法考题 - CSDN文库

山东大学软件学院

需积分: 49 163 浏览量更新于2023-05-03 评论 1 收藏 146KB DOCX 举报

身份认证购VIP最低享 7 折!

领优惠券(最高得80元）

资源详情

资源评论

资源推荐

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 题答案

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余1页未读，立即下载

评论0

qq_40422851

粉丝: 15
资源: 7

会员权益专享

图片转文字

全年可省5，000元立即开通

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈