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

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

A Clas of Distributed Recognition Algorithms for Acyclic Database Schemes

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

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

基于正区域求核算法的最好时间复杂度为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(N.(|V|+|E|)),其中N是算法所产生二叉树的叶点数,|V|和|E|分别表示网络的节点数和边数.对一些网络进行了计算,结果显示利用该算法计算根通信可靠度所产生的N比其他算法的要小得多,因此,所提算法更有效.     

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

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

无向树图的k点连通最小扩充

解决了以最少边集扩充一个任意无向树图为k点连通图这一优化问题,提出了一个计算复杂度为D(|V|~4)的算法。为进一步研究可靠网络的计算机辅助设计打下基础。     

基于一种曲率最小优化准则的散乱点三角剖分

从曲率入手,提出一种空间凸四边形的曲率估计算法,由此建立了一种新的基于该曲率的三角剖分优化准则以及曲面三角剖分算法．该算法修改了部分常用的数据结构,使得算法有更好的空间复杂度．通过分析,算法的时间复杂度为O(m^2),同时还将这一优化准则与几种常用的优化准则作了扼要比较．实验结果分析表明本算法具有保形特性,这在曲面重构和曲面设计等方面有很好的实用价值．     

一个新非线性系统的动力学分析与混沌控制

为解决混沌系统在保密通信中的控制问题, 计算分析耗散性函数的耗散性, 并结合Lyapunov指数证明其混沌性. 根据Routh Hurwitz判据分析平衡点的稳定性, 利用MATLAB软件模拟相图. 结果表明: 该系统具有丰富的动力学特征, 且与Lorenz系统拓扑不相似; 用微分反馈控制法可控制并消除该系统的混沌现象, 用x|x| 控制法可对新系统进行周期控制, 使其周期态和混沌交替出现.     

一个新非线性系统的动力学分析与混沌控制

为解决混沌系统在保密通信中的控制问题, 计算分析耗散性函数的耗散性, 并结合Lyapunov指数证明其混沌性. 根据Routh Hurwitz判据分析平衡点的稳定性, 利用MATLAB软件模拟相图. 结果表明: 该系统具有丰富的动力学特征, 且与Lorenz系统拓扑不相似; 用微分反馈控制法可控制并消除该系统的混沌现象, 用x|x| 控制法可对新系统进行周期控制, 使其周期态和混沌交替出现.     

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

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