计算主动数据库中不可归约规则集的有效算法

主动数据库中规则集的可终止性判定是一个重要问题,已经成为一个研究热点．有些研究工作提出了在编译阶段运用触发图和活化图的方法解决这个问题,其中的一个关键技术就是计算主动规则集的不可归约规则集．现有的计算方法由于具有一定保守性,使得计算出的不可归约规则集仍可进一步地归约,这无疑将影响到规则集的可终止性判定的准确性和运行阶段规则分析的效率．经过深入分析活化规则可无限执行的特点,提出了活化路径等概念．基于这些概念,提出了一个计算主动规则集的不可归约规则集的有效算法,使现有方法求得的不可归约规则集得到进一步的归约．     

大数据上函数查询解答的复杂度分析

函数查询是大数据应用中重要的操作,查询解答问题一直是数据库理论中的核心问题。为了分析大数据上函数查询解答问题的复杂度,首先,使用映射归约方法将函数查询语言归约到已知的可判定语言,证明了函数查询解答问题的可计算性;其次,使用一阶语言描述函数查询,并分析了一阶语言的复杂度;在此基础上,使用NC-factor归约方法将函数查询类归约到已知的\mathrm{\Pi }{\mathrm{{\rm T}}}_Q-complete类中。证明函数查询解答问题经过PTIME（多项式时间）预处理后,可以在NC（并行多项式-对数）时间内求解。通过以上证明可以推出,函数查询解答问题在大数据上是可处理的。     

单分支线性约束循环程序的终止性分析

秩函数法是循环终止性分析的主要方法,秩函数的存在表明了循环程序是可终止的.针对单分支线性约束循环程序,提出一种方法对此类循环的终止性进行分析.基于增函数法向空间的计算,该方法将原程序空间上的秩函数计算问题归结为其子空间上的秩函数计算问题.实验结果表明,该方法能有效验证现有文献中大部分循环程序的终止性.     

含有非独立型触发环的主动规则集归约算法研究

可终止性判定问题是主动数据库的一个核心问题。现有的研究工作提出了运用触发图和活化图的方法解决这个问题,其中的一个关键技术就是利用归约算法对主动规则集进行归约。已有的计算方法对一些可归约规则无法识别。本文提出了独立型触发环、非独立型触发环、活化路径、禁止活化环、禁止活化规则等概念。基于这些概念,提出了一个新的归约算法,从而可识别出更多的可归约规则。     

函数式语言FP中并行的开发和控制

函数式语言的突出特点是特别适合于并行处理.本文着重讨论函数式语言——FP在多处理机系统中并行实现的方法.文中的FP语言是在John Backus’FP的基础上增加了流的功能和类型定义.在[1,2]原有的理论基础上,提出了一个改进的结合LE计值语义的多步向前驱动法.LE计值中由于引进了延迟对象,使得延迟计值统一为函数对对象的作用,因而简化了编译系统的代码生成.多步向前驱动法是一种结合需求驱动和数据驱动的方法,该方法在开发了尽可能多的并行的同时,又保证了程序并行归约的终止性.根据这些方法,一分布式内存的多处理机软件模拟系统已在MIC-VAX Ⅱ上实现.文中最后给出了一些实验数据,这些数据有力地证明了多步向前驱动法的有效性,从而揭示了函数式语言并行处理是一非常有发展前途的研究方向.     

一种基于算法骨架的函数式程序变换技术

如何提高函数式程序设计语言在传统冯·诺依曼机器上的执行速度.及效率,一直是该领域中研究的主要论题,对此,并行图归约技术、并行闭包归约、并行编译、并行程序转换等等技术相继成为改善这种状况的措施。     

有界闭区间并上的非线性循环程序的终止性验证

利用符号动力学理论中有关一维离散映射的函数和区间的转换图方法及相关结论,证明一类非线性循环程序不终止的必要条件是在该程序循环区间上有不动点或者周期点存在,并给出相应的终止性验证算法.利用该算法可以验证一维有界闭区间上的非线性循环程序的终止性.最后,给出计算实例演示该算法的算法步骤.     

用于求解正则(3,4)-SAT实例集的修正警示传播算法

