一种高效的分辨函数范式转换算法*

基于分辨矩阵获取一个决策表所有约简的过程实质上是一个将分辨函数从合取范式转换为析取范式的过程,其效率对于属性约简算法性能至关重要。依据人工范式转换的运行机制,充分利用合取运算和析取运算的吸收率,并借助队列结构,提出了一种面向分辨函数的范式转换算法。该算法易于理解,实现简便。仿真实验表明算法能够高效地完成范式转换。     

一种基于广义表的HLA乐观时间推进算法

针对保守时间推进机制缺乏灵活性、仿真时间长等问题,研究高层体系结构中的时间管理服务,通过分析和比较,证明乐观时间推进算法可以弥补保守时间推进机制的不足。引入广义表存储结构,实现乐观时间推进机制中的存储和回退等关键技术。测试结果表明,该算法可以减少系统的仿真时间,提高系统的实时性。     

一种数据立方查询条件优化策略

当数据立方查询条件不是合取范式时，一般是将它转化成为若干合取范式的并的形式(析取范式)。但如果各合取范式之间有交集，则交集部分的记录会被多次查询。为了解决这个问题，文章提出了一种数据立方查询条件优化策略，把查询条件转化为互不相交的立方块的并的形式。文章详细地讨论了数据立方中互不相交的立方块的划分方法，并给出了该优化策略的实现算法和性能分析。结果表明，当查询条件不是合取范式时，该优化策略明显提高了查询性能。     

一种新的基于扩展规则的定理证明算法

基于扩展规则的定理证明方法是一种与归结方法互补的新的定理证明方法,首先通过对扩展规则的深入研究,给出了扩展规则的一个重要性质,设计并实现了该性质的判定算法.此外,从理论上分析及证明了该判定算法的时问和空间复杂性.基于此,提出了一种新的基于扩展规则的定理证明算法NER,将判定子句集可满足性问题转化为一系列文字集合的包含问题,而非计数问题.实验结果表明,算法NER的执行效率较原有扩展规则算法IER和基于归结的有向归结算法DR有明显提高,有些问题可以提高两个数量级.     

一种基于前缀广义表的关联规则增量式更新算法

关联规则挖掘是数据挖掘研究的一个重要方面，关联规则的高效维护算法研究是当前研究的热点．传统更新算法与Apriori算法框架一致，要多遍扫描数据库并产生大量的候选项目集．为此，该文对FP-tree进行了改进，引入了前缀广义表——PG-List，并提出了基于PG-List的关联规则挖掘(MARBPGL)与增量式更新算法(IUABPGL)．算法MARBPGL仅须扫描数据库两遍，算法IUABPGL在最坏的情况下仅须扫描原数据库一遍，扫描新增数据库两遍，且两个算法均无须生成候选项目集，避免了产生“知识的组合爆炸”，提高了挖掘和维护的效率．理论分析和实验结果表明该文提出的算法是有效可行的．     

广义表的二叉链式存储表示及其算法设计

在分析广义表(Generalized list)的抽象数据类型定义、特点和存储结构的基础上,提出了广义表的二叉链式存储表示(称之为广义二叉链表,Generalized Binary Linked List,简称GBLL)。广义二叉链表是对广义链表的一种改进,它有利于广义表的推广和应用。此外还给出了若干个基于广义二叉链表的算法设计,并分析了算法的时间复杂性。为减少运行时的内存开销和提高算法的执行效率,大多是采用非递归算法实现。     

一种基于时间戳的简单表缩减算法

