说明:双击或选中下面任意单词,将显示该词的音标、读音、翻译等;选中中文或多个词,将显示翻译。
您的位置:首页 -> 词典 -> 非确定性数据查询
1)  Uncertain Data Queries
非确定性数据查询
2)  Uncertainty query
非确定性查询
3)  uncertain data
非确定性数据
1.
On handling NULL values in uncertain database;
非确定性数据库中空值处理
4)  uncertain databases
非确定性数据库
5)  data-definition query
数据定义查询
6)  uncertain data structure
非确定性数据结构
补充资料:非确定性
      理论计算机科学中的一个重要概念。各种计算机器模型(自动机),在每一时刻,根据当时的状态和输入,若机器的动作可唯一确定时,则称机器为确定性的;若有多个动作可供选择时,则称机器为非确定性的。任意一种自动机,按其动作的确定程度,大体可分为确定的和非确定的两类。在对非确定性的研究中,一个核心课题就是非确定性能否增加机器的计算能力。具体说,对同一类自动机,确定型和非确定型机器在计算能力方面有没有区别?是什么关系?这类问题因其在理论上和实践中的重要意义而受到普遍重视。其中有些问题至今尚未解决,成为理论计算机科学中重要的悬案,NP=?P问题就是一个突出的例子。
  
  一个单带图灵机,由一个有限控制器、一条输入带和相应的读写头组成。图灵机的动作是由有限控制器的状态和读写头扫视方格中的符号,依一定规则来定的。每一动作包括:改变机器的状态;在读写头扫视的方格中打印一个符号,以代替原来的符号;读写头向左或向右移一个方格。对于给定的状态和读写头读到的符号,图灵机的下一动作可能是唯一确定的,也可能有有穷多个动作可供选择。如果对于任何状态-符号对,下一动作都是唯一的,这种机器称为确定型单带图灵机;如果有有穷多个(包括零个或一个的情形)可以任意选择的下一动作,且规定对于给定的输入,只要在所有可能的动作序列中有一个序列导致接受状态,机器就接受其输入,这种机器就称为非确定型单带图灵机。对于确定型和非确定型的其他类型自动机,均可以类似地给出定义。
  
  对于同一类型的自动机,确定型可以看作是非确定型的特殊情形。因此,非确定型的计算能力一般说应比确定型的强。然而是否真强,则取决于所讨论的自动机的类型。从自动机接受语言(见形式语言理论)的能力来说,对于有限自动机,确定型机器和非确定型机器接受的语言类完全一样,都是正规集合。对于下推自动机,确定型机器接受的语言类(确定的上下文无关语言)是非确定型机器接受的语言类(上下文无关语言)的真子类。例如,L={0i1j2k|i=j或j=κ}就是一个属于后者而不属于前者的语言。对于线性有界自动机,确定型机器和非确定型机器接受能力是否相等的问题,至今尚未解决,这就是著名的"LBA问题"。对于图灵机,已经证明确定机器与非确定机器具有相同的接受能力,它们所接受的语言类都是递归可枚举集合。
  
  在计算复杂性理论中不仅考虑能不能计算的问题,还考虑计算时耗费资源(时间、空间等)的数量。在图灵机的情况下,如考虑资源界限,则对计算能力问题的回答便不一样。例如,当考虑多项式空间界限时,确定型图灵机接受的语言类PSPACE和非确定型图灵机接受的语言类 NPSPACE是相同的。而当考虑多项式时间界限时,就产生了著名的"NP=?P问题"。
  
  NP=?P问题  确定型图灵机在多项式时间内接受的语言所组成的类,记作P;非确定型图灵机在多项式时间内接受的语言所组成的类,记作NP。后者包含前者,但两者是否相同这个问题至今仍未解决。
  
  关于NP=?P问题的研究,大体有四方面工作:借助归约方法进行的NP完全性理论的研究;借助ORACLE(橡树岭自动计算机和逻辑机)进行的相对化语言类的研究;结合各种语言时间(空间)复杂性类进行的研究;细分非确定性、可证明 NP和P等其他方面的研究。在研究过程中,有人试图证明NP=P;更多的则猜测并力图证明NPP。有越来越多的人趋向于认为:NP=?P问题是独立于公理系统的,即在通常的公理化系统中,既不能证明NP=P,也不能否证它。
  
  这个问题的研究,在理论和实践两个方面都具有重要意义。从理论上说,它使人们对非确定性这样一个重要概念的本质,有了越来越深的认识。同时,随着NP=?P问题研究的深入,引出了许多新的理论问题,它们都程度不同地和NP=?P问题相关。一旦NP=?P问题获得解决,就会导致一系列理论问题的解决。
  
  其次,实践中的大量问题不是属于 P,就是属于NP。尽管图灵机能解决的问题都是可计算的,但普遍认为,只有属于 P的问题才是在计算机上现实可计算的。需要指数时间的问题虽然可计算,但因需要太多的时间,以致不被认为是现实可计算的。NP=?P问题就成为直接关系到NP中相当一批实际问题是否是"现实可计算的"这样一个大问题。实际上,若NP=P,那么NP中一切问题都是现实可计算的;但若NP厵P,NP中就将会有一批实际问题不是现实可计算的。
  

说明:补充资料仅用于学习参考,请勿用于其它任何用途。
参考词条