排序算法探讨

通过对多种排序方法的比较与评价,提出多种改进的思路,形成改进型的排序算法。这些改进型的算法通过减少比较次数或交换次数,从而进一步改进平均情况下算法的时间性能。     

基于特定范围的关键字的快速排序算法

本文给出了一种对关键字在特定范围内的数据记录不用进行数据的比较交换的快速排序算法、算法思想、算法描述、时间复杂度及空间复杂度分析,并用C＋＋语言编写程序进行算法比较。结果表明：在关键字范围远远小于记录数的情况下,此算法的时间复杂度仅为O（n）,并且明显优于其他排序算法。     

一个选择算法及其并行化

文中用合并选择的思想及堆上的最佳算法，给出了求解选择问题的一个新算法及其相应的并行化。将串行合并选择算法的复杂度ｎＬｏｇｋ＋Ｏ（ｎ）降低到（ｎＬｏｇｋ）／２＋（ｎＬｏｇＬｏｇｋ）／２＋Ｏ（ｎ），并保持了原并行算法的结构，在ＳＩＭＤ树型机器的并行计算模型上，并行运行     

边故障K元3立方体的二不交路覆盖

研究具有故障边的[k]元3立方体的非指定二不交路覆盖问题。证明了在具有至多3条故障边的[k]元3立方体[Qk3]中,任意给定两个源点和两个汇点,则存在两条顶点不交的路[P1]和[P2],分别连接一个源点和汇点,且[V(P1)?V(P2)=V(Qk3)]。     

The complexity of the Quantum Adiabatic Algorithm

The Quantum Adiabatic Algorithm has been proposed as a general purpose algorithm for solving hard optimization problems on a quantum computer. Early work on very small sizes indicated that the running time (complexity) only increased as a (quite small) power of the problem size N. We report results of Quantum Monte Carlo simulations, using parallel tempering, with which we determine the minimum energy gap (and hence get information the complexity) for much bigger sizes than was possible before. The aim is to see if there is a “crossover” to exponential complexity at large N. We present data for the typical (median) complexity as a function of N, which indicate a crossover to a first order transition at large sizes. This implies that the complexity is exponential at large N, at least for the problem studied.     

On algorithms for construction of all irreducible partial covers

Lower and upper bounds on the cardinality and the number of irreducible partial covers for almost all set cover problems are obtained. These bounds allow us to prove that there is no polynomial algorithm which for almost all set cover problems constructs all irreducible partial covers, but there exists a totally polynomial algorithm which constructs all irreducible partial covers for almost all set cover problems.     

Computing unique canonical covers for simple FDs via transitive reduction

Although there is a rich body of research on dependency theory, only few results concerning simple functional dependencies (FDs) have been published. In this paper, the following key results regarding simple FDs are shown. First, given an acyclic set F of simple FDs there exists exactly one canonical cover for F. Second, this uniquely determined canonical cover can be computed via transitive reduction. Third, it is shown how a uniquely determined canonical cover can be fixed in case of arbitrary simple FDs via transitive reduction.     

Evaluation techniques for zero-dimensional primary decomposition

This paper presents a new algorithm that computes the local algebras of the roots of a zero-dimensional polynomial equation system, with a number of operations in the coefficient field that is polynomial in the number of variables, in the evaluation cost of the equations and in a Bézout number.     

The algorithmic complexity of mixed domination in graphs

Let G=(V,E) be a simple graph with vertex set V and edge set E. A subset W⊆V∪E is a mixed dominating set if every element x∈(V∪E)?W is either adjacent or incident to an element of W. The mixed domination problem is to find a minimum mixed dominating set of G. In this paper we first prove that a connected graph is a tree if and only if its total graph is strongly chordal, and thus we obtain a polynomial-time algorithm for this problem in trees. Further we design another linear-time labeling algorithm for this problem in trees. At the end of the paper, we show that the mixed domination problem is NP-complete even when restricted to split graphs, a subclass of chordal graphs.     

