特殊形式和结构的MSP问题NP完全性研究

针对一个NP完全问题,即MSP问题,研究其问题的结构性质,猜想特殊的结构可以使其算法证明得到简化.以简化证明为导引,提出一种特殊形式和结构的MSP问题.而约束了形状的特殊形式和结构的MSP问题如果不具备NP完全性,会极大影响进一步简化算法证明的研究意义.因此,提出的特殊形式和结构的MSP问题进行了NP完全性质证明.类比对SAT问题开展研究时,同样开展特殊结构的2-SAT问题、3-SAT问题、k-SAT、max-SAT问题研究,特殊形式和结构的MSP问题同样具有重要意义,并进一步推动原问题的研究.     

MSP问题NP完全性研究

针对文献[1,2]提出的MSP问题,研究了MSP问题与着色问题、子图同构问题的对应关系,揭示了MSP问题所反映的NP完全问题的共性;分析了MSP问题的相变现象,为文献[1,2]提出的多项式时间算法框架的测试提供了难例产生方法。     

TMS与一般逻辑程序的语义等价性

1.稳固模型和良构指派 首先假定读者已熟悉有关逻辑程序设计的最基本概念,有关详细论述请参阅[3]。 定义1.设P是一Horn逻辑程序(简称Horn程序),B_P是P的Herbrand域.T_P是一从解释I到另一解释T_P(I)的映射,定义为: T_P(I)={A∈B_P|存在P中某子句的实例代换A←A_1,…,A_n,使得{A_1,…,A_n}I}     

进程创建的语义及等价性

针对一个基于共享变量的带有进程创建的命令式语言,用变迁系统描述了它的结构操作语义,并用扩展的状态变迁迹模型定义了它的指称语义,在该模型下,状态变迁被区分为两种不同形式,分别表示发生在原进程和被创建进程中的状态变迁,这样便可以定义适当的语义复合运算,在对命令的指称进行复合时根据变迁类型的不同对变迁迹进行串行或交错连接,恰当地反映了进程的并发运行受创建命令在程序中的相对位置的限制,最后证明了这两个语义     

d-正则(k,s)-SAT问题的NP完全性

研究具有正则结构的SAT问题是否是NP完全问题,具有重要的理论价值.(k,s)-CNF公式类和正则(k,s)-CNF公式类已被证明存在一个临界函数f(k),使得当s≤f(k)时,所有实例都可满足;当s≥f(k)+1时,对应的SAT问题是NP完全问题.研究具有更强正则约束的d-正则(k,s)-SAT问题,其要求实例中每个变元的正负出现次数之差不超过给定的自然数d.通过设计一种多项式时间的归约方法,证明d-正则(k,s)-SAT问题存在一个临界函数f(k,d),使得当s≤f(k,d)时,所有实例都可满足;当s≥f(k,d)+1时,d-正则(k,s)-SAT问题是NP完全问题.这种多项式时间的归约变换方法通过添加新的变元和新的子句,可以更改公式的子句约束密度,并约束每个变元正负出现次数的差值.这进一步说明,只用子句约束密度不足以刻画CNF公式结构的特点,对临界函数f(k,d)的研究有助于在更强正则约束条件下构造难解实例.     

线性阈值单元神经元网络的图灵等价性

关于神经元网络计算能力，其奠基人即认为神经元网络与图灵机等价，１９９１年，孙等给出出了其与图灵机等价的一个构造性证明，只是他们的网络是完全联结的、二阶权的回归式网络，与一般讲的神经元网络不同，本文则给出了用线阈值单元构成的神经元网络去计算部分递归函数的构造性证明，由于部分递归函数与图灵机等价，从而这样的神经元网络与图灵机等价。     

多出口petri网与petri网的等价性

1.引言 为了便于描述程序的控制结构,文[1,2]引入了多出口Petri网的概念,并指出,在一定意义下,多出口Petri网与一般Petri网是等价的。本文旨在从理论上讨论这两个概念的等价性,并给出严格的证明。     

基于等价类和最大完全图集聚类的关联规则发现算法

关联规则的发现是数据挖掘中的一个重要问题,本文提供了一个基于等价类和最大完全图集聚类的关联规则的发现算法。     

分布式计算中稳定性质的等价类划分

分布式计算中的稳定性质是那些在计算中一旦成立将保持成立的性质，如分布式死锁、分布式终止和分布式废码等，稳定性质检测是分布式计算中计算中的重要问题，常通过构造一致全局系统状态来检测稳定性质。     

D—时刻表的求解算法

在文[1]中,我们提出了时间关系约束的关系矩阵表示法,本文是文[1]的继续.在给定的时间关系以及时间宽度的约束条件下,求同时满足这两个约束条件的时刻表,称为D-时刻表.文中讨论了D-时刻表、最优D-时刻表的求解方法以及它的计算复杂性.     

基于超图的求等价属性集算法研究

本文讨论了有关等价属性集的一些性质，提出了准等价属性集和基本等价属性集的概念。在此基础上给出了一种求等价属性集的算法。     

一种基于等价的联盟演化机制

联盟是多Ａｇｅｎｔ之间一种重要的合作方法,多数方法没有考虑联盟的演化问题,难以避免大量的计算,而且对于联盟值是已知的假设也是不实际的,文中给出了联盟问题的等价性和相应的联盟演化机制,不通过对联盟值预先计算,可求得联盟问题的解,可以降低计算复杂度,与Ｓｈｅｈｏｒｙ ＆ Ｋｒａｕｓ的工作相比引入了联盟的等价和演化,放松了对联盟值已知的假设限制。     

EQUIVALENCE CLASSES: TOWARD MORE EFFICIENT SEARCH

This paper describes a simple technique for applying Known Ciphertext Attack to a certain class of cryptosystems. The feature of the class that the technique exploits is that the ciphertext characters depend only on small portions of the key and a single plaintext character. After deriving a preferential list of locations to start the search, the keyspace is attacked piecemeal in the locations most likely to lead to confirmation or contradiction. By ordering the list of search locations, the attack is made more efficient.     

键位相关速度当量的研究

本文从二百多万个实验数据中统计分析出通用小键盘连续击键键位相关速度当量矩阵。键位相关速度当量表是优化汉字键盘输入键位设计的人机工程基础据, 也为自动浏定汉字键盘输入方法速度素质提供了科学依据。本文还介绍了采集数上述数据的实验设计原理和数据处理所采用的方法。     

一种紧凑式编码表的设计方法

本文提出了一种紧凑式编码表的设计方案。在设计数据库时，通过整理不同编码长度的属性项，将其放在有限的几个根据编码长度设计的表中。实践证明，这种设计方法可以大大减少数据库中用户表的数量，同时不影响效率，是一种可以推广的编码表设计方法。     

泛表的构造及与限制关系表达式的关系

在本文中提出了泛表的新概念，讨论了泛表的性质，构造一个泛表的规则，详细分析和研究了泛表和限制关系表达式之间的关系。     

数字设计中基于图的状态等价类集生成算法

在完全确定状态的时序电路、状态机等数字系统设计中,确定全部状态等价类,是进行最优状态化简的前提.结合图论理论提出一种等价类集生成算法,首先建立等价类与图中连通分支的联系,然后给出了通过化简图的邻接矩阵而得到等价类集的方法.算法易于编程实现,适合那些状态完全确定的包含几十、上百甚至更多初始状态的大规模数字系统设计.