面向对象类簇级测试中控制依赖分析方法研究

类簇控制依赖信息是进行类间数据流测试的基础。本文通过克服已有类控制流分析的不足之处,提出了CCFG算法,依照类间测试序,通过分析继承、聚集和关联等类间关系特 征进而增量式地构造类间控制流图（ICCFG算法）,并初步探讨了动态控制依赖分析方法。实验表明,上述控制流分析方法可方便地用于类间数据流测试,并能有效地探测定义一使用错误。     

一种类间测试顺序改进算法

确定类的测试顺序是面向对象程序测试中的关键步骤。描述对象关系图模型,提出一种基于对象关系图的类间集成测试顺序改进算法,与Tai和Traon等人提出的算法相比,该算法需要的测试桩较少、效率较高。在Redflag4系统下用Kylix3(C++)对算法进行实现。理论分析和初步实验证明了该算法的可行性和有效性。     

一种面向对象类间关系测试方法

面向对象软件的一个突出特点就是存在于类间的复杂依赖关系:继承、聚合和关联。提出了一种测试类间关系的方法,自动从UML图或源代码中导出类间的三种关系,并给出了相应的类间关系图和各个类的测试次序的类簇测试算法。该算法导出的类间关系可用于类间的静态和动态依赖关系测试。     

面向对象软件的依赖性分析与回归测试

针对面向对象软件中类之间复杂的依赖性问题,通过分析UML类图中类之间的各种静态关系,提出一个基于UML类图的依赖性分析模型。为了实现自动化分析,引入了类依赖关系图的概念,并提出一个基于UML类图导出的XMI文件的类依赖关系图生成算法。根据这个模型,通过分析一个类或依赖关系的改变对其他类产生的影响,提出测试路径查找算法,并利用此算法得到需要进行回归测试的类集与测试序列。     

类测试顺序的研究

讨论了Tai.Daniel与Briand两种常用的集成测试生成策略,针对其在主要测试层次中忽略了关联关系以及类存根重用率低的问题,提出基于类测试顺序的增量类测试.最后,通过对ADS的测试,验证其优越性.     

基于扩展ORD图的类间集成测试顺序改进算法

在UML类图的基础上,将传统对象关系图(ORD)模型进行了扩展,并对它们进行了形式化的定义.提出了一种基于扩展ORD图的类间集成测试顺序改进算法,通过递归调用改进的Kosaraj鉴别强连通分量的算法来确定SCCs.本算法与Tai和Traon的两种算法比较,需要的测试桩最少,效率最高.理论分析和初步的实验证明这种方法是可行和有效的.     

一种用于类测试的新方法

面向对象程序的复杂性和类对象间广泛的相互依赖性使得对这样的程序的测试变得非常困难,而类又是面向对象测试中最基本的单元。对类的测试又可以分为3个级别(方法内测试,方法间测试,类内测试),难点主要集中在类内测试上。文章提出一种基于OSD(对象状态图)的新的算法用来产生进行类内测试的方法调用序列。这种算法是对传统的类测试的两种方法基于规格说明的测试和数据流测试的综合,可以使产生测试用例的复杂度大大的降低。     

分支测试中测试路径用例的简化生成方法

结构性测试是对过程式和面向对象程序都非常有效的测试方法,分支覆盖准则被实践证明是其中性价比最高的一种策略．通过深入研究DD图的性质并分析FTPS算法的不足,提出了一种简便、快捷和适合于大规模程序的非约束边集近似求解算法Find_SemiUE;还给出了基于正（逆）向广度（深度）生成树的分支测试路径用例集的简化生成算法Generate_PathSet,该算法在时间和空间开销上较FTPS算法均有较大提高．此外,所证明的关于DD图的结论也值得借鉴用于该图的更深一步研究．     

一种新的面向对象软件集成测试序列生成方法

集成测试是面向对象软件测试中的重要环节。UML不仅在软件分析领域具有重要作用,同时是软件测试的有力依据。在本文中,提出了一种以UML类图为基础的面向对象软件集成测试的测试序列生成方法。从UML类图中提取类的所有信息。然后依据提取的信息计算每个类的内聚度和类间耦合度,将计算结果存入数据库中。最后根据计算的类间耦合度与类的内聚度从高到低对类进行遍历。最后生成集成测试时的类测试序列。经证明该方法对于软件有较好效果。     