利用极小不可满足公式的临界特性,可以将任意的一个3-CNF公式多项式时间归约转换为一个正则(3,4)-CNF公式,从而得到一个保留NP完全性的正则(3,4)-SAT问题。警示传播算法(Warning Propagation,WP)在归约转换后的正则(3,4)-SAT实例集上高概率收敛,但在任意一个实例上都无法判断公式的可满足性,因此算法求解失效。对于一个归约转换后的正则(3,4)-CNF公式,每一变元出现的正负次数之差具有趋于稳定的结构特征,基于该特征,提出基于变元正负出现次数规则的WP算法来求解归约转换后的正则(3,4)-SAT实例。实验结果表明,修正的WP算法对正则公式的可满足性判定有效,从而可以利用公式的正则性特征进一步研究WP算法的收敛性特征条件。     

循环程序的界函数合成

作为循环程序终止性分析的主流方法,当前的秩函数方法大多局限于线性或多项式秩函数的求解.针对循环程序若不存在对应的线性或多项式秩函数,现有秩函数方法就无法证明其终止性的问题,提出一个新的方法来合成给定循环程序对应的界函数.对于给定的循环程序,倘若能找到其界函数,则表明该循环程序是可终止的.首先将界函数的求解问题转化为一个...     

基于Tversky参数化的犹豫模糊集相似性测度研究

针对传统的犹豫模糊集相似性测度对原始数据信息处理不全面的问题,提出一种基于Tversky参数化比率相似性模型的犹豫模糊集相似性测度函数,分析其差异化系数在不同需求情况下的转换形式,并运用于犹豫模糊信息的聚类分析。新的相似性测度函数一方面可避免因添加或取特定的值而导致原始数据信息不准确,另一方面通过对差异化系数的赋值,得出多组可供比较的相似性结果,体现出相似性测度函数良好的动态性和数值的精确性。     

基于灰度特征的一致性弹性配准算法

医学图像配准算法中,基于灰度的弹性配准方法具有自动化程度高的优点,但是灰度对应性的模糊容易导致误配准.提出一种利用局部互相关系数作为相似性测度的灰度一致性配准算法.该算法在相似性测度函数中将前向变换和后向变换联系起来,把局部互相关系数的和作为相似性测度函数,并通过在局部互相关系数相似性测度中引入一致性约束条件,有效地确保了前向变换和后向变换的互逆性,同时进一步增强了待配准图像灰度的对应性.     

一种快速组合算子归约模型FCRM

本文在分析了Turner归约模型中组合算子表达式的膨胀原因后,提出了一种快速组合算子归约模型FCRM。本文描述了FCRM的形式体系、转换规则T和归约规则R_c,并且证明和验证了FCRM组合算子表达式的长度一般为Turner表达式的3/4,而FCRM模型的归约路径仅为Turner模型的一半。     

基于GPU_CPU异构并行加速的人头检测方法

多尺度协同的人头检测系统中,梯度方向直方图应用于高清视频监控领域时常因特征提取时的海量计算而不能满足监控视频的实时性要求,提出一种基于GPU_CPU异构并行加速的人头检测方法,GPU端负责HOG特征提取的庞大的密集型的区块的并行计算,CPU端负责检测过程中的其它模块的执行.传统的并行归约算法因其在HOG特征提取过程中的时间复杂度不够理想,提出改进的并行归约算法,通过“下扫”的并行计算方式,减少节点被计算的次数,降低了HOG特征提取时的时间复杂度.实验表明,提出的方法检测速率优于传统的CPU的检测方法,其效率提升约10倍.     

基于SVM的多项式循环程序秩函数生成

程序终止性问题是自动程序验证领域中的一个研究热点.秩函数探测是进行终止性分析的主要方法.针对单重无条件分支的多项式循环程序,将其秩函数计算问题归结为二分类问题,从而可利用支持向量机（SVM）算法来计算程序的秩函数.与基于量词消去技术的秩函数计算方法不同,该方法能在可接受的时间范围内探测到更为复杂的秩函数.     

基于向量角分解的高维多目标进化算法

