基因组Translocation排序问题的改进多项式算法

该文给出基因组Transhocation排序问题的一个改进多项式算法，原算法所有存储空间O（n)，时间复杂度为O(n^3)，文中改进算法仍采用O(n)存储空间，时间复杂度为O(n^2logn),具体地，将计算Translocation距离的时间复杂度由O(n^3)改进为O(n^2),将计算Translocation序列的时间复杂度由O(n^3)改进为O(n^2logn).     

一个几何约束系统分解的新算法

几何约束系统的分解是参数化设计中的关键问题,利用从已知实体出发,使约束变动逐步向外围传播的思想,给出了一个分解陈述式约束系统的算法,其空间和时间复杂度分别为O(n)和O(n^2),该算法已经在机械绘图与设计系统GH MDS中得到应用。     

有向基因组移位排序问题的O(n2)快速算法

有向基因组移位排序问题在计算生物学研究中占有重要位置．以前最好的算法时间复杂度为O(n^2logn)．该文给出一个有向基因组移位排序的新多项式算法，将移位排序的时间复杂度改进为O(n^2)．算法改进的关键在于找到一种寻找有效合理移位的新方法，通过在最小子排列中删除无关顶点确定一个合理移位是否有效，从而将寻找一个有效移位的时间复杂度改进为O(n)，总时间复杂度由此降为O(n^2)．     

一种同构、非同构布局模式构造算法

给出了一种基于完全关联图的准确构造同构、非同构布局模式的算法,并给出了其计算复杂度及适应范围.与李广强等（2003）的布局模式构造方法相比较表明,本算法能构造准确布局模式,适用范围较广,计算复杂度低,前者为O（n^3）,本文为O（n）,O（n^2）或O（n^3）.     

方位关系约束满足问题的推理求解

约束满足问题（Constraint Satisfaction Problems CSP）是人工智能的一个研究领域,诸如空间查找、规划等问题都可转化为约束满足问题。方位关系是空间关系的重要组成部分,用以确定空间对象间的一种顺序。本文研究了空间方位关系模型,给出了方位关系约束的一般表示形式。在此基础上,利用组合表推理给出了方位关系约束满足问题的一个推理求解算法,该算法的时间复杂度为O（n^2）。     

位排序--一种快速排序法

众所周知,排序速度的快慢,取决于排序算法的时间复杂度和空间复杂度。因而,排序算法设计的主导思想,就是要千方百计降低算法的时间复杂度和空间复杂度。虽然计算机硬件的运算速度越来越快,但排序算法的研究仍是算法理论中的一个重要课题。已有的排序算法很多,在所有基于“记录关键字之间比较”的排序方法中,快速排序(quick sort)是平均时间性能最好的一种方法,平均时间为O（n*log n)。但是在最坏情况下,时间复杂度却很高,为O(n^2)。     

一种判定图中Hamilton圈的邻接边增长算法

一个图是否为Hamilton图在于图中是否有Hamilton圈。文中提出了变换的方法来寻找图中的Hamilton圈，即在图的顶点集中寻找满足包含给定图中所有顶点的自归邻接边增长变换的方法来寻找给定图中的Hamilton圈。由此，设计了一个在Edmonds意义下的有效算法——自归邻接边增长算法(AEG)来寻找给定图中的自归邻接边增长变换，证明了该算法能正确判断给定简单无向图中有无Hamilton圈且时间复杂度为O(n^2)。最后通过应用实例说明该算法的有效性和实用性。     

适用于复杂场景的碰撞检测算法研究

创建虚拟场景不仅要进行静态建模，更重要的是进行动态建模。而且物体之间的实时碰撞检测是关键。首先对常用检测算法的检测效率进行了分析和比较。然后重点针对复杂虚拟场景中吉有大量物体的特点，提出了混合包围盒碰撞检测算法。该算法利用帧与帧之间的时间和几何相关性，把对（cn^2＋m）个对象的动态跟踪转化为它们在三个坐标轴上的投影的排序问题，把时间复杂度由O（n^2）降低为O（n）。并引入树的深度的概念，根据不同的应用场合合理控制检测深度以加快检测速度。理论分析和仿真计算都表明，该算法能够满足多达几百个运动物体的实时交互碰撞检测。     

一种剖分平面多边形的通用算法描述

提出了一种用梯形来剖分非单调平面多边形的通用算法，算法包括三部分：初始化，梯形化和优化（后处理），所处理的多边形可以包含孔，孔可以嵌套。本算法的时间复杂度是O(n^2log2n).     

虫孔路由二维网孔机器上的最优图论算法

连通分量和最小生成树是图论中的两个基本问题 ,在许多领域都有很多应用 .对于顶点数为 n的图和规模为 p× p的虫孔路由二维网孔机器 ,该文针对 p n和 n

相似文献   

Hybrid Scheduling of Dynamic Task Graphs with Selective Duplication for Multiprocessors under Memory and Time Constraints

This paper presents a hybrid scheduling methodology for task graphs to multiprocessor embedded systems. The proposed methodology is designed for task graphs which are dynamic in nature due to the presence of conditional tasks as well as tasks whose execution times are unpredictable but bounded. We have presented the methodology as a three phase strategy in which task nodes are mapped to the processors in the first (static mapping) phase. In the second (selective duplication) phase some critical nodes are identified and duplicated for possible rescheduling at run-time depending on the code memory constraints of the processors. The third (online) phase is a run-time scheduling algorithm that performs list scheduling based on actual dynamics of the schedule up to the current time. We show that this technique provides better schedule length (up to 20%) compared to previous techniques which are predominantly static in nature with low overhead and comparable in complexity with existing online techniques. The effects of model parameters like number of processors, memory and various task graph parameters on performance are investigated in this paper.     

