A Clas of Distributed Recognition Algorithms for Acyclic Database Schemes

各种非环的数据库模式有许多好的性质，特别是在分布式环境中，研究关系数据库的非环性程度是一个重要的课题．对Ａｌｐｈａ，Ｂｅｔａ，Ｇａｍｍａ，Ｂｅｒｇｅ这几种非环数据库模式，我们给出一组分布式算法．该算法的最坏消息复杂度是Ｏ（｜Ｎ｜２），而最坏时间复杂度是Ｏ（｜Ｎ｜２），其中｜Ｎ｜是给定的网络中结点的个数．     

一个约简非环数据库模式的算法

利用数据库模式与超图的对应关系，将对数据库的讨论转化为对超图的讨论，设Ｈ＝｛Ｎ，Ｅ｝是θ非环超图，ｓ是Ｎ的一个子集，给出了一个根据ｓ约简超图Ｈ的算法ＮＭＣ［Ｈ，Ｓ，ＤＣ（Ｈ）］＼算法的输出仍是θ非坏的，且ＤＣ（Ｈ）中任何一个结点都是非冗余点，并证明了算法的时间复杂度为Ｏ（｜Ｎ｜．｜Ｅ｜＾２）。     

用线图模型在分部式环境中识别数据库模式的四种非环性

介绍一个在分部式环境下,用线图模型识别数据库模式的四种常见非环性（即,Ａｌｐｈａ,Ｂｅｔａ,Ｇａｍｍａ,Ｂｅｒｇｅ非环性）的算法ＤＰＲＥ,并证明该算法的最坏消息复杂度为Ｏ（｜Ｅ｜）,其中｜Ｅ｜表示数据库中有公共属性的关系对之总数．     

关系模式的BCNF分解的一种新方法

传统的关系模式的BCNF分解算法必须判断“一个关系模式是否为BCNF”,该判断是一个NP-完全问题,因此传统算法缺乏实用性.本文避免这一判断,给出一个关系模式的BCNF分解的新算法,它的时间复杂性是O(kn~2)级的,其中n为模式中的属性个数,K为产生的模式个数.     

二部图最大匹配的快速动态优化算法

建立了二部图C=（V，U，E）的二级优先匹配规则，在此规则下，用改进的深度优先搜索对匹配算法进行改进，使得算法能够根据连通分量的个数动态优化算法的性能，使动态最大匹配算法的时间复杂度提高到0（max（｜V｜，｜E｜，m｜E｜））．     

粗糙集高效遗传约简算法

提出了简化差别函数的概念及其算法，简化差别函数不仅具有与决策表相同的决策能力，而且剔除了由决策表导出的原始差别函数中的重复项和冗余项．为了降低遗传约简算法适应度函数的搜索空间，有效提高计算速度，又提出了一种高效遗传约简算法，其将染色体时简化差别函数的覆盖度以及染色体中包含1的个数作为适应度函数的参数，从而保证了算法朝着最小约简收敛，并从理论上证明了算法的属性约简结果为最优，算法的时间复杂度为O（｜f′｜｜｜C｜｜U｜^2）,同时，通过4个实例对算法进行了验证，结果表明简化差别函数的项分别为原来的0．39％、0．0008％、0．00008％和0．0003%，且在500代以内能够获得最小属性约简．     

特殊射影线性群PSL(2,q)的类方程分解

群的元素间的共轭关系是等价关系,于是群G的所有元按共轭关系可分为若干个互不相交的共轭类Ｃ１＝｛e｝,C２,…,Ｃk,并且有Ｇ＝Ｃ１∪Ｃ２∪…∪Ｃk,称｜Ｇ｜＝｜Ｃ１｜＋｜Ｃ２｜＋…＋｜Ｃk｜为群G的类方程,k称为G的类数,共轭类Ci包含的元素个数｜Ci｜叫做Ci的长度.作者对求出特殊射影线性群PSL(2,q)的类方程的算法进行了讨论,最后得到了一些群的类方程.     

识别非环的数据库模式的一组分布式算法

各种非环的数据库模式有许多好的性质，特别是在分布式环境中，研究关系数据库的非环性程度是一个重要的课题，对Ａｌｐｈａ Ｂｅｔａ，Ｇａｍｍａ，Ｂｅｒｇｅ这几各非环数据库模式，我们给出一组颁式算法，该算法的最坏消息复杂度是Ｏ（／Ｎ／），而最坏时间复杂度是Ｏ（／Ｎ／＾２），／Ｎ／是给定的网络中结点的个数。     

单台机器速度可选择的排序问题

