程序复杂性度量

本文力图阐明程序复杂性度量的有关定义研究内容、技术和方法，并探讨它用软件产品的质量、交付的时间和费用的关系以及它在软件开发中的作用。     

On a Nearest-Neighbor Problem Under Minkowski and Power Metrics for Large Data Sets

The paper presents the sequential and the parallel algorithm for solving the nearest-neighbor problem in the plane, based on the generalized Voronoi diagram construction. The applications of the problem are found in the areas of networking, communications, distributed systems, computer modeling and information retrieval. The input for the problem is the set of circular sites S with varying radii, the query point p and the metric (Minkowski or power) according to which the site, neighboring the query point, is to be reported. The sequential algorithm takes O(n) time to build the data structure and O(log n) time for each query. The parallel algorithm requires O(log n log) preprocessing time and O(log) query time on EREW PRAM architecture with n/log n processors. The IDG/NNM software was developed for an experimental study of the problem. The experimental results demonstrate that the Voronoi diagram method outperforms the k – d tree method for all tested input configurations. The tests were conducted on large data sets, comprising thousands of generators.     

On the Complexity of Matroid Isomorphism Problem

We study the complexity of testing if two given matroids are isomorphic. The problem is easily seen to be in S₂^p\Sigma_{2}^{p}. In the case of linear matroids, which are represented over polynomially growing fields, we note that the problem is unlikely to be S₂^p\Sigma_{2}^{p}-complete and is co NP-hard. We show that when the rank of the matroid is bounded by a constant, linear matroid isomorphism, and matroid isomorphism are both polynomial time many-one equivalent to graph isomorphism.     

程序复杂性度量的一种新方法

通过分析传统的程序复杂性度量方法的不足之处,首先提出了一种基于程序分解机制的路径复杂性度量方法,然后给出了计算路径复杂度的算法,最后给出了实例。新的度量方法指出了一个程序需要的完全测试路径数目。     

构件软件的回归测试复杂性度量

基于构件的软件构建方法目前被广泛使用在软件开发中,用于减少软件开发的工程成本和加快软件开发进度.在软件维护过程中,由于构件更新或者新版本的发布,基于构件的系统会受到影响,需要进行回归测试.对于指定的软件修改需求,维护者可以实施不同的修改手段.不同的修改手段会导致不同的回归测试复杂性,这种复杂性是软件维护成本和有效性的重要因素.目前的研究没有强调构件软件的回归测试复杂性问题.基于修改影响复杂性模型和度量,提出一种回归测试的复杂性度量框架.该度量框架包括两个部分:基于图的模型和形式化度量计算.该度量可以有效表示构件软件分别在构件和系统层面的回归测试复杂性因素,可视化地体现复杂性变化.然后根据模型,提出具体的度量计算方式.最后,通过实验研究,针对同一个构件软件的相同修改需求,利用若干个实验组进行独立修改实施,然后比较回归测试的复杂性.实验结果表明,所提出的度量方式是可行和有效的.     

Detecting Distributed Denial-of-Service Attacks Using Kolmogorov Complexity Metrics

This paper describes an approach to detecting distributed denial of service (DDoS) attacks that is based on fundamentals of Information Theory, specifically Kolmogorov Complexity. A theorem derived using principles of Kolmogorov Complexity states that the joint complexity measure of random strings is lower than the sum of the complexities of the individual strings when the strings exhibit some correlation. Furthermore, the joint complexity measure varies inversely with the amount of correlation. We propose a distributed active network-based algorithm that exploits this property to correlate arbitrary traffic flows in the network to detect possible denial-of-service attacks. One of the strengths of this algorithm is that it does not require special filtering rules and hence it can be used to detect any type of DDoS attack. We implement and investigate the performance of the algorithm in an active network. Our results show that DDoS attacks can be detected in a manner that is not sensitive to legitimate background traffic.This research has been funded by the Defense Advanced Research Projects Agency (DARPA) contract F30602-01-C-0182 and managed by the Air Force Research Laboratory (AFRL) Information Directorate.General Electric Global Research Center, Niskayuna, New York.     

The Use of Software Complexity Metrics in Software Maintenance

This paper reports on a modest study which relates seven different software complexity metrics to the experience of maintenance activities performed on a medium size software system. Three different versions of the system that evolved over a period of three years were analyzed in this study. A major revision of the system, while still in its design phase, was also analyzed.     

数据库应用软件交互复杂性度量研究

依据软件度量的思想和方法,提出数据库应用软件交互复杂性度量的概念。利用4个指标参量表征应用程序与数据库管理系统的交互过程,根据软件测试需要为指标指定权重向量,并通过指标向量与权重向量的乘积将4个指标归一化为一个复杂性度量值。通过实例验证表明,该方法能够客观、准确、灵活地度量数据库应用软件交互过程复杂性。     

基于熵的信息系统业务模型复杂性度量

