计算理论导引

《计算理论导引》由会员分享，可在线阅读，更多相关《计算理论导引（7页珍藏版）》请在金锄头文库上搜索。

1、本文格式为Word版，下载可任意编辑计算理论导引 计算理论导引期末复习 东 华 大 学 2022 2022学年第考试试题参考答案 和评分标准 考试学院： 计算机 考试专业： 计算机科学与技术 考试课程名称： 计算理论导引与算法繁杂性 一、单项选择题（每空2分，此题共20分） 1. DFA和NFA的识别在于（B ）。 A、NFA能够识别的语言DFA不确定能够识别 B、对同一个输入串两者的计算过程不同 C、DFA能够识别的语言NFA不确定能够识别 D、NFA比DFA多拥有一个栈 2. 若一个语言A是非正那么的，对于个给定的一个泵长p,若存在一个串s=xyz,|s| p，那么 （ A ）。 A、|y

2、|可能大于等于0 B、xz A C、xyyz A D、|xy|不成能小于等于p 3. 下推自动机与图灵机的不同之处是( B )。 A、下推自动机比图灵机识别的语言多 B、下推自动机比图灵机识别的语言少 C、下推自动机识别的语言是不成判定 D、拥有一个无限的存储带 4. 假设一个语言是图灵可判定的，那么（A ）。 A、对于一个不属于它串s，图灵机计算s时，确定能够到达拒绝状态 B、对于一个不属于它串s，不确定有一个判定器判定s C、对于一个不属于它串s，图灵机计算s时，有可能进入无限循环状态 D、对于一个不属于它串s，图灵机计算s时，确定不会停机 5. 一个集合在条件（ C ）下是不成数的。 A

3、、该集合为无限集合 B、组成该集合的元素是实数 C、该集合的规模大于自然数集合的规模 D、该集合是一个有限的集合 6. 对于一个语言，（ C ）的说法是正确的。 A、假设它属于Turing-recognizable，那么，确定属于EXPTIME B、假设它是NP-hard，那么，确定属于NP C、假设它是NP-complete，那么，确定属于NP D、它确定能被图灵机识别 7. 假设A mB且B是可判定的，那么（A）。 计算理论导引期末复习 A、A也是可判定的 B、A不确定是可判定 C、A是不成判定的 D、A可判定否与B无关 8. 当（A）时，P=NP。 A、语言B是NP完全的且B P B、计

4、算速度快到确定峰值时 C、计算机内存达成无限 D、 计算机性价比很高时 9. 对于SAT问题（ A ）的说法是对的。 A、SAT问题不能用线性时间算法解决 B、SAT PSPACE C、SAT NSPACE D、SAT NP 10 假设B是PSPACE-hard，那么（C）。 A、B NPSPACE B、B P C、B PSPACE D、B确定是NP完全的 二、综合应用题 (10分+10分+10分+10分+10分,此题共50分) 1用5元组形式写出下面状态图对应的自动机。 参考答案： 1.Q =q1, q2, q3, q4, 2. =0,1, 3. is described as 0 1 q1

5、 q1 q1,q2 q2 q3 q3 q3 q4 q4 q4 q4 4. q1 is the start state, and 5. F=q4. 评分标准：5元组每一片面2分 2. 利用泵引理证明下述语言不是上下文无关的。 计算理论导引期末复习 C=aibjck|0 i j k 参考答案： 令p为泵长 令s=apbpcp =uyz， 考虑v和y都含有一种符号和v和y含有一种符号以上符号 先判定uv0xy0z C? 再判定uv2xy2z C? 评分标准：每步2分 3. 证明：实数集合是不成数的。 参考答案：用反证法。假设实数集可数，那么可构造出如下映射： 1 3.14159 2 55.55555

6、 3 0.12345 4 0.50000 x=0. 2 11 1 然后，构造一个实数x，它的第i位小数与 f(i),1 i n 不同，推出冲突。 评分标准：映射5分，实数5分 4.给定一个3cnf公式 =(x1 x1 x2) ( x2 x2)，请把它规约为符合语言VERTEX-COVER要求的图。 参考答案： v10xv11 vv4 x2 v13 v7 x2 v1 v2 x1 x1 x2 1 1 v3 v2 2 6 评分标准：画出上图得10分，画出图，但图上只标x没标出顶点V扣2分。 5.请把上述 规约为符合语言SUBSET-SUM要求的一个表。 计算理论导引期末复习 参考答案： 1 2 c1

7、 c2 c3 Y1 1 0 1 0 0 Z1 1 0 0 1 1 Y2 1 1 0 1 Z2 1 0 1 0 G1 1 0 0 H1 1 0 0 G2 1 0 H2 1 0 G3 1 T 1 1 3 3 3 评分标准：2分 三、完成下述操作（30分） * 1.请根据正那么表达式(0 1)010构造一个NFA,要求写出构造步骤。 参考答案： 计算理论导引期末复习 评分标准：“0”,“1”，“0 1”，“(0 1)”，“010”各1分，“(0 1)010”5分;如 * * 果没按书上的步骤且结果也能表示出该语言，那么酌情给8-3分 2.设计一个判定语言RELPRIME=x,y|x与y互为素数的图灵

8、机，并用大“O”形式写出其时间繁杂度。 参考答案： E=“On input x,y where x and y are natural numbers in binary: 1. Repeat until y=0: 2. Assign x x mod y. 3. Exchange x and y. 4. Output x.” R=“On input x,y where x and y are natural numbers in binary: 1. Run E on x,y. 2. If the result is 1, accept. Otherwise, reject.” 时间繁杂度O(n) 评分标准：写出E得5分，写出R和O(n)得5分； 假设只写出一个图灵机且步骤完整，能正确运行，且时间繁杂度合理，那么也可得10分；其他处境根据所写的图灵机酌情给8-3分。 3. 以你熟谙的形式写出一个解决团问题的算法，并用大“O”形式写出其时间繁杂度和空间繁杂度。 此题为个人发挥题，没有固定答案。 评分标准：1）算法书写模范易懂得2分； 2）算法书写模范易懂且正确得6分； 3）算法书写模范易懂、正确，时间繁杂度和空间繁杂度正确得10分； 7