什么是基本运算.docVIP

什么是基本运算？ 什么是算法的时间复杂性（度）？ 什么是算法的渐近时间复杂性？ 表示渐进时间复杂性的三个记号的具体定义是什么？ 什么是最坏情况时间复杂性？什么是平均情况时间复杂性？ 一般认为什么是算法？什么是计算过程？ 算法研究有哪几个主要步骤？主要从哪几个方面评价算法？ 关于多项式时间与指数时间有什么样的结论？ 什么是相互独立的函数序列？何时称函数项μk(x)能被其它函数项线性表出？ 根据特征根的情况，常系数线性递归方程的解有哪几种不同的形式？ 求和中的通项与积分中的被积函数之间有什么样的关系？ 主定理的内容是什么？根据主定理的结论，可以获得哪些关于算法改进的启示？ 分治法的要领是什么？（分治法可分为哪三个主要步骤？） 分治法求最大、最小元算法的主要思想？ 求最大、最小元算法的时间复杂度（比较次数）下界是多少？分治算法在什么情况下可以达到下界？ 如何用分治法求两个n位二进制数x和y的乘积？算法的时间复杂度是多少？ 用200字概括Select（求第k小元）算法的主要思路。 矩阵相乘算法目前最好的时间复杂度是多少？ 叙述Strassen矩阵相乘算法的主要思路和意义。 试用200～300字概述寻找最近点对算法的主要步骤。该算法中有哪几点最为关键？该算法是否可改进？ 做DFT时，是否总假定有n=2m？ 什么是快速傅立叶变换（FFT）？如何用FFT来计算2个多项式的乘积？ 什么是平衡？分治法与平衡有着什么样的关系？ 分治法与动态规划法之间的相同点是什么？不同之处在哪些方面？ 简述求矩阵连乘最少乘法次数的动态规划算法（不超过300字） 能够用动态规划法求解的问题通常具有什么样的特征？ 什么是最长公共子序列问题？在求LCS的算法中，C[i,j]是如何计算的？为什么需要这样计算？ 用200～300字概述求最优二分有哪些信誉好的足球投注网站树算法的主要步骤。算法中有哪几点最为关键？ 有了Tij的根的序号后，如何构造出最优二分有哪些信誉好的足球投注网站树？ Francis Yao的办法为什么会把算法时间复杂度从O(n3)降到O(n2)？ 用200～300字概述二维流水作业调度算法的主要步骤 什么是备忘录方法？它在什么情况下使用较为有效？ 简单不相交集的合并算法中为什么要引进集合的外部名和内部名？ 什么是平摊分析？平摊分析常用的手法有哪几种？简单说明这几种手法的要点。 为什么树结构下执行O(n)条带路径压缩的Union-Find指令只需要O(n*G(n))时间？ 树结构下执行O(n)条带路径压缩的Union-Find指令能否降到线性即O(n)时间？ 用200～300字概述Link(v,r)程序的执行过程。该程序的要点在什么地方？ 你认为脱线MIN算法的关键点在什么地方？ 比较Las Vegas算法和Monte Carlo算法，它们有什么相同和相异之处？随机算法有哪些优点？ 简述随机取数算法和找第k小元素的随机算法。 什么是Sherwood随机化方法？简述Testing String Equality算法的误判率分析。 计算模型RAM与RASP之间有什么相同和相异之处？ Alan Turing是怎样对人类计算过程进行概括的？ Church-Turing Thesis的内容是什么？它有什么意义？ RAM程序、RASP程序与Turing机相互之间的时间复杂度关系是怎样的（考虑两种耗费标准）？ RASP程序如何模拟RAM程序？RAM如何模拟Turing机？ Turing机如何模拟RAM？ Turing机所接受的语言是什么样的语言? 各种语言之间有什么样的关系？ 非确定性Turing机与确定性Turing机的主要区别在什么地方？ 非确定性Turing机的时间复杂度是如何定义的？ Karp多项式规约是如何表述的？它与Cook多项式规约之间的关系如何？ 什么是NP-完全性语言？什么是NP-完全性问题？什么是NP-hard问题？ 引入NP-完全性概念有什么意义？列举20个NP-完全性或NP-hard问题。 什么是多项式时间近似方案（PTAS）？什么是完全多项式时间近似方案（FPTAS，FPAS）？ 什么是伪多项式时间的算法？如何用动态规划法求解背包问题？ NP的假定之下，可以分成哪4类（举例）？(NP-hard问题在P 为什么当k≥2，k背包问题不存在FPTAS，除非P=NP？