一种基于UML的多态性测试线索生成方法

首先分析了多态性的成因及形式化表示;然后借用控制流图的思想分析协作图,将类图中的信息结合到协作图中,对传统的函数间受限控制流图IRCFG进行多态性扩展并带上类图的基本信息;最后分析了测试覆盖准则并给出测试线索的生成方法。     

基于最小路径交叉度的域内路由保护方案

已有的路由保护方案面临下面两个问题：（1）默认路径和备份路径包含的公共边数量较高,如ECMP和LFA等;（2）为了计算两条包含公共边数量较少的路径,限制默认路径不能使用最短路径,如红绿树方案等.针对上述两个问题,首先将计算默认路径和备份路径描述为一个整数规划问题,然后提出采用启发式方法求解该问题,接着介绍了转发算法,最后通过仿真实验和真实实验对算法进行了测试.实验结果表明,该算法不仅具有较低的计算复杂度,而且可以降低默认路径和最短路径包含的公共边的数量,提升网络可用性.     

自适应快速FCM彩色图像分割研究

模糊C均值聚类算法（FCM）广泛用于彩色图像分割,但该算法存在需要预先指定聚类数目、计算量大、耗时长且易陷入局部最优等缺点。提出一种自适应快速模糊C均值彩色图像分割方法,该方法首先运用蚁群算法,自动获取初始聚类中心和聚类数目,然后使用基于梯度的分水岭算法对原始彩色图像进行预分割,得到一系列由色彩特征空间具有一致性的点构成的子集,最后对这些子集的中心进行模糊聚类。实验结果表明：由于子集数量远小于原始图像像素数目,使聚类样本数量显著减少,大大提高了聚类速度,同时在聚类中以特征距离代替欧式距离,增强了算法的鲁棒性。     

H.264帧内4×4块预测模式选择快速算法研究

在H．264视频编码过程中，编码时间受诸多因素的影响，如帧间／帧内模式选择、运动估计（ME）、率失真优化（RDO）等。为了以较快速度和较好质量进行编码，针对H．264帧内模式选择，提出了一种适用于H．264帧内4×4块预测的模式选择快速算法。该算法利用帧内4×4块最优预测模式与和它相邻的预测模式之间率失真代价（RDCost）的高相关性，以及绝对变换误差和（SATD）与率失真（RD）性能之间的强相关性，有效地跳过一些不太可能的预测模式，从而使帧内4×4块模式选择过程只需进行4次率失真代价计算即可。实验结果显示，该算法在编码性能和编码速度之间取得了很好的折衷。     

基于多类指数损失函数逐步添加模型的改进多分类AdaBoost算法

多类指数损失函数逐步添加模型（SAMME）是一种多分类的AdaBoost算法,为进一步提升SAMME算法的性能,针对使用加权概率和伪损失对算法的影响进行研究,在此基础上提出了一种基于基分类器对样本有效邻域分类的动态加权AdaBoost算法SAMME.RD。首先,确定是否使用加权概率和伪损失;然后,求出待测样本在训练集中的有效邻域;最后,根据基分类器针对有效邻域的分类结果确定基分类器的加权系数。使用UCI数据集进行验证,实验结果表明：使用真实的错误率计算基分类器加权系数效果更好;在数据类别较少且分布平衡时,使用真实概率进行基分类器筛选效果较好;在数据类别较多且分布不平衡时,使用加权概率进行基分类器筛选效果较好。所提的SAMME.RD算法可以有效提高多分类AdaBoost算法的分类正确率。     

Reclassification as supervised clustering

In some branches of science, such as molecular biology, classes may be defined but not completely trusted. Sometimes posterior analysis proves them to be partially incorrect. Despite its relevance, this phenomenon has not received much attention within the neural computation community. We define reclassification as the task of redefining some given classes by maximum likelihood learning in a model that contains both supervised and unsupervised information. This approach leads to supervised clustering with an additional complexity penalizing term on the number of new classes. As a proof of concept, a simple reclassification algorithm is designed and applied to a data set of gene sequences. To test the performance of the algorithm, two of the original classes are merged. The algorithm is capable of unraveling the original three-class hidden structure, in contrast to the unsupervised version (K-means); moreover, it predicts the subdivision of one of the original classes into two different ones.     