一种软件复杂性度量系统的设计与实现

本文结合软件复杂性度量的多种算法,对我们研制开发的一个软件复杂性度量系统,进行了详细介绍,并将系统与已有的各种度量工具进行了分析比较。     

基于存储结构的汉字分组排序及其复杂度分析

自从计算机被用来进行大规模的数据处理,数据序列的排序问题便一直成为研究的热点,汉语言本身所具有的特点,使得汉字符串的排序问题成为中文信息处理领域中备受关注的问题,提出了一种汉字符串的快速分组排序算法,算法复杂度仅为O(n)。     

A New String Matching Algorithm

In this paper a new exact string-matching algorithm with sub-linear average case complexity has been presented. Unlike other sub-linear string-matching algorithms it never performs more than n text character comparisons while working on a text of length n . It requires only O ( m +σ) extra pre-processing time and space, where m is the length of the pattern and σ is the size of the alphabet.     

Yet some more complexity results for default logic

We identify several new tractable subsets and several new intractable simple cases for reasoning in the propositional version of Reiter's default logic. The majority of our findings are related to brave reasoning. By making some intuitive observations, most classes that we identify can be derived quite easily from some subsets of default logic already known in the literature. Some of the subsets we discuss are subclasses of the so-called “extended logic programs”. All the tractable subsets presented in this paper can be recognized in linear time.     

多种形状窗口下的快速中值滤波算法

针对各类形状的窗口的对称特性,巧妙设定滤波窗口移动顺序,同时利用两个方向相邻窗口的已有信息将每个新窗口查找中值的比较次数降到很低。对七种常用形状的窗口分别设计了算法,实验证明这一组算法比传统快速排序算法和已有的一些改进算法在速度上均有不同程度的提高。     

Net results [3D graphics]

A good 3D visual imagination is valuable for anyone working in 3D graphics. An excellent way to develop that imagination is to build models and hold them, turn them, and study them. The author begins with Platonic solids. He shows an unfolded shape, such as a tetrahedron made of four equilateral triangles, and includes small assembly flaps. He shows the unfolded diagrams or nets for these solids. He discusses the kaleidocycle, one of the most interesting dynamic polyhedral models     

Hundreds of impossibility results for distributed computing

We survey results from distributed computing that show tasks to be impossible, either outright or within given resource bounds, in various models. The parameters of the models considered include synchrony, fault-tolerance, different communication media, and randomization. The resource bounds refer to time, space and message complexity. These results are useful in understanding the inherent difficulty of individual problems and in studying the power of different models of distributed computing. There is a strong emphasis in our presentation on explaining the wide variety of techniques that are used to obtain the results described.Received: September 2001, Accepted: February 2003,     

基于数据驱动的单循环排序算法及其优化

排序是计算机科学中最基本、最重要的研究问题之一。目前常用的排序算法均为双重或多重循环设计，并且大多是程序驱动，本文提出一种新型的基于数据驱动的单循环排序算法，并对该算法进行了性能优化与分析.     

New complexity results for the k-covers problem

The k-covers problem (kCP) asks us to compute a minimum cardinality set of strings of given length k > 1 that covers a given string. It was shown in a recent paper, by reduction to 3-SAT, that the k-covers problem is NP-complete. In this paper we introduce a new problem, that we call the k-bounded relaxed vertex cover problem (RVCP_k), which we show is equivalent to k-bounded set cover (SCP_k). We show further that kCP is a special case of RVCP_k restricted to certain classes G_x,k of graphs that represent all strings x. Thus a minimum k-cover can be approximated to within a factor k in polynomial time. We discuss approximate solutions of kCP, and we state a number of conjectures and open problems related to kCP and G_x,k.     

A Distributed Algorithm for Determining Minimal Covers of Acyclic Database Schemes

Acyclic databases possess several desirable properties for their design and use.A distributed algorithm is proposed for determining a minimal cover of an alpha-,beta-,gamma-,or Berge-acyclic database scheme over a set of attributes in a distributed environment.