什么是基本运算.doc

什么是基本运算？
什么是算法的时间复杂性（度）？
什么是算法的渐近时间复杂性？
表示渐进时间复杂性的三个记号的具体定义是什么？
什么是最坏情况时间复杂性？什么是平均情况时间复杂性？
一般认为什么是算法？什么是计算过程？
算法研究有哪几个主要步骤？主要从哪几个方面评价算法？
关于多项式时间与指数时间有什么样的结论？
什么是相互独立的函数序列？何时称函数项μ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？