软件学报杂志 北大期刊 CSCD期刊 统计源期刊

软件学报 2007年第06期杂志 文档列表

软件学报杂志理论计算机科学

面向语义Web语义表示的模糊描述逻辑1257-1269

摘要：分析了语义Web语义表示理论的研究现状及存在的问题,提出了一种新的面向语义Web语义表示的模糊描述逻辑FSHOIQ（fuzzy SHOIQ）.给出了FSHOIQ的语法和语义,提出了FSHOIQ的模糊Tableaux的概念,给出了一种基于模糊Tableaux的FSHOIQ的ABox约束下的可满足性推理算法,证明了可满足性推理算法的正确性.提出了FSHOIQ的TBox扩展和去除方法,并证明了FSHOIQ的TBox约束下的包含推理问题可以转化为ABox约束下的可满足性推理问题.FSHOIQ为语义Web表示和推理模糊知识提供了理论基础.

并发反应式系统的组合模型检验与组合精化检验1270-1281

摘要：模型检验和精化检验是两种重要的形式验证方法,其应用的主要困难在于如何缓解状态爆炸问题.基于分而治之的思想进行组合模型检验和组合精化检验是应对这个问题的重要方法,它们利用系统的组合结构对问题进行分解,通过对各子系统性质的检验和综合推理导出整个系统的性质.在一个统一的框架下对组合模型检验和组合精化检验作了系统的分析和归纳,从模块检验的角度阐述了上述两种组合验证方法的原理及其相应的组合验证策略.同时总结了各类问题的复杂性,并对上述两种方法作了比较分析,揭示了它们之间的内在联系.最后展望了组合模型检验与组合精化检验的发展方向.

基于量子逻辑的自动机理论的拓扑性质1282-1286

摘要：研究了基于量子逻辑的自动机理论（简称l-值自动机理论）的拓扑性质.给出了successor算子和source算子的另一种定义,讨论了successor算子、source算子和l-值子自动机之间的关系,得到了successor算子、source算子和l-值子自动机的某种等价性.进一步描述了由successor算子、source算子和l-值子自动机来构造拓扑.得出了successor算子、source算子和l-值子自动机的一些基本性质,证明了在＆关于∨分配时,successor算子、source算子以及l-值子自动机的某些特殊性质.因而得到了由它们构造拓扑的一个较弱的条件,并且澄清了三者构造拓扑时的等价性.

软件学报杂志算法设计与分析

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

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

一种基于彩色编码技术的基序发现算法1298-1307

摘要：从DNA序列中发现基序是生物计算中的一个重要问题，序列条数K=20包含基序用例的序列条数k=16的（l，d）-（K-k）问题（记作（l，d）-（20-16）问题）是目前生物学家十分关注的基序发现问题．针对该问题提出了一种基于彩色编码技术的SDA（sample—driven algorithm）搜索算法——彩色编码基序搜索算法（color coding motif finding algorithm，简称CCMF算法）．它利用彩色编码技术将该问题转化为（l，d）-（16—16）问题，再采用分治算法和分支定界法来求解．在解决将（l，d）-（20-16）问题转化为（l，d）-（16-16）问题时，CCMF算法利用彩色编码技术将4845个组合降低到403个着色，这将极大地提高算法的整体运行效率．使用模拟数据和生物数据进行测试的结果表明，CCMF算法能够快速发现所有（l，d）-（20-16）问题的基序模型和基序用例，具有优于其他算法的综合性能评价，能够用于真实的基序发现问题．同时，通过修改着色方案，CCMF算法可以用于求解一般的（l，d）-（K-k）问题，其中，k〈K．

Ad Hoc网络中基于方向性天线的分布式拓扑控制算法1308-1318

摘要：提出了一种基于方向性天线的分布式拓扑控制算法,可以同时通过调整网络中各节点的发射功率和改变节点天线的方向来对网络的拓扑进行控制,每个节点逐渐增大它的发射功率直到该节点在其方向性天线的每个扇区内找到足够数量的邻节点为止.在这种基于方向性天线的分布式拓扑控制算法的基础上又使用了两种不同的拓扑平面化优化算法,进一步删除了拓扑图中多余的交织边,使得网络最终的结构为一幅平坦图.由于每个节点使用了较低的发射功率以及算法形成的网络拓扑图中的平均节点度数较小,从而提高了整个网络的使用寿命,减少了节点间的干扰.仿真结果充分说明了算法的有效性.