研究一类单台机器具有速度可选择约束的排序问题。引进了有关记号，给出了该问题解的概念。ｍ＝１的情形问题１｜ｓｐｅ．｜ΣＣ＿ｊ和问题１｜ｓｐｅ．｜Σｗ＿ｊＣ＿ｉ具有多项式时间算法，即为所谓的Ｐ问题，但对ｍ为一般情形其计算复杂性尚未解决。     

一种新的快速求核算法

为了解决核影响属性约简算法的速度和效率等问题，提出了一种基于正区域的求核算法．采用基数排序思想计算正区域，分别得到决策属性正区域的条件属性集和除决策属性正区域的一个条件属性之外的条件属性集，并且计算这2种属性集的基数之差，以判断该条件属性是否是核属性，依次判断所有条件属性，从而快速获得所需要的核．基于正区域求核算法的时间复杂度为O（｜C｜｜U｜）．实验结果表明，利用该算法求核，所耗时间将随对象数的增加呈线性增长，且当对象数最大时，求核所耗时间仅为对比算法的0．6％，同时证明了该算法对各种数据集均有很好的适应性．     

计算有圈有向网络根通信可靠度的因子分解算法

对有圈有向网络的拓扑结构进行了研究,提出了一个保持网络可靠度不变的缩减规则和因子分解的一个选边规则.由此建立了一个计算有圈有向网络根可靠度的有效算法.算法的时间复杂度是O(N.(|V|+|E|)),其中N是算法所产生二叉树的叶点数,|V|和|E|分别表示网络的节点数和边数.对一些网络进行了计算,结果显示利用该算法计算根通信可靠度所产生的N比其他算法的要小得多,因此,所提算法更有效.     

Overlay组播网络上带QoS约束的路由算法

为了保证多媒体应用的服务质量,本文在追求最大组播延迟极小化的同时考虑了网络节点的度约束条件,采用一种统一的方式来处理传输延迟和节点处理延迟,并基于此方法定义了带有QoS约束的Overlay组播路由选择优化模型,进而设计了一个求解该模型的启发式算法.该算法的时间复杂性为O(|V|3),优于许多求解该问题的同类算法,这些算法的时间复杂性多为O(|V|4),V为给定网络的节点集合.仿真结果也表明,本文算法解的质量也更优,即延迟更小.     

关联规则Apriori算法的改进

针对Apriori算法存在多次扫描数据库及产生大量候选项集的缺陷,提出了一种改进算法.该算法只需扫描数据库一次,并将事务变换成二进制存储到数据库,可节省存储空间、提高速度.实验结果表明,改进算法挖掘关联规则的效率有较大提高.     

处理机具有不同的开始加工时间的Q,ai｜pmtn｜Cmax排序问题

本文给出处理机具有不同的开始加工时间的Ｑ，ａｉ｜ｐｍｉｔｎ｜Ｃｍａｘ排序问题的一个最优算法，算法的复杂性为Ｏ（ｍ＾２ｎ＾２）。     

基于正区域的快速求核算法

基于正区域求核算法的最好时间复杂度为O(|C|2|U|log|U|),为降低该求核算法的时间复杂度,给出了基于正区域的简化决策表定义和相应核的定义.证明了该简化决策表的核与原决策表的核等价.由于求正区域的简化决策表首先要求划分U/C,而求划分U/C的最好算法的时间复杂度为O(|C||U|log|U|),因此以基数排序的思想设计了一个新的求划分U/C的算法,其时间复杂度为O(|C||U|).最后以快速缩小搜索空间为目的设计了一个新的求正区域POSC(D)的算法.在此基础上,利用核的性质设计了一个新的求核算法,其时间复杂度为max(O(|C||U|,O(|C|2|U/C|)).并用实例说明了算法的实用性.     

粗糙集中基于信息量的决策表属性约简算法

高效的属性约简算法是粗糙集理论应用于知识发现的基础,要在令人可接受的时间内获得约简的通常做法是基于启发式的约简方法。本文提出了决策表中决策属性集相对条件属性集的条件信息量的概念,同时用知识的条件信息量定义了属性的重要性,在此基础上,提出了一种新的基于信息量的属性约简算法,该算法的时间复杂度为(O|C|3|U|2),通过实例分析,表明该算法是有效的。     

一种改进的Apriori算法

Apriori算法存在许多可以改进的地方.例如它需要反复读取数据库,并且读取的次数由项目集中的项目个数来确定,I/O负载与最大项目集的项数成正比.本文提出一种只读一次数据库的的改进算法.     

二部图上的K1,m划分问题

 考虑了二部图上的|V|-K_1,m划分问题.首先利用网络最大流与网络最小费用流算法给出了赋权二部图上该问题的1个多项式算法,然后证明了:不考虑二部图上的权重或w是一固定常数时,该算法的复杂度为O((|V|+|U|)³.最后证明了:赋权二部图上最小最大|V|-K_1,m划分问题是NP-难的.