Self-protected quantum algorithms based on quantum state tomography

Only a few classes of quantum algorithms are known which provide a speed-up over classical algorithms. However, these and any new quantum algorithms provide important motivation for the development of quantum computers. In this article new quantum algorithms are given which are based on quantum state tomography. These include an algorithm for the calculation of several quantum mechanical expectation values and an algorithm for the determination of polynomial factors. These quantum algorithms are important in their own right. However, it is remarkable that these quantum algorithms are immune to a large class of errors. We describe these algorithms and provide conditions for immunity.      

归约算法统一描述

归约算法在并行计算中应用广泛,目前有很多归约算法应用于不同的情形。这些归约算法各不相同, 逻辑拓扑是 造成区别的关键 。为了统一描述归约算法,揭示它们的共性,给出了一个逻辑拓扑的定义及其性质。在此基础上,给出了归约算法的统一描述,以利于对归约算法的理解,从而设计适应不同应用和环境的归约算法。该描述也可视为可集成不同语义的归约算法框架,从而有助于设计具有新语义的归约算法。本质上,该统一描述是一个归约算法形式定义,有助于验证归约算法的正确性。     

Second-Level Algorithms,Superrecursivity, and Recovery Problem in Distributed Systems

In this paper, we analyze network recovery algorithms, which allow computer networks to properly function in spite of failures. In this analysis, we use methods and tools of the theory of super-recursive algorithms. The concept of algorithm of the second level is introduced and studied. It is demonstrated that although the main components of various check-point/recovery algorithms are recursive algorithms, check-point/recovery algorithms, as a whole, are super-recursive second-level algorithms. Treating network recovery algorithms as second level algorithms is oriented at developing more powerful algorithms by combining existing ones in a common schema.     

Making Fault-Sensitive Algorithms Tolerate Link Failures

We present a unified approach for converting a class of distributed algorithms that are fault-sensitive into algorithms tolerating undetectable link failures in asynchronous distributed systems. Single and multiple link failures not leading to a network partition are considered. Our technique is applied on several examples and fault-tolerant algorithms are derived. On the message complexity measure, the derived fault-tolerant distributed algorithms compare well with the fault-sensitive algorithms.     

MapReduce大数据处理平台与算法研究进展

本文综述了近年来基于MapReduce编程模型的大数据处理平台与算法的研究进展。首先介绍了12个典型的基于MapReduce的大数据处理平台,分析对比它们的实现原理和适用场景,抽象它们的共性。随后介绍基于MapReduce的大数据分析算法,包括搜索算法、数据清洗/变换算法、聚集算法、连接算法、排序算法、偏好查询、最优化算法、图算法、数据挖掘算法。将这些算法按MapReduce实现方式分类,分析影响这算法性能的因素。最后,将大数据处理算法抽象为外存算法,并对外存算法的特征加以梳理,提出了普适的外存算法性能优化方法的研究思路和研究问题,以供研究人员参考。具体包括优化外存算法的磁盘I/O,优化外存算法的局部性,以及设计增量式迭代算法。现有大数据处理平台和算法研究多集中在基于资源分配和任务调度的平台动态性能优化、特定算法并行化、特定算法性能优化等领域,本文提出的外存算法性能优化属于静态优化方法,是现有研究的良好补充,为研究人员提供了广阔的研究空间。     

Iterative and core-guided MaxSAT solving: A survey and assessment

Maximum Satisfiability (MaxSAT) is an optimization version of SAT, and many real world applications can be naturally encoded as such. Solving MaxSAT is an important problem from both a theoretical and a practical point of view. In recent years, there has been considerable interest in developing efficient algorithms and several families of algorithms have been proposed. This paper overviews recent approaches to handle MaxSAT and presents a survey of MaxSAT algorithms based on iteratively calling a SAT solver which are particularly effective to solve problems arising in industrial settings. First, classic algorithms based on iteratively calling a SAT solver and updating a bound are overviewed. Such algorithms are referred to as iterative MaxSAT algorithms. Then, more sophisticated algorithms that additionally take advantage of unsatisfiable cores are described, which are referred to as core-guided MaxSAT algorithms. Core-guided MaxSAT algorithms use the information provided by unsatisfiable cores to relax clauses on demand and to create simpler constraints. Finally, a comprehensive empirical study on non-random benchmarks is conducted, including not only the surveyed algorithms, but also other state-of-the-art MaxSAT solvers. The results indicate that (i) core-guided MaxSAT algorithms in general abort in less instances than classic solvers based on iteratively calling a SAT solver and that (ii) core-guided MaxSAT algorithms are fairly competitive compared to other approaches.     

Cooperative Distributed Algorithms for Dynamic Cycle Prevention