背包类问题的并行O（2^5n/6）时间-空间-处理机折衷1319-1327

摘要：将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O（2^n/8）的处理机在O（2^7n/16）的时间和O（2^13n/48）的空间求解n维背包类问题,其时间-空间-处理机折衷为O（2^5n/6）.与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.

软件学报杂志模式识别与人工智能

STRIPS规划领域中动作效果关系的研究1328-1349

摘要：以规划领域中的动作为研究对象,提出了描述动作前提条件和效果之间关系的方法,定义了动作前提和效果之间的基本关系：直接伴随关系、条件伴随关系和直接阻碍关系等,这些基本关系反映了规划动作中所隐含的领域知识.对动作效果的基本关系,定义了进行关系组合的运算,产生出间接阻碍关系和绝对阻碍关系.间接阻碍关系反映出动作前提条件的传递性;绝对阻碍关系表达出实现一个谓词对其他谓词实现的影响.最后给出动作效果关系在规划求解过程中的具体运用,这些动作效果关系为目标实现顺序的排序、目标状态可解性的判定以及动作选择策略的优化等提供了必要的理论依据.

基于平行性约束的摄像机标定与3D重构1350-1360

摘要：引入了梯形的一个仿射不变量,并利用这个不变量,建立了梯形的相似不变量与摄像机内参数之间的约束关系.基于这个约束关系,利用摄像机内参数的知识或梯形相似不变量的知识,可以线性确定摄像机的内参数、运动参数和梯形的相似不变量.由于梯形是由一对平行线段唯一确定的,平行线段在许多场景中经常出现,因而该方法有很广泛的适用性.实验结果表明了该算法的有效性.该工作提供了一个基于平行性约束的框架,以往的基于平行四边形、平行六面体的方法都可以纳入到这个框架中.

一种检测器长度可变的非选择算法1361-1368

摘要：检测器生成是非选择算法的关键步骤.已有检测器生成算法在生成检测器时存在“漏洞”区域和冗余检测器问题.提出了一种检测器长度可变的检测器生成算法,不仅可以消除“漏洞”区域,还可以通过相应的检测器优化算法减少冗余检测器,进而提高检测器生成效率和检测效率.对算法进行了分析和实验证明,结果表明,该算法比传统的非选择算法及r可变的非选择算法具有更好的性能.

基于改进多目标遗传算法的入侵检测集成方法1369-1378

摘要：针对现有入侵检测算法中存在着对不同类型攻击检测的不均衡性以及冗余或无用特征导致的检测模型复杂与检测精度下降的问题,提出了一种基于改进多目标遗传算法的入侵检测集成方法.利用改进的多目标遗传算法生成检测率与误报率均衡优化的最优特征子集的集合,并采用选择性集成方法挑选精确的、具有多样性的基分类器构造集成入侵检测模型.实验结果表明,该算法能够有效地解决入侵检测中存在的特征选择问题,并在保证较高检测精度的基础上,对不同类型的攻击检测具有良好的均衡性.

软件学报杂志数据库技术

P2P持久存储研究1379-1399

摘要：P2P（peer-to-peer）的组织模式已经成为新一代互联网应用的重要形式,它为应用带来了更好的扩展性、容错性和高性能.P2P存储系统一直是研究界所关注的热点,被认为是P2P最具前途的应用之一.数据的持久存储是制约P2P存储系统发展的关键问题,也是其研究的难点.综述了P2P存储系统及数据持久存储相关技术的研究现状.首先概述了P2P存储系统的基本技术组成及其在不同应用环境中的优势,并介绍了数据冗余、数据分发、错误检测和冗余数据维护等多种持久存储的基本技术.在一个P2P存储系统研究框架下,介绍了目前知名的P2P存储系统及其使用的持久存储技术.对各种技术进行了详细综述和对比讨论,分析了各种技术的适应环境及优劣,指出了存在的问题和未来研究的方向.

XML数据的查询技术1400-1418