表约束是一种外延的知识表示方法,每个约束在对应的变量集上列举出所有支持或禁止的元组.广义弧相容（generalized arc consistency,简称GAC）是求解约束满足问题应用最广泛的相容性.Simple Tabular Reduction（STR）是一类高效的维持GAC的算法.在回溯搜索中,STR动态地删除无效元组,降低了查找支持的开销,并拥有单位时间的回溯代价,在高元表约束上获得了广泛运用,并有大量基于STR的改进算法被提出,其中,元组集的压缩表示是目前研究较多的方法.同样基于动态维持元组集有效部分的思想,为STR提出一种检测并删除无效元组和为变量更新支持的算法,作用于原始表约束并拥有单位时间的回溯代价.实验结果表明,该算法在表约束上维持GAC的效率普遍高于现有的非基于压缩表示的STR算法,并且在一些实例上的效率高于最新的基于元组集压缩表示的STR算法.     

DNA计算机中广义表数据结构的设计与实现

类似于电子计算机,数据结构能帮助DNA计算机合理、高效地组织要处理的信息.文中提出了DNA计算机中广义表的一种设计方法.首先,讨论了k-臂 DNA分子的结构及其在DNA计算中的应用.接着,在讨论了广义表存储结构的同时.给出了广义表两种节点的k-臂 DNA编码的形式描述.最后详细描述了DNA计算机中广义表主要操作的实现算法.这些操作包括初始化空的广义表,创建包含指定元素的广义表和遍历广义表的元素.文中的方法可推广到DNA计算机上其它非线性数据结构.     

求解对称带状广义特征值问题的扩展分治算法

提出了分布式环境下计算对称带状广义特征值问题的一种扩展分治算法,给出了特征值分割定理及其证明．算法在扩展分治的基础上,利用二分压缩结合广义Rayleigh商迭代计算广义特征对．理论分析和数值实验表明,对于窄带宽大规模的广义特征值问题,该分治算法明显优于LAPACK软件包．结合并行性好的多分法,在分布式环境下获得了很好的并行效果．     

一种基于STR算法的新表压缩方法

约束传播是约束编程的关键方法,近些年来,一些约束传播算法中频繁用到简单表缩减(simple tabular reduction, STR)算法来降低约束表的空间消耗,同时提高广义弧相容(generalised arc consistent, GAC)算法的运行速度.短支持方法是在约束传播算法中使用最广泛的一种表压缩方式,但当约束表压缩率较低时,短支持方法提高运行速度效果不明显.因此提出一种压缩约束表的新算法STRO(simple tabular reduction optimization),结合短支持压缩和位操作,在提高STR算法的运行速度的同时压缩表空间效果更好.实验结果表明：在约束表的平均大小不是特别小的情况下,STRO与ShortSTR2,STR2算法相比,速度更快、效率更高;与STRbit算法相比,在时间上可以替代STRbit算法,但STRO算法的表压缩率更大、更加节省空间.     

Gdel区间值逻辑系统的广义拟重言式

吴洪博博士将王国俊教授在R0逻辑系统中的广义重言式理论推广到Gdel逻辑系统中,通过定义两个同构映射,得到其逻辑系统F(S)的一个分划。将这一理论推广到区间值模糊命题逻辑系统中,定义了两个新的区间同构映射,最终得到区间值逻辑系统F(S)的一个分划。     

基于扩展自然序树的概化关联规则增量挖掘方法

概化关联规则挖掘作为数据挖掘领域一个重要的拓展性研究课题,首先提出了一种概化扩展自然序树(generalized extended canonical-order tree,GECT)结构及其增量挖掘算法GECT-IM.该算法对原始分类事务数据库只扫描一次,就可以将所有交易信息映射至一棵压缩格式的GECT,然后通过对更新交易数据集扫描得到更新数据集中各项集的计数,结合相关性质及运算就可以发现大部分更新后的概化频繁项集;其次,针对GECT规模较大以及GECT-IM 算法仍然可能需要遍历初始GECT树的局限,在界定数据库更新和重构概念的基础上,基于一种可量化度量的准最小支持度阈值,提出了一种改进的准频繁概化扩展自然序树(pre-large generalized extended canonical-order tree,PGECT)结构及其增量挖掘算法PGECT-IM.由于有效避免了对初始GECT进行遍历的情形,从而进一步提升了概化关联规则增量挖掘效率.实验证明,提出的概化关联规则增量挖掘算法 GECT-IM 及其优化算法PGECT-IM,比现有增量挖掘算法具有更高的挖掘效率和更好的扩展性.     