选择是进化的主要驱动力,也是多目标进化算法的关键特征,然而,在处理高维多目标问题时,随着目标维数的增加种群的收敛性和分布性的冲突加剧,传统多目标进化算法中的选择算子已难以有效地维持种群的收敛性与分布性之间的平衡.针对该问题,提出一种基于向量角分解的高维多目标进化算法.首先,将个体本身作为参考向量,利用目标向量之间的夹角作为个体的相似度测度估计种群分布性,以减轻算法预先指定权重向量的负担;然后,利用成绩标量函数作为个体的收敛性测度,该收敛测度在引导种群走向Pareto最优前沿方面发挥着重要作用;最后,提出一种基于向量角分解的精英选择策略,其在环境选择过程中利用向量角信息将目标空间动态分解,并利用成绩标量函数从分布性较好的区域中挑选较好的个体进入下一代,能够动态地平衡种群的收敛性和分布性.对比实验结果表明,所提出算法具有较强的竞争力,其在保持种群分布性的同时具有足够的选择压力,能够有效地引导高维目标空间的搜索.     

基于深度学习和反例制导的循环程序秩函数生成

程序终止性判定是程序分析与验证领域中的一个研究热点. 针对非线性循环程序, 提出了一种基于反例制导的神经网络型秩函数的构造方法. 该方法采用学习组件和验证组件交互的迭代框架, 其中学习组件利用程序轨迹作为训练集合构造一个候选秩函数, 验证组件运用可满足性模理论(Satisfiability Modulo Theories, SMT)确保候选秩函数的有效性, 而由SMT返回的反例则进一步用于扩展学习组件中的训练集合以对候选秩函数进行精化.实验结果表明, 所提出的方法比已有的机器学习方法在秩函数的构造效率和构造能力上具有优势.     

一种新型多目标智能加权灰靶决策模型

提出一种新的多目标加权灰靶决策模型.针对具有满意域的效益型、成本型和适中型等不同性质的决策目标,构造出效益型目标效果测度、成本型目标效果测度、适中型目标下限效果测度、适中型目标上限效果测度等4种新型一致效果测度函数.据此可将具有不同意义、不同量纲、不同性质的决策目标转换为一致效果测度,从而能够方便地求出综合效果测度矩阵.将灰靶临界值设计为一致效果测度函数的正负分界点(即零点),充分考虑了目标效果值中靶和脱靶两种不同情形,物理涵义清晰,综合效果测度的分辨率也大大提高.     

在PROLOG中嵌入函数型语言功能的探讨与比较

本文指出在PROLOG中嵌入函数功能有三种可能的途径,一是像原PROLOG的办法将函数唯一地变换成关系。二是采用一步归约的办法。三是采用N步归约的办法。本文在PROLOG中给出了后两种办法的具体算法,具体地分析了三种办法的利弊,提出了如何嵌入函数型语言功能的建议。文中算法均用LISP语言描述并且在计算机上实现了。     

非定向军事路网交通流隐蔽性测度及分配模型

为了解决原有军事路网隐蔽性测度模型中存在的不同运量在相同路况下隐蔽性测度值相等的悖论, 以及路网定向性导致分配非最优两方面缺陷, 本文在对隐蔽性测度方法进行修正以及对非定向军 事路网三方面性质(始点终点相连路段的定向性、路网的可转换性、中点相连路段的后定向性) 详细分析的基础上,提出了一个基于隐蔽性测度修正方法的非定向军事路网交通流分配模型, 并针对模型在计算过程中可能出现的循环流现象提出了逐步去环的解决方法.最后,通过算例证 实了非定向路网三方面性质及计算中可能存在的循环流现象,计算过程和结果充分说明新模型的可行性与实用性.     

基于迭代轨迹划分的单分支循环程序终止性分析

秩函数作为循环程序终止性分析的重要方法已得到广泛研究。文中着重研究了单分支循环的终止性。首先提出了双向迭代循环概念，将单分支循环分为双向迭代循环和非双向迭代循环。其次，针对双向迭代循环程序，建立了一种划分思路，提出了三段式秩函数的概念，并证明了若该双向迭代循环存在三段式秩函数，则其是终止的。而对非双向迭代循环，引用增函数的划分思路，即利用增函数将原程序空间划分为更小的空间，并通过计算更小空间上的秩函数来证明原程序的终止性。最后，将三段式秩函数的计算问题归结为SVM分类问题，并利用工具Z3或bottema对由SVM所得的候选秩函数进行验证。