共查询到20条相似文献,搜索用时 570 毫秒
1.
In ensemble (or bulk) quantum computation, all computations are performed on an ensemble of computers rather than on a single computer. Measurements of qubits in an individual computer cannot be performed; instead,
only expectation values (over the complete ensemble of computers) can be measured. As a result of this limitation on the model
of computation, many algorithms cannot be processed directly on such computers, and must be modified, as the common strategy
of delaying the measurements usually does not resolve this ensemble-measurement problem. Here we present several new strategies for resolving this problem. Based on these strategies we provide new versions of
some of the most important quantum algorithms, versions that are suitable for implementing on ensemble quantum computers,
e.g., on liquid NMR quantum computers. These algorithms are Shor’s factorization algorithm, Grover’s search algorithm (with
several marked items), and an algorithm for quantum fault-tolerant computation. The first two algorithms are simply modified
using a randomizing and a sorting strategies. For the last algorithm, we develop a classical-quantum hybrid strategy for removing measurements. We use it to
present a novel quantum fault-tolerant scheme. More explicitly, we present schemes for fault-tolerant measurement-free implementation
of Toffoli and sz1/4,\sigma_{z}^{1/4}, as these operations cannot be implemented “bitwise”, and their standard fault-tolerant implementations require measurement. 相似文献
2.
Coalition formation for task allocation: theory and algorithms 总被引:1,自引:0,他引:1
This paper focuses on coalition formation for task allocation in both multi-agent and multi-robot domains. Two different problem
formalizations are considered, one for multi-agent domains where agent resources are transferable and one for multi-robot
domains. We demonstrate complexity theoretic differences between both models and show that, under both, the coalition formation
problem, with m tasks, is NP-hard to both solve exactly and to approximate within a factor of O(m1-e){O(m^{1-\epsilon})} for all ${\epsilon > 0}${\epsilon > 0}. Two natural restrictions of the coalition formation problem are considered. In the first situation agents are drawn from
a set of j types. Agents of each type are indistinguishable from one another. For this situation a dynamic programming based approach
is presented, which, for fixed j finds the optimal coalition structure in polynomial time and is applicable in both multi-agent and multi-robot domains. We
then consider situations where coalitions are restricted to k or fewer agents. We present two different algorithms. Each guarantees the generated solution to be within a constant factor,
for fixed k, of the optimal in terms of utility. Our algorithms complement Shehory and Kraus’ algorithm (Artif Intell 101(1–2):165–200,
1998), which provides guarantee’s on solution cost, as ours provides guarantees on utility. Our algorithm for general multi-agent
domains is a modification of and has the same running time as Shehory and Kraus’ algorithm, while our approach for multi-robot
domains runs in time
O(n\frac32m){O(n^{\frac{3}{2}}m)}, much faster than Vig and Adams (J Intell Robot Syst 50(1):85–118, 2007) modifications to Shehory and Kraus’ algorithm for
multi-robot domains, which ran in time O(n
k
m), for n agents and m tasks. 相似文献
3.
We present two new techniques for regular expression searching and use them to
derive faster practical algorithms.
Based on the specific properties of Glushkov’s nondeterministic finite automaton
construction algorithm, we show how to encode a deterministic finite
automaton (DFA) using O(m2m) bits, where m is the number of characters,
excluding operator symbols, in the regular expression. This compares favorably
against the worst case of O(m2m|Σ|) bits needed by a classical DFA
representation (where Σ is the alphabet) and O(m22m) bits needed
by the Wu and Manber approach implemented in Agrep.
We also present a new way to search for regular expressions, which is
able to skip text characters. The idea is to determine the minimum
length ℓ of a string matching the regular expression,
manipulate the original automaton so that it recognizes all the
reverse prefixes of length up to ℓ of the strings originally accepted,
and use it to skip text characters as done for exact string matching
in previous work.
We combine these techniques into two algorithms, one able and one unable to
skip text characters. The algorithms are simple to implement, and our
experiments show that they permit fast searching for regular expressions,
normally faster than any existing algorithm. 相似文献
4.
The notion of P-simple points was introduced by Bertrand to conceive parallel thinning algorithms. In ‘A 3D fully parallel thinning algorithm
for generating medial faces’ (Pattern Recogn. Lett. 16:83–87, 1995), Ma proposed an algorithm for which there are objects whose topology is not preserved. In this paper, we propose a new application
of P-simple points: to automatically correct Ma’s algorithm. 相似文献
5.
Symbolic techniques based on Binary Decision Diagrams (BDDs) are widely employed for reasoning about temporal properties of
hardware circuits and synchronous controllers. However, they often perform poorly when dealing with the huge state spaces
underlying systems based on interleaving semantics, such as communications protocols and distributed software, which are composed of independently acting subsystems that communicate
via shared events.
This article shows that the efficiency of state-space exploration techniques using decision diagrams can be drastically improved
by exploiting the interleaving semantics underlying many event-based and component-based system models. A new algorithm for
symbolically generating state spaces is presented that (i) encodes a model’s state vectors with Multi–valued Decision Diagrams (MDDs) rather than flattening them into BDDs and (ii) partitions the model’s Kronecker–consistent next–state function by event and subsystem, thus enabling multiple lightweight next–state transformations rather than a single
heavyweight one. Together, this paves the way for a novel iteration order, called saturation, which replaces the breadth–first search order of traditional algorithms. The resulting saturation algorithm is implemented in the tool SMART, and experimental studies show that it is often several orders of magnitude better in terms
of time efficiency, final memory consumption, and peak memory consumption than existing symbolic algorithms. 相似文献
6.
We provide sharp estimates for the probabilistic behaviour of the main parameters of the Euclid Algorithms, both on polynomials
and on integer numbers. We study in particular the distribution of the bit-complexity which involves two main parameters:
digit-costs and length of remainders. We first show here that an asymptotic Gaussian law holds for the length of remainders
at a fraction of the execution, which exhibits a deep regularity phenomenon. Then, we study in each framework—polynomials
(P) and integer numbers (I)—two gcd algorithms, the standard one (S) which only computes the gcd, and the extended one (E) which also computes the Bezout pair, and is widely used for computing modular inverses.
The extended algorithm is more regular than the standard one, and this explains that our results are more precise for the
Extended algorithm: we exhibit an asymptotic Gaussian law for the bit-complexity of the extended algorithm, in both cases (P) and (I). We also prove that an asymptotic Gaussian law for the bit-complexity of the standard gcd in case (P), but we do not succeed obtaining a similar result in case (I).
The integer study is more involved than the polynomial study, as it is usually the case. In the polynomial case, we deal with
the central tools of the distributional analysis of algorithms, namely bivariate generating functions. In the integer case,
we are led to dynamical methods, which heavily use the dynamical system underlying the number Euclidean algorithm, and its
transfer operator. Baladi and Vallée (J. Number Theory 110(2):331–386, 2005) have recently designed a general framework for “distributional dynamical analysis”, where they have exhibited asymptotic
Gaussian laws for a large family of parameters. However, this family does not contain neither the bit-complexity cost nor
the size of remainders, and we have to extend their methods for obtaining our results. Even if these dynamical methods are
not necessary in case (P), we explain how the polynomial dynamical system can be also used for proving our results. This provides a common framework
for both analyses, which well explains the similarities and the differences between the two cases (P) and (I), for the algorithms themselves, and also for their analysis. An extended abstract of this paper can be found in Lhote and
Vallée (Proceedings of LATIN’06, Lecture Notes in Computer Science, vol. 3887, pp. 689–702, 2006). 相似文献
8.
L. D. Jelfimova 《Cybernetics and Systems Analysis》2011,47(6):881-888
New hybrid algorithms are proposed for multiplying (n × n) matrices. They are based on Laderman’s algorithm for multiplying (3 × 3)-matrices. As compared with well-known hybrid matrix
multiplication algorithms, the new algorithms are characterized by the minimum computational complexity. The multiplicative,
additive, and overall complexities of the algorithms are estimated. 相似文献
9.
Mackworth and Freuder have analyzed the time complexity of several constraint satisfaction algorithms.(1) Mohr and Henderson have given new algorithms, AC-4 and PC-3, for arc and path consistency, respectively, and have shown that the arc consistency algorithm is optimal in time complexity and of the same order space complexity as the earlier algorithms.(2) In this paper, we give parallel algorithms for solving node and arc consistency. We show that any parallel algorithm for enforcing are consistency in the worst case must have O(na) sequential steps, wheren is number of nodes, anda is the number of labels per node. We give several parallel algorithms to do arc consistency. It is also shown that they all have optimal time complexity. The results of running the parallel algorithms on a BBN Butterfly multiprocessor are also presented.This work was partially supported by NSF Grants MCS-8221750, DCR-8506393, and DMC-8502115. 相似文献
10.
Finding the nearest k objects to a query object is a fundamental operation for many data mining algorithms. With the recent interest in privacy,
it is not surprising that there is strong interest in k-NN queries to enable clustering, classification and outlier-detection tasks. However, previous approaches to privacy-preserving
k-NN have been costly and can only be realistically applied to small data sets. In this paper, we provide efficient solutions
for k-NN queries for vertically partitioned data. We provide the first solution for the L
∞ (or Chessboard) metric as well as detailed privacy-preserving computation of all other Minkowski metrics. We enable privacy-preserving
L
∞ by providing a practical approach to the Yao’s millionaires problem with more than two parties. This is based on a pragmatic
and implementable solution to Yao’s millionaires problem with shares. We also provide privacy-preserving algorithms for combinations
of local metrics into a global metric that handles the large dimensionality and diversity of attributes common in vertically
partitioned data. To manage very large data sets, we provide a privacy-preserving SASH (a very successful data structure for associative queries in high dimensions). Besides providing a theoretical analysis,
we illustrate the efficiency of our approach with an empirical evaluation. 相似文献
11.
The arguments given in this paper suggest that Grover’s and Shor’s algorithms are more closely related than one might at first
expect. Specifically, we show that Grover’s algorithm can be viewed as a quantum algorithm which solves a non-abelian hidden
subgroup problem (HSP). But we then go on to show that the standard non-abelian quantum hidden subgroup (QHS) algorithm can
not find a solution to this particular HSP. This leaves open the question as to whether or not there is some modification
of the standard non-abelian QHS algorithm which is equivalent to Grover’s algorithm.
相似文献
12.
Thresholding techniques for image segmentation is one of the most popular approaches in Computational Vision systems. Recently,
M. Albuquerque has proposed a thresholding method (Albuquerque et al. in Pattern Recognit Lett 25:1059–1065, 2004) based on the Tsallis entropy, which is a generalization of the traditional Shannon entropy through the introduction of an
entropic parameter q. However, the solution may be very dependent on the q value and the development of an automatic approach to compute a suitable value for q remains also an open problem. In this paper, we propose a generalization of the Tsallis theory in order to improve the non-extensive
segmentation method. Specifically, we work out over a suitable property of Tsallis theory, named the pseudo-additive property,
which states the formalism to compute the whole entropy from two probability distributions given an unique q value. Our idea is to use the original M. Albuquerque’s algorithm to compute an initial threshold and then update the q value using the ratio of the areas observed in the image histogram for the background and foreground. The proposed technique
is less sensitive to the q value and overcomes the M. Albuquerque and k-means algorithms, as we will demonstrate for both ultrasound breast cancer images and synthetic data. 相似文献
13.
Two minimal requirements for a satisfactory multiagent learning algorithm are that it 1. learns to play optimally against stationary
opponents and 2. converges to a Nash equilibrium in self-play. The previous algorithm that has come closest, WoLF-IGA, has
been proven to have these two properties in 2-player 2-action (repeated) games—assuming that the opponent’s mixed strategy
is observable. Another algorithm, ReDVaLeR (which was introduced after the algorithm described in this paper), achieves the
two properties in games with arbitrary numbers of actions and players, but still requires that the opponents' mixed strategies
are observable. In this paper we present AWESOME, the first algorithm that is guaranteed to have the two properties in games
with arbitrary numbers of actions and players. It is still the only algorithm that does so while only relying on observing
the other players' actual actions (not their mixed strategies). It also learns to play optimally against opponents that eventually become stationary. The basic idea behind AWESOME (Adapt When Everybody is Stationary, Otherwise Move to Equilibrium) is to try to adapt to the others' strategies when they appear stationary, but otherwise to retreat to a precomputed equilibrium
strategy. We provide experimental results that suggest that AWESOME converges fast in practice. The techniques used to prove
the properties of AWESOME are fundamentally different from those used for previous algorithms, and may help in analyzing future
multiagent learning algorithms as well.
Editors: Amy Greenwald and Michael Littman 相似文献
14.
Romeo Rizzi 《Algorithmica》2009,53(3):402-424
In the last years, new variants of the minimum cycle basis (MCB) problem and new classes of cycle bases have been introduced, as motivated by several applications from disparate areas of
scientific and technological inquiry. At present, the complexity status of the MCB problem is settled only for undirected, directed, and strictly fundamental cycle bases (SFCB’s). Weakly fundamental cycle
bases (WFCB’s) form a natural superclass of SFCB’s. A cycle basis
of a graph G is a WFCB iff ν=0 or there exists an edge e of G and a circuit C
i
in
such that
is a WFCB of G∖e. WFCB’s still possess several of the nice properties offered by SFCB’s. At the same time, several classes of graphs enjoying
WFCB’s of cost asymptotically inferior to the cost of the cheapest SFCB’s have been found and exhibited in the literature.
Considered also the computational difficulty of finding cheap SFCB’s, these works advocated an in-depth study of WFCB’s. In
this paper, we settle the complexity status of the MCB problem for WFCB’s (the MWFCB problem). The problem turns out to be
-hard. However, in this paper, we also offer a simple and practical 2⌈log 2
n⌉-approximation algorithm for the MWFCB problem. In O(n
ν) time, this algorithm actually returns a WFCB whose cost is at most 2⌈log 2
n⌉∑
e∈E(G)
w
e
, thus allowing a fast 2⌈log 2
n⌉-approximation also for the MCB problem. With this algorithm, we provide tight bounds on the cost of any MCB and MWFCB. 相似文献
15.
Binary Image Thinning Using Autowaves Generated by PCNN 总被引:2,自引:0,他引:2
This paper proposes a novel binary image thinning algorithm by using the autowaves generated by Pulse Coupled Neural Network
(PCNN). Once the autowaves travelling in different directions meet, the PCNN delivers the thinning results. Four meeting conditions
are given for autowaves meeting. If a neuron satisfies one of the four conditions, the pixel corresponding to this neuron
belongs to the thinning result. Moreover, the specification of the PCNNs parameters is given, which makes the implementation
of the proposed thinning algorithm easy. Experimental results show that the proposed algorithm is efficient in extracting
the skeleton of images (such as Chinese characters, alphabet letters, numbers, fingerprints, etc.). Finally, a rate called
“R
MSkel” is given to evaluate the performance of different thinning algorithms, and comparisons show that the proposed algorithm
has higher “R
MSkel” and costs less time. 相似文献
16.
We present a generalized let-polymorphic type inference algorithm, prove that any of its instances is sound and complete with
respect to the Hindley/Milner let-polymorphic type system, and find a condition on two instance algorithms so that one algorithm
should find type errors earlier than the other.
By instantiating the generalized algorithm with different parameters, we can obtain not only the two opposite algorithms (the
bottom-up standard algorithmW and the top-down algorithmM) but also other hybrid algorithms which are used in real compilers. Such instances’ soudness and completeness follow automatically,
and their relative earliness in detecting type-errors is determined by checking a simple condition. The set of instances of
the generalized algorithm is a superset of those used in the two most popular ML compilers: SML/NJ and OCaml.
This work is supported by Creative Research Initiatives of the Korean Ministry of Science and Technology
National Creative Research Initiative Center, http://ropas.kaist.ac.kr
Work done while the third author was associated with Korea Advanced Institute of Science and Technology
Hyunjun Eo: He is a Ph.D. candidate in the Department of Computer Science at KAIST (Korea Advanced Institute of Science and Technology).
He recieved his bachelor’s degree and master’s degree in Computer Science from KAIST in 1996 and 1998, respectively. His research
interest has been on static program analysis, fixpoint iteration algorithm and higher-order and typed languages. From fall
1998, he has been a research assistant of the National Creative Research Initiative Center for Research on Program Analysis
System. He is currently working on developing a tool for automatic generation of program analyzer.
Oukseh Lee: He is a Ph.D. candidate in the Department of Computer Science at KAIST (Korea Advanced Institute of Science and Technology).
He received his bachelor’s and master’s degree in Computer Science from KAIST in 1995 and 1997, respectively. His research
interest has been on static program analysis, type system, program language implementation, higher-order and typed languages,
and program verification. From 1998, he has been a research assistant of the National Creative Research Initiative Center
for Research on Program Analysis System. He is currently working on compile-time analyses and verification for the memory
behavior of programs.
Kwangkeun Yi, Ph.D.: His research interest has been on semanticbased program analysis and systems application of language technologies. After
his Ph.D. from University of Illinois at Urbana-Champaign he joined the Software Principles Research Department at Bell Laboratories,
where he worked on various static analysis approaches for higher-order and typed programming languages. For 1995 to 2003 he
was a faculty member in the Department of Computer Science, Korea Advanced Institute of Science and Technology. Since fall
2003, he has been a faculty member in the School of Computer Science and Engineering, Seoul National University. 相似文献
17.
In this paper, we consider two scheduling problems on a single machine, where a specific objective function has to be maximized
in contrast to usual minimization problems. We propose exact algorithms for the single machine problem of maximizing total
tardiness 1‖max-ΣT
j
and for the problem of maximizing the number of tardy jobs 1‖maxΣU
j
. In both cases, it is assumed that the processing of the first job starts at time zero and there is no idle time between
the jobs. We show that problem 1‖max-ΣT
j
is polynomially solvable. For several special cases of problem 1‖maxΣT
j
, we present exact polynomial algorithms. Moreover, we give an exact pseudo-polynomial algorithm for the general case of the
latter problem and an alternative exact algorithm. 相似文献
18.
An efficient algorithm which synthesizes all shortest linear-feedback shift registers generating K given sequences with possibly different lengths over a field is derived, and its correctness is proved. The proposed algorithm
generalizes the Berlekamp-Massey and Feng-Tzeng algorithms and is based on Massey’s ideas. The time complexity of the algorithm
is O(KλN) ≲ O(KN
2), where N is the length of a longest sequence and λ is the linear complexity of the sequences. 相似文献
19.
Daniel Molina Manuel Lozano Ana M. S��nchez Francisco Herrera 《Soft Computing - A Fusion of Foundations, Methodologies and Applications》2011,15(11):2201-2220
Nowadays, large scale optimisation problems arise as a very interesting field of research, because they appear in many real-world
problems (bio-computing, data mining, etc.). Thus, scalability becomes an essential requirement for modern optimisation algorithms.
In a previous work, we presented memetic algorithms based on local search chains. Local search chain concerns the idea that,
at one stage, the local search operator may continue the operation of a previous invocation, starting from the final configuration
reached by this one. Using this technique, it was presented a memetic algorithm, MA-CMA-Chains, using the CMA-ES algorithm
as its local search component. This proposal obtained very good results for continuous optimisation problems, in particular
with medium-size (with up to dimension 50). Unfortunately, CMA-ES scalability is restricted by several costly operations,
thus MA-CMA-Chains could not be successfully applied to large scale problems. In this article we study the scalability of
memetic algorithms based on local search chains, creating memetic algorithms with different local search methods and comparing
them, considering both the error values and the processing cost. We also propose a variation of Solis Wets method, that we call Subgrouping Solis Wets algorithm. This local search method explores, at each step of the algorithm, only a random subset of the variables. This
subset changes after a certain number of evaluations. Finally, we propose a new memetic algorithm based on local search chains
for high dimensionality, MA-SSW-Chains, using the Subgrouping Solis Wets’ algorithm as its local search method. This algorithm is compared with MA-CMA-Chains and different reference algorithms, and
it is shown that the proposal is fairly scalable and it is statistically very competitive for high-dimensional problems. 相似文献
20.
P.-E. Bernard E. Deleersnijder V. Legat J.-F. Remacle 《Journal of scientific computing》2008,34(1):26-47
A technique for analyzing dispersion properties of numerical schemes is proposed. The method is able to deal with both non
dispersive or dispersive waves, i.e. waves for which the phase speed varies with wavenumber. It can be applied to unstructured
grids and to finite domains with or without periodic boundary conditions.
We consider the discrete version L of a linear differential operator ℒ. An eigenvalue analysis of L gives eigenfunctions and eigenvalues (l
i
,λ
i
). The spatially resolved modes are found out using a standard a posteriori error estimation procedure applied to eigenmodes. Resolved eigenfunctions l
i
’s are used to determine numerical wavenumbers k
i
’s. Eigenvalues’ imaginary parts are the wave frequencies ω
i
and a discrete dispersion relation ω
i
=f(k
i
) is constructed and compared with the exact dispersion relation of the continuous operator ℒ. Real parts of eigenvalues λ
i
’s allow to compute dissipation errors of the scheme for each given class of wave.
The method is applied to the discontinuous Galerkin discretization of shallow water equations in a rotating framework with
a variable Coriolis force. Such a model exhibits three families of dispersive waves, including the slow Rossby waves that
are usually difficult to analyze. In this paper, we present dissipation and dispersion errors for Rossby, Poincaré and Kelvin
waves. We exhibit the strong superconvergence of numerical wave numbers issued of discontinuous Galerkin discretizations for
all families of waves. In particular, the theoretical superconvergent rates, demonstrated for a one dimensional linear transport
equation, for dissipation and dispersion errors are obtained in this two dimensional model with a variable Coriolis parameter
for the Kelvin and Poincaré waves. 相似文献