2011年计算机科学与技术基础

NJU2025 年计算机科学与技术基础试卷与答案科目名称:计算机科学与技术基础一、（10 分)我们有下列两个问题,并已有各自的算法:1。 已知等腰三角形各边长,求高.2. 已知直角三角形的任意两边长，求第三边的长度。利用这两个问题解释多项式时间规约的概念，并说明多项式时间规约在计算机算法理论中的作用。NP 问 题 的 全 称 是 ： Non deterministic Ploynomial 问 题 , 即 非 确 定 性 多 项 式 问 题 . 多 项 式 时 间（Polynomial time）在计算复杂度理论中，指的是一个问题的计算时间 m(n)不大于问题大小 n 的多项式倍数。答案参考:http：//blog。csdn.net/yanghangjun/article/details/7298798等腰三角形可分解成对称的两个直角三角形，问题 2 的答案可用于解决问题 1。因此问题 2 若能在多项式时间内解决，则问题 1 也能在多项式时间内解决。（多项式时间归约 假定给了两个问题类 q 和 q0,假如存在一个确定型图灵机 Mq和一个多项式 P，对于 q 中任意一个实例 x,Mq都能在 P（n）时间内计算出 q0中一个实例 y（其中 n 是实例 x 的编码长度),使得 x q 中有肯定回答的实例，当且仅当 y 是 q0中有肯定回答的实例，我们就说 q 多项式时间归约到 q0 )多项式时间规约对于讨论 NP，NP 完全问题具有重大作用.对于一个规模为 n 的输入，在最坏情况下的运行时间是，其中 k 是某一确定的常数，即称时间负责度为的算法为多项式时间算法。一般来说，在多项式时间内可解的问题是易处理的问题，在超过多项式时间内解决的问题是不易处理的问题。不能够这样限制时间复杂度的算法被称为指数时间算法。例如，时间 复 杂 度 为 O(nlog （ n) ） 、 O （ n^3 ） 的 算 法 都 是 多 项 式 时 间 算 法 ， 时 间 复 杂 度 为O(n^log(n）)、O（n！)、O(2^n）的算法是指时间算法。计算复杂性理论所讨论的资源中最常见的是时间(要通过多少步演算才能解决问题）和空间（在解决问题时需要多少内存）。其他资源亦可考虑，例如在并行计算中，需要多少并行处理器才能解决问题。时间复杂度是指在计算机科学与工程领域完成一个算法所需要的时间，是衡量一个算法优劣的重要参数。时间复杂度越小，说明该算法效率越高，则该算法越有价值.空间复杂度是指计算机科学领域完成一个算法所需要占用的存储空间，一般是输入参数的函数。它是算法优劣的重要度量指标，一般来说，...