Almost Exact Matchings

In the exact matching problem we are given a graph G, some of whose edges are colored red, and a positive integer k. The goal is to determine if G has a perfect matching, exactly k edges of which are red. More generally if the matching number of G is m=m(G), the goal is to find a matching with m edges, exactly k edges of which are red, or determine that no such matching exists. This problem is one of the few remaining problems that have efficient randomized algorithms (in fact, this problem is in RNC), but for which no polynomial time deterministic algorithm is known. Our first result shows that, in a sense, this problem is as close to being in P as one can get. We give a polynomial time deterministic algorithm that either correctly decides that no maximum matching has exactly k red edges, or exhibits a matching with m(G)?1 edges having exactly k red edges. Hence, the additive error is one. We also present an efficient algorithm for the exact matching problem in families of graphs for which this problem is known to be tractable. We show how to count the number of exact perfect matchings in K _3,3-minor free graphs (these include all planar graphs as well as many others) in O(n ^3.19) worst case time. Our algorithm can also count the number of perfect matchings in K _3,3-minor free graphs in O(n ^2.19) time.     

A constant approximation algorithm for the densest k-subgraph problem on chordal graphs

The densest k-subgraph (DkS) problem asks for a k-vertex subgraph of a given graph with the maximum number of edges. The DkS problem is NP-hard even for special graph classes including bipartite, planar, comparability and chordal graphs, while no constant approximation algorithm is known for any of these classes. In this paper we present a 3-approximation algorithm for the class of chordal graphs. The analysis of our algorithm is based on a graph theoretic lemma of independent interest.     

确定两个任意简单多边形交、并、差的算法

提出了把多边形的边分为奇偶边的新思想，根据输入多边形A，B之间边的拓扑关系，划分A，B边为内边、外边、重叠边3种，揭示A，B与它们的交、并、差之间边的本质联系，进而描述了确定任意两个简单多边形交、并、差算法．算法的时间复杂度为O((n m k)log(n m k))，其中n，m分别是A，B的顶点数，k是两多边形的交点数．算法建立在数学理论基础之上，很好地处理了布尔运算的奇异情形，比如重叠边，边与边相交于边的顶点等情形．本算法易于编程实现。     

基于粗糙数据推理的TextRank关键词提取算法

基于图模型的TextRank算法是一种有效的关键词提取算法,在提取关键词时可取得较高准确度。但该算法在构造图的关联边时,所采用的共现窗口规则仅考虑了局部词汇间的关联,并具有较大随意性与不确定性。针对这一问题,该文提出了一种基于粗糙数据推理理论的改进TextRank关键词提取算法,粗糙数据推理可扩大关联范围,增加关联数据,得到的结果更加全面。结合粗糙数据推理理论中的关联规则,该文提出的算法做了以下改进: 依据词义对候选关键词进行划分;再通过粗糙数据推理对不同分类中候选词间的关联关系进行推理。实验结果表明,与传统的TextRank算法相比,改进后算法的提取精度有了明显的提高,证明了利用粗糙数据推理的思想能有效地改善算法提取关键词的性能。     

一种基于关联分析的KNN文本分类方法

KNN算法在数据挖掘的分支-文本分类中有重要的应用。在分析了传统KNN方法不足的基础上,提出了一种基于关联分析的KNN改进算法。该方法首先针对不同类别的训练文本提取每个类别的频繁特征集及其关联的文本,然后基于对各个类别文本的关联分析结果,为未知类别文本确定适当的近邻数k,并在已知类别的训练文本中快速选取k个近邻,进而根据近邻的类别确定未知文本的类别。相比于基于传统KNN的文本分类方法,改进方法能够较好地确定k值,并能降低时间复杂度。实验结果表明,文中提出的基于改进KNN的文本分类方法提高了文本分类的效率和准确率。