Parallel distributed algorithms are presented for adding and deleting edges in a directed graph without creating a cycle. Such algorithms are useful for a variety of problems in distributed systems such as preventing deadlock or ordering priorities. The algorithms operate in a realistic asynchronous computer network environment in which there are numerous possible interactions among overlapping instances of the algorithms.     

Reusable components for partitioning clustering algorithms

Clustering algorithms are well-established and widely used for solving data-mining tasks. Every clustering algorithm is composed of several solutions for specific sub-problems in the clustering process. These solutions are linked together in a clustering algorithm, and they define the process and the structure of the algorithm. Frequently, many of these solutions occur in more than one clustering algorithm. Mostly, new clustering algorithms include frequently occurring solutions to typical sub-problems from clustering, as well as from other machine-learning algorithms. The problem is that these solutions are usually integrated in their algorithms, and that original algorithms are not designed to share solutions to sub-problems outside the original algorithm easily. We propose a way of designing cluster algorithms and to improve existing ones, based on reusable components. Reusable components are well-documented, frequently occurring solutions to specific sub-problems in a specific area. Thus we identify reusable components, first, as solutions to characteristic sub-problems in partitioning cluster algorithms, and, further, identify a generic structure for the design of partitioning cluster algorithms. We analyze some partitioning algorithms (K-means, X-means, MPCK-means, and Kohonen SOM), and identify reusable components in them. We give examples of how new cluster algorithms can be designed based on them.     

Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning

This article presents a general class of associative reinforcement learning algorithms for connectionist networks containing stochastic units. These algorithms, called REINFORCE algorithms, are shown to make weight adjustments in a direction that lies along the gradient of expected reinforcement in both immediate-reinforcement tasks and certain limited forms of delayed-reinforcement tasks, and they do this without explicitly computing gradient estimates or even storing information from which such estimates could be computed. Specific examples of such algorithms are presented, some of which bear a close relationship to certain existing algorithms while others are novel but potentially interesting in their own right. Also given are results that show how such algorithms can be naturally integrated with backpropagation. We close with a brief discussion of a number of additional issues surrounding the use of such algorithms, including what is known about their limiting behaviors as well as further considerations that might be used to help develop similar but potentially more powerful reinforcement learning algorithms.     

Hybrid Splitting Methods for the System of Operator Inclusions with Monotone Operators1

New algorithms are proposed to solve a system of operator inclusions with monotone operators acting in a Hilbert space. The algorithms are based on three well-known methods: the Tseng forward-backward splitting algorithm and two hybrid algorithms for approximation of fixed points of nonexpansive operators. Theorems on the strong convergence of the sequences generated by the algorithms are proved.     

A convergence analysis of generalized hill climbing algorithms

Generalized hill climbing (GHC) algorithms provide a well-defined framework for describing the performance of local search algorithms for discrete optimization problems. Necessary and sufficient convergence conditions for GHC algorithms are presented. These convergence conditions are derived using a new iteration classification scheme for GHC algorithms. The implications of the necessary and the sufficient convergence conditions fur GHC algorithms with respect to existing convergence theory for simulated annealing are also discussed     

Generalized filtering algorithms for infeasibility analysis

We present generalized filtering algorithms for debugging linear, mixed integer and nonlinear infeasible programs. Given a set of constraints that are infeasible or inconsistent, we give algorithms to identify a minimal subset of these constraints that are inconsistent. The algorithms combine existing filtering algorithms with a binary-search based divide-and-conquer approach to improve search speed. We give computational results to show the speed of the algorithms on various problem types.     

优化处理并行数据库查询的并行数据流方法

本文使用并行数据流技术优化和处理并行数据库查询的方法,提出了一整套相关算法,并给出了一个基于并行数据流方法的并行数据库查询优化处理器的完整设计.这些算法和相应的查询优化处理器已经用于作者自行设计的并行数据库管理系统原型.实践证明,并行数据流方法不仅能够快速有效地实现并行数据库管理系统,也能够有效地进行并行数据库查询的优化处理.     

Adaptation Algorithms in Finite form for Nonlinear Dynamic Objects

A class of adaptation algorithms for adaptive control of nonlinear dynamic objects of a class is introduced. Implementation of algorithms without the need for direct measurements of the first time derivatives is investigated and sufficient conditions for the existence of such algorithms are formulated. For a class of nonlinear objects and formulated adaptive control aim, examples are given to illustrate the realization of adaptation algorithms. These algorithms are compared with the traditional gradient algorithms.     

布谷鸟搜索算法研究及其应用进展