业务模型的复杂度决定企业信息系统的复杂度,也对信息系统的重构性能具有很大程度的影响。目前研究多侧重于代码级软件的复杂度度量,而对业务模型的复杂度则关注较少。本文首先给出了企业业务模型的分层体系结构,依据模型实体之间的依赖关系与分解关系将业务模型分解为一组基本模型单元。然后重点提出一种基于熵的模型复杂性度量方法,使用信息熵来描述业务模型的复杂性,通过计算基本模型单元的复杂度递归得到各模型实体、依赖关系的复杂性,进而综合得到模型的复杂性。最后通过实际案例验证了此方法的可行性。该方法为信息系统的设计与构造过程提供了有效的参考与决策依据。     

The Complexity of the Empire Colouring Problem

We investigate the computational complexity of the empire colouring problem (as defined by Percy Heawood in Q. J. Pure Appl. Math. 24:332–338, 1890) for maps containing empires formed by exactly r>1 countries each. We prove that the problem can be solved in polynomial time using s colours on maps whose underlying adjacency graph has no induced subgraph of average degree larger than s/r. However, if s≥3, the problem is NP-hard even if the graph is a for forests of paths of arbitrary lengths (for any r≥2, provided $s < 2r - \sqrt{2r + \frac{1}{4}}+ \frac{3}{2}$ ). Furthermore we obtain a complete characterization of the problem’s complexity for the case when the input graph is a tree, whereas our result for arbitrary planar graphs fall just short of a similar dichotomy. Specifically, we prove that the empire colouring problem is NP-hard for trees, for any r≥2, if 3≤s≤2r?1 (and polynomial time solvable otherwise). For arbitrary planar graphs we prove NP-hardness if s<7 for r=2, and s<6r?3, for r≥3. The result for planar graphs also proves the NP-hardness of colouring with less than 7 colours graphs of thickness two and less than 6r?3 colours graphs of thickness r≥3.     

On the Complexity of the Regenerator Cost Problem in General Networks with Traffic Grooming

In a communication network one often needs to combine several communication requests into a path in a physical layer of the network. In these cases the cost is measured in terms of the total length of these paths or the total hardware cost of maintaining these paths. In this paper we consider a problem belonging to this general family of optimization problems. We consider the problem of minimizing the number of regenerators in optical networks with traffic grooming. In this problem we are given a network with an underlying topology of a graph G, a set of requests that correspond to paths in G and two positive integers g and d. There is a need to put a regenerator every d edges of every path, because of a degradation in the quality of the signal. Each regenerator can be shared by at most g paths, g being the grooming factor. On the one hand, we show that even in the case of d=1 the problem is APX-hard, i.e. a polynomial time approximation scheme for it does not exist (unless P=NP). On the other hand, we solve such a problem for general G and any d and g, by providing an O(logg)-approximation algorithm and thus extending previous results holding only for specific topologies and specific values of d or g.     

The Problem of Sparse Image Coding

Linear expansions of images find many applications in image processing and computer vision. Overcomplete expansions are often desirable, as they are better models of the image-generation process. Such expansions lead to the use of sparse codes. However, minimizing the number of non-zero coefficients of linear expansions is an unsolved problem. In this article, a generative-model framework is used to analyze the requirements, the difficulty, and current approaches to sparse image coding.     

基于继承图的面向对象软件复杂性度量研究

面向对象软件开发是一种新的可以减少成本、提高可用性和灵活性的高效的软件系统开发方法。复杂性度量在软件开发中起着非常重要的作用,它可减少整个开发周期的费用,但目前还没有成熟的用于面向对象软件复杂性的度量方法。文章首先通过继承图描述面向对象软件复杂性度量方法,然后讨论了单元重复继承算法,最后给出了具体实例。     

A Hybrid Set of Complexity Metrics for Large-Scale Object-Oriented Software Systems

Large-scale object-oriented (OO) software systems have recently been found to share global network characteristics such as small world and scale free, which go beyond the scope of traditional software measurement and assessment methodologies. To measure the complexity at various levels of granularity, namely graph, class (and object) and source code, we propose a hierarchical set of metrics in terms of coupling and cohesion — the most important characteristics of software, and analyze a sample of 12 open-source OO software systems to empirically validate the set. Experimental results of the correlations between cross-level metrics indicate that the graph measures of our set complement traditional software metrics well from the viewpoint of network thinking, and provide more effective information about fault-prone classes in practice.     

Measuring the Psychological Complexity of Software Maintenance Tasks with the Halstead and McCabe Metrics

Three software complexity measures (Halstead's E, McCabe's u(G), and the length as measured by number of statements) were compared to programmer performance on two software maintenance tasks. In an experiment on understanding, length and u(G) correlated with the percent of statements correctly recalled. In an experiment on modification, most significant correlations were obtained with metrics computed on modified rather than unmodified code. All three metrics correlated with both the accuracy of the modification and the time to completion. Relationships in both experiments occurred primarily in unstructured rather than structured code, and in code with no comments. The metrics were also most predictive of performance for less experienced programmers. Thus, these metrics appear to assess psychological complexity primarily where programming practices do not provide assistance in understanding the code.