摘要：XML规范已成为当前网络应用（包括数字图书馆、Web服务以及电子商务）中事实上的数据表达、交换的标准.针对XML数据的查询在当前XML数据管理研究中占有重要的地位,也是当前XML数据处理研究领域的热点方向,相关的研究文献有很多.根据查询模式描述的不同,将当前XML查询技术归入两大类：XML Query方式和XML IR方式.后者又进而可分以为3个子类：XML IR/keyword方式、XML IR/fragment和XMLIR/query方式,并从中挑选出3个研究者关注的问题进行了简述,它们是：Twig查询模式的处理、SLCA（smallest lowest common ancestor）节点的获取以及对所获取的XML片段相似性的度量.以方便普通用户使用为准则探讨了相关XML查询技术的优、缺点,将如下4个问题作为需要进一步关注的研究内容：结构化关键字查询及相应的结构相似性度量方法,如何消除XML Query查询处理模式（包含XML IR/query）和XML IR/keyword查询处理模式间数据冗余的问题,XML Query查询方式的理论探讨及其实现以及针对特定应用的XML数据的有效管理.

基于最大间隙空间映射的高维数据索引技术1419-1428

摘要：在基于高维索引技术的相似性查询处理中,通常通过过滤那些不包含任何查询结果的非活动子空间来不断缩减搜索空间.但是在活动子空间中,有些可能根本就不包含任何查询结果,这样的活动子空间被称为假活动子空间.显然,查询处理性能会随着假活动子空间访问次数的增加而下降.这一问题在高维数据情况下将会变得更加严重,实验显示出随着维数的增加,假活动子空间的访问次数也会增加.为了解决这一问题,提出了一种空间映射方法来减少这种不必要的访问.对于一个给定的查询,可以通过在映射空间内进一步精炼该查询来过滤假活动子空间.为了提高映射空间内查询精炼的处理效率,提出了一个最大间隙空间映射策略——MaxGapMapping.基于这种映射方法,设计并实现了一种新的索引结构——MS-tree,给出了索引的构建算法和范围查询处理算法.最后对MS-tree及其他索引结构的性能进行了详细的比较和分析.

F-Index：一种加速Twig查询处理的扁平结构索引1429-1442

摘要：如何快速、有效地处理twig形式的查询是XML查询处理的关键问题,通过过滤与查询无关的元素可以减少查询中需要处理的元素数目,从而提高查询的执行效率.提出一种扁平结构索引F-Index,能够快速过滤所有与查询无关的索引结点,进而过滤掉查询无关的元素,在处理深度嵌套的复杂结构XML文档时具有很大的优势.提出一种新的查询算法,能够有效处理过滤后剩余元素的匹配问题.基于不同数据集的实验表明,使用F-Index进行过滤可以极大地提高查询处理的性能.

非结构化对等计算系统中多维范围搜索1443-1455

摘要：对等计算数据管理中的一个重要问题是如何有效地支持多维数据空间上的相似性搜索.现有的非结构化对等计算数据共享系统仅支持简单的查询处理方法,即匹配查询处理.将近似技术和路由索引结合在一起,设计了一种简单、有效的索引结构EVARI（扩展近似向量路由索引）.利用EVARI,每个节点不仅可以在本地共享的数据集上处理范围查询,而且还可以将查询转发给最有希望获得查询结果的邻居节点.为了建立EVARI,每个节点使用空间划分技术概括本地的共享内容,并与邻居节点交换概要信息.而且,每个节点都可以重新配置自己的邻居节点,使得相关节点位置相互邻近,优化了系统资源配置,提升了系统性能.仿真实验证明了该方法的良好性能.

一种基于有限编码的多副本分簇管理方法1456-1467

摘要：针对大量数据副本所带来的资源管理问题,提出一种基于有限编码的多副本分簇管理方法.在该方法中,根据单副本复制产生新副本的过程对副本分级和分簇,通过定义“副本级别＋副本顺序”的编码规则对划分后的副本进行编码和组织,并依据编码规则对由于副本的动态调整（增加或撤消）而引起的簇的动态变化进行有效管理.通过该方法,在大量副本之间建立局域集中、广域对等的管理模式,再结合定义的“最小更新传播时间”可以降低大量副本的一致性维护开销.讨论了方法中编码规则与副本规模之间的关系,以及副本失效和恢复时的解决方法.性能测试结果表明,该方法能够有效组织大规模的数据副本,具有较好的可扩展性,对适度的结点失效不敏感,适合更新频繁的应用.

基于数据时态特性的实时事务并发控制1468-1476

摘要：通过对数据时态特性及其对事务调度的影响进行分析,提出了基于数据时态特性的实时事务并发控制算法.该算法根据数据截止期及事务的执行时间估算,改进了事务的验证规则,对事务的提交顺序进行调整,提高了系统的实时性能.理论分析与实验结果表明：该算法降低了事务重启个数及超截止期百分率,性能要优于已有的实时并发控制算法.