Specifying safety-critical systems with a decidable duration logic

Punctual timing constraints are important in formal modelling of safety-critical real-time systems. But they are very expensive to express in dense time. In most cases, punctuality and dense-time lead to undecidability. Efforts have been successful to obtain decidability; but the results are either non-primitive recursive or nonelementary. In this paper we propose a duration logic which can express quantitative temporal constraints and punctuality timing constraints over continuous intervals and has a reasonable complexity. Our logic allows most specifications that are interesting in practice, and retains punctuality. It can capture the semantics of both events and states, and incorporates the notions duration and accumulation. We call this logic ESDL (the acronym stands for Event- and State-based Duration Logic). We show that the satisfiability problem is decidable, and the complexity of the satisfiability problem is NEXPTIME. ESDL is one of a few decidable interval temporal logics with metric operators. Through some case studies, we also show that ESDL can specify many safety-critical real-time system properties which were previously specified by undecidable interval logics or their decidable reductions based on some abstractions.     

Set Constraints with Intersection

Set constraints are inclusions between expressions denoting sets of trees. The efficiency of their satisfiability test is a central issue in set-based program analysis, their main application domain. We introduce the class of set constraints with intersection (the only operators forming the expressions are constructors and intersection) and show that its satisfiability problem is DEXPTIME-complete. The complexity characterization continues to hold for negative set constraints with intersection (which have positive and negated inclusions). We reduce the satisfiability problem for these constraints to one over the interpretation domain of nonempty sets of trees. Set constraints with intersection over the domain of nonempty sets of trees enjoy the fundamental property of independence of negated conjuncts. This allows us to handle each negated inclusion separately by the entailment algorithm that we devise. We furthermore prove that set constraints with intersection are equivalent to the class of definite set constraints and thereby settle the complexity question of the historically first class for which the decidability question was solved.     

基于快速排序的数字高程模型分级填洼算法

数字高程模型（DEM）的填洼过程是水系提取中最耗费时间的过程,在Moran和Vezina提出的填洼思想（M&V填洼算法）的基础上,建立了基于快速排序的分级填洼算法,既能有效地减少填洼过程中的搜索路径,提高填洼效率,又能保证依此提取水系的完整与连贯。对于一个给定的DEM地形,传统的填洼算法的执行效率是固定的,而分级填洼的实际执行效率取决于分级数量,对于自然流域,一般200至500的分级量可使计算效率达到最高。通过在6个不同流域上的应用表明,在平均情况下,分级填洼算法的时间复杂度约为O(n1.29),其执行效率远高于M&V填洼算法及Arcgis 9.2（采用改进Jenson&Domingue算法）的执行效率。     

Finite satisfiability of integrity constraints in object-orienteddatabase schemas

Checking satisfiability of database constraints is a fundamental problem in database design. In addition, database constraints have to be not only satisfiable but also finitely satisfiable. This problem is generally addressed by using theorem provers that, being developed for first order logic formulas, are based on semidecidable procedures. Furthermore, even in simple cases, theorem provers are quite inefficient in dealing with comparison operators such as, for instance, the equality. In this paper, a decidable, sound, and complete method for checking finite satisfiability of a specific class of integrity constraints for object-oriented databases, including the equality constraints, is presented. The method, that is based on a graph-theoretic approach, has exponential complexity in the worst case, rarely occurring in practice     

TSP 基于参考点的相邻插入法和两阶段方法

通过分析已有的最近插入法，提出了一种基于参考点的相邻插入法(RPBNI)及其改进策略(I-RPBNI)，用于求解旅行商问题(TSP)，时间性能分别为O(n^2)NO(n^3)；进而提出了结合模拟退火算法和I-RPBNI的两阶段方法．通过典型算例的数值仿真，验证了所提出算法的有效性、高效性和鲁棒性．     

MODELING TIMED BEHAVIOR IN REAL-TIME SYSTEMS WITH TEMPORAL LOGIC

This article presents graphic as well as assertional representations of the timed behavior of a real-time system. It introduces finite, directed, labeled graphs called temporal I/O automata (TA_i/o) to provide a visual means of modeling system behavior. A real-time system is modeled as a collection of communicating TA_i/os. A TA_i/o is associated with an external clock, which makes it possible to formulate hard, real-time constraints on actions performed by a system. Timing constraints provide control engineers with a means of measuring the responsive ness of a system to its environment. This article suggests how real-time temporal logic can be used to describe system behavior concisely. Temporal specifications provide (1) a means of verifying the; correctness of a system design, and (2) a basis for constructing implementations of system designs. The behavior of control systems for autonomous vehicles guided by visual feedback are described graphically with TA_i/oS and textually with temporal logic formulas. Suggestions on how such control systems can be implemented in distributed Ada are also presented.     

实时Java平台的类预处理器研究

设计并实现一种针对32 bit嵌入式实时Java平台的类预处理器,通过把标准class文件转换成适合Java处理器——Jpor32直接执行的内存映像,将在运行时动态装载和解析class的工作交由类预处理器提前完成,从而消除影响运行时实时性的一些操作,并降低Java处理器的设计复杂性。     

LS—RISC指令级功耗模型的开发

针对笔者自主研制的LS-RISC微处理器,讨论了其指令级功耗模型的开发。为了降低指令间效应对功耗分析带来的复杂度,按照指令执行时经过的功能部件,对指令进行重新分类,使得分析的复杂度由O(n2)减小到了O(n)。功耗模型的成功开发,为低功耗编译和软件功耗优化奠定了基础。