哈工程计算理论历年真题解析与复习指南

"哈工程计算理论期末考试真题集，包含2007年至2019年的试题，缺少2015年的资料。重点复习这些题目有助于取得好成绩，如想拿到60分以上，熟记真题是关键；80分以上需深入理解；90分以上则需要对计算理论有深入计算和理解。" 本文将详细讨论计算理论的一些核心概念，主要基于提供的试题摘要。 一、填空题 1. 正则表达式(01+)∗表示的是所有0后面至少跟着一个1的字符串集合。 2. 上下文无关文法A→0A1|ε描述了语言{0n1n|n≥0}，即n个0后跟着n个1的字符串序列。 3. 转移函数描述了图灵机的工作，若δ(qi,b)=(qj,c,L)，则格局uaqibv可以转换为uqjacv。 4. 自动机理论中，ANFA（有穷自动机）可以决定某些特定的语言，但并非所有语言。 5. 映射可归约性是计算复杂性理论中的概念，如果A可以通过计算函数f映射到B，则A可归约到B。 6. 多项式时间算法的验证意味着每一步都在多项式时间内完成，适用于确定型图灵机。 7. 对于时间复杂度，一个t(n)时间的多带图灵机可以被一个O(t²(n))时间的单带图灵机等效模拟。 8. NL完全的语言B同时属于NL并能接收通过数空间归约的所有NL语言。 9. 图灵机在更广阔的空间或时间复杂度下，理论上可以解决更多问题，但这并不意味着所有问题是可解的。 二、简答题 1. 题目不清晰，通常会涉及算法或计算理论的基本概念。 2. 递归引理和self-reducibility是计算理论的重要概念，前者允许构造递归函数，后者涉及问题自我简化的过程。 3. 圆率算法（如AKS素数测试）通常关注于高效判断一个数字是否为素数。 三、构造题 1. 未给出具体语言的FA构造，通常要求设计能识别特定语言的有穷自动机。 2. PDA构造题目的语言也不明确，PDA用于识别上下文无关语言。 3. TMM（图灵机）构造题，要求构建一个判定语言{w|w具有相同数量的0和1}的机器。 四、证明题 1. INFINITEPDA的可判定性证明涉及证明对于识别无限语言的PDA集合，存在一个能判断其是否无限的图灵机。 2. EQCFG的不可判定性证明表明无法存在一个通用算法来判断两个上下文无关文法是否生成相同的语言。 3. 证明VERTEX-COVER是NP完全的，意味着它是NP问题中最难的一类，需要证明其难度不低于其他任何NP问题。 4. 题目不清晰，可能要求证明某个语言或问题的性质。 总结，计算理论涵盖了正则表达式、上下文无关文法、图灵机、计算复杂性理论等多个领域。通过理解这些概念及其相互关系，可以更好地应对计算理论的期末考试。