可计算与计算复杂度-题目
编辑1.构造计算f(x) = 2x 的图灵机，其中的数字x 用 x 个1表示。
字母表加上特殊标记
字母表：{1, *}
q1 B R q2 进入计算
q2 1 * q3 找到左侧1，将其标记
q3 1 R q3 右移找尾
q3 * R q3
q3 B * q4 找到最后一个1后将空白变为*
q4 * L q4
q4 1 L q5
q5 1 L q5
q5 * R q2
q4 B R q6
q6 * 1 q7
q7 1 R q6
字母表无特殊标记
q1 B R q2 进入计算
q2 1 R q2 右移找尾
q2 B R q3 找到初始输入尾部的空白
q3 1 R q3
q3 B 1 q4 找到空白后第一个位置改成1
q4 1 R q4 找到下一个位置
q4 B 1 q5 将下一个位置改成1，进入回头状态
q5 1 L q5
q5 B L q6 回头找到空格
q6 1 L q6
q6 B R q7 找到最左侧空格的下一个1
q7 1 B q1
2. 证明不存在具有如下功能的程序：对任意程序X和输入Y，该程序能判断程序X输入Y时是否会在屏幕上打印字符A。
假设存在程序H ，判断给定的程序X 和输入Y 是否会在屏幕上打印字符 A。
构造程序G，输入是一个程序X。$G(X)$ 会调用H(X,X)，即判断程序X 是否会在输入X 时打印字符 A。
考虑G(G) 的行为:
如果H(G,G)=1，那么根据程序G 的定义，程序G 应该进入无限循环，不打印任何字符。然而，这与H(G,G)=1 相矛盾（因为如果H(G,G) =1，它表明G 会打印字符 A）。
如果H(G,G) = 0，那么程序G 会打印字符 A。但这也与H(G,G)=0 矛盾，因为它意味着程序 G 不会打印字符 A。
推出矛盾，因此不存在具有如下功能的程序：对任意程序X和输入Y，该程序能判断程序X输入Y时是否会在屏幕上打印字符A。
3. 证明3-SAT\le _{p} Subset-Sum (子集和)
4. 描述子集和问题的动态规划算法，并分析其计算复杂度
子集和问题描述：
给定一个整数集合 S = {s_1, s_2, ..., s_n} 和一个目标值 T，我们需要判断是否可以从集合 S 中选择一些元素，使得这些元素的和等于 T。
动态规划求解子集和问题的思路：
状态定义： 定义
dp[i][j]表示使用前i个元素是否能够构成和为j的子集。dp[i][j] = true，表示前i个元素可以构成和为j的子集。dp[i][j] = false，表示前i个元素不能构成和为j的子集。
状态转移方程：
如果不选择第
i个元素，那么dp[i][j] = dp[i-1][j]。如果选择第
i个元素，那么dp[i][j] = dp[i-1][j-s[i]]，前提是j大于等于s[i]。
因此，状态转移方程为：
dpi=dpi−1 or dpi−1]dpi = dpi-1 \, \text{or} \, dpi-1]
边界条件：
dp[0][0] = true，表示空集合和为0。dp[i][0] = true，表示任何子集都可以形成和为0。dp[0][j] = false对于所有j > 0，表示没有元素时不能形成非零的和。
结果：
最终的结果是
dp[n][T]，表示是否可以从集合S中选出一些元素使得和为T。
动态规划的伪代码：
function subsetSum(S, T):
n = length(S)
// 创建一个二维数组 dp，大小为 (n+1) x (T+1)
dp = array of size (n+1) x (T+1)
// 初始化边界条件
for i = 0 to n:
dp[i][0] = true // 和为 0 总是可以通过选择空集实现
for j = 1 to T:
dp[0][j] = false // 对于非零目标和，空集无法实现
// 填充 dp 数组
for i = 1 to n:
for j = 1 to T:
if S[i-1] > j:
dp[i][j] = dp[i-1][j] // 当前元素大于目标和，不能选择
else:
dp[i][j] = dp[i-1][j] or dp[i-1][j-S[i-1]] // 选择或不选择当前元素
return dp[n][T]时间复杂度分析：
数组
dp的大小是(n+1) x (T+1)，因此总共有(n+1) * (T+1)个元素。每个元素的填充需要常数时间（即
O(1)），所以总体的时间复杂度为O(n * T)。
空间复杂度分析：
我们使用了一个大小为
(n+1) x (T+1)的二维数组来保存状态，因此空间复杂度是O(n * T)。
C++ 实现
#include <iostream>
#include <vector>
using namespace std;
bool subsetSum(const vector<int>& S, int T) {
int n = S.size();
// 创建二维 dp 数组，dp[i][j] 表示前 i 个元素是否能组成和为 j
vector<vector<bool>> dp(n + 1, vector<bool>(T + 1, false));
// 初始化边界条件
for (int i = 0; i <= n; ++i) {
dp[i][0] = true; // 和为 0 总是可以通过选择空集实现
}
// 填充 dp 数组
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= T; ++j) {
if (S[i - 1] > j) {
dp[i][j] = dp[i - 1][j]; // 当前元素大于目标和，不能选择
} else {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - S[i - 1]]; // 选择或不选择当前元素
}
}
}
return dp[n][T];
}
int main() {
vector<int> S = {3, 34, 4, 12, 5, 2}; // 示例集合
int T = 9; // 目标和
if (subsetSum(S, T)) {
cout << "There is a subset with the given sum.\n";
} else {
cout << "No subset with the given sum.\n";
}
return 0;
}说明：
subsetSum函数使用动态规划求解子集和问题，返回true如果存在和为T的子集，false否则。在
main函数中，示例集合为{3, 34, 4, 12, 5, 2}，目标和为9，输出结果为There is a subset with the given sum.，因为子集{4, 5}的和为9。
结论：
通过动态规划，可以有效地解决子集和问题，时间复杂度为 O(n * T)，空间复杂度为 O(n * T)。
- 0
- 0
-
分享