计算理论2022期末（哈工大）
一、请回答关于图灵机的问题。(15 分)
- 确定图灵机的形式化定义是什么？
- 不确定图灵机和确定图灵机的区别是什么？
二、请回答设计图灵机相关的问题（画出状态转移图即可）。（15 分）
- 构造确定图灵机识别语言 L={0m1
n
| m>=0, n>0}。 - 构造确定图灵机识别语言 L={0n1
n
| n>0}。 - 构造图灵机识别所有包含 101 且不包含 111 的“01”字符串构成的语言。
三、问答题。（25 分）
- 什么是 NP 完全问题？
- 什么是莱斯（Rice）定理？
- 什么是丘奇-图灵命题（Church-Turing Thesis）？
- 可判定问题与不可判定问题的区别是什么？
- 什么是萨维奇（Savitch）定理？
四、证明题。（25 分）
- 如果 L 是递归语言，那么¬L 也是递归语言。
- 最大团问题：给定一个图 G=(V,E) 和一个整数 K，判断图 G 是否包含一个至少有 K 个节点的
完全图。证明最大团问题是 NP 完全问题。
3.语言 L 定义为 L={⟨𝐌⟩|𝐌是一个接受𝟏𝟎𝟏的图灵机}，其中⟨𝐌⟩表示图灵机 M 的编码字
符串。证明 L 是不可判定的。
五、解答题。（20 分）
（1）考虑一个 3SAT 问题的变形 MSAT：每个子句最多有 3 个变量，且每个子句至
少包含一个“否定变量”（形如 x）。MSAT 问题是否是 NP 完全问题，给出原因。
（2）图的 3 可着色问题：给定无向图 G=(V, E)，利用红、黄、蓝三种颜色对 V 中的
顶点着色，问是否存在一个着色方案使得任意相连的两点都是不同的颜色（即对任意
E 中的边(u,v)，u 和 v 的颜色不同）？请证明图的 3 可着色问题是 NP 完全问题文章来源地址https://www.toymoban.com/news/detail-495216.html
文章来源：https://www.toymoban.com/news/detail-495216.html
到了这里，关于计算理论期末2022哈工大的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