为进一步加强布谷鸟算法的搜寻能力并提升收敛速度,加快对算法的研究与应用进程,综述了布谷鸟算法的原理、研究概况和其他同类群体智能优化算法的比较及发展趋势。首先给出了算法的基本模型和实现步骤;然后重点阐述了基于发现概率和步长控制量、基于自适应步长、基于混沌理论、与其他算法混合、基于种群特征和种群变异、结合优化策略及基于种群多样性等方面的改进方法,总结了算法的主要应用领域及其进展;随后将其与遗传算法、蚁群优化算法、粒子群优化算法及人工蜂群优化算法的优点、缺点及适用性诸方面进行了对比;最后指出了布谷鸟搜索算法尚存在的缺陷并对进一步的研究方向进行了展望。     

Semi-asynchronous and distributed weighted connected dominating set algorithms for wireless sensor networks

Energy-efficient backbone construction is one of the most important objective in a wireless sensor network (WSN) and to construct a more robust backbone, weighted connected dominating sets can be used where the energy of the nodes are directly related to their weights. In this study, we propose algorithms for this purpose and classify our algorithms as weighted dominating set algorithms and weighted Steiner tree algorithms where these algorithms are used together to construct a weighted connected dominating set (WCDS). We provide fully distributed algorithms with semi-asynchronous versions. We show the design of the algorithms, analyze their proof of correctness, time, message and space complexities and provide the simulation results in ns2 environment. We show that the approximation ratio of our algorithms is 3ln(S) where S is the total weight of optimum solution. To the best of our knowledge, our algorithms are the first fully distributed and semi-asynchronous WCDS algorithms with 3ln(S) approximation ratio. We compare our proposed algorithms with the related work and show that our algorithms select backbone with lower cost and less number of nodes.     

A unifying framework for linear estimation: Generalized partitioned algorithms

In this paper, generalized partitioned algorithms are presented that serve as the unifying framework for linear filtering and smoothing. The fundamental and all encompassing nature of the generalized partitioned algorithms (hereon denoted GPA) is clearly demonstrated by showing that the GPA contain as special cases important generalizations of past well-known linear estimation algorithms, as well as whole families of such algorithms, of which all previously obtained major filtering and smoothing algorithms are special cases. Specifically, generalized partitioned filtering and smoothing algorithms are given in terms of integral expressions, that are theoretically interesting, computationally attractive, as well as provide a unification of all previous approaches to linear filtering and smoothing, and clear delineation of their inter-relationships. In particular, the GPA for filtering are shown to contain as special cases families of filtering algorithms which constitute generalizations of the Kalman-Bucy, and Chandrasekhar algorithms as well as of the previously obtained partitioned algorithms of Lainiotis. These generalizations pertain to arbitrary initial conditions and time-varying models. Further, the GPA for smoothing are shown to contain two families of generalized backward and forward smoothing algorithms valid for arbitrary boundary conditions, of which all previous backward and forward algorithms are special cases. It is also shown that the GPA may also be given in terms of an imbedded generalized Chandrasekhar algorithm with the consequent computational advantages. Furthermore, the GPA are shown to serve as the basis of computationally effective, fast, and numerically robust algorithms for the numerical implementation of the estimation formulas. A particularly effective doubling algorithm is also given for calculating the steady-state filter. The partitioned numerical algorithms are given exactly in terms of a set of elemental solutions which are both simple as well as completely decoupled, and as such computable in either a parallel or serial processing mode. Moreover, the overall solution is given by a simple recursive operation on the elemental solutions.     

Study on enhanced Karnik–Mendel algorithms: Initialization explanations and computation improvements

Computing the centroid of an interval type-2 fuzzy set is an important operation in a type-2 fuzzy logic system, and is usually implemented by Karnik–Mendel (KM) iterative algorithms. By connecting KM algorithms and continuous KM algorithms together, this paper gives theoretical explanations on the initialization methods of KM and Enhanced Karnik–Mendel (EKM) algorithms, proposes exact methods for centroid computation of an interval type-2 fuzzy set, and extends the Enhanced Karnik–Mendel (EKM) algorithms to three different forms of weighted EKM (WEKM) algorithms. It shows that EKM algorithms become a special case of the WEKM algorithms when the weights of the latter are constant value. It also shows that, in general, the weighted EKM algorithms have smaller absolute error and faster convergence speed than the EKM algorithms which make them very attractive for real-time applications of fuzzy logic system. Four numerical examples are used to illustrate and analyze the performance of WEKM algorithms.     

多元约束混合搜索算法研究

解空间搜索是约束求解的关键环节. 目前较为常用的搜索算法一般是基于二元约束或单一搜索策略设计的. 本文设计了六个基于多元约束的混合搜索算法(BM_GASBJ, BM_GBJ, BM_CBJ, FC_GASBJ, FC_GBJ, FC_CBJ), 它们分别混合同一类搜索策略中不同算法或不同类搜索策略; 分析并给出了不同混合算法的性能差异. 系统测试结果表明混合搜索算法明显提高了解搜索效率和约束求解系统的性能.