复杂性理论测试
判断题
2.停机问题是不可判定的，无法用任何算法求解。1
3.素数问题PRIME是典型的NP问题而非P问题。1
4.时间复杂度函数n(n-1)/2∈Θ(n^3)and∈Ω(n^2).0
5.超越多项式时间复杂度的精确算法一般是不可接受的。1
6.递归算法的简洁性可能会掩盖它的低效率。0
7.只要解决NPC中的任何一个问题，即找到其多项式求解算法， 那么所有的NP问题都能得到解决。1
8.所有的语言构成的集合不可数，因此语言的个数比TM个数多，因此一定有TM无法识别的语言。1
9.如果一个算法不能用图灵机来描述，也必定不能在一台物理机上实现；反之如果一个算法能在一台物理机上实现，也必定可以用图灵机来描述。1
10.任何一个多带TM都等价于某个单带TM。1
单选题20’
1.下列不属于NPC问题的是
旅行商问题 顶点覆盖问题 \2SAT** 完全子图问题
2.下列不属于算法特性的是
正确性 一般性 高效性 \简洁性**
3.如果P≠NP，下列说法不正确的是
NPC是NP层面比较难的问题 NPC∈NP
NP hard问题比NP难 NPC∈NP hard
4.下列关于算法复杂性理论说法不正确的是
算法理论其目标是寻找某个问题的最佳算法
复杂性理论关心求解问题所需资源的下界
复杂性理论是密码学的基础
\复杂性理论证明某个问题不能有效求解，则该问题没什么意义和价值**
5.下列断言为假的是
n(n+1)/2∈O(n^3） n(n+1)/2∈O(n^2）
\n(n+1)/2∈Θ****(****n^3****)** n(n+1)/2∈Ω(n)
\6. 下列关于算法效率分析说法不正确的是
A、最优效率分析运远不如最差效率分析重要.
B、平均效率的分析比最差效率和最优效率的分析难很多
C、\可以用最差效率和最优效率的平均数方法来求平均效率**
D、如展一个算法的最优效率不能满足要求，则可以抛弃
7.在计算复杂性理论中，将所有在多项式时间内可求解的问题和可验证的问题分别称之为
NP和NPC问题 \P****问题和N****P****问题**
NP问题和P问题 NPC问题和P问题
8.下列属于P问题的是
\P****ATH****问题** HAMPATH问题 3-COLOR问题 CLIQUE问题
9.关于归约的说法不正确的是
归约的过程只有用多项式时间完成才有意义
问题A可归约为问题B，说明问题A不比问题B难
归约之间存在传递性
\S****AT****是N****PC****问题，如果一个问题可以归约到S****AT****，则该问题必定是N****PC**
10.下列说法不正确的是
图灵是计算机理论之父和人工智能之父
\图灵命题已被证明是定理**
图灵测试奠定了人工智能的基础
图灵机是冯诺依曼设计的物理机器的基础
简答题25’
1.是否可以写出一个程序来判断另一个程序停机？
不能，
2.如何从图灵机角度看待算法的时间复杂度和空间复杂度？
步数和方格数
3.实际应用中如何判定一个问题是NPC问题？第一个NPC问题是怎么发现的？
是否是NP问题，已知NPC问题是否能归约到它；
1971年库克教授在论文中提出了第一个NPC问题并给出了证明。这使得世人知道了这类NPC问题是真的存在的。库克教授给出的这第一个NPC问题叫做“SAT问题”，又称作“可满足性问题”，英文为“The Satisfiability Problem”，SAT是Satisfiability单词的前三个字母。“SAT问题是一个NPC问题”这个结论被称作库克定理
4.算法提升的本质是什么？提升算法效率的方法有哪些？
效率；减少数据冗余，优化循环、减少嵌套，避免大量使用递归；
5.谈谈你对计算复杂性理论的认识，并举一个简单的安全或有关的实例说明。
1.算法设计的重要性：计算复杂性理论告诉我们，并非所有的问题都可以通过高效的算法解决。对于某些问题，可能不存在多项式时间内解决它们的算法。因此，在学习算法设计和问题求解时，需要考虑问题的复杂性，并寻找合适的算法来解决。
2.问题的可证明性：计算复杂性理论研究问题的难解性和可解性，它提供了一种形式化的框架来研究问题是否可以在有效的时间内解决。这启发我们思考问题的本质和边界，以及寻找问题的可证明性和难解性。
3.理论与实践的结合：计算复杂性理论不仅仅关注问题的理论分析，还与实际问题密切相关。它为算法设计和问题求解提供了基本的指导原则和方法。通过理解计算复杂性理论，我们可以更好地理解和设计高效的算法，提高计算问题的解决效率。
4.密码学和安全性的研究：计算复杂性理论对密码学和安全性的研究有重要的影响。它提供了分析密码算法安全性的工具和方法，帮助我们设计和评估安全的加密算法
综合分析题20’
1.证明定理：如果t1(n)∈O(g1(n))并且t2(n)∈O(g2(n))，则t1(n)+ t2(n)∈O(max{ g1(n), g2(n)})
定义法；
2.写出将十进制正整数转换为二进制的标准算法。
a.用伪代码描述该算法。
b.分析算法时间复杂度。
1 | M=[] |
3.设计一个图灵机M，使之接受语言L={w#w | w∈(0,1)*}，画出L（M）的状态转移图，并用简单实例进行验证。