Recognition of Simple Enlarged Horn Formulas and Simple Extended Horn Formulas

The enlarged Horn formulas generalize the extended Horn formulas introduced by Chandru and Hooker (1991). Their satisfying truth assignments can be generated with polynomial delay. Unfortunately no polynomial algorithm is known for recognizing enlarged Horn formulas or extended Horn formulas. In this paper we define the class of simple enlarged Horn formulas, a subclass of the enlarged Horn formulas, that contains the simple extended Horn formulas introduced by Swaminathan and Wagner (1995). We present recognition algorithms for the simple enlarged Horn formulas and the simple extended Horn formulas whose complexity is bounded by the complexity of the arborescence-realization problem.     

广义延拓插值模型在RSSI测距方法中的应用

室内无线传感器网络定位通常采用基于信号强度指示RSSI（Received Signal Strength Indicator）的测距方法,但由于室内信号反射、阻挡严重,同时不同硬件之间存在性能差异,导致RSSI随距离的衰减模型难以精确表述。本文提出一种基于广义延拓插值的RSSI测距模型,通过对实测数据进行拟合和插值,构造出能够反映实测环境下的衰减模型,避免了大尺度衰减模型中环境衰减因子难以由经验值给出的问题,同时也减小了不同硬件间的性能差异带来的影响,相比传统的大尺度衰减模型测距精度得到很大改善。     

二值命题逻辑理论的结论类型和分类

以公式真度为基础,研究了二值命题逻辑系统中有限理论逻辑推出的结论类型和分别基于公式真度以及逻辑等价的分类问题,给出了分类定理以及同一理论结论的相似度的一个下界。     

基于自动推理技术的智能规划方法

对几种智能规划方法中利用的逻辑演绎与推理技术予以分析,分别介绍利用命题逻辑的基于可满足性的规划方法与规划系统,利用模态逻辑与析取推理的Conformant规划方法与规划系统,利用非单调逻辑的规划方法和利用模糊描述逻辑的Flexible规划方法,并结合国际规划竞赛和相关论文等的实验结论说明上述方法的有效性和可行性.最后,提出目前基于自动推理技术的智能规划方法所面临的挑战、可能的处理方法以及与之相关的研究热点与趋势.     

基于扩展路径表达式的XML查询

XML查询问题是当前计算机界研究的热点问题之一，国内外学者提出了众多的模型与算法．其中，日本学者Makoto Murata等提出采用扩展路径表达式来表达查询，并利用hedge自动机和字符串自动机进行XML的查询计算．这种方法与采用路径表达式控制的XML查询相比，克服了后者不能充分利用XML文档有序性的缺点．另外，扩展路径表达式具有较强的表达能力，可以表达任何MSO(一元二阶逻辑)查询．因此，扩展路径表达式已作为XML查询问题研究的主要理论框架之一，但是扩展路径表达式的编写比较困难，表达式也比较复杂，导致算法时间复杂度的提高．在扩展路径表达式中引入通配符，使得扩展路径表达式更加简单灵活；同时在查询的计算过程中提出并应用带截止集的自动机提高计算的时间效率．     

Generalized Extended State Observer Based Control for Networked Interconnected Systems with Delays

This paper is concerned with the generalized extended state observer based control for a class of networked interconnected systems with short time‐varying delays. First, the uncertainties induced by the delays are modeled as an additive bounded disturbance. Then, a novel state feedback stabilizing controller is designed based on generalized extended state observers (GESOs). The GESO is used to estimate the system state and the disturbance simultaneously, and the effect of the uncertainty induced by the delay is eliminated by the GESO based controller. Finally, an illustrative example is provided to verify the effectiveness of the proposed method.