求解二维矩形Packing问题的完备算法

对于典型的NP难度问题——二维矩形Packing问题,经典完备算法的计算复杂度不仅与待放块的数目相关,也与矩形框的宽和高相关。通过观察二维矩形Packing问题的合法布局的特点,将其与一对有向无环图相对应,并基于Prüfer码进行编码,提出了一种计算复杂度仅与待放块数相关的复杂度较低的完备算法。     

一种基于主题建模的代码功能挖掘工具

代码复用是重要的软件复用方式之一,复用者需要理解软件代码实现的功能方能有效实施软件复用。基于主题建模技术的程序理解方法逐渐受到研究人员的重视,它能够帮助软件开发者和使用者更好地理解软件的功能。目前,基于主题建模技术的程序理解方法一般欠缺对挖掘出的Topic的语义分析,为此提出的基于代码静态分析和LDA技术的代码功能挖掘(Code Function Mining,CFM)方法可作为对这类方法的补充。CFM是一套以代码为研究对象的挖掘、筛选、组织和描述主题(Topic)的方法,该方法能够生成带描述的功能型Topic的层次结构,以供使用者更清晰和方便地浏览、学习软件的功能。功能型Topic的描述能够帮助复用者理解代码功能,其层次结构能够让复用者从不同抽象层次理解代码功能。CFM方法包括4个部分:挖掘Topic、筛选Topic、组织Topic、描述Topic。以CFM方法为基础,设计并实现了一个CFM工具。CFM工具能够分析用户提交的代码,通过Web页面向用户展示带描述的功能型Topic的层次结构。最后,对CFM方法中的几个关键算法进行实验分析,验证了CFM方法的有效性。     

一种改进的小波域图像修复算法

针对全变分小波图像修复算法在平滑区易产生阶梯效应并且噪声抑制不充分的缺陷,提出一种新颖的小波域图像修复模型。通过优化一个全变分和图像梯度的二范数的能量泛函来实现小波域的图像修复,使得在去除噪声的同时较好地保留了图像的边缘,在平滑区域削弱了阶梯效应,并利用有限差分法对所建立的扩散方程进行数值求解。实验结果表明:所提方法对于不同丢失比例的图像以及噪声图像都取得了较好的修复效果,尤其当小波系数丢失率较高时更为明显。     

基于逐层剪枝的中文高频重复模式快速提取算法

为了从大规模语料中快速提取高频重复模式,以递增n-gram模型为基础,使用散列数据结构提取重复串,并提出了一种基于低频字符和层次剪枝的逐层剪枝算法,用于过滤低频垃圾字串,减少I/O读写次数。在此基础上,应用改进的字串排序算法,使字符串排序可在O(n)时间内完成,从而有效提高重复模式的提取效率。实验表明,该算法是一种有效的重复模式提取算法,其I/O读写次数同语料规模呈线性关系,远小于使用首字符进行语料划分的方法,能快速有效地从规模远大于内存容量的文本语料中提取重复模式,特别适合于大规模语料的高频重复模式提取,对以重复模式为基础的新词识别、术语抽取等具有重要的支撑作用。     

基于随机优势关系的区间值信息系统

在区间值信息系统中引入了分布函数,得到了基于随机优势关系的区间值信息系统,构造了区间值信息系统的α-随机优势关系。利用Levy距离,对α-随机优势关系进行了计算,实例说明了方法的有效性。     

Progressive events in supervisory control and compositional verification

This paper investigates some limitations of the nonblocking property when used for supervisor synthesis in discrete event systems. It is shown that there are cases where synthesis with the nonblocking property gives undesired results. To address such cases, the paper introduces progressive events as a means to specify more precisely how a synthesised supervisor should complete its tasks. The nonblocking property is modified to take progressive events into account, and appropriate methods for verification and synthesis are proposed. Experiments show that progressive events can be used in the analysis of industrial-scale systems, and can expose issues that remain undetected by standard nonblocking verification.     

基于约束关系的变强度组合测试用例集生成算法

针对传统的变强度组合测试方法对系统中各因素之间的约束关系考虑不足,从而可能导致测试用例冗余的问题,论文提出了一种基于one-Test-at-a-time策略的变强度组合测试用例集生成算法,该算法充分考虑了因素间的约束关系,从而在一定程度上减少了测试用例集的规模。最后通过实验验证了算法的可行性和有效性。     

关于流体模拟细节增强技术的研究

基于物理的流体动画技术一直是计算机图形学领域研究的重点,但是之前大多数研究一直针对的是如何对流体模拟进行加速,而文章对于如何更加精细的模拟流体做了全面的综述,重点从模拟方法、界面重构、边界控制及算法优化方面做了介绍与分析.     

一种分层式无线传感器网络密钥分配管理方案

当传感器节点部署在开放的、无人照看、无物理保护的环境下,安全问题变得非常重要,即它们极易受到不同类型的恶意攻击.论文针对分层组织的无线传感器网络提出了一种安全的密钥管理方案,这种方案在一个簇中高效地分配密钥并更新预先部署的密钥以减轻对节点的有害攻击.     

基于静态分析的函数调用关系研究

为了帮助研发人员理解复杂系统的架构,通过对源码进行静态分析,在此基础之上,重点对函数调用关系进行研究,并且基于开源编译器ncc实现了函数调用关系的解析.实验结果表明该方法可以有效地获取函数的调用关系且准确地解析钩子函数对应的回调函数.