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

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

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

基于正区域求核算法的最好时间复杂度为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),通过实例分析,表明该算法是有效的。     

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

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

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

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

用于IC版图运算的O(N)排序算法

扫描线算法是集成电路版图运算的主流算法,排序在其中占有相当大的工作量．针对集成电路版图的特点,提出一种线性的排序算法,其时间复杂度为Ｏ（Ｎ）,比通常的快速排序算法时间复杂度（Ｏ（ＮｌｏｇＮ）低,适用于基于扫描线算法的集成电路版图运算．对于层次式设计的版图,该算法更具优越性     

Feature Selection Based on Difference and Similitude in Data Mining

Feature selection is the pretreatment of data mining. Heuristic search algorithms are often used for this subject. Many heuristic search algorithms are based on discernibility matrices, which only consider the difference in information system. Because the similar characteristics are not revealed in discernibility matrix, the result may not be the simplest rules. Although differencesimilitude（DS） methods take both of the difference and the similitude into account, the existing search strategy will cause some important features to be ignored. An improved DS based algorithm is proposed to solve this problem in this paper. An attribute rank function, which considers both of the difference and similitude in feature selection, is defined in the improved algorithm. Experiments show that it is an effective algorithm, especially for large-scale databases. The time complexity of the algorithm is O（｜ C ｜^2｜U ｜^2）.     

任意无向图的R点连通扩充

为研究以最少边集扩充一个任意无向图为R点连通图这一尚未解决的优化问题，通过将无向图点连通问题转化为有向图边连通问题，采用增广扩充的方法，提出了一个复杂度为O（｜V｜^5）的算法．利用该算法可最优地将给定无向图中任意2点达到所要求的点连通度．它发展了K点连通最优扩充的研究，从而使图的点连通扩充的研究在应用于网络设计的可靠性设计方面更具有实际意义．     

任意无向图的最小R边连通扩充

研究了以最少边集扩充一个任意无向图为R边连通图这一优化问题。给出了一个复杂度为O(|V|~5)的算法。利用该算法可最优地将所研究图形中任意两点达到所要求的边连通度。它发展了K边连通最优扩充的研究,从而使图的边连通扩充的研究在应用于网络结线的可靠性设计方面更具有实际意义。     

复杂性O(│v│~(1/2)*│A│)s-t连通度算法

使用简单网络的最大流算法给出复杂性为O(|v|(1/2)*|A|)s-t连通度算法。此算法为一有效的多项式时间算法。     

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

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

典型"稳定婚姻问题"的简明矩阵算法实现

对于典型“稳定婚姻问题”,借助矩阵（二维数组）给出了一种简明的实现方法．在本算法中,所采用的存储结构和实现方法灵活巧妙,通俗易懂,方便实现;而且用于存储所要处理数据的内存空间相对于其它一些算法节省了一半,空间复杂度为O（1）;由于存储结构的巧妙性,算法的时间复杂度在最好的情况下为线性时间N,在最坏的情况下为O（N^2）．     

决定非环性数据库模式的最小覆盖的算法

本文给出一个决定非环性数据库模式在某个指定的属性子集上的边最小覆盖算法，叫做ＭＣ－ＡＣＹＣＬＩＣ．该算法的时间复杂性为，其中｜Ｎ｜是给定的数据库模式中属性的个数和｜Ｅ｜是关系模式的个数．     

由先序序列和结点的层数构造严格二叉树的高效算法

提出一种新的通过一棵严格二叉树的先序序列和这棵严格二叉树的结点的层数构造这棵严格二叉树的非递归算法.举例说明新算法的执行过程.对于有n个结点的严格二叉树,新算法的时间复杂度为O(n),比相应的递归算法的低,新算法的最差情况空间复杂度为O(n),与相应的递归算法的相同.     

求解凸二次规划的一种二阶Mehrotra型预估一校正算法

给出了求解凸二次规划的一种二阶Mehrotra型预估一校正算法。该算法受Salahi等人对线性规划提出的相应算法启发,引入了安全步策略,保证了校正步步长有适当下界,从而具有多项式复杂性。由于算法迭代方向不正交,算法在罚参数的校正和复杂性的分析上有别于线性规划的情形。最后,通过一些新的技术性引理,证明了算法在最坏情况下的迭代复杂性为O（n^3/2log（x^0）^TS^0/ε）.     

一类带有Neumann边界的奇异拟线性椭圆方程解的存在性

应用变分方法中的极值理论来研究Neumann边界问题{ -div(｜x｜α｜▽u｜p-2▽u)=｜x｜βup(α,β)-1-λ｜x｜γup-1+｜x｜μq-1,u(x)＞0,x∈Ω｜▽u｜p-2?u/?u=0, x∈?Ω其中Ω是RN(N≥3)中具有C2光滑边界的有界区域,0 ∈Ω,n表示(e)Ω的单位外法向向量,且1＜p＜N,α＜0,β＜0,使得p(α,β)(△)p(N+β)/N-p+α＞P,γ＞α-p,P＜q＜p(α,μ).对于参数α,β,γ及μ的不同范围,建立上述方程解的存在性结果.其中对参数不同范围的讨论对解的存在性所起到的至关重要的作用.     

An Algorithm for the Spectral Immunity of Binary Sequence with Period 2~n

To resist the fast algebraic attack and fast selective discrete Fourier transform attacks, spectral immunity of a sequence or a Boolean function was proposed. At the same time, an algorithm to compute the spectral immunity of the binary sequence with odd period N was presented, here N is a factor of 2~n-1, where n is an integer. The case is more complicated when the period is even. In this paper, we compute linear complexity of every orthogonal sequence of a given sequence using Chan-Games algorithm and k- error linear complexity algorithm. Then, an algorithm for spectral immunity of binary sequence with period N=2~n is obtained. Furthermore, the time complexity of this algorithm is proved to be O(n).     

亚纯函数特征的一个性质

本文证明了亚纯函数的一个性质:设b_1、b_2,…是亚纯函数f(z)的极点,|b_1|<|b_2|<…,假设(1)有0<δ_0<1/2,使得对充分大的v,当|b_v|≠|b_(v+1)|时,|b_(v+1)|-|b_v|≥δ_0(|b_0|+1)(2) (3)则对任意小的δ>0,存在R_0(δ)>0,当δR>R_0(δ)时,μ(E_R)≥R~δ其中μ为面积测度E_R={Z;R<|z|<2R,log|f(z)|+N(|z|)>1/2T(R)}     

极大网络寿命的认知无线电网络组网算法

根据认知无线电网络的特点，本文提出一种基于鱼群算法与图论中极小独立集支配集算法相结合的认知无线电组网算法 (maximal cognitive radio network lifetime MCRNL)。该算法分为鱼群大小确定阶段和簇头选举阶段，前者以极小的能量完成节点配置和确定受影响的认知用户范围，后者确保以极小的能量进行通信，极大化网络寿命和簇头选举的公平性。仿真结果表明，该算法整体消息复杂度为O(n)，最坏时间复杂度为O(log(D+n))，算法性能优于MWMIDS，可以有效的应用于认知无线电网络基于MCRNL的路由协议中。