共查询到20条相似文献,搜索用时 343 毫秒
1.
2.
Pawlak教授提出的粗糙集理论是解决集合边界不确定的重要手段,他构建了边界不确定集合的两条精确边界,但没有给出用已有知识基来精确或近似地构建目标概念(集合)X的方法.在前期的研究中提出了寻找目标概念X的近似集方法,但并没有给出最优的近似集.首先,回顾了集合间的相似度概念和粗糙集的近似集Rλ(X)的构建方法,提出并证明了Rλ(X)所满足的运算性质.其次,找到了Rλ(X)比上近似集R(X)和下近似集R(X)更近似于目标概念X的λ成立的区间.最后,提出了R0.5(X)作为目标概念的最优近似集所满足的条件. 相似文献
3.
本文定义了ω幂上下文无关语言ω—P— cfl和一类ω下推自动机ω—pda,给出了它们
的关系.借助于ω时序转换器ω—ST,讨论了ω—p—cfl类的某些封闭性质,证明了对于ω—p—cfl类L,m(L)={s’(A)|A∈s'是一个ω—ST)=(h2(h1-1(A)∩R)|A∈L,R是一个ω正规语言,h1相似文献
4.
个体单体型MSR(minimum SNP removal)问题是指如何利用个体的基因测序片断数据去掉最少的SNP(single-nucleotide polymorphisms)位点,以确定该个体单体型的计算问题.对此问题,Bafna等人提出了时间复杂度为O(2kn2m)的算法,其中,m为DNA片断总数,n为SNP位点总数,k为片断中洞(片断中的空值位点)的个数.由于一个Mate-Pair片段中洞的个数可以达到100,因此,在片段数据中有Mate-Pair的情况下,Bafna的算法通常是不可行的.根据片段数据的特点提出了一个时间复杂度为O((n-1)(k1-1)k222h+(k1+1)2h+nk2+mk1)的新算法,其中,k1为一个片断覆盖的最大SNP位点数(不大于n),k2为覆盖同一SNP位点的片段的最大数(通常不大于19),h为覆盖同一SNP位点且在该位点取空值的片断的最大数(不大于k2).该算法的时间复杂度与片断中洞的个数的最大值k没有直接的关系,在有Mate-Pair片断数据的情况下仍然能够有效地进行计算,具有良好的可扩展性和较高的实用价值. 相似文献
5.
波长指派是光网络设计的基本问题,设计波长指派算法是洞察光网络通信能力的基本方法.基于光RP(k)网络,讨论了其波长指派问题. 含有N=2n个节点的Hypercube通信模式,构造了节点间的一种排列次序Xn,并设计了RP(k)网络上的波长指派算法.在构造该算法的过程中,得到了在环网络上实现n维Hypercube通信模式的波长指派算法.这两个算法具有较高的嵌入效率.在RP(k)网络上,实现Hypercube通信模式需要max{2,「5(2n-5/3」}个波长.而在环网络上,实现该通信模式需要复用(N/3+N/12(个波长,比已有算法需要复用「N/3+N/4」个波长有较大的改进.这两个算法对于光网络的设计具有较大的指导价值. 相似文献
6.
7.
置信传播算法求解RB(k,n,α,rc,p)模型实例时非常有效,几乎能够有效求解接近可满足性相变点的难解实例.然而,因子图带有回路的实例,置信传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.置信传播算法是最为基础的信息传播算法,对置信传播算法的收敛性分析是其他信息传播算法收敛性分析的重要基础.在RB(k,n,α,rc,p)模型中,取k=2,α>(1/k),rc>0均为常数,且满足ke-(α/(rc))≥1.证明了如果p∈(0,n-2α),则置信传播算法在RB(k,n,α,rc,p)模型产生的随机实例集上高概率收敛.最后,在RB(k,n,α,rc,p)模型上选取了几组不同的数据进行数值模拟,实验结果表明该结论有效.当问题规模n增大时,在RB(k,n,α,rc,p)模型的可满足区域,实验收敛区间趋于一个固定范围,而理论收敛区间逐渐变窄.原因在于,RB(k,n,α,rc,p)模型是一个具有增长定义域的随机CSP实例产生模型,不协调赋值的数目与参数p及问题规模n有关. 相似文献
8.
在消息传递并行机上的高效的最小生成树算法 总被引:5,自引:0,他引:5
基于传统的Borǔ vka串行最小生成树算法,提出了一个在消息传递并行机上的高效的最小生成树算法.并且采用3种方法来提高该算法的效率,即通过两趟合并及打包收缩的方法来减少通信开销,通过平衡数据分布的办法使各个处理器的计算量平衡.该算法的计算和通信复杂度分别为O(n2/p)和O((tsp+twn)n/p).在曙光-1000并行机上运行的实际效果是,对于有10 000个顶点的稀疏图,通过16个节点的运行加速比是12. 相似文献
9.
10.
提出具有模态词□φ=□1V□2φ的命题模态逻辑,给出其语言、语法与语义,其公理化系统是可靠与完备的,其中,□1与□2是给定的模态词.该逻辑的公理化系统具有与公理系统S5相似的语言,但具有不同的语法与语义.对于任意的公式φ,□φ=□1V□2φ;框架定义为三元组W,R1,R2,模型定义为四元组W,R1,R2,I;在完备性定理证明过程中,需要在由所有极大协调集所构成的集合上构造出两个等价关系,其典型模型的构建方法与经典典型模型的构建方法不同.如果□1的可达关系R1等于□2的可达关系R2,那么该逻辑的公理化系统变成S5. 相似文献
11.
Adaptive data structures form a central topic of on-line algorithms research. The area of Competitive Analysis began with the results of Sleator and Tarjan showing that splay trees achieve static optimality for search trees, and that Move-to-Front is constant competitive for the list update problem [ST1], [ST2]. In a parallel development, powerful algorithms have been developed in Machine Learning for problems of on-line prediction [LW], [FS]. This paper is inspired by the observation made in [BB] that if computational decision-making costs are not considered, then these ``weighted experts'' techniques from Machine Learning allow one to achieve a 1+ε ratio against the best static object in hindsight for a wide range of data structure problems. In this paper we give two results. First, we show that for the case of lists , we can achieve a 1+ε ratio with respect to the best static list in hindsight, by a simple efficient algorithm. This algorithm can then be combined with existing results to achieve good static and dynamic bounds simultaneously. Second, for trees, we show a (computationally in efficient) algorithm that achieves what we call ``dynamic search optimality'': dynamic optimality if we allow the on-line algorithm to make free rotations after each request. We hope this to be a step towards solving the longstanding open problem of achieving true dynamic optimality for trees. 相似文献
12.
Nagumo H. Mi Lu Watson K.L. 《Parallel and Distributed Systems, IEEE Transactions on》1999,10(12):1241-1251
The data compression based on dictionary techniques works by replacing phrases in the input string with indexes into some dictionary. The dictionary can be static or dynamic. In static dictionary compression, the dictionary contains a predetermined fixed set of entries. In dynamic dictionary compression, the dictionary changes its entries during compression. We present parallel algorithms for two parsing strategies for static dictionary compression. One is the optimal parsing strategy with dictionaries that have the prefix properly, for which our algorithm requires O(L+log n) time and O(n) processors, where n is the number of symbols in the input string, and L is the maximum length of the dictionary entries, while previous results run in O(L+log n) time using O(n2) processors or in O(L+log2 n) time using O(n) processors. The other is the longest fragment first (LFF) parsing strategy, for which our algorithm requires O(L+log n,) time and O(n log L) processors, while a previous result obtained an O(L log n) time performance on O(n/log n) processors. For both strategies, we derive our parallel algorithms by modifying the on-line algorithms using a pointer doubling technique 相似文献
13.
Abstract. Adaptive data structures form a central topic of on-line algorithms research. The area of Competitive Analysis began with
the results of Sleator and Tarjan showing that splay trees achieve static optimality for search trees, and that Move-to-Front
is constant competitive for the list update problem [ST1], [ST2]. In a parallel development, powerful algorithms have been
developed in Machine Learning for problems of on-line prediction [LW], [FS]. This paper is inspired by the observation made
in [BB] that if computational decision-making costs are not considered, then these ``weighted experts' techniques from Machine
Learning allow one to achieve a 1+ε ratio against the best static object in hindsight for a wide range of data structure problems.
In this paper we give two results. First, we show that for the case of lists , we can achieve a 1+ε ratio with respect to the best static list in hindsight, by a simple efficient algorithm. This algorithm can then be combined with existing results to achieve good static and dynamic bounds simultaneously.
Second, for trees, we show a (computationally in efficient) algorithm that achieves what we call ``dynamic search optimality': dynamic optimality if we allow the on-line algorithm to make free rotations after each request. We hope this to be a step towards solving the longstanding open problem
of achieving true dynamic optimality for trees. 相似文献
14.
Gadiel Seroussi 《Algorithmica》2006,46(3-4):557-565
We show that the number of t-ary trees with path length equal to p is $\exp({{(\alpha {p}/{\log p})}(1+o(1))}),$ where $\alpha=h(t^{-1})t\log t$ and $h(x)={-}x\log x {-}(1{-}x)\log (1{-}x).$ Besides its intrinsic combinatorial interest, the question recently arose in the context of information theory, where the number of t-ary trees with path length p estimates the number of universal types, or, equivalently, the number of different possible Lempel-Ziv '78 dictionaries for sequences of length p over an alphabet of size t. 相似文献
15.
The increased availability of data describing biological interactions provides important clues on how complex chains of genes
and proteins interact with each other. Most previous approaches either restrict their attention to analyzing simple substructures
such as paths or trees in these graphs, or use heuristics that do not provide performance guarantees when general substructures
are analyzed. We investigate a formulation to model pathway structures directly and give a probabilistic algorithm to find
an optimal path structure in
time and
space, where n and m are respectively the number of vertices and the number of edges in the given network, k is the number
of vertices in the path structure, and t is the maximum number of vertices (i.e., "width") at each level of the structure.
Even for the case t = 1 which corresponds to finding simple paths of length k, our time complexity
is a significant improvement over previous probabilistic approaches. To allow for the analysis of multiple pathway structures,
we further consider a variant of the algorithm that provides probabilistic guarantees for the top suboptimal path structures
with a slight increase in time and space. We show that our algorithm can identify pathway structures with high sensitivity
by applying it to protein interaction networks in the DIP database. 相似文献
16.
We consider the problem of routing in
an asynchronous dynamically changing ring of processors
using schemes that minimize the storage space for the routing
information. In general, applying static techniques to a dynamic
network would require significant re-computation. Moreover, the
known dynamic techniques applied to the ring lead to inefficient schemes.
In this paper we introduce a new technique, Dynamic Interval Routing,
and we show tradeoffs between
the stretch factor, the adaptation cost, and the size of
the update messages used by routing schemes based upon it.
We give three algorithms for rings of maximum size N: the first two
are deterministic,
one with adaptation cost zero but worst case stretch factor \lfloor
N/2 \rfloor,
the other with worst case adaptation cost O(N) update messages of O(log N)
bits and stretch factor 1. The third algorithm
is randomized,
uses update messages of size O(k log N), has adaptation cost O(k), and
expected stretch factor 1+1/k, for any
integer k 3.
All schemes require O(log N) bits per node for
the routing information and all messages headers are of O(log N) bits. 相似文献
17.
This paper presents an efficient scheme maintaining a separator decomposition representation in dynamic trees using asymptotically optimal labels. In order to maintain the short labels, the scheme uses relatively low
message complexity. In particular, if the initial dynamic tree contains only the root, then the scheme incurs an O(log4
n) amortized message complexity per topology change, where n is the current number of vertices in the tree. As a separator decomposition is a fundamental decomposition of trees used
extensively as a component in many static graph algorithms, our dynamic scheme for separator decomposition may be used for
constructing dynamic versions to these algorithms. The paper then shows how to use our dynamic separator decomposition to
construct efficient labeling schemes on dynamic trees, using the same message complexity as our dynamic separator scheme.
Specifically, we construct efficient routing schemes on dynamic trees, for both the designer and the adversary port models,
which maintain optimal labels, up to a multiplicative factor of O(log log n). In addition, it is shown how to use our dynamic separator decomposition scheme to construct dynamic labeling schemes supporting
the ancestry and NCA relations using asymptotically optimal labels, as well as to extend a known result on dynamic distance
labeling schemes.
Supported in part at the Technion by an Aly Kaufman fellowship.
Supported in part by a grant from the Israel Science Foundation. 相似文献
18.
Distance labeling schemes are composed of a marker algorithm for
labeling the vertices of a graph with short labels, coupled with a
decoder algorithm allowing one to compute the distance between
any two vertices directly from their labels (without using any additional
information).
As applications for distance labeling schemes
concern mainly large and dynamically changing networks,
it is of interest to study distributed dynamic labeling schemes.
The current paper considers the problem on dynamic trees,
and proposes efficient distributed schemes for it.
The paper first presents a labeling scheme for distances in the dynamic
tree model, with amortized message complexity O(log2
n) per operation,
where n is the size of the tree at the time the operation takes place.
The protocol maintains O(log2
n) bit labels.
This label size is known to be optimal even in the static scenario.
A more general labeling scheme is then introduced for the dynamic tree
model, based on extending an existing static tree labeling
scheme to the dynamic setting. The approach fits a number of
natural tree functions, such as distance, separation level, and flow.
The main resulting scheme incurs an overhead
of an O(log n) multiplicative factor in both the label size and
amortized message complexity in the case of dynamically growing
trees (with no vertex deletions).
If an upper bound on n is known in advance,
this method yields a different tradeoff, with an
O(log2
n/log log n) multiplicative overhead on the label
size but only an O(log n/log log n) overhead on the amortized
message complexity.
In the fully dynamic model the scheme also incurs an increased
additive overhead in amortized communication, of O(log2
n)
messages per operation. 相似文献
19.