背包问题的最优并行算法

利用分治策略,提出一种基于SIMD共享存储计算机模型的并行背包问题求解算法.算法允许使用O(2^n/4)^1-ε个并行处理机单元,0≤ε≤1,O(2^n/2)个存储单元,在O(2^n/4(2^n/4)^ε)时间内求解n维背包问题,算法的成本为O(2^n/2).将提出的算法与已有文献结论进行对比表明,该算法改进了已有文献的相应结果,是求解背包问题的成本最优并行算法.同时还指出了相关文献主要结论的错误.     

一类ω—正则语言

ω—语言是由有穷字母表∑上的某些无穷串组成的集合。被所谓的ω—有穷自动机接受的ω—语言称为ω—正则语言。在[4]中作者曾从集合的角度给出—ω—语言为ω—正则语言的几个充分条件。在本文作者仍从集合的角度给出一个ω—语言为ω—正则语言的充分条件,即若—ω—凸语言L满足L=adh(pref(L))=pref(L)tail(L),则L是—ω—正则语言。从而,确定了ω—正则语言类的一个子类。     

描述逻辑εL混合循环术语集的LCS和MSC推理

分析了描述逻辑循环术语集的研究现状和存在的问题,在F.Baader工作的基础上进一步研究了描述逻辑εL混合循环术语集的LCS(least common subsumer)和MSC(most specific concept)推理问题.给出了εL混合循环术语集的语法和语义.针对εL混合循环术语集LCS和MSC推理的需要,提出了TBox-完全的概念,并重新定义了描述图.使用描述图和TBox-完全给出了最大不动点语义下εL混合循环术语集LCS和MSC的推理算法,证明了推理算法的正确性,并证明了推理算法是多项式时间复杂的.该推理算法为(L混合循环术语集的LCS和MSC推理提供了理论基础.     

RNA二级结构预测中动态规划的优化和有效并行

基于最小自由能模型的方法是计算生物学中RNA二级结构预测的主要方法,而计算最小自由能的动态规划算法需要O(n⁴)的时间,其中n是RNA序列的长度.目前有两种降低时间复杂度的策略:限制二级结构中内部环的大小不超过k,得到O(n²×k²)算法;Lyngso方法根据环的能量规则,不限制环的大小,在O(n3)的时间内获得近似最优解.通过使用额外的O(n)的空间,计算内部环中的冗余计算大为减少,从而在同样不限制环大小的情况下,在O(n³)的时间内能够获得最优解.然而,优化后的算法仍然非常耗时,通过有效的负载平衡方法,在机群系统上实现并行程序.实验结果表明,并行程序获得了很好的加速比.     

一种有效的挖掘数据流近似频繁项算法

数据流频繁项是指在数据流中出现频率超出指定阈值的数据项.查找数据流频繁项在网络故障监测、流数据分析以及流数据挖掘等多个领域有着广泛的应用.在数据流模型下,算法只能一遍扫描数据,并且可用的存储空间远远小于数据流的规模,因此,挖掘出所有准确的数据流频繁项通常是不可能的.提出一种新的挖掘数据流近似频繁项的算法.该算法的空间复杂性为O(ε^-1),每个数据项的平均处理时间为O(1),输出结果的频率误差界限为ε(1-s+     

一种基于多类型偏好的偏好逻辑

针对目前缺乏多类型偏好共存的偏好逻辑系统的现状,提出并构造了一个能够描述和推理多种类型偏好的逻辑系统MPL(logic of many kinds of preference).在进一步提出MPL语言L_MPL基于最粗糙/最细致描述原则的非单调语义基础上,通过分级知识库这种常用偏好表示方法的L_MPL重写,初步考察了L_MPL表示能力,最后进行总结并提出需要进一步研究解决的问题.     

用擂台赛法则构造多目标Pareto最优解集的方法

针对多目标进化的特点,提出了用擂台赛法则(arena's principle,简称AP)构造多目标Pareto最优解集的方法,论证了构造方法的正确性,分析了其时间复杂度为O(rmN)(0＜m/N＜1).理论上,当AP与Deb的算法以及Jensen的算法比较时(它们的时间复杂度分别为O(rN²)和O(Nlog^(r-1)N)),AP优于Deb的算法;当目标数r较大时(如r≥5),AP优于Jensen的算法;此外,当m/N较小时(如m/N≤50%),AP的效率与其他两种算法比较具有优势.对比实验结果表明,AP具有比其他两种算法更好的CPU时间效率.在应用中,AP可以被集成到任何基于Pareto的MOEA中,并能在较大程度上提高MOEA的运行效率.     

确定任意多边形凸凹顶点的算法

本文提出一种确定任意多边形凸凹顶点的算法．该算法的时间复杂性为O(n²logn)次乘法和O(n²)次比较．     

PRAM和LARPBS模型上有向序列翻转距离并行算法

分别在两种重要并行计算模型中给出计算有向基因组排列的反转距离新的并行算法.基于Hannenhalli和Pevzner理论,分3个主要部分设计并行算法:构建断点图、计算断点图中圈数、计算断点图中障碍的数目.在CREW-PRAM模型上,算法使用O(n²)处理器,时间复杂度为O(log²n);在基于流水光总线的可重构线性阵列系统(linear array with a reconfigurable pipelined bus system, LARPBS)模型上,算法使用O(n³)处理器,计算时间复杂度为O(logn).     

模糊聚类计算的最佳算法

给出模糊关系传递闭包在对应模糊图上的几何意义,并提出一个基于图连通分支计算的模糊聚类最佳算法.对任给的n个样本,新算法最坏情况下的时间复杂性函数T(n)满足O(n)≤T(n)≤O(n²).与经典的基于模糊传递闭包计算的模糊聚类算法的O(n³logn)计算时间相比,新算法至少降低了O(n相似文献   

基于语义模式的英语动词汉译

英语动词正确汉译是机器翻译的难点.为此,提出一种基于动词语义模式库、固定句式库和变量库的英语动词汉译算法.介绍语义模式的提取方法,构建常用动词的语义模式库、固定句式库和变量库,归纳动词语义模式的3种结构形式:V语义模式,VO相邻语义模式和VO非相邻语义模式.动词语义模式库由上述3种结构形式对应的模式库构成.实验结果表明...     

多民族语言本体知识库构建技术

语义本体是共享概念模型的显示的形式化规范说明,其目标是将杂乱无章的信息源转变为有序易用的知识源。语义本体知识库的构建是文本自动处理的一个重要环节,跨语言信息检索、信息抽取、自动翻译等领域中都有广泛的应用。该文旨在描述统一标准、统一接口的多民族语言本体知识库的创建思路,以及包含的若干问题,例如 多民族语言中共有概念的一般表示与各民族语言特有的事物表达方式的规律,基于词汇语义的、包括汉语、英语及少数民族语言在内的多民族语言语义本体的表示理论与方法等。     

Optimal Computing the Chessboard Distance Transform on Parallel Processing Systems

Thedistance transform(DT) is an image computation tool which can be used to extract the information about the shape and the position of the foreground pixels relative to each other. It converts a binary image into a grey-level image, where each pixel has a value corresponding to the distance to the nearest foreground pixel. The time complexity for computing the distance transform is fully dependent on the different distance metrics. Especially, the more exact the distance transform is, the worse execution time reached will be. Nowadays, quite often thousands of images are processed in a limited time. It seems quite impossible for a sequential computer to do such a computation for the distance transform in real time. In order to provide efficient distance transform computation, it is considerably desirable to develop a parallel algorithm for this operation. In this paper, based on the diagonal propagation approach, we first provide anO(N²) time sequential algorithm to compute thechessboard distance transform(CDT) of anN×Nimage, which is a DT using the chessboard distance metrics. Based on the proposed sequential algorithm, the CDT of a 2D binary image array of sizeN×Ncan be computed inO(logN) time on the EREW PRAM model usingO(N²/logN) processors,O(log logN) time on the CRCW PRAM model usingO(N²/log logN) processors, andO(logN) time on the hypercube computer usingO(N²/logN) processors. Following the mapping as proposed by Lee and Horng, the algorithm for the medial axis transform is also efficiently derived. The medial axis transform of a 2D binary image array of sizeN×Ncan be computed inO(logN) time on the EREW PRAM model usingO(N²/logN) processors,O(log logN) time on the CRCW PRAM model usingO(N²/log logN) processors, andO(logN) time on the hypercube computer usingO(N²/logN) processors. The proposed parallel algorithms are composed of a set of prefix operations. In each prefix operation phase, only increase (add-one) operation and minimum operation are employed. So, the algorithms are especially efficient in practical applications.     

Hypercube sandwich approach to conferencing

This paper presents a novel cascaded conference network that provides distributed processing and signal transmission among members of disjoint sets of generic send/receive devices called conferees. It assumes an online request model in which idle groups of conferees may request the formation of a conference interconnection. Once a conference is established, all conferees remain connected until the entire conference is dissolved. The Hypercube Sandwich Network (HSN) consists of two components. A bidirectional permutation network is used for routing purposes to and from a hypercube of special processing elements for the purpose of conference formation. The HSN achieves strictly nonblocking performance for N conferees using O(Nlog N) processing elements, and this is shown to be tight to within a log ^1/4 N factor. Previous constructions required a quadratic number of processing elements for strictly nonblocking performance or could only provide wide-sense nonblocking conferencing. If the stronger requirement is made that the communication delay is logarithmic in the conference size, a simple algorithm is presented for wide-sense nonblocking conferencing in an HSN with O(N log N) processing elements.An earlier version of this paper was presented at the 1995 International Conference on Parallel Processing Techniques and Applications.     

基于语义选择与信息特征的英语机器翻译系统

本文基于语义选择与信息特征设计了英语自动化机器翻译系统。通过语义信息特征制定了机器翻译流程,以GIZA++为载体进行翻译,利用伯克利对准器对齐词语,基于反向转换语法,详细阐述汉语语言模式与英语翻译语言模式的结构关联特性,以语句动静配置,实现自动化机器翻译。最后通过系统测试,结果表明,与传统机器翻译系统相比,准确率显著提高,这就表明基于语义选择与信息特征的英语自动化机器翻译系统的翻译准确率较高,可为英汉机器翻译奠定坚实的基础支持。     

藏文语义词典建设中语义关系抽取方法的研究

研究语义是当前人工智能、语义网、语义词典等研究领域的热点,它可以有效支持机器翻译和自然语言处理等技术。文章根据藏文独特的文法特性,运用藏文逻辑格和计算语言学知识,在保留藏文原有特点的基础上,为藏文语义关系抽取方法建立较完整的语义场,以此为藏文语义词典建设提供了基础性构建方法。     

A New and Faster Gaussian Elimination Based Fault Tolerant Systolic Linear System Solver

This paper presents a new systolic algorithm for thecompletesolution of a system ofNlinear equations in (N²/2 +O(N)) time steps using 2Nprocessing elements (PEs). It is based on a variant of the Gaussian elimination (GE) algorithm called the successive GE and is faster than any existing GE based algorithm usingO(N) PEs. We also suggest two fault tolerant schemes that tolerate up toNPE failures. The first scheme is a time redundancy based approach with no hardware overhead and 100% time overhead. This scheme can tolerate up toNPE failures. The second scheme is based on algorithm based fault tolerance (ABFT) and usesNextra PEs to tolerate up toN− 1 PE failures with very little time overhead. The number of errors that can be detected/corrected in both schemes is more than that in any existing fault tolerant systolic array.     

A fine-grained data-flow analysis framework

 A fine-grained data-flow analysis framework (L, F) where the elements of the semilattice L are mappings from a set of items I to a semilattice of values V is introduced, and an algorithm is presented to solve this framework by considering the elements of I and V individually, rather than regarding the elements of L as atomic values. It is shown that a variety of useful data-flow problems fit into the fine-grained data-flow analysis framework, and can be solved in O(∣I∣×∣N∣) time. Received 20 August, 1991/ 3 June, 1996     

一种空间更优的数据流查询包含编码区间索引

给出一种基于CEI(containment-encoded intervals)的存储优化的数据流查询区间索引结构.在数据流处理中涉及到大量的数值型区间查询操作,构造一个基于主存并支持快速查询的区间索引结构十分必要.对CEI索引结构而言,虽然支持高速查询,但存储利用率较低.针对该问题,提出了索引结构ACEI(advanced-CEI).在CEI索引结构的基础上,通过数据结构调整和参数优化,ACEI可在保持原有查询速度的前提下将CEI的空间复杂度由O(R+N(W/L+N(log(L))降为O(sqrt(R(N)+N(sqrt(W)).实验结果表明,ACEI结构可以极大地提高索引结构的存储利用率,并且可以用于大端点值域下的区间索引.     

Semantic language and multi-language MT approach based on SL

Any natural language is regarded as a representation of semantic language.The translation between two languages (I,J) is regarded as a transformation between two representations.A natural language-Ⅰ is translated into another natural language-J only by two steps.One is semantic-analysis of language-Ⅰ based on “semantic-element-representation-base of language-I“,the other is deploying into the representation of language-J based on “semantic-element-representation-base of language-J‘.For translating in N natural languages,it is needed to develop N translation systems only,rather than N（N-1）/2,or 2N systems.