Joux, Antoine
2009-01-01
Illustrating the power of algorithms, Algorithmic Cryptanalysis describes algorithmic methods with cryptographically relevant examples. Focusing on both private- and public-key cryptographic algorithms, it presents each algorithm either as a textual description, in pseudo-code, or in a C code program.Divided into three parts, the book begins with a short introduction to cryptography and a background chapter on elementary number theory and algebra. It then moves on to algorithms, with each chapter in this section dedicated to a single topic and often illustrated with simple cryptographic applic
Hougardy, Stefan
2016-01-01
Algorithms play an increasingly important role in nearly all fields of mathematics. This book allows readers to develop basic mathematical abilities, in particular those concerning the design and analysis of algorithms as well as their implementation. It presents not only fundamental algorithms like the sieve of Eratosthenes, the Euclidean algorithm, sorting algorithms, algorithms on graphs, and Gaussian elimination, but also discusses elementary data structures, basic graph theory, and numerical questions. In addition, it provides an introduction to programming and demonstrates in detail how to implement algorithms in C++. This textbook is suitable for students who are new to the subject and covers a basic mathematical lecture course, complementing traditional courses on analysis and linear algebra. Both authors have given this "Algorithmic Mathematics" course at the University of Bonn several times in recent years.
Tel, G.
1993-01-01
We define the notion of total algorithms for networks of processes. A total algorithm enforces that a "decision" is taken by a subset of the processes, and that participation of all processes is required to reach this decision. Total algorithms are an important building block in the design of distri
Hromkovic, Juraj
2009-01-01
Explores the science of computing. This book starts with the development of computer science, algorithms and programming, and then explains and shows how to exploit the concepts of infinity, computability, computational complexity, nondeterminism and randomness.
DEFF Research Database (Denmark)
Markham, Annette
This paper takes an actor network theory approach to explore some of the ways that algorithms co-construct identity and relational meaning in contemporary use of social media. Based on intensive interviews with participants as well as activity logging and data tracking, the author presents a richly...... layered set of accounts to help build our understanding of how individuals relate to their devices, search systems, and social network sites. This work extends critical analyses of the power of algorithms in implicating the social self by offering narrative accounts from multiple perspectives. It also...
Hu, T C
2002-01-01
Newly enlarged, updated second edition of a valuable text presents algorithms for shortest paths, maximum flows, dynamic programming and backtracking. Also discusses binary trees, heuristic and near optimums, matrix multiplication, and NP-complete problems. 153 black-and-white illus. 23 tables.Newly enlarged, updated second edition of a valuable, widely used text presents algorithms for shortest paths, maximum flows, dynamic programming and backtracking. Also discussed are binary trees, heuristic and near optimums, matrix multiplication, and NP-complete problems. New to this edition: Chapter 9
DEFF Research Database (Denmark)
Gustavson, Fred G.; Reid, John K.; Wasniewski, Jerzy
2007-01-01
variables, and the speed is usually better than that of the LAPACK algorithm that uses full storage (n2 variables). Included are subroutines for rearranging a matrix whose upper or lower-triangular part is packed by columns to this format and for the inverse rearrangement. Also included is a kernel...
Casanova, Henri; Robert, Yves
2008-01-01
""…The authors of the present book, who have extensive credentials in both research and instruction in the area of parallelism, present a sound, principled treatment of parallel algorithms. … This book is very well written and extremely well designed from an instructional point of view. … The authors have created an instructive and fascinating text. The book will serve researchers as well as instructors who need a solid, readable text for a course on parallelism in computing. Indeed, for anyone who wants an understandable text from which to acquire a current, rigorous, and broad vi
Evolutionary Graph Drawing Algorithms
Institute of Scientific and Technical Information of China (English)
Huang Jing-wei; Wei Wen-fang
2003-01-01
In this paper, graph drawing algorithms based on genetic algorithms are designed for general undirected graphs and directed graphs. As being shown, graph drawing algorithms designed by genetic algorithms have the following advantages: the frames of the algorithms are unified, the method is simple, different algorithms may be attained by designing different objective functions, therefore enhance the reuse of the algorithms. Also, aesthetics or constrains may be added to satisfy different requirements.
Energy Technology Data Exchange (ETDEWEB)
Fontana, W.
1990-12-13
In this paper complex adaptive systems are defined by a self- referential loop in which objects encode functions that act back on these objects. A model for this loop is presented. It uses a simple recursive formal language, derived from the lambda-calculus, to provide a semantics that maps character strings into functions that manipulate symbols on strings. The interaction between two functions, or algorithms, is defined naturally within the language through function composition, and results in the production of a new function. An iterated map acting on sets of functions and a corresponding graph representation are defined. Their properties are useful to discuss the behavior of a fixed size ensemble of randomly interacting functions. This function gas'', or Turning gas'', is studied under various conditions, and evolves cooperative interaction patterns of considerable intricacy. These patterns adapt under the influence of perturbations consisting in the addition of new random functions to the system. Different organizations emerge depending on the availability of self-replicators.
DEFF Research Database (Denmark)
This book constitutes the refereed proceedings of the 10th Scandinavian Workshop on Algorithm Theory, SWAT 2006, held in Riga, Latvia, in July 2006. The 36 revised full papers presented together with 3 invited papers were carefully reviewed and selected from 154 submissions. The papers address all...... issues of theoretical algorithmics and applications in various fields including graph algorithms, computational geometry, scheduling, approximation algorithms, network algorithms, data storage and manipulation, combinatorics, sorting, searching, online algorithms, optimization, etc....
Skiena, Steven S
2008-01-01
Explaining designing algorithms, and analyzing their efficacy and efficiency, this book covers combinatorial algorithms technology, stressing design over analysis. It presents instruction on methods for designing and analyzing computer algorithms. It contains the catalog of algorithmic resources, implementations and a bibliography
Fister, Iztok; Yang, Xin-She; Fister, Dušan
2013-01-01
Swarm intelligence is a very powerful technique to be used for optimization purposes. In this paper we present a new swarm intelligence algorithm, based on the bat algorithm. The Bat algorithm is hybridized with differential evolution strategies. Besides showing very promising results of the standard benchmark functions, this hybridization also significantly improves the original bat algorithm.
Energy Technology Data Exchange (ETDEWEB)
Geist, G.A. [Oak Ridge National Lab., TN (United States). Computer Science and Mathematics Div.; Howell, G.W. [Florida Inst. of Tech., Melbourne, FL (United States). Dept. of Applied Mathematics; Watkins, D.S. [Washington State Univ., Pullman, WA (United States). Dept. of Pure and Applied Mathematics
1997-11-01
The BR algorithm, a new method for calculating the eigenvalues of an upper Hessenberg matrix, is introduced. It is a bulge-chasing algorithm like the QR algorithm, but, unlike the QR algorithm, it is well adapted to computing the eigenvalues of the narrowband, nearly tridiagonal matrices generated by the look-ahead Lanczos process. This paper describes the BR algorithm and gives numerical evidence that it works well in conjunction with the Lanczos process. On the biggest problems run so far, the BR algorithm beats the QR algorithm by a factor of 30--60 in computing time and a factor of over 100 in matrix storage space.
Algorithmically specialized parallel computers
Snyder, Lawrence; Gannon, Dennis B
1985-01-01
Algorithmically Specialized Parallel Computers focuses on the concept and characteristics of an algorithmically specialized computer.This book discusses the algorithmically specialized computers, algorithmic specialization using VLSI, and innovative architectures. The architectures and algorithms for digital signal, speech, and image processing and specialized architectures for numerical computations are also elaborated. Other topics include the model for analyzing generalized inter-processor, pipelined architecture for search tree maintenance, and specialized computer organization for raster
Institute of Scientific and Technical Information of China (English)
Tian-qi WU; Min YAO; Jian-hua YANG
2016-01-01
By adopting the distributed problem-solving strategy, swarm intelligence algorithms have been successfully applied to many optimization problems that are difficult to deal with using traditional methods. At present, there are many well-implemented algorithms, such as particle swarm optimization, genetic algorithm, artificial bee colony algorithm, and ant colony optimization. These algorithms have already shown favorable performances. However, with the objects becoming increasingly complex, it is becoming gradually more difficult for these algorithms to meet human’s demand in terms of accuracy and time. Designing a new algorithm to seek better solutions for optimization problems is becoming increasingly essential. Dolphins have many noteworthy biological characteristics and living habits such as echolocation, information exchanges, cooperation, and division of labor. Combining these biological characteristics and living habits with swarm intelligence and bringing them into optimization prob-lems, we propose a brand new algorithm named the ‘dolphin swarm algorithm’ in this paper. We also provide the definitions of the algorithm and specific descriptions of the four pivotal phases in the algorithm, which are the search phase, call phase, reception phase, and predation phase. Ten benchmark functions with different properties are tested using the dolphin swarm algorithm, particle swarm optimization, genetic algorithm, and artificial bee colony algorithm. The convergence rates and benchmark func-tion results of these four algorithms are compared to testify the effect of the dolphin swarm algorithm. The results show that in most cases, the dolphin swarm algorithm performs better. The dolphin swarm algorithm possesses some great features, such as first-slow-then-fast convergence, periodic convergence, local-optimum-free, and no specific demand on benchmark functions. Moreover, the dolphin swarm algorithm is particularly appropriate to optimization problems, with more
Decoherence in Search Algorithms
Abal, G; Marquezino, F L; Oliveira, A C; Portugal, R
2009-01-01
Recently several quantum search algorithms based on quantum walks were proposed. Those algorithms differ from Grover's algorithm in many aspects. The goal is to find a marked vertex in a graph faster than classical algorithms. Since the implementation of those new algorithms in quantum computers or in other quantum devices is error-prone, it is important to analyze their robustness under decoherence. In this work we analyze the impact of decoherence on quantum search algorithms implemented on two-dimensional grids and on hypercubes.
Symplectic algebraic dynamics algorithm
Institute of Scientific and Technical Information of China (English)
2007-01-01
Based on the algebraic dynamics solution of ordinary differential equations andintegration of ,the symplectic algebraic dynamics algorithm sn is designed,which preserves the local symplectic geometric structure of a Hamiltonian systemand possesses the same precision of the na ve algebraic dynamics algorithm n.Computer experiments for the 4th order algorithms are made for five test modelsand the numerical results are compared with the conventional symplectic geometric algorithm,indicating that sn has higher precision,the algorithm-inducedphase shift of the conventional symplectic geometric algorithm can be reduced,and the dynamical fidelity can be improved by one order of magnitude.
New focused crawling algorithm
Institute of Scientific and Technical Information of China (English)
Su Guiyang; Li Jianhua; Ma Yinghua; Li Shenghong; Song Juping
2005-01-01
Focused carawling is a new research approach of search engine. It restricts information retrieval and provides search service in specific topic area. Focused crawling search algorithm is a key technique of focused crawler which directly affects the search quality. This paper first introduces several traditional topic-specific crawling algorithms, then an inverse link based topic-specific crawling algorithm is put forward. Comparison experiment proves that this algorithm has a good performance in recall, obviously better than traditional Breadth-First and Shark-Search algorithms. The experiment also proves that this algorithm has a good precision.
Competing Sudakov Veto Algorithms
Kleiss, Ronald
2016-01-01
We present a way to analyze the distribution produced by a Monte Carlo algorithm. We perform these analyses on several versions of the Sudakov veto algorithm, adding a cutoff, a second variable and competition between emission channels. The analysis allows us to prove that multiple, seemingly different competition algorithms, including those that are currently implemented in most parton showers, lead to the same result. Finally, we test their performance and show that there are significantly faster alternatives to the commonly used algorithms.
Borbely, Eva
2007-01-01
A quantum algorithm is a set of instructions for a quantum computer, however, unlike algorithms in classical computer science their results cannot be guaranteed. A quantum system can undergo two types of operation, measurement and quantum state transformation, operations themselves must be unitary (reversible). Most quantum algorithms involve a series of quantum state transformations followed by a measurement. Currently very few quantum algorithms are known and no general design methodology e...
Accurate Finite Difference Algorithms
Goodrich, John W.
1996-01-01
Two families of finite difference algorithms for computational aeroacoustics are presented and compared. All of the algorithms are single step explicit methods, they have the same order of accuracy in both space and time, with examples up to eleventh order, and they have multidimensional extensions. One of the algorithm families has spectral like high resolution. Propagation with high order and high resolution algorithms can produce accurate results after O(10(exp 6)) periods of propagation with eight grid points per wavelength.
Autonomous Star Tracker Algorithms
DEFF Research Database (Denmark)
Betto, Maurizio; Jørgensen, John Leif; Kilsgaard, Søren;
1998-01-01
Proposal, in response to an ESA R.f.P., to design algorithms for autonomous star tracker operations.The proposal also included the development of a star tracker breadboard to test the algorithms performances.......Proposal, in response to an ESA R.f.P., to design algorithms for autonomous star tracker operations.The proposal also included the development of a star tracker breadboard to test the algorithms performances....
Approximate iterative algorithms
Almudevar, Anthony Louis
2014-01-01
Iterative algorithms often rely on approximate evaluation techniques, which may include statistical estimation, computer simulation or functional approximation. This volume presents methods for the study of approximate iterative algorithms, providing tools for the derivation of error bounds and convergence rates, and for the optimal design of such algorithms. Techniques of functional analysis are used to derive analytical relationships between approximation methods and convergence properties for general classes of algorithms. This work provides the necessary background in functional analysis a
DEFF Research Database (Denmark)
Husfeldt, Thore
2015-01-01
This chapter presents an introduction to graph colouring algorithms. The focus is on vertex-colouring algorithms that work for general classes of graphs with worst-case performance guarantees in a sequential model of computation. The presentation aims to demonstrate the breadth of available...... techniques and is organized by algorithmic paradigm....
Nature-inspired optimization algorithms
Yang, Xin-She
2014-01-01
Nature-Inspired Optimization Algorithms provides a systematic introduction to all major nature-inspired algorithms for optimization. The book's unified approach, balancing algorithm introduction, theoretical background and practical implementation, complements extensive literature with well-chosen case studies to illustrate how these algorithms work. Topics include particle swarm optimization, ant and bee algorithms, simulated annealing, cuckoo search, firefly algorithm, bat algorithm, flower algorithm, harmony search, algorithm analysis, constraint handling, hybrid methods, parameter tuning
Akl, Selim G
1985-01-01
Parallel Sorting Algorithms explains how to use parallel algorithms to sort a sequence of items on a variety of parallel computers. The book reviews the sorting problem, the parallel models of computation, parallel algorithms, and the lower bounds on the parallel sorting problems. The text also presents twenty different algorithms, such as linear arrays, mesh-connected computers, cube-connected computers. Another example where algorithm can be applied is on the shared-memory SIMD (single instruction stream multiple data stream) computers in which the whole sequence to be sorted can fit in the
Modified Clipped LMS Algorithm
Directory of Open Access Journals (Sweden)
Lotfizad Mojtaba
2005-01-01
Full Text Available Abstract A new algorithm is proposed for updating the weights of an adaptive filter. The proposed algorithm is a modification of an existing method, namely, the clipped LMS, and uses a three-level quantization ( scheme that involves the threshold clipping of the input signals in the filter weight update formula. Mathematical analysis shows the convergence of the filter weights to the optimum Wiener filter weights. Also, it can be proved that the proposed modified clipped LMS (MCLMS algorithm has better tracking than the LMS algorithm. In addition, this algorithm has reduced computational complexity relative to the unmodified one. By using a suitable threshold, it is possible to increase the tracking capability of the MCLMS algorithm compared to the LMS algorithm, but this causes slower convergence. Computer simulations confirm the mathematical analysis presented.
Zhou, Xiaojun; Gui, Weihua
2012-01-01
In terms of the concepts of state and state transition, a new heuristic random search algorithm named state transition algorithm is proposed. For continuous function optimization problems, four special transformation operators called rotation, translation, expansion and axesion are designed. Adjusting measures of the transformations are mainly studied to keep the balance of exploration and exploitation. Convergence analysis is also discussed about the algorithm based on random search method. In the meanwhile, to strengthen the search ability in high dimensional space, communication strategy is introduced into the basic algorithm and intermittent exchange is presented to prevent premature convergence. Finally, experiments are carried out for the algorithms. With 10 common benchmark unconstrained continuous functions used to test the performance, the results show that state transition algorithms are promising algorithms due to their good global search capability and convergence property when compared with some ...
Adaptive Alternating Minimization Algorithms
Niesen, Urs; Wornell, Gregory
2007-01-01
The classical alternating minimization (or projection) algorithm has been successful in the context of solving optimization problems over two variables or equivalently of finding a point in the intersection of two sets. The iterative nature and simplicity of the algorithm has led to its application to many areas such as signal processing, information theory, control, and finance. A general set of sufficient conditions for the convergence and correctness of the algorithm is quite well-known when the underlying problem parameters are fixed. In many practical situations, however, the underlying problem parameters are changing over time, and the use of an adaptive algorithm is more appropriate. In this paper, we study such an adaptive version of the alternating minimization algorithm. As a main result of this paper, we provide a general set of sufficient conditions for the convergence and correctness of the adaptive algorithm. Perhaps surprisingly, these conditions seem to be the minimal ones one would expect in ...
Introduction to Evolutionary Algorithms
Yu, Xinjie
2010-01-01
Evolutionary algorithms (EAs) are becoming increasingly attractive for researchers from various disciplines, such as operations research, computer science, industrial engineering, electrical engineering, social science, economics, etc. This book presents an insightful, comprehensive, and up-to-date treatment of EAs, such as genetic algorithms, differential evolution, evolution strategy, constraint optimization, multimodal optimization, multiobjective optimization, combinatorial optimization, evolvable hardware, estimation of distribution algorithms, ant colony optimization, particle swarm opti
Redesigning linear algebra algorithms
Energy Technology Data Exchange (ETDEWEB)
Dongarra, J.J.
1983-01-01
Many of the standard algorithms in linear algebra as implemented in FORTRAN do not achieve maximum performance on today's large-scale vector computers. The author examines the problem and constructs alternative formulations of algorithms that do not lose the clarity of the original algorithm or sacrifice the FORTRAN portable environment, but do gain the performance attainable on these supercomputers. The resulting implementation not only performs well on vector computers but also increases performance on conventional sequential computers. 13 references.
Redesigning linear algebra algorithms
Energy Technology Data Exchange (ETDEWEB)
Dongarra, J.J.
1983-01-01
Many of the standard algorithms in linear algebra as implemented in FORTRAN do not achieve maximum performance on today's large-scale vector computers. In this paper we examine the problem and construct alternative formulations of algorithms that do not lose the clarity of the original algorithm or sacrifice the Fortran portable environment, but do gain the performance attainable on these supercomputers. The resulting implementation not only performs well on vector computers but also increases performance on conventional sequential computers.
Deductive Algorithmic Knowledge
Pucella, Riccardo
2004-01-01
The framework of algorithmic knowledge assumes that agents use algorithms to compute the facts they explicitly know. In many cases of interest, a deductive system, rather than a particular algorithm, captures the formal reasoning used by the agents to compute what they explicitly know. We introduce a logic for reasoning about both implicit and explicit knowledge with the latter defined with respect to a deductive system formalizing a logical theory for agents. The highly structured nature of ...
Integer factorization algorithms
Bogataj, Polona
2011-01-01
The decomposition of a natural number into a product of prime numbers is called factorization. The main problem with factorization is the fact that there is no known efficient algorithm which would factor a given natural number n in polynomial time. The closest equivalent to such an algorithm is Shor's algorithm for quantum computers, which is still not practically applicable. The difficulties with factorization form the basis for modern cryptosystems—the most renowned among them is the RSA a...
Recursive forgetting algorithms
DEFF Research Database (Denmark)
Parkum, Jens; Poulsen, Niels Kjølstad; Holst, Jan
1992-01-01
In the first part of the paper, a general forgetting algorithm is formulated and analysed. It contains most existing forgetting schemes as special cases. Conditions are given ensuring that the basic convergence properties will hold. In the second part of the paper, the results are applied...... to a specific algorithm with selective forgetting. Here, the forgetting is non-uniform in time and space. The theoretical analysis is supported by a simulation example demonstrating the practical performance of this algorithm...
Fingerprint Feature Extraction Algorithm
Directory of Open Access Journals (Sweden)
Mehala. G
2014-03-01
Full Text Available The goal of this paper is to design an efficient Fingerprint Feature Extraction (FFE algorithm to extract the fingerprint features for Automatic Fingerprint Identification Systems (AFIS. FFE algorithm, consists of two major subdivisions, Fingerprint image preprocessing, Fingerprint image postprocessing. A few of the challenges presented in an earlier are, consequently addressed, in this paper. The proposed algorithm is able to enhance the fingerprint image and also extracting true minutiae.
Fingerprint Feature Extraction Algorithm
Mehala. G
2014-01-01
The goal of this paper is to design an efficient Fingerprint Feature Extraction (FFE) algorithm to extract the fingerprint features for Automatic Fingerprint Identification Systems (AFIS). FFE algorithm, consists of two major subdivisions, Fingerprint image preprocessing, Fingerprint image postprocessing. A few of the challenges presented in an earlier are, consequently addressed, in this paper. The proposed algorithm is able to enhance the fingerprint image and also extractin...
Spectral Decomposition Algorithm (SDA)
National Aeronautics and Space Administration — Spectral Decomposition Algorithm (SDA) is an unsupervised feature extraction technique similar to PCA that was developed to better distinguish spectral features in...
Explaining algorithms using metaphors
Forišek, Michal
2013-01-01
There is a significant difference between designing a new algorithm, proving its correctness, and teaching it to an audience. When teaching algorithms, the teacher's main goal should be to convey the underlying ideas and to help the students form correct mental models related to the algorithm. This process can often be facilitated by using suitable metaphors. This work provides a set of novel metaphors identified and developed as suitable tools for teaching many of the 'classic textbook' algorithms taught in undergraduate courses worldwide. Each chapter provides exercises and didactic notes fo
Parallel Algorithms for Normalization
Boehm, Janko; Laplagne, Santiago; Pfister, Gerhard; Steenpass, Andreas; Steidel, Stefan
2011-01-01
Given a reduced affine algebra A over a perfect field K, we present parallel algorithms to compute the normalization \\bar{A} of A. Our starting point is the algorithm of Greuel, Laplagne, and Seelisch, which is an improvement of de Jong's algorithm. First, we propose to stratify the singular locus Sing(A) in a way which is compatible with normalization, apply a local version of the normalization algorithm at each stratum, and find \\bar{A} by putting the local results together. Second, in the case where K = Q is the field of rationals, we propose modular versions of the global and local algorithms. We have implemented our algorithms in the computer algebra system SINGULAR and compare their performance with that of other algorithms. In the case where K = Q, we also discuss the use of modular computations of Groebner bases, radicals and primary decompositions. We point out that in most examples, the new algorithms outperform the algorithm of Greuel, Laplagne, and Seelisch by far, even if we do not run them in pa...
DEFF Research Database (Denmark)
Bilardi, Gianfranco; Pietracaprina, Andrea; Pucci, Geppino;
2016-01-01
A framework is proposed for the design and analysis of network-oblivious algorithms, namely algorithms that can run unchanged, yet efficiently, on a variety of machines characterized by different degrees of parallelism and communication capabilities. The framework prescribes that a network......-oblivious algorithm be specified on a parallel model of computation where the only parameter is the problem’s input size, and then evaluated on a model with two parameters, capturing parallelism granularity and communication latency. It is shown that for a wide class of network-oblivious algorithms, optimality...... of cache hierarchies, to the realm of parallel computation. Its effectiveness is illustrated by providing optimal network-oblivious algorithms for a number of key problems. Some limitations of the oblivious approach are also discussed....
A New Modified Firefly Algorithm
Directory of Open Access Journals (Sweden)
Medha Gupta
2016-07-01
Full Text Available Nature inspired meta-heuristic algorithms studies the emergent collective intelligence of groups of simple agents. Firefly Algorithm is one of the new such swarm-based metaheuristic algorithm inspired by the flashing behavior of fireflies. The algorithm was first proposed in 2008 and since then has been successfully used for solving various optimization problems. In this work, we intend to propose a new modified version of Firefly algorithm (MoFA and later its performance is compared with the standard firefly algorithm along with various other meta-heuristic algorithms. Numerical studies and results demonstrate that the proposed algorithm is superior to existing algorithms.
Directory of Open Access Journals (Sweden)
Hans Schonemann
1996-12-01
Full Text Available Some algorithms for singularity theory and algebraic geometry The use of Grobner basis computations for treating systems of polynomial equations has become an important tool in many areas. This paper introduces of the concept of standard bases (a generalization of Grobner bases and the application to some problems from algebraic geometry. The examples are presented as SINGULAR commands. A general introduction to Grobner bases can be found in the textbook [CLO], an introduction to syzygies in [E] and [St1]. SINGULAR is a computer algebra system for computing information about singularities, for use in algebraic geometry. The basic algorithms in SINGULAR are several variants of a general standard basis algorithm for general monomial orderings (see [GG]. This includes wellorderings (Buchberger algorithm ([B1], [B2] and tangent cone orderings (Mora algorithm ([M1], [MPT] as special cases: It is able to work with non-homogeneous and homogeneous input and also to compute in the localization of the polynomial ring in 0. Recent versions include algorithms to factorize polynomials and a factorizing Grobner basis algorithm. For a complete description of SINGULAR see [Si].
Unsupervised learning algorithms
Aydin, Kemal
2016-01-01
This book summarizes the state-of-the-art in unsupervised learning. The contributors discuss how with the proliferation of massive amounts of unlabeled data, unsupervised learning algorithms, which can automatically discover interesting and useful patterns in such data, have gained popularity among researchers and practitioners. The authors outline how these algorithms have found numerous applications including pattern recognition, market basket analysis, web mining, social network analysis, information retrieval, recommender systems, market research, intrusion detection, and fraud detection. They present how the difficulty of developing theoretically sound approaches that are amenable to objective evaluation have resulted in the proposal of numerous unsupervised learning algorithms over the past half-century. The intended audience includes researchers and practitioners who are increasingly using unsupervised learning algorithms to analyze their data. Topics of interest include anomaly detection, clustering,...
A Simple Calculator Algorithm.
Cook, Lyle; McWilliam, James
1983-01-01
The problem of finding cube roots when limited to a calculator with only square root capability is discussed. An algorithm is demonstrated and explained which should always produce a good approximation within a few iterations. (MP)
Quantum algorithmic information theory
Svozil, Karl
1995-01-01
The agenda of quantum algorithmic information theory, ordered `top-down,' is the quantum halting amplitude, followed by the quantum algorithmic information content, which in turn requires the theory of quantum computation. The fundamental atoms processed by quantum computation are the quantum bits which are dealt with in quantum information theory. The theory of quantum computation will be based upon a model of universal quantum computer whose elementary unit is a two-port interferometer capa...
Algorithmic Problem Complexity
Burgin, Mark
2008-01-01
People solve different problems and know that some of them are simple, some are complex and some insoluble. The main goal of this work is to develop a mathematical theory of algorithmic complexity for problems. This theory is aimed at determination of computer abilities in solving different problems and estimation of resources that computers need to do this. Here we build the part of this theory related to static measures of algorithms. At first, we consider problems for finite words and stud...
The proximal distance algorithm
Lange, Kenneth; Keys, Kevin L.
2015-01-01
The MM principle is a device for creating optimization algorithms satisfying the ascent or descent property. The current survey emphasizes the role of the MM principle in nonlinear programming. For smooth functions, one can construct an adaptive interior point method based on scaled Bregmann barriers. This algorithm does not follow the central path. For convex programming subject to nonsmooth constraints, one can combine an exact penalty method with distance majorization to create versatile a...
Institute of Scientific and Technical Information of China (English)
WANG Ji-Ke; MAO Ze-Pu; BIAN Jian-Ming; CAO Guo-Fu; CAO Xue-Xiang; CHEN Shen-Jian; DENG Zi-Yan; FU Cheng-Dong; GAO Yuan-Ning; HE Kang-Lin; HE Miao; HUA Chun-Fei; HUANG Bin; HUANG Xing-Tao; JI Xiao-Sin; LI Fei; LI Hai-Bo; LI Wei-Dong; LIANG Yu-Tie; LIU Chun-Xiu; LIU Huai-Min; LIU Suo; LIU Ying-Jie; MA Qiu-Mei; MA Xiang; MAO Ya-Jun; MO Xiao-Hu; PAN Ming-Hua; PANG Cai-Ying; PING Rong-Gang; QIN Ya-Hong; QIU Jin-Fa; SUN Sheng-Sen; SUN Yong-Zhao; WANG Liang-Liang; WEN Shuo-Pin; WU Ling-Hui; XIE Yu-Guang; XU Min; YAN Liang; YOU Zheng-Yun; YUAN Chang-Zheng; YUAN Ye; ZHANG Bing-Yun; ZHANG Chang-Chun; ZHANG Jian-Yong; ZHANG Xue-Yao; ZHANG Yao; ZHENG Yang-Heng; ZHU Ke-Jun; ZHU Yong-Sheng; ZHU Zhi-Li; ZOU Jia-Heng
2009-01-01
A track fitting algorithm based on the Kalman filter method has been developed for BESⅢ of BEPCⅡ.The effects of multiple scattering and energy loss when the charged particles go through the detector,non-uniformity of magnetic field (NUMF) and wire sag, etc., have been carefully handled.This algorithm works well and the performance satisfies the physical requirements tested by the simulation data.
Optimization algorithms and applications
Arora, Rajesh Kumar
2015-01-01
Choose the Correct Solution Method for Your Optimization ProblemOptimization: Algorithms and Applications presents a variety of solution techniques for optimization problems, emphasizing concepts rather than rigorous mathematical details and proofs. The book covers both gradient and stochastic methods as solution techniques for unconstrained and constrained optimization problems. It discusses the conjugate gradient method, Broyden-Fletcher-Goldfarb-Shanno algorithm, Powell method, penalty function, augmented Lagrange multiplier method, sequential quadratic programming, method of feasible direc
Institute of Scientific and Technical Information of China (English)
无
2008-01-01
The search for patterns or motifs in data represents a problem area of key interest to finance and economic researchers. In this paper, we introduce the motif tracking algorithm (MTA), a novel immune inspired (IS) pattern identification tool that is able to identify unknown motifs of a non specified length which repeat within time series data. The power of the algorithm comes from the fact that it uses a small number of parameters with minimal assumptions regarding the data being examined or the underlying motifs. Our interest lies in applying the algorithm to financial time series data to identify unknown patterns that exist. The algorithm is tested using three separate data sets. Particular suitability to financial data is shown by applying it to oil price data. In all cases, the algorithm identifies the presence of a motif population in a fast and efficient manner due to the utilization of an intuitive symbolic representation.The resulting population of motifs is shown to have considerable potential value for other applications such as forecasting and algorithm seeding.
Institute of Scientific and Technical Information of China (English)
WANG ShunJin; ZHANG Hua
2007-01-01
Based on the exact analytical solution of ordinary differential equations,a truncation of the Taylor series of the exact solution to the Nth order leads to the Nth order algebraic dynamics algorithm.A detailed numerical comparison is presented with Runge-Kutta algorithm and symplectic geometric algorithm for 12 test models.The results show that the algebraic dynamics algorithm can better preserve both geometrical and dynamical fidelity of a dynamical system at a controllable precision,and it can solve the problem of algorithm-induced dissipation for the Runge-Kutta algorithm and the problem of algorithm-induced phase shift for the symplectic geometric algorithm.
Institute of Scientific and Technical Information of China (English)
2007-01-01
Based on the exact analytical solution of ordinary differential equations, a truncation of the Taylor series of the exact solution to the Nth order leads to the Nth order algebraic dynamics algorithm. A detailed numerical comparison is presented with Runge-Kutta algorithm and symplectic geometric algorithm for 12 test models. The results show that the algebraic dynamics algorithm can better preserve both geometrical and dynamical fidelity of a dynamical system at a controllable precision, and it can solve the problem of algorithm-induced dissipation for the Runge-Kutta algorithm and the problem of algorithm-induced phase shift for the symplectic geometric algorithm.
Wilson, William; Aickelin, Uwe; 10.1007/s11633.008.0032.0
2010-01-01
The search for patterns or motifs in data represents a problem area of key interest to finance and economic researchers. In this paper we introduce the Motif Tracking Algorithm, a novel immune inspired pattern identification tool that is able to identify unknown motifs of a non specified length which repeat within time series data. The power of the algorithm comes from the fact that it uses a small number of parameters with minimal assumptions regarding the data being examined or the underlying motifs. Our interest lies in applying the algorithm to financial time series data to identify unknown patterns that exist. The algorithm is tested using three separate data sets. Particular suitability to financial data is shown by applying it to oil price data. In all cases the algorithm identifies the presence of a motif population in a fast and efficient manner due to the utilisation of an intuitive symbolic representation. The resulting population of motifs is shown to have considerable potential value for other ap...
A Parallel Butterfly Algorithm
Poulson, Jack
2014-02-04
The butterfly algorithm is a fast algorithm which approximately evaluates a discrete analogue of the integral transform (Equation Presented.) at large numbers of target points when the kernel, K(x, y), is approximately low-rank when restricted to subdomains satisfying a certain simple geometric condition. In d dimensions with O(Nd) quasi-uniformly distributed source and target points, when each appropriate submatrix of K is approximately rank-r, the running time of the algorithm is at most O(r2Nd logN). A parallelization of the butterfly algorithm is introduced which, assuming a message latency of α and per-process inverse bandwidth of β, executes in at most (Equation Presented.) time using p processes. This parallel algorithm was then instantiated in the form of the open-source DistButterfly library for the special case where K(x, y) = exp(iΦ(x, y)), where Φ(x, y) is a black-box, sufficiently smooth, real-valued phase function. Experiments on Blue Gene/Q demonstrate impressive strong-scaling results for important classes of phase functions. Using quasi-uniform sources, hyperbolic Radon transforms, and an analogue of a three-dimensional generalized Radon transform were, respectively, observed to strong-scale from 1-node/16-cores up to 1024-nodes/16,384-cores with greater than 90% and 82% efficiency, respectively. © 2014 Society for Industrial and Applied Mathematics.
Fusion of motion segmentation algorithms
Ellis, Anna-Louise
2008-01-01
Many algorithms have been developed to achieve motion segmentation for video surveillance. The algorithms produce varying performances under the infinite amount of changing conditions. It has been recognised that individually these algorithms have useful properties. Fusing the statistical result of these algorithms is investigated, with robust motion segmentation in mind.
Quantum CPU and Quantum Algorithm
Wang, An Min
1999-01-01
Making use of an universal quantum network -- QCPU proposed by me\\upcite{My1}, it is obtained that the whole quantum network which can implement some the known quantum algorithms including Deutsch algorithm, quantum Fourier transformation, Shor's algorithm and Grover's algorithm.
CERN. Geneva; PUNZI, Giovanni
2015-01-01
Charge particle reconstruction is one of the most demanding computational tasks found in HEP, and it becomes increasingly important to perform it in real time. We envision that HEP would greatly benefit from achieving a long-term goal of making track reconstruction happen transparently as part of the detector readout ("detector-embedded tracking"). We describe here a track-reconstruction approach based on a massively parallel pattern-recognition algorithm, inspired by studies of the processing of visual images by the brain as it happens in nature ('RETINA algorithm'). It turns out that high-quality tracking in large HEP detectors is possible with very small latencies, when this algorithm is implemented in specialized processors, based on current state-of-the-art, high-speed/high-bandwidth digital devices.
Handbook of Memetic Algorithms
Cotta, Carlos; Moscato, Pablo
2012-01-01
Memetic Algorithms (MAs) are computational intelligence structures combining multiple and various operators in order to address optimization problems. The combination and interaction amongst operators evolves and promotes the diffusion of the most successful units and generates an algorithmic behavior which can handle complex objective functions and hard fitness landscapes. “Handbook of Memetic Algorithms” organizes, in a structured way, all the the most important results in the field of MAs since their earliest definition until now. A broad review including various algorithmic solutions as well as successful applications is included in this book. Each class of optimization problems, such as constrained optimization, multi-objective optimization, continuous vs combinatorial problems, uncertainties, are analysed separately and, for each problem, memetic recipes for tackling the difficulties are given with some successful examples. Although this book contains chapters written by multiple authors, ...
Temperature Corrected Bootstrap Algorithm
Comiso, Joey C.; Zwally, H. Jay
1997-01-01
A temperature corrected Bootstrap Algorithm has been developed using Nimbus-7 Scanning Multichannel Microwave Radiometer data in preparation to the upcoming AMSR instrument aboard ADEOS and EOS-PM. The procedure first calculates the effective surface emissivity using emissivities of ice and water at 6 GHz and a mixing formulation that utilizes ice concentrations derived using the current Bootstrap algorithm but using brightness temperatures from 6 GHz and 37 GHz channels. These effective emissivities are then used to calculate surface ice which in turn are used to convert the 18 GHz and 37 GHz brightness temperatures to emissivities. Ice concentrations are then derived using the same technique as with the Bootstrap algorithm but using emissivities instead of brightness temperatures. The results show significant improvement in the area where ice temperature is expected to vary considerably such as near the continental areas in the Antarctic, where the ice temperature is colder than average, and in marginal ice zones.
DEFF Research Database (Denmark)
Vissing, S.; Hededal, O.
An algorithm is presented for computing the m smallest eigenvalues and corresponding eigenvectors of the generalized eigenvalue problem (A - λB)Φ = 0 where A and B are real n x n symmetric matrices. In an iteration scheme the matrices A and B are projected simultaneously onto an m-dimensional sub......An algorithm is presented for computing the m smallest eigenvalues and corresponding eigenvectors of the generalized eigenvalue problem (A - λB)Φ = 0 where A and B are real n x n symmetric matrices. In an iteration scheme the matrices A and B are projected simultaneously onto an m......-dimensional subspace in order to establish and solve a symmetric generalized eigenvalue problem in the subspace. The algorithm is described in pseudo code and implemented in the C programming language for lower triangular matrices A and B. The implementation includes procedures for selecting initial iteration vectors...
Directory of Open Access Journals (Sweden)
T. Karpagam
2012-01-01
Full Text Available Problem statement: Network topology design problems find application in several real life scenario. Approach: Most designs in the past either optimize for a single criterion like shortest or cost minimization or maximum flow. Results: This study discussed about solving a multi objective network topology design problem for a realistic traffic model specifically in the pipeline transportation. Here flow based algorithm focusing to transport liquid goods with maximum capacity with shortest distance, this algorithm developed with the sense of basic pert and critical path method. Conclusion/Recommendations: This flow based algorithm helps to give optimal result for transporting maximum capacity with minimum cost. It could be used in the juice factory, milk industry and its best alternate for the vehicle routing problem.
An Ordering Linear Unification Algorithm
Institute of Scientific and Technical Information of China (English)
胡运发
1989-01-01
In this paper,we present an ordering linear unification algorithm(OLU).A new idea on substituteion of the binding terms is introduced to the algorithm,which is able to overcome some drawbacks of other algorithms,e.g.,MM algorithm[1],RG1 and RG2 algorithms[2],Particularly,if we use the directed eyclie graphs,the algoritm needs not check the binding order,then the OLU algorithm can also be aplied to the infinite tree data struceture,and a higher efficiency can be expected.The paper focuses upon the discussion of OLU algorithm and a partial order structure with respect to the unification algorithm.This algorithm has been implemented in the GKD-PROLOG/VAX 780 interpreting system.Experimental results have shown that the algorithm is very simple and efficient.
Fast Local Computation Algorithms
Rubinfeld, Ronitt; Tamir, Gil; Vardi, Shai; Xie, Ning
2011-01-01
For input $x$, let $F(x)$ denote the set of outputs that are the "legal" answers for a computational problem $F$. Suppose $x$ and members of $F(x)$ are so large that there is not time to read them in their entirety. We propose a model of {\\em local computation algorithms} which for a given input $x$, support queries by a user to values of specified locations $y_i$ in a legal output $y \\in F(x)$. When more than one legal output $y$ exists for a given $x$, the local computation algorithm should...
Algorithms for Reinforcement Learning
Szepesvari, Csaba
2010-01-01
Reinforcement learning is a learning paradigm concerned with learning to control a system so as to maximize a numerical performance measure that expresses a long-term objective. What distinguishes reinforcement learning from supervised learning is that only partial feedback is given to the learner about the learner's predictions. Further, the predictions may have long term effects through influencing the future state of the controlled system. Thus, time plays a special role. The goal in reinforcement learning is to develop efficient learning algorithms, as well as to understand the algorithms'
A Generalized Jacobi Algorithm
DEFF Research Database (Denmark)
Vissing, S.; Krenk, S.
An algorithm is developed for the generalized eigenvalue problem (A - λB)φ = O where A and B are real symmetric matrices. The matrices A and B are diagonalized simultaneously by a series of generalized Jacobi transformations and all eigenvalues and eigenvectors are obtained. A criterion expressed...... in terms of the transformation parameters is used to omit transformations leading to very small changes. The algorithm is described in pseudo code for lower triangular matrices A and B and implemented in the programming Language C....
Randomized Filtering Algorithms
DEFF Research Database (Denmark)
Katriel, Irit; Van Hentenryck, Pascal
2008-01-01
of AllDifferent and is generalization, the Global Cardinality Constraint. The first delayed filtering scheme is a Monte Carlo algorithm: its running time is superior, in the worst case, to that of enforcing are consistency after every domain event, while its filtering effectiveness is analyzed...... in the expected sense. The second scheme is a Las Vegas algorithm using filtering triggers: Its effectiveness is the same as enforcing are consistency after every domain event, while in the expected case it is faster by a factor of m/n, where n and m are, respectively, the number of nodes and edges...
Tiled QR factorization algorithms
Bouwmeester, Henricus; Jacquelin, Mathias; Langou, Julien; Robert, Yves
2011-01-01
This work revisits existing algorithms for the QR factorization of rectangular matrices composed of p-by-q tiles, where p >= q. Within this framework, we study the critical paths and performance of algorithms such as Sameh and Kuck, Modi and Clarke, Greedy, and those found within PLASMA. Although neither Modi and Clarke nor Greedy is optimal, both are shown to be asymptotically optimal for all matrices of size p = q^2 f(q), where f is any function such that \\lim_{+\\infty} f= 0. This novel and...
Wireless communications algorithmic techniques
Vitetta, Giorgio; Colavolpe, Giulio; Pancaldi, Fabrizio; Martin, Philippa A
2013-01-01
This book introduces the theoretical elements at the basis of various classes of algorithms commonly employed in the physical layer (and, in part, in MAC layer) of wireless communications systems. It focuses on single user systems, so ignoring multiple access techniques. Moreover, emphasis is put on single-input single-output (SISO) systems, although some relevant topics about multiple-input multiple-output (MIMO) systems are also illustrated.Comprehensive wireless specific guide to algorithmic techniquesProvides a detailed analysis of channel equalization and channel coding for wi
Algorithm for structure constants
Paiva, F M
2011-01-01
In a $n$-dimensional Lie algebra, random numerical values are assigned by computer to $n(n-1)$ especially selected structure constants. An algorithm is then created, which calculates without ambiguity the remaining constants, obeying the Jacobi conditions. Differently from others, this algorithm is suitable even for poor personal computer. ------------- En $n$-dimensia algebro de Lie, hazardaj numeraj valoroj estas asignitaj per komputilo al $n(n-1)$ speciale elektitaj konstantoj de strukturo. Tiam algoritmo estas kreita, kalkulante senambigue la ceterajn konstantojn, obeante kondicxojn de Jacobi. Malsimile al aliaj algoritmoj, tiu cxi tauxgas ecx por malpotenca komputilo.
Parallel Algorithms and Patterns
Energy Technology Data Exchange (ETDEWEB)
Robey, Robert W. [Los Alamos National Lab. (LANL), Los Alamos, NM (United States)
2016-06-16
This is a powerpoint presentation on parallel algorithms and patterns. A parallel algorithm is a well-defined, step-by-step computational procedure that emphasizes concurrency to solve a problem. Examples of problems include: Sorting, searching, optimization, matrix operations. A parallel pattern is a computational step in a sequence of independent, potentially concurrent operations that occurs in diverse scenarios with some frequency. Examples are: Reductions, prefix scans, ghost cell updates. We only touch on parallel patterns in this presentation. It really deserves its own detailed discussion which Gabe Rockefeller would like to develop.
A Panoply of Quantum Algorithms
Furrow, Bartholomew
2006-01-01
We create a variety of new quantum algorithms that use Grover's algorithm and similar techniques to give polynomial speedups over their classical counterparts. We begin by introducing a set of tools that carefully minimize the impact of errors on running time; those tools provide us with speedups to already-published quantum algorithms, such as improving Durr, Heiligman, Hoyer and Mhalla's algorithm for single-source shortest paths [quant-ph/0401091] by a factor of lg N. The algorithms we con...
The Middle Pivot Element Algorithm
Anchala Kumari; Soubhik Chakraborty
2012-01-01
This paper is an improvement over the previous work on New Sorting Algorithm first proposed by Sundararajan and Chakraborty (2007). Here we have taken the pivot element as the middle element of the array. We call this improved version Middle Pivot Element Algorithm (MPA) and it is found that MPA is much faster than the two algorithms RPA (Random Pivot element Algorithm) and FPA (First Pivot element Algorithm) in which the pivot element was selected either randomly or as the first element, res...
New Optimization Algorithms in Physics
Hartmann, Alexander K
2004-01-01
Many physicists are not aware of the fact that they can solve their problems by applying optimization algorithms. Since the number of such algorithms is steadily increasing, many new algorithms have not been presented comprehensively until now. This presentation of recently developed algorithms applied in physics, including demonstrations of how they work and related results, aims to encourage their application, and as such the algorithms selected cover concepts and methods from statistical physics to optimization problems emerging in theoretical computer science.
Automatic design of decision-tree algorithms with evolutionary algorithms.
Barros, Rodrigo C; Basgalupp, Márcio P; de Carvalho, André C P L F; Freitas, Alex A
2013-01-01
This study reports the empirical analysis of a hyper-heuristic evolutionary algorithm that is capable of automatically designing top-down decision-tree induction algorithms. Top-down decision-tree algorithms are of great importance, considering their ability to provide an intuitive and accurate knowledge representation for classification problems. The automatic design of these algorithms seems timely, given the large literature accumulated over more than 40 years of research in the manual design of decision-tree induction algorithms. The proposed hyper-heuristic evolutionary algorithm, HEAD-DT, is extensively tested using 20 public UCI datasets and 10 microarray gene expression datasets. The algorithms automatically designed by HEAD-DT are compared with traditional decision-tree induction algorithms, such as C4.5 and CART. Experimental results show that HEAD-DT is capable of generating algorithms which are significantly more accurate than C4.5 and CART.
Python algorithms mastering basic algorithms in the Python language
Hetland, Magnus Lie
2014-01-01
Python Algorithms, Second Edition explains the Python approach to algorithm analysis and design. Written by Magnus Lie Hetland, author of Beginning Python, this book is sharply focused on classical algorithms, but it also gives a solid understanding of fundamental algorithmic problem-solving techniques. The book deals with some of the most important and challenging areas of programming and computer science in a highly readable manner. It covers both algorithmic theory and programming practice, demonstrating how theory is reflected in real Python programs. Well-known algorithms and data struc
Drake, Michael
2011-01-01
One debate that periodically arises in mathematics education is the issue of how to teach calculation more effectively. "Modern" approaches seem to initially favour mental calculation, informal methods, and the development of understanding before introducing written forms, while traditionalists tend to champion particular algorithms. The debate is…
Thulasiraman, K
2011-01-01
This adaptation of an earlier work by the authors is a graduate text and professional reference on the fundamentals of graph theory. It covers the theory of graphs, its applications to computer networks and the theory of graph algorithms. Also includes exercises and an updated bibliography.
Hogg, T; Polak, W H; Rieffel, E; Hogg, Tad; Mochon, Carlos; Polak, Wolfgang; Rieffel, Eleanor
1999-01-01
We present efficient implementations of a number of operations for quantum computers. These include controlled phase adjustments of the amplitudes in a superposition, permutations, approximations of transformations and generalizations of the phase adjustments to block matrix transformations. These operations generalize those used in proposed quantum search algorithms.
Comprehensive eye evaluation algorithm
Agurto, C.; Nemeth, S.; Zamora, G.; Vahtel, M.; Soliz, P.; Barriga, S.
2016-03-01
In recent years, several research groups have developed automatic algorithms to detect diabetic retinopathy (DR) in individuals with diabetes (DM), using digital retinal images. Studies have indicated that diabetics have 1.5 times the annual risk of developing primary open angle glaucoma (POAG) as do people without DM. Moreover, DM patients have 1.8 times the risk for age-related macular degeneration (AMD). Although numerous investigators are developing automatic DR detection algorithms, there have been few successful efforts to create an automatic algorithm that can detect other ocular diseases, such as POAG and AMD. Consequently, our aim in the current study was to develop a comprehensive eye evaluation algorithm that not only detects DR in retinal images, but also automatically identifies glaucoma suspects and AMD by integrating other personal medical information with the retinal features. The proposed system is fully automatic and provides the likelihood of each of the three eye disease. The system was evaluated in two datasets of 104 and 88 diabetic cases. For each eye, we used two non-mydriatic digital color fundus photographs (macula and optic disc centered) and, when available, information about age, duration of diabetes, cataracts, hypertension, gender, and laboratory data. Our results show that the combination of multimodal features can increase the AUC by up to 5%, 7%, and 8% in the detection of AMD, DR, and glaucoma respectively. Marked improvement was achieved when laboratory results were combined with retinal image features.
General cardinality genetic algorithms
Koehler; Bhattacharyya; Vose
1997-01-01
A complete generalization of the Vose genetic algorithm model from the binary to higher cardinality case is provided. Boolean AND and EXCLUSIVE-OR operators are replaced by multiplication and addition over rings of integers. Walsh matrices are generalized with finite Fourier transforms for higher cardinality usage. Comparison of results to the binary case are provided. PMID:10021767
Institute of Scientific and Technical Information of China (English)
袁亚湘
1995-01-01
The DFP method is one of the most famous numerical algorithms for unconstrained optimization. For uniformly convex objective functions convergence properties of the DFP method are studied. Several conditions that can ensure the global convergence of the DFP method are given.
An Algorithmic Diversity Diet?
DEFF Research Database (Denmark)
Sørensen, Jannick Kirk; Schmidt, Jan-Hinrik
2016-01-01
With the growing influence of personalized algorithmic recommender systems on the exposure of media content to users, the relevance of discussing the diversity of recommendations increases, particularly as far as public service media (PSM) is concerned. An imagined implementation of a diversity d...
Algorithmic information theory
P.D. Grünwald; P.M.B. Vitányi
2008-01-01
We introduce algorithmic information theory, also known as the theory of Kolmogorov complexity. We explain the main concepts of this quantitative approach to defining `information'. We discuss the extent to which Kolmogorov's and Shannon's information theory have a common purpose, and where they are
Algorithmic information theory
P.D. Grünwald; P.M.B. Vitányi
2008-01-01
We introduce algorithmic information theory, also known as the theory of Kolmogorov complexity. We explain the main concepts of this quantitative approach to defining 'information'. We discuss the extent to which Kolmogorov's and Shannon's information theory have a common purpose, and where they are
The Copenhagen Triage Algorithm
DEFF Research Database (Denmark)
Hasselbalch, Rasmus Bo; Plesner, Louis Lind; Pries-Heje, Mia;
2016-01-01
is non-inferior to an existing triage model in a prospective randomized trial. METHODS: The Copenhagen Triage Algorithm (CTA) study is a prospective two-center, cluster-randomized, cross-over, non-inferiority trial comparing CTA to the Danish Emergency Process Triage (DEPT). We include patients ≥16 years...
de Casteljau's Algorithm Revisited
DEFF Research Database (Denmark)
Gravesen, Jens
1998-01-01
It is demonstrated how all the basic properties of Bezier curves can be derived swiftly and efficiently without any reference to the Bernstein polynomials and essentially with only geometric arguments. This is achieved by viewing one step in de Casteljau's algorithm as an operator (the de Casteljau...
Modular Regularization Algorithms
DEFF Research Database (Denmark)
Jacobsen, Michael
2004-01-01
The class of linear ill-posed problems is introduced along with a range of standard numerical tools and basic concepts from linear algebra, statistics and optimization. Known algorithms for solving linear inverse ill-posed problems are analyzed to determine how they can be decomposed into indepen......The class of linear ill-posed problems is introduced along with a range of standard numerical tools and basic concepts from linear algebra, statistics and optimization. Known algorithms for solving linear inverse ill-posed problems are analyzed to determine how they can be decomposed...... into independent modules. These modules are then combined to form new regularization algorithms with other properties than those we started out with. Several variations are tested using the Matlab toolbox MOORe Tools created in connection with this thesis. Object oriented programming techniques are explained...... and used to set up the illposed problems in the toolbox. Hereby, we are able to write regularization algorithms that automatically exploit structure in the ill-posed problem without being rewritten explicitly. We explain how to implement a stopping criteria for a parameter choice method based upon...
Multisource Algorithmic Information Theory
Shen, Alexander
2006-01-01
Multisource information theory is well known in Shannon setting. It studies the possibilities of information transfer through a network with limited capacities. Similar questions could be studied for algorithmic information theory and provide a framework for several known results and interesting questions.
A propositional CONEstrip algorithm
Quaeghebeur, E.; Laurent, A.; Strauss, O.; Bouchon-Meunier, B.; Yager, R.R.
2014-01-01
We present a variant of the CONEstrip algorithm for checking whether the origin lies in a finitely generated convex cone that can be open, closed, or neither. This variant is designed to deal efficiently with problems where the rays defining the cone are specified as linear combinations of propositi
The Xmath Integration Algorithm
Bringslid, Odd
2009-01-01
The projects Xmath (Bringslid and Canessa, 2002) and dMath (Bringslid, de la Villa and Rodriguez, 2007) were supported by the European Commission in the so called Minerva Action (Xmath) and The Leonardo da Vinci programme (dMath). The Xmath eBook (Bringslid, 2006) includes algorithms into a wide range of undergraduate mathematical issues embedded…
Benchmarking monthly homogenization algorithms
Directory of Open Access Journals (Sweden)
V. K. C. Venema
2011-08-01
Full Text Available The COST (European Cooperation in Science and Technology Action ES0601: Advances in homogenization methods of climate series: an integrated approach (HOME has executed a blind intercomparison and validation study for monthly homogenization algorithms. Time series of monthly temperature and precipitation were evaluated because of their importance for climate studies and because they represent two important types of statistics (additive and multiplicative. The algorithms were validated against a realistic benchmark dataset. The benchmark contains real inhomogeneous data as well as simulated data with inserted inhomogeneities. Random break-type inhomogeneities were added to the simulated datasets modeled as a Poisson process with normally distributed breakpoint sizes. To approximate real world conditions, breaks were introduced that occur simultaneously in multiple station series within a simulated network of station data. The simulated time series also contained outliers, missing data periods and local station trends. Further, a stochastic nonlinear global (network-wide trend was added.
Participants provided 25 separate homogenized contributions as part of the blind study as well as 22 additional solutions submitted after the details of the imposed inhomogeneities were revealed. These homogenized datasets were assessed by a number of performance metrics including (i the centered root mean square error relative to the true homogeneous value at various averaging scales, (ii the error in linear trend estimates and (iii traditional contingency skill scores. The metrics were computed both using the individual station series as well as the network average regional series. The performance of the contributions depends significantly on the error metric considered. Contingency scores by themselves are not very informative. Although relative homogenization algorithms typically improve the homogeneity of temperature data, only the best ones improve
Skeletonization Algorithm for Numeral Patterns
Directory of Open Access Journals (Sweden)
Gupta Rakesh
2008-12-01
Full Text Available Skeletonization has been a part of morphological image processing for a wide variety of applications. Skeletonization algorithms have played an important role in the preprocessing phase of OCR systems. Many algorithms for vectorization by skeletonization have been devised and applied to a great variety of pictures and drawings for data compression, pattern recognition and raster-to-vector conversion. The vectorization algorithms often used in pattern recognition tasks also require one-pixel-wide lines as input. But parallel skeletonization algorithms which generate one-pixel-wide skeletons can have difficulty in preserving the connectivity of an image or generate spurious branches. In this paper an alternative parallel skeletonization algorithm has been developed and implemented. This algorithm is better than already existing algorithms in terms of connectivity and spurious branches. A few most common skeletonization algorithms have been implemented and evaluated on the basis of performance parameters and compared with newly developed algorithm.
Genetic Algorithms and Local Search
Whitley, Darrell
1996-01-01
The first part of this presentation is a tutorial level introduction to the principles of genetic search and models of simple genetic algorithms. The second half covers the combination of genetic algorithms with local search methods to produce hybrid genetic algorithms. Hybrid algorithms can be modeled within the existing theoretical framework developed for simple genetic algorithms. An application of a hybrid to geometric model matching is given. The hybrid algorithm yields results that improve on the current state-of-the-art for this problem.
An efficient algorithm for function optimization: modified stem cells algorithm
Taherdangkoo, Mohammad; Paziresh, Mahsa; Yazdi, Mehran; Bagheri, Mohammad
2013-03-01
In this paper, we propose an optimization algorithm based on the intelligent behavior of stem cell swarms in reproduction and self-organization. Optimization algorithms, such as the Genetic Algorithm (GA), Particle Swarm Optimization (PSO) algorithm, Ant Colony Optimization (ACO) algorithm and Artificial Bee Colony (ABC) algorithm, can give solutions to linear and non-linear problems near to the optimum for many applications; however, in some case, they can suffer from becoming trapped in local optima. The Stem Cells Algorithm (SCA) is an optimization algorithm inspired by the natural behavior of stem cells in evolving themselves into new and improved cells. The SCA avoids the local optima problem successfully. In this paper, we have made small changes in the implementation of this algorithm to obtain improved performance over previous versions. Using a series of benchmark functions, we assess the performance of the proposed algorithm and compare it with that of the other aforementioned optimization algorithms. The obtained results prove the superiority of the Modified Stem Cells Algorithm (MSCA).
Convex hull ranking algorithm for multi-objective evolutionary algorithms
Davoodi Monfrared, M.; Mohades, A.; Rezaei, J.
2012-01-01
Due to many applications of multi-objective evolutionary algorithms in real world optimization problems, several studies have been done to improve these algorithms in recent years. Since most multi-objective evolutionary algorithms are based on the non-dominated principle, and their complexity depen
Evolutionary algorithm based index assignment algorithm for noisy channel
Institute of Scientific and Technical Information of China (English)
李天昊; 余松煜
2004-01-01
A globally optimal solution to vector quantization (VQ) index assignment on noisy channel, the evolutionary algorithm based index assignment algorithm (EAIAA), is presented. The algorithm yields a significant reduction in average distortion due to channel errors, over conventional arbitrary index assignment, as confirmed by experimental results over the memoryless binary symmetric channel (BSC) for any bit error.
Deprit, André; Palacián, Jesúus; Deprit, Etienne
2001-03-01
The relegation algorithm extends the method of normalization by Lie transformations. Given a Hamiltonian that is a power series ℋ = ℋ0+ ɛℋ1+ ... of a small parameter ɛ, normalization constructs a map which converts the principal part ℋ0into an integral of the transformed system — relegation does the same for an arbitrary function ℋ[G]. If the Lie derivative induced by ℋ[G] is semi-simple, a double recursion produces the generator of the relegating transformation. The relegation algorithm is illustrated with an elementary example borrowed from galactic dynamics; the exercise serves as a standard against which to test software implementations. Relegation is also applied to the more substantial example of a Keplerian system perturbed by radiation pressure emanating from a rotating source.
Evaluating Discourse Processing Algorithms
Walker, M A
1994-01-01
In order to take steps towards establishing a methodology for evaluating Natural Language systems, we conducted a case study. We attempt to evaluate two different approaches to anaphoric processing in discourse by comparing the accuracy and coverage of two published algorithms for finding the co-specifiers of pronouns in naturally occurring texts and dialogues. We present the quantitative results of hand-simulating these algorithms, but this analysis naturally gives rise to both a qualitative evaluation and recommendations for performing such evaluations in general. We illustrate the general difficulties encountered with quantitative evaluation. These are problems with: (a) allowing for underlying assumptions, (b) determining how to handle underspecifications, and (c) evaluating the contribution of false positives and error chaining.
Institute of Scientific and Technical Information of China (English)
LIU Shan; LIAO Yongyi
2007-01-01
In this paper,We study the Apriori and FP-growth algorithm in mining association rules and give a method for computing all the frequent item-sets in a database.Its basic idea is giving a concept based on the boolean vector business product,which be computed between all the businesses,then we can get all the two frequent item-sets (min_sup=2).We basis their inclusive relation to construct a set-tree of item-sets in database transaction,and then traverse path in it and get all the frequent item-sets.Therefore,we can get minimal frequent item sets between transactions and items in the database without scanning the database and iteratively computing in Apriori algorithm.
Partitional clustering algorithms
2015-01-01
This book summarizes the state-of-the-art in partitional clustering. Clustering, the unsupervised classification of patterns into groups, is one of the most important tasks in exploratory data analysis. Primary goals of clustering include gaining insight into, classifying, and compressing data. Clustering has a long and rich history that spans a variety of scientific disciplines including anthropology, biology, medicine, psychology, statistics, mathematics, engineering, and computer science. As a result, numerous clustering algorithms have been proposed since the early 1950s. Among these algorithms, partitional (nonhierarchical) ones have found many applications, especially in engineering and computer science. This book provides coverage of consensus clustering, constrained clustering, large scale and/or high dimensional clustering, cluster validity, cluster visualization, and applications of clustering. Examines clustering as it applies to large and/or high-dimensional data sets commonly encountered in reali...
SYMBOLIC VERSOR COMPRESSION ALGORITHM
Institute of Scientific and Technical Information of China (English)
Li Hongbo
2009-01-01
In an inner-product space, an invertible vector generates a reflection with re-spect to a hyperplane, and the Clifford product of several invertible vectors, called a versor in Clifford algebra, generates the composition of the corresponding reflections, which is an orthogonal transformation. Given a versor in a Clifford algebra, finding another sequence of invertible vectors of strictly shorter length but whose Clifford product still equals the input versor, is called versor compression. Geometrically, versor compression is equivalent to decomposing an orthogoual transformation into a shorter sequence of reflections. This paper proposes a simple algorithm of compressing versors of symbolic form in Clifford algebra. The algorithm is based on computing the intersections of lines with planes in the corresponding Grassmann-Cayley algebra, and is complete in the case of Euclidean or Minkowski inner-product space.
Demaine, Erik D.; Lynch, Jayson; Mirano, Geronimo J.; Tyagi, Nirvan
2016-01-01
We initiate the systematic study of the energy complexity of algorithms (in addition to time and space complexity) based on Landauer's Principle in physics, which gives a lower bound on the amount of energy a system must dissipate if it destroys information. We propose energy-aware variations of three standard models of computation: circuit RAM, word RAM, and transdichotomous RAM. On top of these models, we build familiar high-level primitives such as control logic, memory allocation, and gar...
Boosting foundations and algorithms
Schapire, Robert E
2012-01-01
Boosting is an approach to machine learning based on the idea of creating a highly accurate predictor by combining many weak and inaccurate "rules of thumb." A remarkably rich theory has evolved around boosting, with connections to a range of topics, including statistics, game theory, convex optimization, and information geometry. Boosting algorithms have also enjoyed practical success in such fields as biology, vision, and speech processing. At various times in its history, boosting has been perceived as mysterious, controversial, even paradoxical.
Graph algorithms for bioinformatics
Profiti, Giuseppe
2015-01-01
Biological data are inherently interconnected: protein sequences are connected to their annotations, the annotations are structured into ontologies, and so on. While protein-protein interactions are already represented by graphs, in this work I am presenting how a graph structure can be used to enrich the annotation of protein sequences thanks to algorithms that analyze the graph topology. We also describe a novel solution to restrict the data generation needed for building such a graph, than...
Evertz, Hans Gerd
1998-03-01
Exciting new investigations have recently become possible for strongly correlated systems of spins, bosons, and fermions, through Quantum Monte Carlo simulations with the Loop Algorithm (H.G. Evertz, G. Lana, and M. Marcu, Phys. Rev. Lett. 70, 875 (1993).) (For a recent review see: H.G. Evertz, xxx.lanl.gov/abs/cond-mat/9707221>cond- mat/9707221.) and its generalizations. A review of this new method, its generalizations and its applications is given, including some new results. The Loop Algorithm is based on a formulation of physical models in an extended ensemble of worldlines and graphs, and is related to Swendsen-Wang cluster algorithms. It performs nonlocal changes of worldline configurations, determined by local stochastic decisions. It overcomes many of the difficulties of traditional worldline simulations. Computer time requirements are reduced by orders of magnitude, through a corresponding reduction in autocorrelations. The grand-canonical ensemble (e.g. varying winding numbers) is naturally simulated. The continuous time limit can be taken directly. Improved Estimators exist which further reduce the errors of measured quantities. The algorithm applies unchanged in any dimension and for varying bond-strengths. It becomes less efficient in the presence of strong site disorder or strong magnetic fields. It applies directly to locally XYZ-like spin, fermion, and hard-core boson models. It has been extended to the Hubbard and the tJ model and generalized to higher spin representations. There have already been several large scale applications, especially for Heisenberg-like models, including a high statistics continuous time calculation of quantum critical exponents on a regularly depleted two-dimensional lattice of up to 20000 spatial sites at temperatures down to T=0.01 J.
Genetic Algorithm for Optimization: Preprocessor and Algorithm
Sen, S. K.; Shaykhian, Gholam A.
2006-01-01
Genetic algorithm (GA) inspired by Darwin's theory of evolution and employed to solve optimization problems - unconstrained or constrained - uses an evolutionary process. A GA has several parameters such the population size, search space, crossover and mutation probabilities, and fitness criterion. These parameters are not universally known/determined a priori for all problems. Depending on the problem at hand, these parameters need to be decided such that the resulting GA performs the best. We present here a preprocessor that achieves just that, i.e., it determines, for a specified problem, the foregoing parameters so that the consequent GA is a best for the problem. We stress also the need for such a preprocessor both for quality (error) and for cost (complexity) to produce the solution. The preprocessor includes, as its first step, making use of all the information such as that of nature/character of the function/system, search space, physical/laboratory experimentation (if already done/available), and the physical environment. It also includes the information that can be generated through any means - deterministic/nondeterministic/graphics. Instead of attempting a solution of the problem straightway through a GA without having/using the information/knowledge of the character of the system, we would do consciously a much better job of producing a solution by using the information generated/created in the very first step of the preprocessor. We, therefore, unstintingly advocate the use of a preprocessor to solve a real-world optimization problem including NP-complete ones before using the statistically most appropriate GA. We also include such a GA for unconstrained function optimization problems.
Building Better Nurse Scheduling Algorithms
Aickelin, Uwe
2008-01-01
The aim of this research is twofold: Firstly, to model and solve a complex nurse scheduling problem with an integer programming formulation and evolutionary algorithms. Secondly, to detail a novel statistical method of comparing and hence building better scheduling algorithms by identifying successful algorithm modifications. The comparison method captures the results of algorithms in a single figure that can then be compared using traditional statistical techniques. Thus, the proposed method of comparing algorithms is an objective procedure designed to assist in the process of improving an algorithm. This is achieved even when some results are non-numeric or missing due to infeasibility. The final algorithm outperforms all previous evolutionary algorithms, which relied on human expertise for modification.
Disk Scheduling: Selection of Algorithm
Yashvir, S.; Prakash, Om
2012-01-01
The objective of this paper is to take some aspects of disk scheduling and scheduling algorithms. The disk scheduling is discussed with a sneak peak in general and selection of algorithm in particular.
Large scale tracking algorithms.
Energy Technology Data Exchange (ETDEWEB)
Hansen, Ross L.; Love, Joshua Alan; Melgaard, David Kennett; Karelitz, David B.; Pitts, Todd Alan; Zollweg, Joshua David; Anderson, Dylan Z.; Nandy, Prabal; Whitlow, Gary L.; Bender, Daniel A.; Byrne, Raymond Harry
2015-01-01
Low signal-to-noise data processing algorithms for improved detection, tracking, discrimination and situational threat assessment are a key research challenge. As sensor technologies progress, the number of pixels will increase signi cantly. This will result in increased resolution, which could improve object discrimination, but unfortunately, will also result in a significant increase in the number of potential targets to track. Many tracking techniques, like multi-hypothesis trackers, suffer from a combinatorial explosion as the number of potential targets increase. As the resolution increases, the phenomenology applied towards detection algorithms also changes. For low resolution sensors, "blob" tracking is the norm. For higher resolution data, additional information may be employed in the detection and classfication steps. The most challenging scenarios are those where the targets cannot be fully resolved, yet must be tracked and distinguished for neighboring closely spaced objects. Tracking vehicles in an urban environment is an example of such a challenging scenario. This report evaluates several potential tracking algorithms for large-scale tracking in an urban environment.
Multipurpose audio watermarking algorithm
Institute of Scientific and Technical Information of China (English)
Ning CHEN; Jie ZHU
2008-01-01
To make audio watermarking accomplish both copyright protection and content authentication with localization, a novel multipurpose audio watermarking scheme is proposed in this paper. The zero-watermarking idea is introduced into the design of robust watermarking algorithm to ensure the transparency and to avoid the interference between the robust watermark and the semi-fragile watermark. The property of natural audio that the VQ indices of DWT-DCT coefficients among neighboring frames tend to be very similar is utilized to extract essential feature from the host audio, which is then used for watermark extraction. And, the chaotic mapping based semi-fragile watermark is embedded in the detail wavelet coefficients based on the instantaneous mixing model of the independent component analysis (ICA) system. Both the robust and semi-fragile watermarks can be extracted blindly and the semi-fragile watermarking algorithm can localize the tampering accurately. Simulation results demonstrate the effectiveness of our algorithm in terms of transparency, security, robustness and tampering localization ability.
Energy Technology Data Exchange (ETDEWEB)
Symbalisty, E.M.D.; Zinn, J.; Whitaker, R.W.
1995-09-01
This paper describes the history, physics, and algorithms of the computer code RADFLO and its extension HYCHEM. RADFLO is a one-dimensional, radiation-transport hydrodynamics code that is used to compute early-time fireball behavior for low-altitude nuclear bursts. The primary use of the code is the prediction of optical signals produced by nuclear explosions. It has also been used to predict thermal and hydrodynamic effects that are used for vulnerability and lethality applications. Another closely related code, HYCHEM, is an extension of RADFLO which includes the effects of nonequilibrium chemistry. Some examples of numerical results will be shown, along with scaling expressions derived from those results. We describe new computations of the structures and luminosities of steady-state shock waves and radiative thermal waves, which have been extended to cover a range of ambient air densities for high-altitude applications. We also describe recent modifications of the codes to use a one-dimensional analog of the CAVEAT fluid-dynamics algorithm in place of the former standard Richtmyer-von Neumann algorithm.
Join-Graph Propagation Algorithms
Mateescu, Robert; Kask, Kalev; Gogate, Vibhav; Dechter, Rina
2014-01-01
The paper investigates parameterized approximate message-passing schemes that are based on bounded inference and are inspired by Pearl's belief propagation algorithm (BP). We start with the bounded inference mini-clustering algorithm and then move to the iterative scheme called Iterative Join-Graph Propagation (IJGP), that combines both iteration and bounded inference. Algorithm IJGP belongs to the class of Generalized Belief Propagation algorithms, a framework that allowed connections with a...
Open Mass Spectrometry Search Algorithm
Geer, L Y; Kowalak, J A; Wagner, L; Xu, M; Maynard, D M; Yang, X; Shi, W; Bryant, S H; Geer, Lewis Y.; Markey, Sanford P.; Kowalak, Jeffrey A.; Wagner, Lukas; Xu, Ming; Maynard, Dawn M.; Yang, Xiaoyu; Shi, Wenyao; Bryant, Stephen H.
2004-01-01
Large numbers of MS/MS peptide spectra generated in proteomics experiments require efficient, sensitive and specific algorithms for peptide identification. In the Open Mass Spectrometry Search Algorithm [OMSSA], specificity is calculated by a classic probability score using an explicit model for matching experimental spectra to sequences. At default thresholds, OMSSA matches more spectra from a standard protein cocktail than a comparable algorithm. OMSSA is designed to be faster than published algorithms in searching large MS/MS datasets.
A Novel Rule Induction Algorithm
Institute of Scientific and Technical Information of China (English)
ZHENG Jianguo; LIU Fang; WANG Lei; JIAO Licheng
2001-01-01
Knowledge discovery in databases is concerned with extracting useful information from databases, and the immune algorithm is a biological theory-based and globally searching algorithm. A specific immune algorithm is designed for discovering a few interesting, high-level prediction rules from databases, rather than discovering classification knowledge as usual in the literatures. Simulations show that this novel algorithm is able to improve the stability of the population, increase the holistic performance and make the rules extracted have higher precision.
Genetic Algorithms and Quantum Computation
Giraldi, Gilson A.; Portugal, Renato; Thess, Ricardo N.
2004-01-01
Recently, researchers have applied genetic algorithms (GAs) to address some problems in quantum computation. Also, there has been some works in the designing of genetic algorithms based on quantum theoretical concepts and techniques. The so called Quantum Evolutionary Programming has two major sub-areas: Quantum Inspired Genetic Algorithms (QIGAs) and Quantum Genetic Algorithms (QGAs). The former adopts qubit chromosomes as representations and employs quantum gates for the search of the best ...
Foundations of genetic algorithms 1991
FOGA
1991-01-01
Foundations of Genetic Algorithms 1991 (FOGA 1) discusses the theoretical foundations of genetic algorithms (GA) and classifier systems.This book compiles research papers on selection and convergence, coding and representation, problem hardness, deception, classifier system design, variation and recombination, parallelization, and population divergence. Other topics include the non-uniform Walsh-schema transform; spurious correlations and premature convergence in genetic algorithms; and variable default hierarchy separation in a classifier system. The grammar-based genetic algorithm; condition
Combinatorial optimization algorithms and complexity
Papadimitriou, Christos H
1998-01-01
This clearly written, mathematically rigorous text includes a novel algorithmic exposition of the simplex method and also discusses the Soviet ellipsoid algorithm for linear programming; efficient algorithms for network flow, matching, spanning trees, and matroids; the theory of NP-complete problems; approximation algorithms, local search heuristics for NP-complete problems, more. All chapters are supplemented by thought-provoking problems. A useful work for graduate-level students with backgrounds in computer science, operations research, and electrical engineering.
Essential algorithms a practical approach to computer algorithms
Stephens, Rod
2013-01-01
A friendly and accessible introduction to the most useful algorithms Computer algorithms are the basic recipes for programming. Professional programmers need to know how to use algorithms to solve difficult programming problems. Written in simple, intuitive English, this book describes how and when to use the most practical classic algorithms, and even how to create new algorithms to meet future needs. The book also includes a collection of questions that can help readers prepare for a programming job interview. Reveals methods for manipulating common data structures s
Continuous Media Tasks Scheduling Algorithm
Directory of Open Access Journals (Sweden)
Myungryun Yoo
2016-03-01
Full Text Available In this paper the authors propose modified proportional share scheduling algorithm considering the characteristics of continuous media such as its continuity and time dependency. Proposed scheduling algorithm shows graceful degradation of performance in overloaded situation and decreases the number of context switching. Proposed scheduling algorithm is evaluated using several numerical tests under various conditions, especially overloaded situation.
Polyceptron: A Polyhedral Learning Algorithm
Manwani, Naresh
2011-01-01
In this paper we propose a new algorithm for learning polyhedral classifiers which we call as Polyceptron. It is a Perception like algorithm which updates the parameters only when the current classifier misclassifies any training data. We give both batch and online version of Polyceptron algorithm. Finally we give experimental results to show the effectiveness of our approach.
Comparison of Text Categorization Algorithms
Institute of Scientific and Technical Information of China (English)
SHI Yong-feng; ZHAO Yan-ping
2004-01-01
This paper summarizes several automatic text categorization algorithms in common use recently, analyzes and compares their advantages and disadvantages.It provides clues for making use of appropriate automatic classifying algorithms in different fields.Finally some evaluations and summaries of these algorithms are discussed, and directions to further research have been pointed out.
Perceptual hashing algorithms benchmark suite
Institute of Scientific and Technical Information of China (English)
Zhang Hui; Schmucker Martin; Niu Xiamu
2007-01-01
Numerous perceptual hashing algorithms have been developed for identification and verification of multimedia objects in recent years. Many application schemes have been adopted for various commercial objects. Developers and users are looking for a benchmark tool to compare and evaluate their current algorithms or technologies. In this paper, a novel benchmark platform is presented. PHABS provides an open framework and lets its users define their own test strategy, perform tests, collect and analyze test data. With PHABS, various performance parameters of algorithms can be tested, and different algorithms or algorithms with different parameters can be evaluated and compared easily.
HISTORY BASED PROBABILISTIC BACKOFF ALGORITHM
Directory of Open Access Journals (Sweden)
Narendran Rajagopalan
2012-01-01
Full Text Available Performance of Wireless LAN can be improved at each layer of the protocol stack with respect to energy efficiency. The Media Access Control layer is responsible for the key functions like access control and flow control. During contention, Backoff algorithm is used to gain access to the medium with minimum probability of collision. After studying different variations of back off algorithms that have been proposed, a new variant called History based Probabilistic Backoff Algorithm is proposed. Through mathematical analysis and simulation results using NS-2, it is seen that proposed History based Probabilistic Backoff algorithm performs better than Binary Exponential Backoff algorithm.
Directory of Open Access Journals (Sweden)
Jyoti Kalyani
2006-01-01
Full Text Available Security of wired and wireless networks is the most challengeable in today's computer world. The aim of this study was to give brief introduction about viruses and worms, their creators and characteristics of algorithms used by viruses. Here wired and wireless network viruses are elaborated. Also viruses are compared with human immune system. On the basis of this comparison four guidelines are given to detect viruses so that more secure systems are made. While concluding this study it is found that the security is most challengeable, thus it is required to make more secure models which automatically detect viruses and prevent the system from its affect.
QCA & CQCA: Quad Countries Algorithm and Chaotic Quad Countries Algorithm
Directory of Open Access Journals (Sweden)
M. A. Soltani-Sarvestani
2012-09-01
Full Text Available This paper introduces an improved evolutionary algorithm based on the Imperialist Com-petitive Algorithm (ICA, called Quad Countries Algorithm (QCA and with a little change called Chaotic Quad Countries Algorithm (CQCA. The Imperialist Competitive Algorithm is inspired by socio-political process of imperialistic competition in the real world and has shown its reliable performance in optimization problems. This algorithm converges quickly, but is easily stuck into a local optimum while solving high-dimensional optimization prob-lems. In the ICA, the countries are classified into two groups: Imperialists and Colonies which Imperialists absorb Colonies, while in the proposed algorithm two other kinds of countries, namely Independent and Seeking Independence countries, are added to the coun-tries collection which helps to more exploration. In the suggested algorithm, Seeking Inde-pendence countries move in a contrary direction to the Imperialists and Independent countries move arbitrarily that in this paper two different movements are considered for this group; random movement (QCA and Chaotic movement (CQCA. On the other hand, in the ICA the Imperialists’ positions are fixed, while in the proposed algorithm, Imperialists will move if they can reach a better position compared to the previous position. The proposed algorithm was tested by famous benchmarks and the compared results of the QCA and CQCA with results of ICA, Genetic Algorithm (GA, Particle Swarm Optimization (PSO, Particle Swarm inspired Evolutionary Algorithm (PS-EA and Artificial Bee Colony (ABC show that the QCA has better performance than all mentioned algorithms. Between all cases, the QCA, ABC and PSO have better performance respectively about 50%, 41.66% and 8.33% of cases.
Rabideau, Gregg R.; Chien, Steve A.
2010-01-01
AVA v2 software selects goals for execution from a set of goals that oversubscribe shared resources. The term goal refers to a science or engineering request to execute a possibly complex command sequence, such as image targets or ground-station downlinks. Developed as an extension to the Virtual Machine Language (VML) execution system, the software enables onboard and remote goal triggering through the use of an embedded, dynamic goal set that can oversubscribe resources. From the set of conflicting goals, a subset must be chosen that maximizes a given quality metric, which in this case is strict priority selection. A goal can never be pre-empted by a lower priority goal, and high-level goals can be added, removed, or updated at any time, and the "best" goals will be selected for execution. The software addresses the issue of re-planning that must be performed in a short time frame by the embedded system where computational resources are constrained. In particular, the algorithm addresses problems with well-defined goal requests without temporal flexibility that oversubscribes available resources. By using a fast, incremental algorithm, goal selection can be postponed in a "just-in-time" fashion allowing requests to be changed or added at the last minute. Thereby enabling shorter response times and greater autonomy for the system under control.
Fatigue evaluation algorithms: Review
Energy Technology Data Exchange (ETDEWEB)
Passipoularidis, V.A.; Broendsted, P.
2009-11-15
A progressive damage fatigue simulator for variable amplitude loads named FADAS is discussed in this work. FADAS (Fatigue Damage Simulator) performs ply by ply stress analysis using classical lamination theory and implements adequate stiffness discount tactics based on the failure criterion of Puck, to model the degradation caused by failure events in ply level. Residual strength is incorporated as fatigue damage accumulation metric. Once the typical fatigue and static properties of the constitutive ply are determined,the performance of an arbitrary lay-up under uniaxial and/or multiaxial load time series can be simulated. The predictions are validated against fatigue life data both from repeated block tests at a single stress ratio as well as against spectral fatigue using the WISPER, WISPERX and NEW WISPER load sequences on a Glass/Epoxy multidirectional laminate typical of a wind turbine rotor blade construction. Two versions of the algorithm, the one using single-step and the other using incremental application of each load cycle (in case of ply failure) are implemented and compared. Simulation results confirm the ability of the algorithm to take into account load sequence effects. In general, FADAS performs well in predicting life under both spectral and block loading fatigue. (author)
Algorithmic Relative Complexity
Directory of Open Access Journals (Sweden)
Daniele Cerra
2011-04-01
Full Text Available Information content and compression are tightly related concepts that can be addressed through both classical and algorithmic information theories, on the basis of Shannon entropy and Kolmogorov complexity, respectively. The definition of several entities in Kolmogorov’s framework relies upon ideas from classical information theory, and these two approaches share many common traits. In this work, we expand the relations between these two frameworks by introducing algorithmic cross-complexity and relative complexity, counterparts of the cross-entropy and relative entropy (or Kullback-Leibler divergence found in Shannon’s framework. We define the cross-complexity of an object x with respect to another object y as the amount of computational resources needed to specify x in terms of y, and the complexity of x related to y as the compression power which is lost when adopting such a description for x, compared to the shortest representation of x. Properties of analogous quantities in classical information theory hold for these new concepts. As these notions are incomputable, a suitable approximation based upon data compression is derived to enable the application to real data, yielding a divergence measure applicable to any pair of strings. Example applications are outlined, involving authorship attribution and satellite image classification, as well as a comparison to similar established techniques.
The Watershed Algorithm for Image Segmentation
Institute of Scientific and Technical Information of China (English)
OU Yan; LIN Nan
2007-01-01
This article introduced the watershed algorithm for the segmentation, illustrated the segmation process by implementing this algorithm. By comparing with another three related algorithm, this article revealed both the advantages and drawbacks of the watershed algorithm.
STAR Algorithm Integration Team - Facilitating operational algorithm development
Mikles, V. J.
2015-12-01
The NOAA/NESDIS Center for Satellite Research and Applications (STAR) provides technical support of the Joint Polar Satellite System (JPSS) algorithm development and integration tasks. Utilizing data from the S-NPP satellite, JPSS generates over thirty Environmental Data Records (EDRs) and Intermediate Products (IPs) spanning atmospheric, ocean, cryosphere, and land weather disciplines. The Algorithm Integration Team (AIT) brings technical expertise and support to product algorithms, specifically in testing and validating science algorithms in a pre-operational environment. The AIT verifies that new and updated algorithms function in the development environment, enforces established software development standards, and ensures that delivered packages are functional and complete. AIT facilitates the development of new JPSS-1 algorithms by implementing a review approach based on the Enterprise Product Lifecycle (EPL) process. Building on relationships established during the S-NPP algorithm development process and coordinating directly with science algorithm developers, the AIT has implemented structured reviews with self-contained document suites. The process has supported algorithm improvements for products such as ozone, active fire, vegetation index, and temperature and moisture profiles.
Multisensor data fusion algorithm development
Energy Technology Data Exchange (ETDEWEB)
Yocky, D.A.; Chadwick, M.D.; Goudy, S.P.; Johnson, D.K.
1995-12-01
This report presents a two-year LDRD research effort into multisensor data fusion. We approached the problem by addressing the available types of data, preprocessing that data, and developing fusion algorithms using that data. The report reflects these three distinct areas. First, the possible data sets for fusion are identified. Second, automated registration techniques for imagery data are analyzed. Third, two fusion techniques are presented. The first fusion algorithm is based on the two-dimensional discrete wavelet transform. Using test images, the wavelet algorithm is compared against intensity modulation and intensity-hue-saturation image fusion algorithms that are available in commercial software. The wavelet approach outperforms the other two fusion techniques by preserving spectral/spatial information more precisely. The wavelet fusion algorithm was also applied to Landsat Thematic Mapper and SPOT panchromatic imagery data. The second algorithm is based on a linear-regression technique. We analyzed the technique using the same Landsat and SPOT data.
Evaluating Data Assimilation Algorithms
Law, K J H
2011-01-01
Data assimilation refers to methodologies for the incorporation of noisy observations of a physical system into an underlying model in order to infer the properties of the state of the system (and/or parameters). The model itself is typically subject to uncertainties, in the input data and in the physical laws themselves. This leads naturally to a Bayesian formulation in which the posterior probability distribution of the system state, given the observations, plays a central conceptual role. The aim of this paper is to use this Bayesian posterior probability distribution as a gold standard against which to evaluate various commonly used data assimilation algorithms. A key aspect of geophysical data assimilation is the high dimensionality of the computational model. With this in mind, yet with the goal of allowing an explicit and accurate computation of the posterior distribution in order to facilitate our evaluation, we study the 2D Navier-Stokes equations in a periodic geometry. We compute the posterior prob...
Trial encoding algorithms ensemble.
Cheng, Lipin Bill; Yeh, Ren Jye
2013-01-01
This paper proposes trial algorithms for some basic components in cryptography and lossless bit compression. The symmetric encryption is accomplished by mixing up randomizations and scrambling with hashing of the key playing an essential role. The digital signature is adapted from the Hill cipher with the verification key matrices incorporating un-invertible parts to hide the signature matrix. The hash is a straight running summation (addition chain) of data bytes plus some randomization. One simplified version can be burst error correcting code. The lossless bit compressor is the Shannon-Fano coding that is less optimal than the later Huffman and Arithmetic coding, but can be conveniently implemented without the use of a tree structure and improvable with bytes concatenation.
Algorithmes, machines et langages
Berry, Gérard
2014-01-01
Enseignement : Le temps et les événements en informatique J’ai donné le cours « Le temps et les événements en informatique » dans le cadre de la chaire Algorithmes, machines et langages, créée le 4 juillet 2013 comme première chaire de plein exercice en informatique. J’avais introduit l’informatique au Collège de France en 2007-2008 par le cours « Pourquoi et comment le monde devient numérique », au sein de la chaire annuelle d’Innovation technologique Liliane Bettencourt, puis, en 2009-2010,...
Fighting Censorship with Algorithms
Mahdian, Mohammad
In countries such as China or Iran where Internet censorship is prevalent, users usually rely on proxies or anonymizers to freely access the web. The obvious difficulty with this approach is that once the address of a proxy or an anonymizer is announced for use to the public, the authorities can easily filter all traffic to that address. This poses a challenge as to how proxy addresses can be announced to users without leaking too much information to the censorship authorities. In this paper, we formulate this question as an interesting algorithmic problem. We study this problem in a static and a dynamic model, and give almost tight bounds on the number of proxy servers required to give access to n people k of whom are adversaries. We will also discuss how trust networks can be used in this context.
Fractal simplex algorithm in VBA
Ouzký, Karel
2009-01-01
Basic idea of fractal simplex algorithm is based in the theory of matrix counting and knowledge of matrix representation of simplex tabuleao from revised simplex method. My desire is to explain theoretical basics on which this algorithm works and provide solution in language Visual Basic for Applications in application MS Excel 2007. Main benefit I see in the fact, that algorithm can solved specific class of mathematical problems in a way of exactness counting whithout necessity of using deci...
Algorithms over partially ordered sets
DEFF Research Database (Denmark)
Baer, Robert M.; Østerby, Ole
1969-01-01
in partially ordered sets, answer the combinatorial question of how many maximal chains might exist in a partially ordered set withn elements, and we give an algorithm for enumerating all maximal chains. We give (in § 3) algorithms which decide whether a partially ordered set is a (lower or upper) semi......-lattice, and whether a lattice has distributive, modular, and Boolean properties. Finally (in § 4) we give Algol realizations of the various algorithms....
Tau reconstruction and identification algorithm
Indian Academy of Sciences (India)
Raman Khurana
2012-11-01
CMS has developed sophisticated tau identification algorithms for tau hadronic decay modes. Production of tau lepton decaying to hadrons are studied at 7 TeV centre-of-mass energy with 2011 collision data collected by CMS detector and has been used to measure the performance of tau identification algorithms by measuring identification efficiency and misidentification rates from electrons, muons and hadronic jets. These algorithms enable extended reach for the searches for MSSM Higgs, and other exotic particles.
Machine Learning an algorithmic perspective
Marsland, Stephen
2009-01-01
Traditional books on machine learning can be divided into two groups - those aimed at advanced undergraduates or early postgraduates with reasonable mathematical knowledge and those that are primers on how to code algorithms. The field is ready for a text that not only demonstrates how to use the algorithms that make up machine learning methods, but also provides the background needed to understand how and why these algorithms work. Machine Learning: An Algorithmic Perspective is that text.Theory Backed up by Practical ExamplesThe book covers neural networks, graphical models, reinforcement le
Diversity-Guided Evolutionary Algorithms
DEFF Research Database (Denmark)
Ursem, Rasmus Kjær
2002-01-01
Population diversity is undoubtably a key issue in the performance of evolutionary algorithms. A common hypothesis is that high diversity is important to avoid premature convergence and to escape local optima. Various diversity measures have been used to analyze algorithms, but so far few...... algorithms have used a measure to guide the search. The diversity-guided evolutionary algorithm (DGEA) uses the wellknown distance-to-average-point measure to alternate between phases of exploration (mutation) and phases of exploitation (recombination and selection). The DGEA showed remarkable results...
A New Metaheuristic Bat-Inspired Algorithm
Yang, Xin-She
2010-01-01
Metaheuristic algorithms such as particle swarm optimization, firefly algorithm and harmony search are now becoming powerful methods for solving many tough optimization problems. In this paper, we propose a new metaheuristic method, the Bat Algorithm, based on the echolocation behaviour of bats. We also intend to combine the advantages of existing algorithms into the new bat algorithm. After a detailed formulation and explanation of its implementation, we will then compare the proposed algorithm with other existing algorithms, including genetic algorithms and particle swarm optimization. Simulations show that the proposed algorithm seems much superior to other algorithms, and further studies are also discussed.
Practical Parallel External Memory Algorithms via Simulation of Parallel Algorithms
Robillard, David E
2010-01-01
This thesis introduces PEMS2, an improvement to PEMS (Parallel External Memory System). PEMS executes Bulk-Synchronous Parallel (BSP) algorithms in an External Memory (EM) context, enabling computation with very large data sets which exceed the size of main memory. Many parallel algorithms have been designed and implemented for Bulk-Synchronous Parallel models of computation. Such algorithms generally assume that the entire data set is stored in main memory at once. PEMS overcomes this limitation without requiring any modification to the algorithm by using disk space as memory for additional "virtual processors". Previous work has shown this to be a promising approach which scales well as computational resources (i.e. processors and disks) are added. However, the technique incurs significant overhead when compared with purpose-built EM algorithms. PEMS2 introduces refinements to the simulation process intended to reduce this overhead as well as the amount of disk space required to run the simulation. New func...
A Review on Quantum Search Algorithms
Giri, Pulak Ranjan; Korepin, Vladimir E.
2016-01-01
The use of superposition of states in quantum computation, known as quantum parallelism, has significant advantage in terms of speed over the classical computation. It can be understood from the early invented quantum algorithms such as Deutsch's algorithm, Deutsch-Jozsa algorithm and its variation as Bernstein-Vazirani algorithm, Simon algorithm, Shor's algorithms etc. Quantum parallelism also significantly speeds up the database search algorithm, which is important in computer science becau...
Recovery Rate of Clustering Algorithms
Li, Fajie; Klette, Reinhard; Wada, T; Huang, F; Lin, S
2009-01-01
This article provides a simple and general way for defining the recovery rate of clustering algorithms using a given family of old clusters for evaluating the performance of the algorithm when calculating a family of new clusters. Under the assumption of dealing with simulated data (i.e., known old
Two Aspects of Evolutionary Algorithms
Institute of Scientific and Technical Information of China (English)
无
2000-01-01
In this paper we discuss the paradigm of evolutionary algorithms (Eas). We argue about the need for new heuristics in real-world problem solving, discussing reasons why some problems are difficult tosolve. After introducing the main concepts of evolutionary algorithms, we concentrate on two issues:(1)self-adaptation of the parameters of EA, and (2) handling constraints.
Executable Pseudocode for Graph Algorithms
Ó Nualláin, B.
2015-01-01
Algorithms are written in pseudocode. However the implementation of an algorithm in a conventional, imperative programming language can often be scattered over hundreds of lines of code thus obscuring its essence. This can lead to difficulties in understanding or verifying the code. Adapting o
Penalty Algorithms in Hilbert Spaces
Institute of Scientific and Technical Information of China (English)
Jean Pierre DUSSAULT; Hai SHEN; André BANDRAUK
2007-01-01
We analyze the classical penalty algorithm for nonlinear programming in HUbert spaces and obtain global convergence results, as well as asymptotic superlinear convergence order. These convergence results generalize similar results obtained for finite-dimensional problems. Moreover, the nature of the algorithms allows us to solve the unconstrained subproblems in finite-dimensional spaces.
Ensemble algorithms in reinforcement learning
Wiering, Marco A; van Hasselt, Hado
2008-01-01
This paper describes several ensemble methods that combine multiple different reinforcement learning (RL) algorithms in a single agent. The aim is to enhance learning speed and final performance by combining the chosen actions or action probabilities of different RL algorithms. We designed and imple
Cascade Error Projection Learning Algorithm
Duong, T. A.; Stubberud, A. R.; Daud, T.
1995-01-01
A detailed mathematical analysis is presented for a new learning algorithm termed cascade error projection (CEP) and a general learning frame work. This frame work can be used to obtain the cascade correlation learning algorithm by choosing a particular set of parameters.
An Improved Moving Mesh Algorithm
Institute of Scientific and Technical Information of China (English)
无
2001-01-01
we consider an iterative algorithm of mesh optimization for finite element solution, and give an improved moving mesh strategy that reduces rapidly the complexity and cost of solving variational problems.A numerical result is presented for a 2-dimensional problem by the improved algorithm.
A Fast Fractional Difference Algorithm
DEFF Research Database (Denmark)
Jensen, Andreas Noack; Nielsen, Morten Ørregaard
We provide a fast algorithm for calculating the fractional difference of a time series. In standard implementations, the calculation speed (number of arithmetic operations) is of order T 2, where T is the length of the time series. Our algorithm allows calculation speed of order T log...
A distributed spanning tree algorithm
DEFF Research Database (Denmark)
Johansen, Karl Erik; Jørgensen, Ulla Lundin; Nielsen, Svend Hauge;
1988-01-01
We present a distributed algorithm for constructing a spanning tree for connected undirected graphs. Nodes correspond to processors and edges correspond to two way channels. Each processor has initially a distinct identity and all processors perform the same algorithm. Computation as well...
Algorithms in combinatorial design theory
Colbourn, CJ
1985-01-01
The scope of the volume includes all algorithmic and computational aspects of research on combinatorial designs. Algorithmic aspects include generation, isomorphism and analysis techniques - both heuristic methods used in practice, and the computational complexity of these operations. The scope within design theory includes all aspects of block designs, Latin squares and their variants, pairwise balanced designs and projective planes and related geometries.
Online co-regularized algorithms
Ruijter, T. de; Tsivtsivadze, E.; Heskes, T.
2012-01-01
We propose an online co-regularized learning algorithm for classification and regression tasks. We demonstrate that by sequentially co-regularizing prediction functions on unlabeled data points, our algorithm provides improved performance in comparison to supervised methods on several UCI benchmarks
Subcubic Control Flow Analysis Algorithms
DEFF Research Database (Denmark)
Midtgaard, Jan; Van Horn, David
We give the first direct subcubic algorithm for performing control flow analysis of higher-order functional programs. Despite the long held belief that inclusion-based flow analysis could not surpass the ``cubic bottleneck, '' we apply known set compression techniques to obtain an algorithm...
A fast fractional difference algorithm
DEFF Research Database (Denmark)
Jensen, Andreas Noack; Nielsen, Morten Ørregaard
2014-01-01
We provide a fast algorithm for calculating the fractional difference of a time series. In standard implementations, the calculation speed (number of arithmetic operations) is of order T 2, where T is the length of the time series. Our algorithm allows calculation speed of order T logT . For...
FORTRAN Algorithm for Image Processing
Roth, Don J.; Hull, David R.
1987-01-01
FORTRAN computer algorithm containing various image-processing analysis and enhancement functions developed. Algorithm developed specifically to process images of developmental heat-engine materials obtained with sophisticated nondestructive evaluation instruments. Applications of program include scientific, industrial, and biomedical imaging for studies of flaws in materials, analyses of steel and ores, and pathology.
Pulmonary thromboembolism diagnosis algorithms
Energy Technology Data Exchange (ETDEWEB)
Kasai, Takeshi; Eto, Jun; Hayano, Daisuke; Ohashi, Masaki; Yoneda, Takahiro; Oyama, Hisaya; Inaba, Akira [Kameda General Hospital, Kamogawa, Chiba (Japan). Trauma and Emergency Care Center
2002-01-01
Our algorithm for diagnosing pulmonary thromboembolism combines ventilation/perfusion scanning with clinical criteria. Our perfusion scanning criterion states that high probability defines 2 segmental perfusion defects without corresponding radiographic abnormality and indeterminate probability defines less than 2 segmental perfusion defects (low probability: less than one segmental perfusion defect; intermediate: perfusion defects between high and low probability). The clinical criterion is divided into 7 items related to symptoms and signs suggestive of pulmonary thromboembolism. More than 4 items are defined as a highly suspicious clinical manifestation (HSCM), and less than 4 are considered a low suspicious clinical manifestation (LSCM). In 31 cases of high probability, 18 of HSCM did not include pulmonary angiograhy (PAG), and 13 of LSCM included PAG (positive: 11; negative: 2). In 12 cases of indeterminate probability, 7 of LSCM were observed without PAG and 5 of HSCM with PAG (positive: 4; negative: 1). PAG performance thus decreased to 41.9%. The positive prediction of high probability is 93.5%, which is very high, compared to indeterminate probability at 33.3%. (author)
Streaming Algorithms for Line Simplification
DEFF Research Database (Denmark)
Abam, Mohammad; de Berg, Mark; Hachenberger, Peter;
2010-01-01
this problem in a streaming setting, where we only have a limited amount of storage, so that we cannot store all the points. We analyze the competitive ratio of our algorithms, allowing resource augmentation: we let our algorithm maintain a simplification with 2k (internal) points and compare the error of our...... simplification to the error of the optimal simplification with k points. We obtain the algorithms with O(1) competitive ratio for three cases: convex paths, where the error is measured using the Hausdorff distance (or Fréchet distance), xy-monotone paths, where the error is measured using the Hausdorff distance...... (or Fréchet distance), and general paths, where the error is measured using the Fréchet distance. In the first case the algorithm needs O(k) additional storage, and in the latter two cases the algorithm needs O(k 2) additional storage....
The Chopthin Algorithm for Resampling
Gandy, Axel; Lau, F. Din-Houn
2016-08-01
Resampling is a standard step in particle filters and more generally sequential Monte Carlo methods. We present an algorithm, called chopthin, for resampling weighted particles. In contrast to standard resampling methods the algorithm does not produce a set of equally weighted particles; instead it merely enforces an upper bound on the ratio between the weights. Simulation studies show that the chopthin algorithm consistently outperforms standard resampling methods. The algorithms chops up particles with large weight and thins out particles with low weight, hence its name. It implicitly guarantees a lower bound on the effective sample size. The algorithm can be implemented efficiently, making it practically useful. We show that the expected computational effort is linear in the number of particles. Implementations for C++, R (on CRAN), Python and Matlab are available.
Directory of Open Access Journals (Sweden)
Issam Dagher
2010-06-01
Full Text Available In this paper a recursive algorithm of calculating the discriminant features of thePCA-LDA procedure is introduced. This algorithm computes the principalcomponents of a sequence of vectors incrementally without estimating thecovariance matrix (so covariance-free and at the same time computing the lineardiscriminant directions along which the classes are well separated. Two majortechniques are used sequentially in a real time fashion in order to obtain the mostefficient and linearly discriminative components. This procedure is done bymerging the runs of two algorithms based on principal component analysis (PCAand linear discriminant analysis (LDA running sequentially. This algorithm isapplied to face recognition problem. Simulation results on different databasesshowed high average success rate of this algorithm compared to PCA and LDAalgorithms. The advantage of the incremental property of this algorithmcompared to the batch PCA-LDA is also shown.
A secured Cryptographic Hashing Algorithm
Mohanty, Rakesh; Bishi, Sukant kumar
2010-01-01
Cryptographic hash functions for calculating the message digest of a message has been in practical use as an effective measure to maintain message integrity since a few decades. This message digest is unique, irreversible and avoids all types of collisions for any given input string. The message digest calculated from this algorithm is propagated in the communication medium along with the original message from the sender side and on the receiver side integrity of the message can be verified by recalculating the message digest of the received message and comparing the two digest values. In this paper we have designed and developed a new algorithm for calculating the message digest of any message and implemented t using a high level programming language. An experimental analysis and comparison with the existing MD5 hashing algorithm, which is predominantly being used as a cryptographic hashing tool, shows this algorithm to provide more randomness and greater strength from intrusion attacks. In this algorithm th...
Imaging algorithms in radio interferometry
Sault, R J
2007-01-01
The paper reviews progress in imaging in radio interferometry for the period 1993-1996. Unlike an optical telescope, the basic measurements of a radio interferometer (correlations between antennas) are indirectly related to a sky brightness image. In a real sense, algorithms and computers are the lenses of a radio interferometer. In the last 20 years, whereas interferometer hardware advances have resulted in improvements of a factor of a few, algorithm and computer advances have resulted in orders of magnitude improvement in image quality. Developing these algorithms has been a fruitful and comparatively inexpensive method of improving the performance of existing telescopes, and has made some newer telescopes possible. In this paper, we review recent developments in the algorithms used in the imaging part of the reduction process. What constitutes an `imaging algorithm'? Whereas once there was a steady `forward' progression in the reduction process of editing, calibrating, transforming and, finally, deconvolv...
A New Page Ranking Algorithm Based On WPRVOL Algorithm
Directory of Open Access Journals (Sweden)
Roja Javadian Kootenae
2013-03-01
Full Text Available The amount of information on the web is always growing, thus powerful search tools are needed to search for such a large collection. Search engines in this direction help users so they can find their desirable information among the massive volume of information in an easier way. But what is important in the search engines and causes a distinction between them is page ranking algorithm used in them. In this paper a new page ranking algorithm based on "Weighted Page Ranking based on Visits of Links (WPRVOL Algorithm" for search engines is being proposed which is called WPR'VOL for short. The proposed algorithm considers the number of visits of first and second level in-links. The original WPRVOL algorithm takes into account the number of visits of first level in-links of the pages and distributes rank scores based on the popularity of the pages whereas the proposed algorithm considers both in-links of that page (first level in-links and in-links of the pages that point to it (second level in-links in order to calculation of rank of the page, hence more related pages are displayed at the top of search result list. In the summary it is said that the proposed algorithm assigns higher rank to pages that both themselves and pages that point to them be important.
Algorithmic advances in stochastic programming
Energy Technology Data Exchange (ETDEWEB)
Morton, D.P.
1993-07-01
Practical planning problems with deterministic forecasts of inherently uncertain parameters often yield unsatisfactory solutions. Stochastic programming formulations allow uncertain parameters to be modeled as random variables with known distributions, but the size of the resulting mathematical programs can be formidable. Decomposition-based algorithms take advantage of special structure and provide an attractive approach to such problems. We consider two classes of decomposition-based stochastic programming algorithms. The first type of algorithm addresses problems with a ``manageable`` number of scenarios. The second class incorporates Monte Carlo sampling within a decomposition algorithm. We develop and empirically study an enhanced Benders decomposition algorithm for solving multistage stochastic linear programs within a prespecified tolerance. The enhancements include warm start basis selection, preliminary cut generation, the multicut procedure, and decision tree traversing strategies. Computational results are presented for a collection of ``real-world`` multistage stochastic hydroelectric scheduling problems. Recently, there has been an increased focus on decomposition-based algorithms that use sampling within the optimization framework. These approaches hold much promise for solving stochastic programs with many scenarios. A critical component of such algorithms is a stopping criterion to ensure the quality of the solution. With this as motivation, we develop a stopping rule theory for algorithms in which bounds on the optimal objective function value are estimated by sampling. Rules are provided for selecting sample sizes and terminating the algorithm under which asymptotic validity of confidence interval statements for the quality of the proposed solution can be verified. Issues associated with the application of this theory to two sampling-based algorithms are considered, and preliminary empirical coverage results are presented.
Cloud-based Evolutionary Algorithms: An algorithmic study
Merelo, Juan-J; Mora, Antonio M; Castillo, Pedro; Romero, Gustavo; Laredo, JLJ
2011-01-01
After a proof of concept using Dropbox(tm), a free storage and synchronization service, showed that an evolutionary algorithm using several dissimilar computers connected via WiFi or Ethernet had a good scaling behavior in terms of evaluations per second, it remains to be proved whether that effect also translates to the algorithmic performance of the algorithm. In this paper we will check several different, and difficult, problems, and see what effects the automatic load-balancing and asynchrony have on the speed of resolution of problems.
An improved form of the ELMS algorithm
Institute of Scientific and Technical Information of China (English)
Gao Ying; Xie Shengli
2005-01-01
ELMS algorithm is the first two-channel adaptive filtering algorithm that takes into account the cross-correlation between the two input signals. The algorithm does not preprocess input signals, so it does not degrade the quality of the speech. However, a lot of computer simulation results show that ELMS algorithm has a bad performance. The ELMS algorithm is analyzed firstly, then a new algorithm is presented by modifying the block matrix used in ELMS algorithm to approximate input signals self-correlation matrix. The computer simulation results indicate that the improved algorithm has a better behavior than the ELMS algorithm.
Neighborhood-following algorithms for linear programming
Institute of Scientific and Technical Information of China (English)
AI Wenbao
2004-01-01
In this paper, we present neighborhood-following algorithms for linear programming. When the neighborhood is a wide neighborhood, our algorithms are wide neighborhood primal-dual interior point algorithms. If the neighborhood degenerates into the central path, our algorithms also degenerate into path-following algorithms. We prove that our algorithms maintain the O(√nL)-iteration complexity still, while the classical wide neighborhood primal-dual interior point algorithms have only the O(nL)-iteration complexity. We also proved that the algorithms are quadratic convergence if the optimal vertex is nondegenerate. Finally, we show some computational results of our algorithms.
Application of detecting algorithm based on network
Institute of Scientific and Technical Information of China (English)
张凤斌; 杨永田; 江子扬; 孙冰心
2004-01-01
Because currently intrusion detection systems cannot detect undefined intrusion behavior effectively,according to the robustness and adaptability of the genetic algorithms, this paper integrates the genetic algorithms into an intrusion detection system, and a detection algorithm based on network traffic is proposed. This algorithm is a real-time and self-study algorithm and can detect undefined intrusion behaviors effectively.
A general framework for shortest path algorithms
W.H.L.M. Pijls (Wim); A.W.J. Kolen
1992-01-01
textabstractIn this paper we present a general framework for shortest path algorithms, including amongst others Dijkstra's algorithm and the A* algorithm. By showing that all algorithms are special cases of one algorithm in which some of the nondeterministic choices are made deterministic, terminati
Directory of Open Access Journals (Sweden)
Ahmed Majid Taha
2015-08-01
Full Text Available In this study a new Bat Algorithm (BA based on multi-swarm technique called the Multi-Swarm Bat Algorithm (MSBA is proposed to address the problem of premature convergence phenomenon. The problem happens when search process converges to non-optimal solution due to the loss of diversity during the evolution process. MSBA was designed with improved ability in exploring new solutions, which was essential in reducing premature convergence. The exploration ability was improved by having a number of sub-swarms watching over the best local optima. In MSBA, when the quality of best local optima does not improve after a pre-defined number of iterations, the population is split equally into several smaller sub-swarms, with one of them remains close to the current best local optima for further exploitation while the other sub-swarms continue to explore for new local optima. The proposed algorithm has been applied in feature selection problem and the results were compared against eight algorithms, which are Ant Colony Optimization (ACO, Genetic Algorithm (GA, Tabu Search (TS, Scatter Search (SS, Great Deluge Algorithm (GDA and stander BA. The results showed that the MSBA is much more effective that it is able to find new best solutions at times when the rest of other algorithms are not able to.
Solving Scheduling problems using Selective Breeding Algorithm and Hybrid Algorithm
P.Sriramya; B. Parvathavarthini; M. Chandrasekaran
2013-01-01
The n-job, m-machine scheduling problem is one of the general scheduling problems in a system. Scheduling problems vary widely according to specific production tasks but most are NP-hard problems.Scheduling problems are usually solved using heuristics to get optimal or near optimal solutions because problems found in practical applications cannot be solved to optimality using reasonable resources in many cases. In this paper, Selective Breeding Algorithm (SBA) and Hybrid Algorithm (HA) are us...
Routing Algorithm Exploits Spatial Relations
Okino, Clayton; Jennings, Esther
2004-01-01
A recently developed routing algorithm for broadcasting in an ad hoc wireless communication network takes account of, and exploits, the spatial relationships among the locations of nodes, in addition to transmission power levels and distances between the nodes. In contrast, most prior algorithms for discovering routes through ad hoc networks rely heavily on transmission power levels and utilize limited graph-topology techniques that do not involve consideration of the aforesaid spatial relationships. The present algorithm extracts the relevant spatial-relationship information by use of a construct denoted the relative-neighborhood graph (RNG).
Cluster algorithms and computational complexity
Li, Xuenan
Cluster algorithms for the 2D Ising model with a staggered field have been studied and a new cluster algorithm for path sampling has been worked out. The complexity properties of Bak-Seppen model and the Growing network model have been studied by using the Computational Complexity Theory. The dynamic critical behavior of the two-replica cluster algorithm is studied. Several versions of the algorithm are applied to the two-dimensional, square lattice Ising model with a staggered field. The dynamic exponent for the full algorithm is found to be less than 0.5. It is found that odd translations of one replica with respect to the other together with global flips are essential for obtaining a small value of the dynamic exponent. The path sampling problem for the 1D Ising model is studied using both a local algorithm and a novel cluster algorithm. The local algorithm is extremely inefficient at low temperature, where the integrated autocorrelation time is found to be proportional to the fourth power of correlation length. The dynamic exponent of the cluster algorithm is found to be zero and therefore proved to be much more efficient than the local algorithm. The parallel computational complexity of the Bak-Sneppen evolution model is studied. It is shown that Bak-Sneppen histories can be generated by a massively parallel computer in a time that is polylog in the length of the history, which means that the logical depth of producing a Bak-Sneppen history is exponentially less than the length of the history. The parallel dynamics for generating Bak-Sneppen histories is contrasted to standard Bak-Sneppen dynamics. The parallel computational complexity of the Growing Network model is studied. The growth of the network with linear kernels is shown to be not complex and an algorithm with polylog parallel running time is found. The growth of the network with gamma ≥ 2 super-linear kernels can be realized by a randomized parallel algorithm with polylog expected running time.
An investigation of genetic algorithms
International Nuclear Information System (INIS)
Genetic algorithms mimic biological evolution by natural selection in their search for better individuals within a changing population. they can be used as efficient optimizers. This report discusses the developing field of genetic algorithms. It gives a simple example of the search process and introduces the concept of schema. It also discusses modifications to the basic genetic algorithm that result in species and niche formation, in machine learning and artificial evolution of computer programs, and in the streamlining of human-computer interaction. (author). 3 refs., 1 tab., 2 figs
EXACT ALGORITHM FOR BIN COVERING
Institute of Scientific and Technical Information of China (English)
无
2001-01-01
This paper presents a new arc flow model for the one-dimensional bin covering problem and an algorithm to solve the problem exactly through a branch-and-bound procedure and the technique of column generation. The subproblems occuring in the procedure of branch-and-bound have the same structure and therefore can be solved by the same algorithm. In order to solve effectively the subproblems which are generally large scale, a column generation algorithm is employed. Many rules found in this paper can improve the performance of the methods.
Instance-specific algorithm configuration
Malitsky, Yuri
2014-01-01
This book presents a modular and expandable technique in the rapidly emerging research area of automatic configuration and selection of the best algorithm for the instance at hand. The author presents the basic model behind ISAC and then details a number of modifications and practical applications. In particular, he addresses automated feature generation, offline algorithm configuration for portfolio generation, algorithm selection, adaptive solvers, online tuning, and parallelization. The author's related thesis was honorably mentioned (runner-up) for the ACP Dissertation Award in 2014,
PRACTICAL ALGORITHMS FOR TORNADO CODES
Institute of Scientific and Technical Information of China (English)
无
2006-01-01
Tornado codes have been used in the error control of data transmission in IP network. The efficiency of this erasure codes is critically affected by the short cycles in its bipartite graph. To remove this effect,two algorithms are introduced: (1) while generating the graph, the cycle eliminating algorithm is used to reduce the number of the short cycles in it; (2) in the decoding algorithm, cycles that are inevitably in the graph are used to remove decoding efficiency degradation. The simulation results show that they have a better performance than that of general tornado codes.
Variables Bounding Based Retiming Algorithm
Institute of Scientific and Technical Information of China (English)
宫宗伟; 林争辉; 陈后鹏
2002-01-01
Retiming is a technique for optimizing sequential circuits. In this paper, wediscuss this problem and propose an improved retiming algorithm based on variables bounding.Through the computation of the lower and upper bounds on variables, the algorithm can signi-ficantly reduce the number of constraints and speed up the execution of retiming. Furthermore,the elements of matrixes D and W are computed in a demand-driven way, which can reducethe capacity of memory. It is shown through the experimental results on ISCAS89 benchmarksthat our algorithm is very effective for large-scale sequential circuits.
Algorithms Design Techniques and Analysis
Alsuwaiyel, M H
1999-01-01
Problem solving is an essential part of every scientific discipline. It has two components: (1) problem identification and formulation, and (2) solution of the formulated problem. One can solve a problem on its own using ad hoc techniques or follow those techniques that have produced efficient solutions to similar problems. This requires the understanding of various algorithm design techniques, how and when to use them to formulate solutions and the context appropriate for each of them. This book advocates the study of algorithm design techniques by presenting most of the useful algorithm desi
Algebraic Approach to Algorithmic Logic
Directory of Open Access Journals (Sweden)
Bancerek Grzegorz
2014-09-01
Full Text Available We introduce algorithmic logic - an algebraic approach according to [25]. It is done in three stages: propositional calculus, quantifier calculus with equality, and finally proper algorithmic logic. For each stage appropriate signature and theory are defined. Propositional calculus and quantifier calculus with equality are explored according to [24]. A language is introduced with language signature including free variables, substitution, and equality. Algorithmic logic requires a bialgebra structure which is an extension of language signature and program algebra. While-if algebra of generator set and algebraic signature is bialgebra with appropriate properties and is used as basic type of algebraic logic.
Cascade Error Projection: A New Learning Algorithm
Duong, T. A.; Stubberud, A. R.; Daud, T.; Thakoor, A. P.
1995-01-01
A new neural network architecture and a hardware implementable learning algorithm is proposed. The algorithm, called cascade error projection (CEP), handles lack of precision and circuit noise better than existing algorithms.
Enhanced Segment Compression Steganographic Algorithm
Directory of Open Access Journals (Sweden)
STRATULAT, M.
2013-08-01
Full Text Available Steganography is the science and art of concealing messages using techniques that allow only the sender and receiver to know of the message?s existence and be able to decipher it. In this article, we would like to present a new steganographic technique for concealing digital images: the Enhanced Segment Compression Steganographic Algorithm (ESCSA. We start by mentioning several desired properties that we have taken into consideration for our algorithm. Next, we define some quality metrics with which we can measure how well / to what extent those properties are achieved. A detailed presentation of the component parts of the algorithm follows, accompanied by quantitative analyses of parameters of interest. Finally, we discuss the strengths and weaknesses of our algorithm. In addition, we make a few suggestions regarding possible further refinements of the ESCSA.
Algorithmic Cheminformatics (Dagstuhl Seminar 14452)
DEFF Research Database (Denmark)
Banzhaf, Wolfgang; Flamm, Christoph; Merkle, Daniel;
2015-01-01
Dagstuhl Seminar 14452 “Algorithmic Cheminformatics” brought together leading researchers from both chemistry and computer science. The meeting successfully aimed at bridging in the apparent gap between the two disciplines. The participants surveyed areas of overlapping interests and identified...
Planar graphs theory and algorithms
Nishizeki, T
1988-01-01
Collected in this volume are most of the important theorems and algorithms currently known for planar graphs, together with constructive proofs for the theorems. Many of the algorithms are written in Pidgin PASCAL, and are the best-known ones; the complexities are linear or 0(nlogn). The first two chapters provide the foundations of graph theoretic notions and algorithmic techniques. The remaining chapters discuss the topics of planarity testing, embedding, drawing, vertex- or edge-coloring, maximum independence set, subgraph listing, planar separator theorem, Hamiltonian cycles, and single- or multicommodity flows. Suitable for a course on algorithms, graph theory, or planar graphs, the volume will also be useful for computer scientists and graph theorists at the research level. An extensive reference section is included.
Kernel Generalized Noise Clustering Algorithm
Institute of Scientific and Technical Information of China (English)
WU Xiao-hong; ZHOU Jian-jiang
2007-01-01
To deal with the nonlinear separable problem, the generalized noise clustering (GNC) algorithm is extended to a kernel generalized noise clustering (KGNC) model. Different from the fuzzy c-means (FCM) model and the GNC model which are based on Euclidean distance, the presented model is based on kernel-induced distance by using kernel method. By kernel method the input data are nonlinearly and implicitly mapped into a high-dimensional feature space, where the nonlinear pattern appears linear and the GNC algorithm is performed. It is unnecessary to calculate in high-dimensional feature space because the kernel function can do itjust in input space. The effectiveness of the proposed algorithm is verified by experiments on three data sets. It is concluded that the KGNC algorithm has better clustering accuracy than FCM and GNC in clustering data sets containing noisy data.
Fibonacci Numbers and Computer Algorithms.
Atkins, John; Geist, Robert
1987-01-01
The Fibonacci Sequence describes a vast array of phenomena from nature. Computer scientists have discovered and used many algorithms which can be classified as applications of Fibonacci's sequence. In this article, several of these applications are considered. (PK)
United assembly algorithm for optical burst switching
Institute of Scientific and Technical Information of China (English)
Jinhui Yu(于金辉); Yijun Yang(杨教军); Yuehua Chen(陈月华); Ge Fan(范戈)
2003-01-01
Optical burst switching (OBS) is a promising optical switching technology. The burst assembly algorithm controls burst assembly, which significantly impacts performance of OBS network. This paper provides a new assembly algorithm, united assembly algorithm, which has more practicability than conventional algorithms. In addition, some factors impacting selections of parameters of this algorithm are discussed and the performance of this algorithm is studied by computer simulation.
Efficient iterative adaptive pole placement algorithm
Institute of Scientific and Technical Information of China (English)
李俊民; 李靖; 杨磊
2004-01-01
An iterative adaptive pole placement algorithm is presented. The stability and the convergence of the algorithm are respectively established. Since one-step iterative formulation in computing controller's parameters is used, the on-line computation cost is greatly reduced with respected to the traditional algorithm. The algorithm with the feed-forward can follow arbitrarily bounded output. The algorithm is also extended to multivariate case. Simulation examples show the efficiency and robustness of the algorithm.
Constructing a Scheduling Algorithm For Multidirectional Elevators
Edlund, Joakim; Berntsson, Fredrik
2015-01-01
With this thesis we aim to create an efficient scheduling algorithm for elevators that can move in multiple directions and establish if and when the algorithm is efficient in comparison to algorithms constructed for traditional elevator algorithms. To measure efficiency, a simulator is constructed to simulate an elevator system implementing different algorithms. Because of the challenge of constructing a simulator and since we did not find either a simulator nor any algorithms for use in mult...
Some tactical algorithms for spherical geometry
Shudde, Rex H.
1986-01-01
This report presents two great circle navigation algorithms, a closest point of approach algorithm and intercept algorithm. It also presents an implementation program for the algorithms that is written in the BASIC language for an IBM PC. Instead of using classical spherical geometry or the general spherical triangle, these algorithms incorporate rectangular coordinates and vectors on the surface of the spherical. The intent of the report is to provide algorithms for spherical earth models th...
Atrial Fibrillation and Pacing Algorithms
Terranova, Paolo; Severgnini, Barbara; Valli, Paolo; Dell'Orto, Simonetta; Greco, Enrico Maria
2006-01-01
Pacing prevention algorithms have been introduced in order to maximize the benefits of atrial pacing in atrial fibrillation prevention. It has been demonstrated that algorithms actually keep overdrive atrial pacing, reduce atrial premature contractions, and prevent short-long atrial cycle phenomenon, with good patient tolerance. However, clinical studies showed inconsistent benefits on clinical endpoints such as atrial fibrillation burden. Factors which may be responsible for neutral results ...
Algorithms for defects in nanostructures
Energy Technology Data Exchange (ETDEWEB)
Chan, T.-L.; Tiago, Murilo L. [Center for Computational Materials, Institute for Computational Engineering and Sciences, University of Texas, Austin, Texas 78712 (United States); Chelikowsky, James R. [Center for Computational Materials, Institute for Computational Engineering and Sciences, University of Texas, Austin, Texas 78712 (United States); Departments of Physics and Chemical Engineering, University of Texas, Austin, Texas 78712 (United States)], E-mail: jrc@ices.utexas.edu
2007-12-15
We illustrate recent progress in developing algorithms for solving the Kohn-Sham problem. Key ingredients of our algorithm include pseudopotentials implemented on a real space grid and the use of damped-Chebyshev polynomial filtered subspace iteration. This procedure allows one to predict electronic properties for many materials across the nano-regime, i.e., from atoms to nanocrystals of sufficient size to replicate bulk properties. We will illustrate this method for large silicon quantum dots doped with phosphorus defect.
An Efficient Pattern Matching Algorithm
Sleit, Azzam; Almobaideen, Wesam; Baarah, Aladdin H.; Abusitta, Adel H.
In this study, we present an efficient algorithm for pattern matching based on the combination of hashing and search trees. The proposed solution is classified as an offline algorithm. Although, this study demonstrates the merits of the technique for text matching, it can be utilized for various forms of digital data including images, audio and video. The performance superiority of the proposed solution is validated analytically and experimentally.
Algorithms to identify failure pattern
Poudel, Bhuwan Krishna Som
2013-01-01
This project report was written for ?Algorithms to Identify Failure Pattern? at NTNU (Norwegian University of Science and Technology), IME (Faculty of Information Technology, Mathematics and Electrical Engineering) and IDI (Department of Computer Science).In software application, there are three types of failure pattern: point pattern, block pattern and stripe pattern. The purpose of the report is to prepare an algorithm that identifies the pattern in a software application. Only theoretical ...
Subsampling algorithms for semidefinite programming
Directory of Open Access Journals (Sweden)
Alexandre W. d'Aspremont
2011-01-01
Full Text Available We derive a stochastic gradient algorithm for semidefinite optimization using randomization techniques. The algorithm uses subsampling to reduce the computational cost of each iteration and the subsampling ratio explicitly controls granularity, i.e. the tradeoff between cost per iteration and total number of iterations. Furthermore, the total computational cost is directly proportional to the complexity (i.e. rank of the solution. We study numerical performance on some large-scale problems arising in statistical learning.
Behavior Classification Algorithms at Intersections
Aoude, Georges; Desaraju, Vishnu Rajeswar; Stephens, Lauren H.; How, Jonathan P.
2011-01-01
The ability to classify driver behavior lays the foundation for more advanced driver assistance systems. Improving safety at intersections has also been identified as high priority due to the large number of intersection related fatalities. This paper focuses on developing algorithms for estimating driver behavior at road intersections. It introduces two classes of algorithms that can classify drivers as compliant or violating. They are based on 1) Support Vector Machines (SVM) and 2) Hidden ...
Multicore Processing for Clustering Algorithms
Directory of Open Access Journals (Sweden)
RekhanshRao
2012-03-01
Full Text Available Data Mining algorithms such as classification and clustering are the future of computation, though multidimensional data-processing is required. People are using multicore processors with GPU’s. Most of the programming languages doesn’t provide multiprocessing facilities and hence wastage of processing resources. Clustering and classification algorithms are more resource consuming. In this paper we have shown strategies to overcome such deficiencies using multicore processing platform OpelCL.
CPU Scheduling Algorithms: A Survey
Imran Qureshi
2014-01-01
Scheduling is the fundamental function of operating system. For scheduling, resources of system shared among processes which are going to be executed. CPU scheduling is a technique by which processes are allocating to the CPU for a specific time quantum. In this paper the review of different scheduling algorithms are perform with different parameters, such as running time, burst time and waiting times etc. The reviews algorithms are first come first serve, Shortest Job First, Round Robin, ...
Communication Complexity (for Algorithm Designers)
Roughgarden, Tim
2015-01-01
This document collects the lecture notes from my course "Communication Complexity (for Algorithm Designers),'' taught at Stanford in the winter quarter of 2015. The two primary goals of the course are: 1. Learn several canonical problems that have proved the most useful for proving lower bounds (Disjointness, Index, Gap-Hamming, etc.). 2. Learn how to reduce lower bounds for fundamental algorithmic problems to communication complexity lower bounds. Along the way, we'll also: 3. Get exposure t...
A memetic fingerprint matching algorithm
Sheng, Weiguo; Howells, Gareth; Fairhurst, Michael; Deravi, Farzin
2007-01-01
Minutiae point pattern matching is the most common approach for fingerprint verification. Although many minutiae point pattern matching algorithms have been proposed, reliable automatic fingerprint verification remains as a challenging problem, both with respect to recovering the optimal alignment and the construction of an adequate matching function. In this paper, we develop a memetic fingerprint matching algorithm (MFMA) which aims to identify the optimal or near optimal global matching, b...
Larson, Harold J.; Jayachandran, Toke.
1983-01-01
The Comprehensive Engine Management System (CEMS) Phase IV, will provide real time data analysis capability for all Air Force oil analysis laboratories. This paper describes the statistical algorithm used by this system to aid the oil analysis technician in making his recommendations. The algorithm incorporates usage and oil consumption variables, and employs least squares to minimize the effects of the random errors in the spectrometer readings. Prepared for: Directorate of M...
The Insights of Algorithmic Entropy
Directory of Open Access Journals (Sweden)
Sean Devine
2009-03-01
Full Text Available The algorithmic entropy of a system, the length of the shortest algorithm that specifies the system’s exact state adds some missing pieces to the entropy jigsaw. Because the approach embodies the traditional entropies as a special case, problematic issues such as the coarse graining framework of the Gibbs’ entropy manifest themselves in a different and more manageable form, appearing as the description of the system and the choice of the universal computing machine. The provisional algorithmic entropy combines the best information about the state of the system together with any underlying uncertainty; the latter represents the Shannon entropy. The algorithmic approach also specifies structure that the traditional entropies take as given. Furthermore, algorithmic entropy provides insights into how a system can maintain itself off equilibrium, leading to Ashby’s law of requisite variety. This review shows how the algorithmic approach can provide insights into real world systems, by outlining recent work on how replicating structures that generate order can evolve to maintain a system far from equilibrium.
TRAVERSAL ALGORITHM FOR COMPLETE COVERAGE
Directory of Open Access Journals (Sweden)
Coimbatore Ganeshsankar Balaji
2012-01-01
Full Text Available There are many applications which require complete coverage and obstacle avoidance. The classical A* algorithm provides the user a shortest path by avoiding the obstacle. As well, the Dijkstraâs algorithm finds the shortest path between the source and destination. But in many applications we require complete coverage of the proposed area with obstacle avoidance. There are LSP, LSSP, BSA, spiral-STC and Complete Coverage D* algorithms which do not realize complete (100% coverage. The complete coverage using a critical point algorithm assures complete coverage, but it is not well suited for applications like mine detection. Also for covering the missed region it keeps the obstacle as a critical point which is not advisable in critical applications where obstacle may be a dangerous one. To overcome this and to achieve the complete coverage we propose a novel graph traversal algorithm Traversal Algorithm for Complete Coverage (TRACC. Here the area to be scanned is decomposed into a finite number of cells. The traversal is done through all the cells after making sure the next cell has no obstacle. TRACC assures thorough coverage of the proposed area and ensuring that all the obstacles are avoided. Hence the TRACC always have the safer path while covering the entire area. It also reports the obstacle placed or blocked cell.
Recursive Branching Simulated Annealing Algorithm
Bolcar, Matthew; Smith, J. Scott; Aronstein, David
2012-01-01
This innovation is a variation of a simulated-annealing optimization algorithm that uses a recursive-branching structure to parallelize the search of a parameter space for the globally optimal solution to an objective. The algorithm has been demonstrated to be more effective at searching a parameter space than traditional simulated-annealing methods for a particular problem of interest, and it can readily be applied to a wide variety of optimization problems, including those with a parameter space having both discrete-value parameters (combinatorial) and continuous-variable parameters. It can take the place of a conventional simulated- annealing, Monte-Carlo, or random- walk algorithm. In a conventional simulated-annealing (SA) algorithm, a starting configuration is randomly selected within the parameter space. The algorithm randomly selects another configuration from the parameter space and evaluates the objective function for that configuration. If the objective function value is better than the previous value, the new configuration is adopted as the new point of interest in the parameter space. If the objective function value is worse than the previous value, the new configuration may be adopted, with a probability determined by a temperature parameter, used in analogy to annealing in metals. As the optimization continues, the region of the parameter space from which new configurations can be selected shrinks, and in conjunction with lowering the annealing temperature (and thus lowering the probability for adopting configurations in parameter space with worse objective functions), the algorithm can converge on the globally optimal configuration. The Recursive Branching Simulated Annealing (RBSA) algorithm shares some features with the SA algorithm, notably including the basic principles that a starting configuration is randomly selected from within the parameter space, the algorithm tests other configurations with the goal of finding the globally optimal
BACKPROPAGATION LEARNING ALGORITHM BASED ON LEVENBERG MARQUARDT ALGORITHM
Directory of Open Access Journals (Sweden)
S.Sapna
2012-10-01
Full Text Available Data Mining aims at discovering knowledge out of data and presenting it in a form that is easily compressible to humans. Data Mining represents a process developed to examine large amounts of data routinely collected. The term also refers to a collection of tools used to perform the process. One of the useful applications in the field of medicine is the incurable chronic disease diabetes. Data Mining algorithm is used for testing the accuracy in predicting diabetic status. Fuzzy Systems are been used for solving a wide range of problems in different application domain and Genetic Algorithm for designing. Fuzzy systems allows in introducing the learning and adaptation capabilities. Neural Networks are efficiently used for learning membership functions. Diabetes occurs throughout the world, but Type 2 is more common in the most developed countries. The greater increase in prevalence is however expected in Asia and Africa where most patients will likely be found by 2030. This paper is proposed on the Levenberg – Marquardt algorithm which is specifically designed to minimize sum-of-square error functions. Levernberg-Marquardt algorithm gives the best performance in the prediction of diabetes compared to any other backpropogation algorithm.
A Review on Quantum Search Algorithms
Giri, Pulak Ranjan
2016-01-01
The use of superposition of states in quantum computation, known as quantum parallelism, has significant advantage in terms of speed over the classical computation. It can be understood from the early invented quantum algorithms such as Deutsch's algorithm, Deutsch-Jozsa algorithm and its variation as Bernstein-Vazirani algorithm, Simon algorithm, Shor's algorithms etc. Quantum parallelism also significantly speeds up the database search algorithm, which is important in computer science because it comes as a subroutine in many important algorithms. Quantum database search of Grover achieves the task of finding the target element in an unsorted database in a time quadratically faster than the classical computer. We review the Grover quantum search algorithms for a singe and multiple target elements in a database. The partial search algorithm of Grover and Radhakrishnan and its optimization by Korepin, called GRK algorithm are also discussed.
Improved autonomous star identification algorithm
Luo, Li-Yan; Xu, Lu-Ping; Zhang, Hua; Sun, Jing-Rong
2015-06-01
The log-polar transform (LPT) is introduced into the star identification because of its rotation invariance. An improved autonomous star identification algorithm is proposed in this paper to avoid the circular shift of the feature vector and to reduce the time consumed in the star identification algorithm using LPT. In the proposed algorithm, the star pattern of the same navigation star remains unchanged when the stellar image is rotated, which makes it able to reduce the star identification time. The logarithmic values of the plane distances between the navigation and its neighbor stars are adopted to structure the feature vector of the navigation star, which enhances the robustness of star identification. In addition, some efforts are made to make it able to find the identification result with fewer comparisons, instead of searching the whole feature database. The simulation results demonstrate that the proposed algorithm can effectively accelerate the star identification. Moreover, the recognition rate and robustness by the proposed algorithm are better than those by the LPT algorithm and the modified grid algorithm. Project supported by the National Natural Science Foundation of China (Grant Nos. 61172138 and 61401340), the Open Research Fund of the Academy of Satellite Application, China (Grant No. 2014_CXJJ-DH_12), the Fundamental Research Funds for the Central Universities, China (Grant Nos. JB141303 and 201413B), the Natural Science Basic Research Plan in Shaanxi Province, China (Grant No. 2013JQ8040), the Research Fund for the Doctoral Program of Higher Education of China (Grant No. 20130203120004), and the Xi’an Science and Technology Plan, China (Grant. No CXY1350(4)).
SDR Input Power Estimation Algorithms
Nappier, Jennifer M.; Briones, Janette C.
2013-01-01
The General Dynamics (GD) S-Band software defined radio (SDR) in the Space Communications and Navigation (SCAN) Testbed on the International Space Station (ISS) provides experimenters an opportunity to develop and demonstrate experimental waveforms in space. The SDR has an analog and a digital automatic gain control (AGC) and the response of the AGCs to changes in SDR input power and temperature was characterized prior to the launch and installation of the SCAN Testbed on the ISS. The AGCs were used to estimate the SDR input power and SNR of the received signal and the characterization results showed a nonlinear response to SDR input power and temperature. In order to estimate the SDR input from the AGCs, three algorithms were developed and implemented on the ground software of the SCAN Testbed. The algorithms include a linear straight line estimator, which used the digital AGC and the temperature to estimate the SDR input power over a narrower section of the SDR input power range. There is a linear adaptive filter algorithm that uses both AGCs and the temperature to estimate the SDR input power over a wide input power range. Finally, an algorithm that uses neural networks was designed to estimate the input power over a wide range. This paper describes the algorithms in detail and their associated performance in estimating the SDR input power.
Ensemble algorithms in reinforcement learning.
Wiering, Marco A; van Hasselt, Hado
2008-08-01
This paper describes several ensemble methods that combine multiple different reinforcement learning (RL) algorithms in a single agent. The aim is to enhance learning speed and final performance by combining the chosen actions or action probabilities of different RL algorithms. We designed and implemented four different ensemble methods combining the following five different RL algorithms: Q-learning, Sarsa, actor-critic (AC), QV-learning, and AC learning automaton. The intuitively designed ensemble methods, namely, majority voting (MV), rank voting, Boltzmann multiplication (BM), and Boltzmann addition, combine the policies derived from the value functions of the different RL algorithms, in contrast to previous work where ensemble methods have been used in RL for representing and learning a single value function. We show experiments on five maze problems of varying complexity; the first problem is simple, but the other four maze tasks are of a dynamic or partially observable nature. The results indicate that the BM and MV ensembles significantly outperform the single RL algorithms. PMID:18632380
Algorithms, complexity, and the sciences.
Papadimitriou, Christos
2014-11-11
Algorithms, perhaps together with Moore's law, compose the engine of the information technology revolution, whereas complexity--the antithesis of algorithms--is one of the deepest realms of mathematical investigation. After introducing the basic concepts of algorithms and complexity, and the fundamental complexity classes P (polynomial time) and NP (nondeterministic polynomial time, or search problems), we discuss briefly the P vs. NP problem. We then focus on certain classes between P and NP which capture important phenomena in the social and life sciences, namely the Nash equlibrium and other equilibria in economics and game theory, and certain processes in population genetics and evolution. Finally, an algorithm known as multiplicative weights update (MWU) provides an algorithmic interpretation of the evolution of allele frequencies in a population under sex and weak selection. All three of these equivalences are rife with domain-specific implications: The concept of Nash equilibrium may be less universal--and therefore less compelling--than has been presumed; selection on gene interactions may entail the maintenance of genetic variation for longer periods than selection on single alleles predicts; whereas MWU can be shown to maximize, for each gene, a convex combination of the gene's cumulative fitness in the population and the entropy of the allele distribution, an insight that may be pertinent to the maintenance of variation in evolution.
POSE Algorithms for Automated Docking
Heaton, Andrew F.; Howard, Richard T.
2011-01-01
POSE (relative position and attitude) can be computed in many different ways. Given a sensor that measures bearing to a finite number of spots corresponding to known features (such as a target) of a spacecraft, a number of different algorithms can be used to compute the POSE. NASA has sponsored the development of a flash LIDAR proximity sensor called the Vision Navigation Sensor (VNS) for use by the Orion capsule in future docking missions. This sensor generates data that can be used by a variety of algorithms to compute POSE solutions inside of 15 meters, including at the critical docking range of approximately 1-2 meters. Previously NASA participated in a DARPA program called Orbital Express that achieved the first automated docking for the American space program. During this mission a large set of high quality mated sensor data was obtained at what is essentially the docking distance. This data set is perhaps the most accurate truth data in existence for docking proximity sensors in orbit. In this paper, the flight data from Orbital Express is used to test POSE algorithms at 1.22 meters range. Two different POSE algorithms are tested for two different Fields-of-View (FOVs) and two different pixel noise levels. The results of the analysis are used to predict future performance of the POSE algorithms with VNS data.
A Hybrid Chaotic Quantum Evolutionary Algorithm
DEFF Research Database (Denmark)
Cai, Y.; Zhang, M.; Cai, H.
2010-01-01
and enhance the global search ability. A large number of tests show that the proposed algorithm has higher convergence speed and better optimizing ability than quantum evolutionary algorithm, real-coded quantum evolutionary algorithm and hybrid quantum genetic algorithm. Tests also show that when chaos...
An inversion algorithm for general tridiagonal matrix
Institute of Scientific and Technical Information of China (English)
Rui-sheng RAN; Ting-zhu HUANG; Xing-ping LIU; Tong-xiang GU
2009-01-01
An algorithm for the inverse of a general tridiagonal matrix is presented. For a tridiagonal matrix having the Doolittle factorization, an inversion algorithm is established.The algorithm is then generalized to deal with a general tridiagonal matrix without any restriction. Comparison with other methods is provided, indicating low computational complexity of the proposed algorithm, and its applicability to general tridiagonal matrices.
An Improved MULTI-SOM Algorithm
Directory of Open Access Journals (Sweden)
Imen Khanchouch
2013-07-01
Full Text Available This paper proposes a clustering algorithm based on the Self Organizing Map (SOM method. To find theoptimal number of clusters, our algorithm uses the Davies Bouldin index which has not been usedpreviously in the multi-SOM. The proposed algorithm is compared to three clustering methods based onfive databases. Results show that our algorithm is as performing as concurrent methods.
A Modified Algorithm for Feedforward Neural Networks
Institute of Scientific and Technical Information of China (English)
夏战国; 管红杰; 李政伟; 孟斌
2002-01-01
As a most popular learning algorithm for the feedforward neural networks, the classic BP algorithm has its many shortages. To overcome some of the shortages, a modified learning algorithm is proposed in the article. And the simulation result illustrate the modified algorithm is more effective and practicable.
Seamless Merging of Hypertext and Algorithm Animation
Karavirta, Ville
2009-01-01
Online learning material that students use by themselves is one of the typical usages of algorithm animation (AA). Thus, the integration of algorithm animations into hypertext is seen as an important topic today to promote the usage of algorithm animation in teaching. This article presents an algorithm animation viewer implemented purely using…
A Note on Shor's Quantum Algorithm
Institute of Scientific and Technical Information of China (English)
CAO Zheng-jun; LIU Li-hua
2006-01-01
Shor proposed a polynomial time algorithm for computing the order of one element in a multiplicative group using a quantum computer. Based on Miller's randomization, he then gave a factorization algorithm. But the algorithm has two shortcomings, the order must be even and the output might be a trivial factor. Actually, these drawbacks can be overcome if the number is an RSA modulus. Applying the special structure of the RSA modulus,an algorithm is presented to overcome the two shortcomings. The new algorithm improves Shor's algorithm for factoring RSA modulus. The cost of the factorization algorithm almost depends on the calculation of the order of 2 in the multiplication group.
New recursive algorithm for matrix inversion
Institute of Scientific and Technical Information of China (English)
Cao Jianshu; Wang Xuegang
2008-01-01
To reduce the computational complexity of matrix inversion, which is the majority of processing in many practical applications, two numerically efficient recursive algorithms (called algorithms Ⅰ and Ⅱ, respectively)are presented. Algorithm Ⅰ is used to calculate the inverse of such a matrix, whose leading principal minors are all nonzero. Algorithm Ⅱ, whereby, the inverse of an arbitrary nonsingular matrix can be evaluated is derived via improving the algorithm Ⅰ. The implementation, for algorithm Ⅱ or Ⅰ, involves matrix-vector multiplications and vector outer products. These operations are computationally fast and highly parallelizable. MATLAB simulations show that both recursive algorithms are valid.
NEW HMM ALGORITHM FOR TOPOLOGY OPTIMIZATION
Institute of Scientific and Technical Information of China (English)
Zuo Kongtian; Zhao Yudong; Chen Liping; Zhong Yifang; Huang Yuying
2005-01-01
A new hybrid MMA-MGCMMA (HMM) algorithm for solving topology optimization problems is presented. This algorithm combines the method of moving asymptotes (MMA) algorithm and the modified globally convergent version of the method of moving asymptotes (MGCMMA) algorithm in the optimization process. This algorithm preserves the advantages of both MMA and MGCMMA. The optimizer is switched from MMA to MGCMMA automatically, depending on the numerical oscillation value existing in the calculation. This algorithm can improve calculation efficiency and accelerate convergence compared with simplex MMA or MGCMMA algorithms, which is proven with an example.
Novel Newton's learning algorithm of neural networks
Institute of Scientific and Technical Information of China (English)
Long Ning; Zhang Fengli
2006-01-01
Newton's learning algorithm of NN is presented and realized. In theory, the convergence rate of learning algorithm of NN based on Newton's method must be faster than BP's and other learning algorithms, because the gradient method is linearly convergent while Newton's method has second order convergence rate.The fast computing algorithm of Hesse matrix of the cost function of NN is proposed and it is the theory basis of the improvement of Newton's learning algorithm. Simulation results show that the convergence rate of Newton's learning algorithm is high and apparently faster than the traditional BP method's, and the robustness of Newton's learning algorithm is also better than BP method's.
Immunity clone algorithm with particle swarm evolution
Institute of Scientific and Technical Information of China (English)
LIU Li-jue; CAI Zi-xing; CHEN Hong
2006-01-01
Combining the clonal selection mechanism of the immune system with the evolution equations of particle swarm optimization, an advanced algorithm was introduced for functions optimization. The advantages of this algorithm lies in two aspects.Via immunity operation, the diversity of the antibodies was maintained, and the speed of convergent was improved by using particle swarm evolution equations. Simulation programme and three functions were used to check the effect of the algorithm. The advanced algorithm were compared with clonal selection algorithm and particle swarm algorithm. The results show that this advanced algorithm can converge to the global optimum at a great rate in a given range, the performance of optimization is improved effectively.
Decryption of pure-position permutation algorithms
Institute of Scientific and Technical Information of China (English)
赵晓宇; 陈刚; 张亶; 王肖虹; 董光昌
2004-01-01
Pure position permutation image encryption algorithms, commonly used as image encryption investigated in this work are unfortunately frail under known-text attack. In view of the weakness of pure position permutation algorithm,we put forward an effective decryption algorithm for all pure-position permutation algorithms. First, a summary of the pure position permutation image encryption algorithms is given by introducing the concept of ergodic matrices. Then, by using probability theory and algebraic principles, the decryption probability of pure-position permutation algorithms is verified theoretically; and then, by defining the operation system of fuzzy ergodic matrices, we improve a specific decryption al-gorithm. Finally, some simulation results are shown.
Old And New Algorithms For Toeplitz Systems
Brent, Richard P.
1988-02-01
Toeplitz linear systems and Toeplitz least squares problems commonly arise in digital signal processing. In this paper we survey some old, "well known" algorithms and some recent algorithms for solving these problems. We concentrate our attention on algorithms which can be implemented efficiently on a variety of parallel machines (including pipelined vector processors and systolic arrays). We distinguish between algorithms which require inner products, and algorithms which avoid inner products, and thus are better suited to parallel implementation on some parallel architectures. Finally, we mention some "asymptotically fast" 0(n(log n)2) algorithms and compare them with 0(n2) algorithms.
Energy Technology Data Exchange (ETDEWEB)
Hindmarsh, A.C.
2000-12-01
In October-November 2000, I gave a series of talks, describing in some detail the algorithms in two general-purpose solvers: (1) the PVODE solver for systems of ordinary differential equations (ODEs), and (2) the IDA solver for systems of differential-algebraic equations (DAEs). The material was organized into three parts: (1) Part A: Overview; (2) Part B: The PVODE Algorithm; and (3) Part C: The IDA Algorithm. This document consists of the viewgraphs for the corresponding three talks. Except for the correction of some minor errors, the talk viewgraphs are given here exactly as presented. Each of the three sets of pages is numbered independently, with page numbers starting at 1. A brief outline of each of the talks, and a list of references, is also included in the report, some of which are cited in the viewgraphs.
Firefly Algorithm for Structural Search.
Avendaño-Franco, Guillermo; Romero, Aldo H
2016-07-12
The problem of computational structure prediction of materials is approached using the firefly (FF) algorithm. Starting from the chemical composition and optionally using prior knowledge of similar structures, the FF method is able to predict not only known stable structures but also a variety of novel competitive metastable structures. This article focuses on the strengths and limitations of the algorithm as a multimodal global searcher. The algorithm has been implemented in software package PyChemia ( https://github.com/MaterialsDiscovery/PyChemia ), an open source python library for materials analysis. We present applications of the method to van der Waals clusters and crystal structures. The FF method is shown to be competitive when compared to other population-based global searchers. PMID:27232694
A Spectral Canonical Electrostatic Algorithm
Webb, Stephen D
2015-01-01
Studying single-particle dynamics over many periods of oscillations is a well-understood problem solved using symplectic integration. Such integration schemes derive their update sequence from an approximate Hamiltonian, guaranteeing that the geometric structure of the underlying problem is preserved. Simulating a self-consistent system over many oscillations can introduce numerical artifacts such as grid heating. This unphysical heating stems from using non-symplectic methods on Hamiltonian systems. With this guidance, we derive an electrostatic algorithm using a discrete form of Hamilton's Principle. The resulting algorithm, a gridless spectral electrostatic macroparticle model, does not exhibit the unphysical heating typical of most particle-in-cell methods. We present results of this using a two-body problem as an example of the algorithm's energy- and momentum-conserving properties.
A Disk Scheduling Algorithm: SPFF
Institute of Scientific and Technical Information of China (English)
HU Ming
2005-01-01
We put forward an optimal disk schedule with n disk requests and prove its optimality mathematically. Generalizing the idea of an optimal disk schedule, we remove the limit of n requests and, at the same time, consider the dynamically arrival model of disk requests to obtain an algorithm, shortest path first-fit first (SPFF). This algorithm is based on the shortest path of disk head motion constructed by all the pendent requests. From view of the head-moving distance, it has the stronger globality than SSTF. From view of the head-moving direction, it has the better flexibility than SCAN. Therefore, SPFF keeps the advantage of SCAN and, at the same time, absorbs the strength of SSTF. The algorithm SPFF not only shows the more superiority than other scheduling polices, but also have higher adjustability to meet the computer system's different demands.
Quantum walks and search algorithms
Portugal, Renato
2013-01-01
This book addresses an interesting area of quantum computation called quantum walks, which play an important role in building quantum algorithms, in particular search algorithms. Quantum walks are the quantum analogue of classical random walks. It is known that quantum computers have great power for searching unsorted databases. This power extends to many kinds of searches, particularly to the problem of finding a specific location in a spatial layout, which can be modeled by a graph. The goal is to find a specific node knowing that the particle uses the edges to jump from one node to the next. This book is self-contained with main topics that include: Grover's algorithm, describing its geometrical interpretation and evolution by means of the spectral decomposition of the evolution operater Analytical solutions of quantum walks on important graphs like line, cycles, two-dimensional lattices, and hypercubes using Fourier transforms Quantum walks on generic graphs, describing methods to calculate the limiting d...
Energy Technology Data Exchange (ETDEWEB)
Haller, Johannes; Kogler, Roman; Lapsien, Tobias [University of Hamburg (Germany)
2015-07-01
Top quarks with high transverse momenta will be produced abundantly at the LHC with increasing center of mass energy. The identification of hadronically decaying top quarks (t → bW → bq anti q) imposes various challenges, since at high transverse momenta all decay products are collimated in one jet. Various algorithms to identify these top quarks, while rejecting light flavour jets, have been studied and employed in CMS. New developments in jet substructure techniques make it possible to improve these existing top taggers significantly. In this talk, various improvements of top tagging algorithms are shown and results are presented based on the shower deconstruction tagger and the MultiR HEP Top tagger. Also measurements of efficiency and misidentification rates of these new top tagging algorithms in the √(s) = 8 TeV dataset are shown.
Fault Tolerant External Memory Algorithms
DEFF Research Database (Denmark)
Jørgensen, Allan Grønlund; Brodal, Gerth Stølting; Mølhave, Thomas
2009-01-01
Algorithms dealing with massive data sets are usually designed for I/O-efficiency, often captured by the I/O model by Aggarwal and Vitter. Another aspect of dealing with massive data is how to deal with memory faults, e.g. captured by the adversary based faulty memory RAM by Finocchi and Italiano....... However, current fault tolerant algorithms do not scale beyond the internal memory. In this paper we investigate for the first time the connection between I/O-efficiency in the I/O model and fault tolerance in the faulty memory RAM, and we assume that both memory and disk are unreliable. We show a lower...... bound on the number of I/Os required for any deterministic dictionary that is resilient to memory faults. We design a static and a dynamic deterministic dictionary with optimal query performance as well as an optimal sorting algorithm and an optimal priority queue. Finally, we consider scenarios where...
Evaluation of Rule Extraction Algorithms
Directory of Open Access Journals (Sweden)
Tiruveedula GopiKrishna
2014-05-01
Full Text Available For the data mining domain, the lack of explanation facilities seems to be a serious drawback for techniques based on Artificial Neural Networks, or, for that matter, any technique producing opaque models In particular, the ability to generate even limited explanations is absolutely crucial for user acceptance of such systems. Since the purpose of most data mining systems is to support decision making,the need for explanation facilities in these systems is apparent. The task for the data miner is thus to identify the complex but general relationships that are likely to carry over to production data and the explanation facility makes this easier. Also focused the quality of the extracted rules; i.e. how well the required explanation is performed. In this research some important rule extraction algorithms are discussed and identified the algorithmic complexity; i.e. how efficient the underlying rule extraction algorithm is
Algorithms for Decision Tree Construction
Chikalov, Igor
2011-01-01
The study of algorithms for decision tree construction was initiated in 1960s. The first algorithms are based on the separation heuristic [13, 31] that at each step tries dividing the set of objects as evenly as possible. Later Garey and Graham [28] showed that such algorithm may construct decision trees whose average depth is arbitrarily far from the minimum. Hyafil and Rivest in [35] proved NP-hardness of DT problem that is constructing a tree with the minimum average depth for a diagnostic problem over 2-valued information system and uniform probability distribution. Cox et al. in [22] showed that for a two-class problem over information system, even finding the root node attribute for an optimal tree is an NP-hard problem. © Springer-Verlag Berlin Heidelberg 2011.
Simple Algorithm Portfolio for SAT
Nikolic, Mladen; Janicic, Predrag
2011-01-01
The importance of algorithm portfolio techniques for SAT has long been noted, and a number of very successful systems have been devised, including the most successful one --- SATzilla. However, all these systems are quite complex (to understand, reimplement, or modify). In this paper we propose a new algorithm portfolio for SAT that is extremely simple, but in the same time so efficient that it outperforms SATzilla. For a new SAT instance to be solved, our portfolio finds its k-nearest neighbors from the training set and invokes a solver that performs the best at those instances. The main distinguishing feature of our algorithm portfolio is the locality of the selection procedure --- the selection of a SAT solver is based only on few instances similar to the input one.
Intuitionistic fuzzy hierarchical clustering algorithms
Institute of Scientific and Technical Information of China (English)
Xu Zeshui
2009-01-01
Intuitionistic fuzzy set (IFS) is a set of 2-tuple arguments, each of which is characterized by a mem-bership degree and a nonmembership degree. The generalized form of IFS is interval-valued intuitionistic fuzzy set (IVIFS), whose components are intervals rather than exact numbers. IFSs and IVIFSs have been found to be very useful to describe vagueness and uncertainty. However, it seems that little attention has been focused on the clus-tering analysis of IFSs and IVIFSs. An intuitionistic fuzzy hierarchical algorithm is introduced for clustering IFSs, which is based on the traditional hierarchical clustering procedure, the intuitionistic fuzzy aggregation operator, and the basic distance measures between IFSs: the Hamming distance, normalized Hamming, weighted Hamming, the Euclidean distance, the normalized Euclidean distance, and the weighted Euclidean distance. Subsequently, the algorithm is extended for clustering IVIFSs. Finally the algorithm and its extended form are applied to the classifications of building materials and enterprises respectively.
Some nonlinear space decomposition algorithms
Energy Technology Data Exchange (ETDEWEB)
Tai, Xue-Cheng; Espedal, M. [Univ. of Bergen (Norway)
1996-12-31
Convergence of a space decomposition method is proved for a general convex programming problem. The space decomposition refers to methods that decompose a space into sums of subspaces, which could be a domain decomposition or a multigrid method for partial differential equations. Two algorithms are proposed. Both can be used for linear as well as nonlinear elliptic problems and they reduce to the standard additive and multiplicative Schwarz methods for linear elliptic problems. Two {open_quotes}hybrid{close_quotes} algorithms are also presented. They converge faster than the additive one and have better parallelism than the multiplicative method. Numerical tests with a two level domain decomposition for linear, nonlinear and interface elliptic problems are presented for the proposed algorithms.
HEATR project: ATR algorithm parallelization
Deardorf, Catherine E.
1998-09-01
High Performance Computing (HPC) Embedded Application for Target Recognition (HEATR) is a project funded by the High Performance Computing Modernization Office through the Common HPC Software Support Initiative (CHSSI). The goal of CHSSI is to produce portable, parallel, multi-purpose, freely distributable, support software to exploit emerging parallel computing technologies and enable application of scalable HPC's for various critical DoD applications. Specifically, the CHSSI goal for HEATR is to provide portable, parallel versions of several existing ATR detection and classification algorithms to the ATR-user community to achieve near real-time capability. The HEATR project will create parallel versions of existing automatic target recognition (ATR) detection and classification algorithms and generate reusable code that will support porting and software development process for ATR HPC software. The HEATR Team has selected detection/classification algorithms from both the model- based and training-based (template-based) arena in order to consider the parallelization requirements for detection/classification algorithms across ATR technology. This would allow the Team to assess the impact that parallelization would have on detection/classification performance across ATR technology. A field demo is included in this project. Finally, any parallel tools produced to support the project will be refined and returned to the ATR user community along with the parallel ATR algorithms. This paper will review: (1) HPCMP structure as it relates to HEATR, (2) Overall structure of the HEATR project, (3) Preliminary results for the first algorithm Alpha Test, (4) CHSSI requirements for HEATR, and (5) Project management issues and lessons learned.
Optimisation combinatoire Theorie et algorithmes
Korte, Bernhard; Fonlupt, Jean
2010-01-01
Ce livre est la traduction fran aise de la quatri me et derni re dition de Combinatorial Optimization: Theory and Algorithms crit par deux minents sp cialistes du domaine: Bernhard Korte et Jens Vygen de l'universit de Bonn en Allemagne. Il met l accent sur les aspects th oriques de l'optimisation combinatoire ainsi que sur les algorithmes efficaces et exacts de r solution de probl mes. Il se distingue en cela des approches heuristiques plus simples et souvent d crites par ailleurs. L ouvrage contient de nombreuses d monstrations, concises et l gantes, de r sultats difficiles. Destin aux tudia
Novel Facial Features Segmentation Algorithm
Institute of Scientific and Technical Information of China (English)
无
2008-01-01
An efficient algorithm for facial features extractions is proposed. The facial features we segment are the two eyes, nose and mouth. The algorithm is based on an improved Gabor wavelets edge detector, morphological approach to detect the face region and facial features regions, and an improved T-shape face mask to locate the extract location of facial features. The experimental results show that the proposed method is robust against facial expression, illumination, and can be also effective if the person wearing glasses, and so on.
Evaluation of flux synthesis algorithms
International Nuclear Information System (INIS)
The flux synthesis algorithm which is the best fit to the numerical solution of the multigroup diffusion equations, was determined. Three different types of synthesis were studied: 1) discontinuous synthesis 2) continuous synthesis 3) pseudo-continuous synthesis. A matrix and a differential formulation were developed for the first two types of synthesis. For pseudo-continuous synthesis only the matrix formulation was used. Some tests were performed and the results allowed us to establish the following order of efficiency for the algorithms: 1) continuous synthesis (matrix formulation) 2) continuous synthesis (differential formulation) 3) pseudo-continuous synthesis 4) discontinuous synthesis (matrix formulation) 5) discontinuous synthesis (differential formulation). (Author)
Combinatorial optimization theory and algorithms
Korte, Bernhard
2002-01-01
Combinatorial optimization is one of the youngest and most active areas of discrete mathematics, and is probably its driving force today. This book describes the most important ideas, theoretical results, and algorithms of this field. It is conceived as an advanced graduate text, and it can also be used as an up-to-date reference work for current research. The book includes the essential fundamentals of graph theory, linear and integer programming, and complexity theory. It covers classical topics in combinatorial optimization as well as very recent ones. The emphasis is on theoretical results and algorithms with provably good performance. Some applications and heuristics are mentioned, too.
Born approximation, scattering, and algorithm
Martinez, Alex; Hu, Mengqi; Gu, Haicheng; Qiao, Zhijun
2015-05-01
In the past few decades, there were many imaging algorithms designed in the case of the absence of multiple scattering. Recently, we discussed an algorithm for removing high order scattering components from collected data. This paper is a continuation of our previous work. First, we investigate the current state of multiple scattering in SAR. Then, we revise our method and test it. Given an estimate of our target reflectivity, we compute the multi scattering effects in the target region for various frequencies. Furthermore, we propagate this energy through free space towards our antenna, and remove it from the collected data.
Hill climbing algorithms and trivium
DEFF Research Database (Denmark)
Borghoff, Julia; Knudsen, Lars Ramkilde; Matusiewicz, Krystian
2011-01-01
This paper proposes a new method to solve certain classes of systems of multivariate equations over the binary field and its cryptanalytical applications. We show how heuristic optimization methods such as hill climbing algorithms can be relevant to solving systems of multivariate equations....... A characteristic of equation systems that may be efficiently solvable by the means of such algorithms is provided. As an example, we investigate equation systems induced by the problem of recovering the internal state of the stream cipher Trivium. We propose an improved variant of the simulated annealing method...
Industrial Applications of Evolutionary Algorithms
Sanchez, Ernesto; Tonda, Alberto
2012-01-01
This book is intended as a reference both for experienced users of evolutionary algorithms and for researchers that are beginning to approach these fascinating optimization techniques. Experienced users will find interesting details of real-world problems, and advice on solving issues related to fitness computation, modeling and setting appropriate parameters to reach optimal solutions. Beginners will find a thorough introduction to evolutionary computation, and a complete presentation of all evolutionary algorithms exploited to solve different problems. The book could fill the gap between the
THE FEATURE SUBSET SELECTION ALGORITHM
Institute of Scientific and Technical Information of China (English)
Liu Yongguo; Li Xueming; Wu Zhongfu
2003-01-01
The motivation of data mining is how to extract effective information from huge data in very large database. However, some redundant and irrelevant attributes, which result in low performance and high computing complexity, are included in the very large database in general.So, Feature Subset Selection (FSS) becomes one important issue in the field of data mining. In this letter, an FSS model based on the filter approach is built, which uses the simulated annealing genetic algorithm. Experimental results show that convergence and stability of this algorithm are adequately achieved.
THE FEATURE SUBSET SELECTION ALGORITHM
Institute of Scientific and Technical Information of China (English)
LiuYongguo; LiXueming; 等
2003-01-01
The motivation of data mining is how to extract effective information from huge data in very large database.However,some redundant irrelevant attributes,which result in low performance and high computing complexity,are included in the very large database in general.So,Feature Selection(FSS)becomes one important issue in the field of data mining.In this letter,an Fss model based on the filter approach is built,which uses the simulated annealing gentic algorithm.Experimental results show that convergence and stability of this algorithm are adequately achieved.
Ensemble Methods Foundations and Algorithms
Zhou, Zhi-Hua
2012-01-01
An up-to-date, self-contained introduction to a state-of-the-art machine learning approach, Ensemble Methods: Foundations and Algorithms shows how these accurate methods are used in real-world tasks. It gives you the necessary groundwork to carry out further research in this evolving field. After presenting background and terminology, the book covers the main algorithms and theories, including Boosting, Bagging, Random Forest, averaging and voting schemes, the Stacking method, mixture of experts, and diversity measures. It also discusses multiclass extension, noise tolerance, error-ambiguity a
Big Data Mining: Tools & Algorithms
Directory of Open Access Journals (Sweden)
Adeel Shiraz Hashmi
2016-03-01
Full Text Available We are now in Big Data era, and there is a growing demand for tools which can process and analyze it. Big data analytics deals with extracting valuable information from that complex data which can’t be handled by traditional data mining tools. This paper surveys the available tools which can handle large volumes of data as well as evolving data streams. The data mining tools and algorithms which can handle big data have also been summarized, and one of the tools has been used for mining of large datasets using distributed algorithms.
Parallel algorithms and cluster computing
Hoffmann, Karl Heinz
2007-01-01
This book presents major advances in high performance computing as well as major advances due to high performance computing. It contains a collection of papers in which results achieved in the collaboration of scientists from computer science, mathematics, physics, and mechanical engineering are presented. From the science problems to the mathematical algorithms and on to the effective implementation of these algorithms on massively parallel and cluster computers we present state-of-the-art methods and technology as well as exemplary results in these fields. This book shows that problems which seem superficially distinct become intimately connected on a computational level.
Wavelets theory, algorithms, and applications
Montefusco, Laura
2014-01-01
Wavelets: Theory, Algorithms, and Applications is the fifth volume in the highly respected series, WAVELET ANALYSIS AND ITS APPLICATIONS. This volume shows why wavelet analysis has become a tool of choice infields ranging from image compression, to signal detection and analysis in electrical engineering and geophysics, to analysis of turbulent or intermittent processes. The 28 papers comprising this volume are organized into seven subject areas: multiresolution analysis, wavelet transforms, tools for time-frequency analysis, wavelets and fractals, numerical methods and algorithms, and applicat
Two Algorithms for Processing Electronic Nose Data
Young, Rebecca; Linnell, Bruce
2007-01-01
Two algorithms for processing the digitized readings of electronic noses, and computer programs to implement the algorithms, have been devised in a continuing effort to increase the utility of electronic noses as means of identifying airborne compounds and measuring their concentrations. One algorithm identifies the two vapors in a two-vapor mixture and estimates the concentration of each vapor (in principle, this algorithm could be extended to more than two vapors). The other algorithm identifies a single vapor and estimates its concentration.
FACE RECOGNITION BASED ON CUCKOO SEARCH ALGORITHM
VIPINKUMAR TIWARI
2012-01-01
Feature Selection is a optimization technique used in face recognition technology. Feature selection removes the irrelevant, noisy and redundant data thus leading to the more accurate recognition of face from the database.Cuckko Algorithm is one of the recent optimization algorithm in the league of nature based algorithm. Its optimization results are better than the PSO and ACO optimization algorithms. The proposal of applying the Cuckoo algorithm for feature selection in the process of face ...
Parallel algorithms for unconstrained optimizations by multisplitting
Energy Technology Data Exchange (ETDEWEB)
He, Qing [Arizona State Univ., Tempe, AZ (United States)
1994-12-31
In this paper a new parallel iterative algorithm for unconstrained optimization using the idea of multisplitting is proposed. This algorithm uses the existing sequential algorithms without any parallelization. Some convergence and numerical results for this algorithm are presented. The experiments are performed on an Intel iPSC/860 Hyper Cube with 64 nodes. It is interesting that the sequential implementation on one node shows that if the problem is split properly, the algorithm converges much faster than one without splitting.
MICROSTRIP COUPLER DESIGN USING BAT ALGORITHM
Directory of Open Access Journals (Sweden)
EzgiDeniz Ulker
2014-01-01
Full Text Available Evolutionary and swarm algorithms have found many applications in design problems since todays computing power enables these algorithms to find solutions to complicated design problems very fast. Newly proposed hybridalgorithm, bat algorithm, has been applied for the design of microwave microstrip couplers for the first time. Simulation results indicate that the bat algorithm is a very fast algorithm and it produces very reliable results.
An Improved Weighted Clustering Algorithm in MANET
Institute of Scientific and Technical Information of China (English)
WANG Jin; XU Li; ZHENG Bao-yu
2004-01-01
The original clustering algorithms in Mobile Ad hoc Network (MANET) are firstly analyzed in this paper.Based on which, an Improved Weighted Clustering Algorithm (IWCA) is proposed. Then, the principle and steps of our algorithm are explained in detail, and a comparison is made between the original algorithms and our improved method in the aspects of average cluster number, topology stability, clusterhead load balance and network lifetime. The experimental results show that our improved algorithm has the best performance on average.
A NEW ALGORITHM FOR SCANSAR PROCESSING
Institute of Scientific and Technical Information of China (English)
Qiao Rongrong; Wang Zhensong; Ian Cumming
2001-01-01
In this paper, a new phase preserving algorithm-the short IFFT algorithm for the burst-mode ScanSAR processing is presented. Analysis and simulation are done to verify the phase accuracy of this algorithm. Finally, the phase accuracy of this algorithm by making interferogram with simulated burst-mode INSAR data is illustrated. The results show that this new algorithm works well for interferometric application of ScanSAR data.
New multi-pattern matching algorithm
Institute of Scientific and Technical Information of China (English)
Liu Gongshen; Li Jianhua; Li Shenghong
2006-01-01
The traditional multiple pattern matching algorithm, deterministic finite state automata, is implemented by tree structure. A new algorithm is proposed by substituting sequential binary tree for traditional tree. It is proved by experiment that the algorithm has three features: its construction process is quick, its cost of memory is small. At the same time, its searching process is as quick as the traditional algorithm. The algorithm is suitable for the application which requires preprocessing the patterns dynamically.
A Fast Algorithm for Mining Association Rules
Institute of Scientific and Technical Information of China (English)
黄刘生; 陈华平; 王洵; 陈国良
2000-01-01
In this paper, the problem of discovering association rules between items in a large database of sales transactions is discussed, and a novel algorithm,BitMatrix, is proposed. The proposed algorithm is fundamentally different from the known algorithms Apriori and AprioriTid. Empirical evaluation shows that the algorithm outperforms the known ones for large databases. Scale-up experiments show that the algorithm scales linearly with the number of transactions.
AN SVAD ALGORITHM BASED ON FNNKD METHOD
Institute of Scientific and Technical Information of China (English)
Chen Dong; Zhang Yan; Kuang Jingming
2002-01-01
The capacity of mobile communication system is improved by using Voice Activity Detection (VAD) technology. In this letter, a novel VAD algorithm, SVAD algorithm based on Fuzzy Neural Network Knowledge Discovery (FNNKD) method is proposed. The performance of SVAD algorithm is discussed and compared with traditional algorithm recommended by ITU G.729B in different situations. The simulation results show that the SVAD algorithm performs better.
A Robust Parsing Algorithm For Link Grammars
Grinberg, Dennis; Lafferty, John; Sleator, Daniel
1995-01-01
In this paper we present a robust parsing algorithm based on the link grammar formalism for parsing natural languages. Our algorithm is a natural extension of the original dynamic programming recognition algorithm which recursively counts the number of linkages between two words in the input sentence. The modified algorithm uses the notion of a null link in order to allow a connection between any pair of adjacent words, regardless of their dictionary definitions. The algorithm proceeds by mak...
Blind Alley Aware ACO Routing Algorithm
Yoshikawa, Masaya; Otani, Kazuo
2010-10-01
The routing problem is applied to various engineering fields. Many researchers study this problem. In this paper, we propose a new routing algorithm which is based on Ant Colony Optimization. The proposed algorithm introduces the tabu search mechanism to escape the blind alley. Thus, the proposed algorithm enables to find the shortest route, even if the map data contains the blind alley. Experiments using map data prove the effectiveness in comparison with Dijkstra algorithm which is the most popular conventional routing algorithm.
Multithreaded Implementation of Hybrid String Matching Algorithm
Directory of Open Access Journals (Sweden)
Akhtar Rasool
2012-03-01
Full Text Available Reading and taking reference from many books and articles, and then analyzing the Navies algorithm, Boyer Moore algorithm and Knuth Morris Pratt (KMP algorithm and a variety of improved algorithms, summarizes various advantages and disadvantages of the pattern matching algorithms. And on this basis, a new algorithm – Multithreaded Hybrid algorithm is introduced. The algorithm refers to Boyer Moore algorithm, KMP algorithm and the thinking of improved algorithms. Utilize the last character of the string, the next character and the method to compare from side to side, and then advance a new hybrid pattern matching algorithm. And it adjusted the comparison direction and the order of the comparison to make the maximum moving distance of each time to reduce the pattern matching time. The algorithm reduces the comparison number and greatlyreduces the moving number of the pattern and improves the matching efficiency. Multithreaded implementation of hybrid, pattern matching algorithm performs the parallel string searching on different text data by executing a number of threads simultaneously. This approach is advantageous from all other string-pattern matching algorithm in terms of time complexity. This again improves the overall string matching efficiency.
Edge Crossing Minimization Algorithm for Hierarchical Graphs Based on Genetic Algorithms
Institute of Scientific and Technical Information of China (English)
无
2001-01-01
We present an edge crossing minimization algorithm forhierarchical gr aphs based on genetic algorithms, and comparing it with some heuristic algorithm s. The proposed algorithm is more efficient and has the following advantages: th e frame of the algorithms is unified, the method is simple, and its implementati on and revision are easy.
New algorithm for OHSS prevention
DEFF Research Database (Denmark)
Papanikolaou, Evangelos G; Humaidan, Peter; Polyzos, Nikos;
2011-01-01
of four new modalities: the GnRH antagonist protocol, GnRH agonist (GnRHa) triggering of ovulation, blastocyst transfer and embryo/oocyte vitrification, renders feasible the elimination of OHSS in connection with ovarian hyperstimulation for IVF treatment. The proposed current algorithm is based...
Adaptive protection algorithm and system
Hedrick, Paul [Pittsburgh, PA; Toms, Helen L [Irwin, PA; Miller, Roger M [Mars, PA
2009-04-28
An adaptive protection algorithm and system for protecting electrical distribution systems traces the flow of power through a distribution system, assigns a value (or rank) to each circuit breaker in the system and then determines the appropriate trip set points based on the assigned rank.
A greatest common divisor algorithm
Belenkiy, A; Vidunas, R
1998-01-01
Algorithms of computation of the Greatest Common Divisor (GCD) of two integers play a principal role in all computational systems dealing with rational arithmetic. The simplest one (Euclidean) is not the best for large numbers (see D. E. Knuth's book "The Art of Computer Programming" for details). O
Algorithm Visualization in Teaching Practice
Törley, Gábor
2014-01-01
This paper presents the history of algorithm visualization (AV), highlighting teaching-methodology aspects. A combined, two-group pedagogical experiment will be presented as well, which measured the efficiency and the impact on the abstract thinking of AV. According to the results, students, who learned with AV, performed better in the experiment.
Variance Adjusted Actor Critic Algorithms
Tamar, Aviv; Mannor, Shie
2013-01-01
We present an actor-critic framework for MDPs where the objective is the variance-adjusted expected return. Our critic uses linear function approximation, and we extend the concept of compatible features to the variance-adjusted setting. We present an episodic actor-critic algorithm and show that it converges almost surely to a locally optimal point of the objective function.
Algorithmic Issues in Modeling Motion
DEFF Research Database (Denmark)
Agarwal, P. K; Guibas, L. J; Edelsbrunner, H.;
2003-01-01
This article is a survey of research areas in which motion plays a pivotal role. The aim of the article is to review current approaches to modeling motion together with related data structures and algorithms, and to summarize the challenges that lie ahead in producing a more unified theory...
Threshold extended ID3 algorithm
Kumar, A. B. Rajesh; Ramesh, C. Phani; Madhusudhan, E.; Padmavathamma, M.
2012-04-01
Information exchange over insecure networks needs to provide authentication and confidentiality to the database in significant problem in datamining. In this paper we propose a novel authenticated multiparty ID3 Algorithm used to construct multiparty secret sharing decision tree for implementation in medical transactions.
Document Organization Using Kohonen's Algorithm.
Guerrero Bote, Vicente P.; Moya Anegon, Felix de; Herrero Solana, Victor
2002-01-01
Discussion of the classification of documents from bibliographic databases focuses on a method of vectorizing reference documents from LISA (Library and Information Science Abstracts) which permits their topological organization using Kohonen's algorithm. Analyzes possibilities of this type of neural network with respect to the development of…
Key Concepts in Informatics: Algorithm
Szlávi, Péter; Zsakó, László
2014-01-01
"The system of key concepts contains the most important key concepts related to the development tasks of knowledge areas and their vertical hierarchy as well as the links of basic key concepts of different knowledge areas." (Vass 2011) One of the most important of these concepts is the algorithm. In everyday life, when learning or…
Understanding Algorithms in Different Presentations
Csernoch, Mária; Biró, Piroska; Abari, Kálmán; Máth, János
2015-01-01
Within the framework of the Testing Algorithmic and Application Skills project we tested first year students of Informatics at the beginning of their tertiary education. We were focusing on the students' level of understanding in different programming environments. In the present paper we provide the results from the University of Debrecen, the…
Randomized approximate nearest neighbors algorithm.
Jones, Peter Wilcox; Osipov, Andrei; Rokhlin, Vladimir
2011-09-20
We present a randomized algorithm for the approximate nearest neighbor problem in d-dimensional Euclidean space. Given N points {x(j)} in R(d), the algorithm attempts to find k nearest neighbors for each of x(j), where k is a user-specified integer parameter. The algorithm is iterative, and its running time requirements are proportional to T·N·(d·(log d) + k·(d + log k)·(log N)) + N·k(2)·(d + log k), with T the number of iterations performed. The memory requirements of the procedure are of the order N·(d + k). A by-product of the scheme is a data structure, permitting a rapid search for the k nearest neighbors among {x(j)} for an arbitrary point x ∈ R(d). The cost of each such query is proportional to T·(d·(log d) + log(N/k)·k·(d + log k)), and the memory requirements for the requisite data structure are of the order N·(d + k) + T·(d + N). The algorithm utilizes random rotations and a basic divide-and-conquer scheme, followed by a local graph search. We analyze the scheme's behavior for certain types of distributions of {x(j)} and illustrate its performance via several numerical examples.
Analysis of Accelerated Gossip Algorithms
Liu, J.; Anderson, B.D.O.; Cao, M.; Morse, A.S.
2009-01-01
This paper investigates accelerated gossip algorithms for distributed computations in networks where shift-registers are utilized at each node. By using tools from matrix analysis, we prove the existence of the desired acceleration and establish the fastest rate of convergence in expectation for two
Classification algorithms using adaptive partitioning
Binev, Peter
2014-12-01
© 2014 Institute of Mathematical Statistics. Algorithms for binary classification based on adaptive tree partitioning are formulated and analyzed for both their risk performance and their friendliness to numerical implementation. The algorithms can be viewed as generating a set approximation to the Bayes set and thus fall into the general category of set estimators. In contrast with the most studied tree-based algorithms, which utilize piecewise constant approximation on the generated partition [IEEE Trans. Inform. Theory 52 (2006) 1335.1353; Mach. Learn. 66 (2007) 209.242], we consider decorated trees, which allow us to derive higher order methods. Convergence rates for these methods are derived in terms the parameter - of margin conditions and a rate s of best approximation of the Bayes set by decorated adaptive partitions. They can also be expressed in terms of the Besov smoothness β of the regression function that governs its approximability by piecewise polynomials on adaptive partition. The execution of the algorithms does not require knowledge of the smoothness or margin conditions. Besov smoothness conditions are weaker than the commonly used Holder conditions, which govern approximation by nonadaptive partitions, and therefore for a given regression function can result in a higher rate of convergence. This in turn mitigates the compatibility conflict between smoothness and margin parameters.
Knowledge-based tracking algorithm
Corbeil, Allan F.; Hawkins, Linda J.; Gilgallon, Paul F.
1990-10-01
This paper describes the Knowledge-Based Tracking (KBT) algorithm for which a real-time flight test demonstration was recently conducted at Rome Air Development Center (RADC). In KBT processing, the radar signal in each resolution cell is thresholded at a lower than normal setting to detect low RCS targets. This lower threshold produces a larger than normal false alarm rate. Therefore, additional signal processing including spectral filtering, CFAR and knowledge-based acceptance testing are performed to eliminate some of the false alarms. TSC's knowledge-based Track-Before-Detect (TBD) algorithm is then applied to the data from each azimuth sector to detect target tracks. In this algorithm, tentative track templates are formed for each threshold crossing and knowledge-based association rules are applied to the range, Doppler, and azimuth measurements from successive scans. Lastly, an M-association out of N-scan rule is used to declare a detection. This scan-to-scan integration enhances the probability of target detection while maintaining an acceptably low output false alarm rate. For a real-time demonstration of the KBT algorithm, the L-band radar in the Surveillance Laboratory (SL) at RADC was used to illuminate a small Cessna 310 test aircraft. The received radar signal wa digitized and processed by a ST-100 Array Processor and VAX computer network in the lab. The ST-100 performed all of the radar signal processing functions, including Moving Target Indicator (MTI) pulse cancelling, FFT Doppler filtering, and CFAR detection. The VAX computers performed the remaining range-Doppler clustering, beamsplitting and TBD processing functions. The KBT algorithm provided a 9.5 dB improvement relative to single scan performance with a nominal real time delay of less than one second between illumination and display.
FICA:fuzzy imperialist competitive algorithm
Institute of Scientific and Technical Information of China (English)
Saeid ARISH; Ali AMIRI; Khadije NOORI
2014-01-01
Despite the success of the imperialist competitive algorithm (ICA) in solving optimization problems, it still suffers from frequently falling into local minima and low convergence speed. In this paper, a fuzzy version of this algorithm is proposed to address these issues. In contrast to the standard version of ICA, in the proposed algorithm, powerful countries are chosen as imperialists in each step;according to a fuzzy membership function, other countries become colonies of all the empires. In ab-sorption policy, based on the fuzzy membership function, colonies move toward the resulting vector of all imperialists. In this algorithm, no empire will be eliminated;instead, during the execution of the algorithm, empires move toward one point. Other steps of the algorithm are similar to the standard ICA. In experiments, the proposed algorithm has been used to solve the real world optimization problems presented for IEEE-CEC 2011 evolutionary algorithm competition. Results of experiments confirm the performance of the algorithm.
Opposition-Based Adaptive Fireworks Algorithm
Directory of Open Access Journals (Sweden)
Chibing Gong
2016-07-01
Full Text Available A fireworks algorithm (FWA is a recent swarm intelligence algorithm that is inspired by observing fireworks explosions. An adaptive fireworks algorithm (AFWA proposes additional adaptive amplitudes to improve the performance of the enhanced fireworks algorithm (EFWA. The purpose of this paper is to add opposition-based learning (OBL to AFWA with the goal of further boosting performance and achieving global optimization. Twelve benchmark functions are tested in use of an opposition-based adaptive fireworks algorithm (OAFWA. The final results conclude that OAFWA significantly outperformed EFWA and AFWA in terms of solution accuracy. Additionally, OAFWA was compared with a bat algorithm (BA, differential evolution (DE, self-adapting control parameters in differential evolution (jDE, a firefly algorithm (FA, and a standard particle swarm optimization 2011 (SPSO2011 algorithm. The research results indicate that OAFWA ranks the highest of the six algorithms for both solution accuracy and runtime cost.
Differential AR algorithm for packet delay prediction
Institute of Scientific and Technical Information of China (English)
无
2006-01-01
Different delay prediction algorithms have been applied in multimedia communication, among which linear prediction is attractive because of its low complexity. AR (auto regressive) algorithm is a traditional one with low computation cost, while NLMS (normalize least mean square) algorithm is more precise. In this paper, referring to ARIMA (auto regression integrated with moving averages) model, a differential AR algorithm (DIAR) is proposed based on the analyses of both AR and NLMS algorithms. The prediction precision of the new algorithm is about 5-10 db higher than that of the AR algorithm without increasing the computation complexity.Compared with NLMS algorithm, its precision slightly improves by 0.1 db on average, but the algorithm complexity reduces more than 90%. Our simulation and tests also demonstrate that this method improves the performance of the average end-to-end delay and packet loss ratio significantly.
Improvement and Validation of the BOAT Algorithm
Directory of Open Access Journals (Sweden)
Yingchun Liu
2014-04-01
Full Text Available The main objective of this paper is improving the BOAT classification algorithm and applying it in credit card big data analysis. Decision tree algorithm is a data analysis method for the classification which can be used to describe the extract important data class models or predict future data trends. The BOAT algorithm can reduce the data during reading and writing the operations, the improved algorithms in large data sets under the operating efficiency, and in line with the popular big data analysis. Through this paper, BOAT algorithm can further improve the performance of the algorithm and the distributed data sources under the performance. In this paper, large banking sectors of credit card data as the being tested data sets. The improved algorithm, the original BOAT algorithms, and the performance of other classical classification algorithms will be compared and analyzed.
Semi-optimal Practicable Algorithmic Cooling
Elias, Yuval; Weinstein, Yossi; 10.1103/PhysRevA.83.042340
2011-01-01
Algorithmic Cooling (AC) of spins applies entropy manipulation algorithms in open spin-systems in order to cool spins far beyond Shannon's entropy bound. AC of nuclear spins was demonstrated experimentally, and may contribute to nuclear magnetic resonance (NMR) spectroscopy. Several cooling algorithms were suggested in recent years, including practicable algorithmic cooling (PAC) and exhaustive AC. Practicable algorithms have simple implementations, yet their level of cooling is far from optimal; Exhaustive algorithms, on the other hand, cool much better, and some even reach (asymptotically) an optimal level of cooling, but they are not practicable. We introduce here semi-optimal practicable AC (SOPAC), wherein few cycles (typically 2-6) are performed at each recursive level. Two classes of SOPAC algorithms are proposed and analyzed. Both attain cooling levels significantly better than PAC, and are much more efficient than the exhaustive algorithms. The new algorithms are shown to bridge the gap between PAC a...
Birkhoffian symplectic algorithms derived from Hamiltonian symplectic algorithms
Xin-Lei, Kong; Hui-Bin, Wu; Feng-Xiang, Mei
2016-01-01
In this paper, we focus on the construction of structure preserving algorithms for Birkhoffian systems, based on existing symplectic schemes for the Hamiltonian equations. The key of the method is to seek an invertible transformation which drives the Birkhoffian equations reduce to the Hamiltonian equations. When there exists such a transformation, applying the corresponding inverse map to symplectic discretization of the Hamiltonian equations, then resulting difference schemes are verified to be Birkhoffian symplectic for the original Birkhoffian equations. To illustrate the operation process of the method, we construct several desirable algorithms for the linear damped oscillator and the single pendulum with linear dissipation respectively. All of them exhibit excellent numerical behavior, especially in preserving conserved quantities. Project supported by the National Natural Science Foundation of China (Grant No. 11272050), the Excellent Young Teachers Program of North China University of Technology (Grant No. XN132), and the Construction Plan for Innovative Research Team of North China University of Technology (Grant No. XN129).
Comparing Online Algorithms for Bin Packing Problems
DEFF Research Database (Denmark)
Epstein, Leah; Favrholdt, Lene Monrad; Kohrt, Jens Svalgaard
2012-01-01
The relative worst-order ratio is a measure of the quality of online algorithms. In contrast to the competitive ratio, this measure compares two online algorithms directly instead of using an intermediate comparison with an optimal offline algorithm. In this paper, we apply the relative worst......-order ratio to online algorithms for several common variants of the bin packing problem. We mainly consider pairs of algorithms that are not distinguished by the competitive ratio and show that the relative worst-order ratio prefers the intuitively better algorithm of each pair....
Affine Projection Algorithm Using Regressive Estimated Error
Zhang, Shu; Zhi, Yongfeng
2011-01-01
An affine projection algorithm using regressive estimated error (APA-REE) is presented in this paper. By redefining the iterated error of the affine projection algorithm (APA), a new algorithm is obtained, and it improves the adaptive filtering convergence rate. We analyze the iterated error signal and the stability for the APA-REE algorithm. The steady-state weights of the APA-REE algorithm are proved to be unbiased and consist. The simulation results show that the proposed algorithm has a f...
Algorithms for Boolean Function Query Properties
Aaronson, Scott
2001-01-01
We present new algorithms to compute fundamental properties of a Boolean function given in truth-table form. Specifically, we give an O(N^2.322 log N) algorithm for block sensitivity, an O(N^1.585 log N) algorithm for `tree decomposition,' and an O(N) algorithm for `quasisymmetry.' These algorithms are based on new insights into the structure of Boolean functions that may be of independent interest. We also give a subexponential-time algorithm for the space-bounded quantum query complexity of...
Generalized fairing algorithm of parametric cubic splines
Institute of Scientific and Technical Information of China (English)
WANG Yuan-jun; CAO Yuan
2006-01-01
Kjellander has reported an algorithm for fairing uniform parametric cubic splines. Poliakoff extended Kjellander's algorithm to non-uniform case. However, they merely changed the bad point's position, and neglected the smoothing of tangent at bad point. In this paper, we present a fairing algorithm that both changed point's position and its corresponding tangent vector. The new algorithm possesses the minimum property of energy. We also proved Poliakoff's fairing algorithm is a deduction of our fairing algorithm. Several fairing examples are given in this paper.
A Survey on Star Identification Algorithms
Directory of Open Access Journals (Sweden)
Daniele Mortari
2009-01-01
Full Text Available The author surveys algorithms used in star identification, commonly used in star trackers to determine the attitude of a spacecraft. Star trackers are a staple of attitude determination systems for most types of satellites. The paper covers: (a lost-in-space algorithms (when no a priori attitude information is available, (b recursive algorithms (when some a priori attitude information is available, and (c non-dimensional algorithms (when the star tracker calibration is not well-known. The performance of selected algorithms and supporting algorithms are compared.
Linear Time Algorithms for Parallel Machine Scheduling
Institute of Scientific and Technical Information of China (English)
Zhi Yi TAN; Yong HE
2007-01-01
This paper addresses linear time algorithms for parallel machine scheduling problems. We introduce a kind of threshold algorithms and discuss their main features. Three linear time threshold algorithm classes DT, PT and DTm are studied thoroughly. For all classes, we study their best possible algorithms among each class. We also present their application to several scheduling problems.The new algorithms are better than classical algorithms in time complexity and/or worst-case ratio.Computer-aided proof technique is used in the proof of main results, which greatly simplifies the proof and decreases case by case analysis.
Mean Shift Registration Algorithm for Dissimilar Sensors
Institute of Scientific and Technical Information of China (English)
QI Yong-qing; JING Zhong-liang; HU Shi-qiang; ZHAO Hai-tao
2009-01-01
The mean shift registration (MSR) algorithm is proposed to accurately estimate the biases for multiple dissimilar sensors. The new algorithm is a batch optimization procedure. The maximum likelihood estimator is used to estimate the target states, and then the mean shift algorithm is implemented to estimate the sensor biases. Monte Carlo simulations show that the MSR algorithm has significant improvement in performance with reducing the standard deviation and mean of sensor biased estimation error compared with the maximum likelihood registration algorithm. The quantitative analysis and the qualitative analysis show that the MSR algorithm has less computation than the maximum likelihood registration method.
The Geometry of Algorithms with Orthogonality Constraints
Edelman, A; Smith, S T; Edelman, Alan; Smith, Steven T.
1998-01-01
In this paper we develop new Newton and conjugate gradient algorithms on the Grassmann and Stiefel manifolds. These manifolds represent the constraints that arise in such areas as the symmetric eigenvalue problem, nonlinear eigenvalue problems, electronic structures computations, and signal processing. In addition to the new algorithms, we show how the geometrical framework gives penetrating new insights allowing us to create, understand, and compare algorithms. The theory proposed here provides a taxonomy for numerical linear algebra algorithms that provide a top level mathematical view of previously unrelated algorithms. It is our hope that developers of new algorithms and perturbation theories will benefit from the theory, methods, and examples in this paper.
Why is Boris algorithm so good?
International Nuclear Information System (INIS)
Due to its excellent long term accuracy, the Boris algorithm is the de facto standard for advancing a charged particle. Despite its popularity, up to now there has been no convincing explanation why the Boris algorithm has this advantageous feature. In this paper, we provide an answer to this question. We show that the Boris algorithm conserves phase space volume, even though it is not symplectic. The global bound on energy error typically associated with symplectic algorithms still holds for the Boris algorithm, making it an effective algorithm for the multi-scale dynamics of plasmas
Garg, Poonam
2010-01-01
Genetic algorithms are a population-based Meta heuristics. They have been successfully applied to many optimization problems. However, premature convergence is an inherent characteristic of such classical genetic algorithms that makes them incapable of searching numerous solutions of the problem domain. A memetic algorithm is an extension of the traditional genetic algorithm. It uses a local search technique to reduce the likelihood of the premature convergence. The cryptanalysis of simplified data encryption standard can be formulated as NP-Hard combinatorial problem. In this paper, a comparison between memetic algorithm and genetic algorithm were made in order to investigate the performance for the cryptanalysis on simplified data encryption standard problems(SDES). The methods were tested and various experimental results show that memetic algorithm performs better than the genetic algorithms for such type of NP-Hard combinatorial problem. This paper represents our first effort toward efficient memetic algo...
An Improved Multicast Routing Algorithm
Institute of Scientific and Technical Information of China (English)
蒋廷耀; 李庆华
2004-01-01
Multicasting is a communication service that allows an application to efficiently transmit copies of data packets to a set of destination nodes. The problem of finding a minimum cost multicast tree can be formulated as a minimum Steiner tree problem in networks, which is NP-completeness. MPH (minimum path cost heuristic) algorithm is a famous solution to this problem. In this paper,we present a novel solution TPMPH (two phase minimum path cost heuristic) to improve the MPH by generating the nodes and the edges of multicast tree separately. The cost of multicast tree generated by the proposed algorithm with the same time as MPH is no more than that of MPH in the worst case. Extensive simulation results show that TPMPH can effectively improve the performance on MPH, and performs better in large-scale networks and wireless networks.
Diversity-Based Boosting Algorithm
Directory of Open Access Journals (Sweden)
Jafar A. Alzubi
2016-05-01
Full Text Available Boosting is a well known and efficient technique for constructing a classifier ensemble. An ensemble is built incrementally by altering the distribution of training data set and forcing learners to focus on misclassification errors. In this paper, an improvement to Boosting algorithm called DivBoosting algorithm is proposed and studied. Experiments on several data sets are conducted on both Boosting and DivBoosting. The experimental results show that DivBoosting is a promising method for ensemble pruning. We believe that it has many advantages over traditional boosting method because its mechanism is not solely based on selecting the most accurate base classifiers but also based on selecting the most diverse set of classifiers.
Innovations in Lattice QCD Algorithms
International Nuclear Information System (INIS)
Lattice QCD calculations demand a substantial amount of computing power in order to achieve the high precision results needed to better understand the nature of strong interactions, assist experiment to discover new physics, and predict the behavior of a diverse set of physical systems ranging from the proton itself to astrophysical objects such as neutron stars. However, computer power alone is clearly not enough to tackle the calculations we need to be doing today. A steady stream of recent algorithmic developments has made an important impact on the kinds of calculations we can currently perform. In this talk I am reviewing these algorithms and their impact on the nature of lattice QCD calculations performed today
Optimisation algorithms for microarray biclustering.
Perrin, Dimitri; Duhamel, Christophe
2013-01-01
In providing simultaneous information on expression profiles for thousands of genes, microarray technologies have, in recent years, been largely used to investigate mechanisms of gene expression. Clustering and classification of such data can, indeed, highlight patterns and provide insight on biological processes. A common approach is to consider genes and samples of microarray datasets as nodes in a bipartite graphs, where edges are weighted e.g. based on the expression levels. In this paper, using a previously-evaluated weighting scheme, we focus on search algorithms and evaluate, in the context of biclustering, several variations of Genetic Algorithms. We also introduce a new heuristic "Propagate", which consists in recursively evaluating neighbour solutions with one more or one less active conditions. The results obtained on three well-known datasets show that, for a given weighting scheme, optimal or near-optimal solutions can be identified. PMID:24109756
Algorithms for Protein Structure Prediction
DEFF Research Database (Denmark)
Paluszewski, Martin
-trace. Here we present three different approaches for reconstruction of C-traces from predictable measures. In our first approach [63, 62], the C-trace is positioned on a lattice and a tabu-search algorithm is applied to find minimum energy structures. The energy function is based on half-sphere-exposure (HSE......) and contact number (CN) measures only. We show that the HSE measure is much more information-rich than CN, nevertheless, HSE does not appear to provide enough information to reconstruct the C-traces of real-sized proteins. Our experiments also show that using tabu search (with our novel tabu definition......) is more robust than standard Monte Carlo search. In the second approach for reconstruction of C-traces, an exact branch and bound algorithm has been developed [67, 65]. The model is discrete and makes use of secondary structure predictions, HSE, CN and radius of gyration. We show how to compute good lower...
MUSIC algorithms for rebar detection
International Nuclear Information System (INIS)
The MUSIC (MUltiple SIgnal Classification) algorithm is employed to detect and localize an unknown number of scattering objects which are small in size as compared to the wavelength. The ensemble of objects to be detected consists of both strong and weak scatterers. This represents a scattering environment challenging for detection purposes as strong scatterers tend to mask the weak ones. Consequently, the detection of more weakly scattering objects is not always guaranteed and can be completely impaired when the noise corrupting data is of a relatively high level. To overcome this drawback, here a new technique is proposed, starting from the idea of applying a two-stage MUSIC algorithm. In the first stage strong scatterers are detected. Then, information concerning their number and location is employed in the second stage focusing only on the weak scatterers. The role of an adequate scattering model is emphasized to improve drastically detection performance in realistic scenarios. (paper)
MUSIC algorithms for rebar detection
Solimene, Raffaele; Leone, Giovanni; Dell'Aversano, Angela
2013-12-01
The MUSIC (MUltiple SIgnal Classification) algorithm is employed to detect and localize an unknown number of scattering objects which are small in size as compared to the wavelength. The ensemble of objects to be detected consists of both strong and weak scatterers. This represents a scattering environment challenging for detection purposes as strong scatterers tend to mask the weak ones. Consequently, the detection of more weakly scattering objects is not always guaranteed and can be completely impaired when the noise corrupting data is of a relatively high level. To overcome this drawback, here a new technique is proposed, starting from the idea of applying a two-stage MUSIC algorithm. In the first stage strong scatterers are detected. Then, information concerning their number and location is employed in the second stage focusing only on the weak scatterers. The role of an adequate scattering model is emphasized to improve drastically detection performance in realistic scenarios.
Genetic Algorithms for Case Adaptation
International Nuclear Information System (INIS)
Case based reasoning (CBR) paradigm has been widely used to provide computer support for recalling and adapting known cases to novel situations. Case adaptation algorithms generally rely on knowledge based and heuristics in order to change the past solutions to solve new problems. However, case adaptation has always been a difficult process to engineers within (CBR) cycle. Its difficulties can be referred to its domain dependency; and computational cost. In an effort to solve this problem, this research explores a general-purpose method that applying a genetic algorithm (GA) to CBR adaptation. Therefore, it can decrease the computational complexity of the search space in the problems having a great dependency on their domain knowledge. The proposed model can be used to perform a variety of design tasks on a broad set of application domains. However, it has been implemented for the tablet formulation as a domain of application. The proposed system has improved the performance of the CBR design systems
Image reconstruction algorithms from projections
International Nuclear Information System (INIS)
Many physical or bio-physical phenomena can be analysed as 'images' that is to say a bi-dimensionnal representation of a characteristic parameter of the material (density, concentration of a given element, resistivity, etc...). The various algorithms reviewed in the paper lead to a numerical reconstitution of such an image from a finite set of measurements considered as 'projections' of the initial object. We first give a physical insight then the mathematical formulation of the various concepts necessary for the presentation of the problem; after that we show why and how many reconstruction algorithms are possible. These different strategies are quickly compared chiefly according to realization facilities, structure, volume and performances (speed, accuracy) of the processing system required
Innovations in Lattice QCD Algorithms
Energy Technology Data Exchange (ETDEWEB)
Konstantinos Orginos
2006-06-25
Lattice QCD calculations demand a substantial amount of computing power in order to achieve the high precision results needed to better understand the nature of strong interactions, assist experiment to discover new physics, and predict the behavior of a diverse set of physical systems ranging from the proton itself to astrophysical objects such as neutron stars. However, computer power alone is clearly not enough to tackle the calculations we need to be doing today. A steady stream of recent algorithmic developments has made an important impact on the kinds of calculations we can currently perform. In this talk I am reviewing these algorithms and their impact on the nature of lattice QCD calculations performed today.
A fast meteor detection algorithm
Gural, P.
2016-01-01
A low latency meteor detection algorithm for use with fast steering mirrors had been previously developed to track and telescopically follow meteors in real-time (Gural, 2007). It has been rewritten as a generic clustering and tracking software module for meteor detection that meets both the demanding throughput requirements of a Raspberry Pi while also maintaining a high probability of detection. The software interface is generalized to work with various forms of front-end video pre-processing approaches and provides a rich product set of parameterized line detection metrics. Discussion will include the Maximum Temporal Pixel (MTP) compression technique as a fast thresholding option for feeding the detection module, the detection algorithm trade for maximum processing throughput, details on the clustering and tracking methodology, processing products, performance metrics, and a general interface description.
An Accelerated Incremental Radiosity Algorithm
Institute of Scientific and Technical Information of China (English)
XING Changyu; SUN Jizhou; R. L. Grimsdale
2000-01-01
The incremental radiosity method has been shown to be an efficient technique for providing global illumination in dynamic environments as it exploits temporal coherence in object space. This paper presents an accelerated incremental radiosity algorithm, which is based on a dynamically followed partial matrix.This not only reduces the computation cost in determining incremental form-factors when the geometrical relationships between objects are constantly changing, but also simplifies the management of user interaction with comparatively little storage cost.
The CMS Particle Flow Algorithm
Beaudette, Florian
2014-01-01
A particle flow event-reconstruction algorithm has been successfully deployed in the CMS experiment and is nowadays used by most of the analyses. It aims at identifying and reconstructing individually each particle arising from the LHC proton-proton collision, by combining the information from all the subdetectors. The resulting particle-flow event reconstruction leads to an improved performance for the reconstruction of jets and MET, and for the identification of electrons, muons, and taus. ...
Weighted graph algorithms with Python
Kapanowski, A.; Gałuszka, Ł.
2015-01-01
Python implementation of selected weighted graph algorithms is presented. The minimal graph interface is defined together with several classes implementing this interface. Graph nodes can be any hashable Python objects. Directed edges are instances of the Edge class. Graphs are instances of the Graph class. It is based on the adjacency-list representation, but with fast lookup of nodes and neighbors (dict-of-dict structure). Other implementations of this class are also possible. In this work,...
Algorithms for regional source localization
Dandach, S. H.; Bullo, F.
2009-01-01
In this paper we use the MAP criterion to locate a region containing a source. Sensors placed in a field of interest divide the latter into smaller regions and take measurements that are transmitted over noisy wireless channels. We propose implementations of our algorithm that consider complete and limited communication among sensors and seek to choose the most likely hypothesis. Each hypothesis corresponds to the event that a given region contains the source. Corrupted measurements are used ...
Recent results on howard's algorithm
DEFF Research Database (Denmark)
Miltersen, P.B.
2012-01-01
is generally recognized as fast in practice, until recently, its worst case time complexity was poorly understood. However, a surge of results since 2009 has led us to a much more satisfactory understanding of the worst case time complexity of the algorithm in the various settings in which it applies....... In this talk, we shall survey these recent results and the open problems that remains....
A secured Cryptographic Hashing Algorithm
Mohanty, Rakesh; Sarangi, Niharjyoti; Bishi, Sukant kumar
2010-01-01
Cryptographic hash functions for calculating the message digest of a message has been in practical use as an effective measure to maintain message integrity since a few decades. This message digest is unique, irreversible and avoids all types of collisions for any given input string. The message digest calculated from this algorithm is propagated in the communication medium along with the original message from the sender side and on the receiver side integrity of the message can be verified b...
Parallel External Memory Graph Algorithms
DEFF Research Database (Denmark)
Arge, Lars Allan; Goodrich, Michael T.; Sitchinava, Nodari
2010-01-01
In this paper, we study parallel I/O efficient graph algorithms in the Parallel External Memory (PEM) model, one o f the private-cache chip multiprocessor (CMP) models. We study the fundamental problem of list ranking which leads to efficient solutions to problems on trees, such as computing lowest...... an optimal speedup of Â¿(P) in parallel I/O complexity and parallel computation time, compared to the single-processor external memory counterparts....
Graphics and visualization principles & algorithms
Theoharis, T; Platis, Nikolaos; Patrikalakis, Nicholas M
2008-01-01
Computer and engineering collections strong in applied graphics and analysis of visual data via computer will find Graphics & Visualization: Principles and Algorithms makes an excellent classroom text as well as supplemental reading. It integrates coverage of computer graphics and other visualization topics, from shadow geneeration and particle tracing to spatial subdivision and vector data visualization, and it provides a thorough review of literature from multiple experts, making for a comprehensive review essential to any advanced computer study.-California Bookw
Machine vision theory, algorithms, practicalities
Davies, E R
2005-01-01
In the last 40 years, machine vision has evolved into a mature field embracing a wide range of applications including surveillance, automated inspection, robot assembly, vehicle guidance, traffic monitoring and control, signature verification, biometric measurement, and analysis of remotely sensed images. While researchers and industry specialists continue to document their work in this area, it has become increasingly difficult for professionals and graduate students to understand the essential theory and practicalities well enough to design their own algorithms and systems. This book directl
ITERATIVE ALGORITHMS FOR DATA ASSIMILATION PROBLEMS
Institute of Scientific and Technical Information of China (English)
无
2002-01-01
Iterative algorithms for solving the data assimilation problems are considered, based on the main and adjoint equations. Spectral properties of the control operators of the problem are studied, the iterative algorithms are justified.
Genetic Programming and Genetic Algorithms for Propositions
Directory of Open Access Journals (Sweden)
Nabil M. HEWAHI
2012-01-01
Full Text Available In this paper we propose a mechanism to discover the compound proposition solutions for a given truth table without knowing the compound propositions that lead to the truth table results. The approach is based on two proposed algorithms, the first is called Producing Formula (PF algorithm which is based on the genetic programming idea, to find out the compound proposition solutions for the given truth table. The second algorithm is called the Solutions Optimization (SO algorithm which is based on genetic algorithms idea, to find a list of the optimum compound propositions that can solve the truth table. The obtained list will depend on the solutions obtained from the PF algorithm. Various types of genetic operators have been introduced to obtain the solutions either within the PF algorithm or SO algorithm.
Teaching Multiplication Algorithms from Other Cultures
Lin, Cheng-Yao
2007-01-01
This article describes a number of multiplication algorithms from different cultures around the world: Hindu, Egyptian, Russian, Japanese, and Chinese. Students can learn these algorithms and better understand the operation and properties of multiplication.
DNA Coding Based Knowledge Discovery Algorithm
Institute of Scientific and Technical Information of China (English)
LI Ji-yun; GENG Zhao-feng; SHAO Shi-huang
2002-01-01
A novel DNA coding based knowledge discovery algorithm was proposed, an example which verified its validity was given. It is proved that this algorithm can discover new simplified rules from the original rule set efficiently.
Algorithmic complexity and entanglement of quantum states.
Mora, Caterina E; Briegel, Hans J
2005-11-11
We define the algorithmic complexity of a quantum state relative to a given precision parameter, and give upper bounds for various examples of states. We also establish a connection between the entanglement of a quantum state and its algorithmic complexity.
An algorithm for generating abstract syntax trees
Noonan, R. E.
1985-01-01
The notion of an abstract syntax is discussed. An algorithm is presented for automatically deriving an abstract syntax directly from a BNF grammar. The implementation of this algorithm and its application to the grammar for Modula are discussed.
Memetic firefly algorithm for combinatorial optimization
Fister, Iztok; Fister, Iztok; Brest, Janez
2012-01-01
Firefly algorithms belong to modern meta-heuristic algorithms inspired by nature that can be successfully applied to continuous optimization problems. In this paper, we have been applied the firefly algorithm, hybridized with local search heuristic, to combinatorial optimization problems, where we use graph 3-coloring problems as test benchmarks. The results of the proposed memetic firefly algorithm (MFFA) were compared with the results of the Hybrid Evolutionary Algorithm (HEA), Tabucol, and the evolutionary algorithm with SAW method (EA-SAW) by coloring the suite of medium-scaled random graphs (graphs with 500 vertices) generated using the Culberson random graph generator. The results of firefly algorithm were very promising and showed a potential that this algorithm could successfully be applied in near future to the other combinatorial optimization problems as well.
Performance Analysis of Cone Detection Algorithms
Mariotti, Letizia
2015-01-01
Many algorithms have been proposed to help clinicians evaluate cone density and spacing, as these may be related to the onset of retinal diseases. However, there has been no rigorous comparison of the performance of these algorithms. In addition, the performance of such algorithms is typically determined by comparison with human observers. Here we propose a technique to simulate realistic images of the cone mosaic. We use the simulated images to test the performance of two popular cone detection algorithms and we introduce an algorithm which is used by astronomers to detect stars in astronomical images. We use Free Response Operating Characteristic (FROC) curves to evaluate and compare the performance of the three algorithms. This allows us to optimize the performance of each algorithm. We observe that performance is significantly enhanced by up-sampling the images. We investigate the effect of noise and image quality on cone mosaic parameters estimated using the different algorithms, finding that the estimat...
Spaceborne SAR Imaging Algorithm for Coherence Optimized.
Directory of Open Access Journals (Sweden)
Zhiwei Qiu
Full Text Available This paper proposes SAR imaging algorithm with largest coherence based on the existing SAR imaging algorithm. The basic idea of SAR imaging algorithm in imaging processing is that output signal can have maximum signal-to-noise ratio (SNR by using the optimal imaging parameters. Traditional imaging algorithm can acquire the best focusing effect, but would bring the decoherence phenomenon in subsequent interference process. Algorithm proposed in this paper is that SAR echo adopts consistent imaging parameters in focusing processing. Although the SNR of the output signal is reduced slightly, their coherence is ensured greatly, and finally the interferogram with high quality is obtained. In this paper, two scenes of Envisat ASAR data in Zhangbei are employed to conduct experiment for this algorithm. Compared with the interferogram from the traditional algorithm, the results show that this algorithm is more suitable for SAR interferometry (InSAR research and application.
Spaceborne SAR Imaging Algorithm for Coherence Optimized.
Qiu, Zhiwei; Yue, Jianping; Wang, Xueqin; Yue, Shun
2016-01-01
This paper proposes SAR imaging algorithm with largest coherence based on the existing SAR imaging algorithm. The basic idea of SAR imaging algorithm in imaging processing is that output signal can have maximum signal-to-noise ratio (SNR) by using the optimal imaging parameters. Traditional imaging algorithm can acquire the best focusing effect, but would bring the decoherence phenomenon in subsequent interference process. Algorithm proposed in this paper is that SAR echo adopts consistent imaging parameters in focusing processing. Although the SNR of the output signal is reduced slightly, their coherence is ensured greatly, and finally the interferogram with high quality is obtained. In this paper, two scenes of Envisat ASAR data in Zhangbei are employed to conduct experiment for this algorithm. Compared with the interferogram from the traditional algorithm, the results show that this algorithm is more suitable for SAR interferometry (InSAR) research and application. PMID:26871446
Spaceborne SAR Imaging Algorithm for Coherence Optimized
Qiu, Zhiwei; Yue, Jianping; Wang, Xueqin; Yue, Shun
2016-01-01
This paper proposes SAR imaging algorithm with largest coherence based on the existing SAR imaging algorithm. The basic idea of SAR imaging algorithm in imaging processing is that output signal can have maximum signal-to-noise ratio (SNR) by using the optimal imaging parameters. Traditional imaging algorithm can acquire the best focusing effect, but would bring the decoherence phenomenon in subsequent interference process. Algorithm proposed in this paper is that SAR echo adopts consistent imaging parameters in focusing processing. Although the SNR of the output signal is reduced slightly, their coherence is ensured greatly, and finally the interferogram with high quality is obtained. In this paper, two scenes of Envisat ASAR data in Zhangbei are employed to conduct experiment for this algorithm. Compared with the interferogram from the traditional algorithm, the results show that this algorithm is more suitable for SAR interferometry (InSAR) research and application. PMID:26871446
A Hybrid Architecture Approach for Quantum Algorithms
Directory of Open Access Journals (Sweden)
Mohammad R.S. Aghaei
2009-01-01
Full Text Available Problem statement: In this study, a general plan of hybrid architecture for quantum algorithms is proposed. Approach: Analysis of the quantum algorithms shows that these algorithms were hybrid with two parts. First, the relationship of classical and quantum parts of the hybrid algorithms was extracted. Then a general plan of hybrid structure was designed. Results: This plan was illustrated the hybrid architecture and the relationship of classical and quantum parts of the algorithms. This general plan was used to increase implementation performance of quantum algorithms. Conclusion/Recommendations: Moreover, simulation results of quantum algorithms on the hybrid architecture proved that quantum algorithms can be implemented on the general plan as well.
Bisection technique for designing synchronous parallel algorithms
Institute of Scientific and Technical Information of China (English)
王能超
1995-01-01
A basic technique for designing synchronous parallel algorithms, the so-called bisection technique, is proposed. The basic pattern of designing parallel algorithms is described. The relationship between the designing idea and I Ching (principles of change) is discussed.
Results of Evolution Supervised by Genetic Algorithms
Jäntschi, Lorentz; Bălan, Mugur C; Sestraş, Radu E
2010-01-01
A series of results of evolution supervised by genetic algorithms with interest to agricultural and horticultural fields are reviewed. New obtained original results from the use of genetic algorithms on structure-activity relationships are reported.
Nurse Rostering with Genetic Algorithms
Aickelin, Uwe
2010-01-01
In recent years genetic algorithms have emerged as a useful tool for the heuristic solution of complex discrete optimisation problems. In particular there has been considerable interest in their use in tackling problems arising in the areas of scheduling and timetabling. However, the classical genetic algorithm paradigm is not well equipped to handle constraints and successful implementations usually require some sort of modification to enable the search to exploit problem specific knowledge in order to overcome this shortcoming. This paper is concerned with the development of a family of genetic algorithms for the solution of a nurse rostering problem at a major UK hospital. The hospital is made up of wards of up to 30 nurses. Each ward has its own group of nurses whose shifts have to be scheduled on a weekly basis. In addition to fulfilling the minimum demand for staff over three daily shifts, nurses' wishes and qualifications have to be taken into account. The schedules must also be seen to be fair, in tha...
Experimental Validation for CRFNFP Algorithm
Directory of Open Access Journals (Sweden)
Wang Mingjun
2012-05-01
Full Text Available In 2010,we proposed CRFNFP[1] algorithm to enhance long-range terrain perception for outdoor robots through the integration of both appearance features and spatial contexts. And our preliminary simulation results indicated the superiority of CRFNFP over other existing approaches in terms of accuracy, robustness and adaptability to dynamic unstructured outdoor environments. In this paper, we further study on the comparison experiments for navigation behaviors of robotic systems with different scene perception algorithms in real outdoor scenes. We implemented 3 robotic systems and repeated the running jobs under various conditions. We also defined 3 creterion to facilitate comparison for all systems: Obstacle Response Distance (ORD, Time to Finish Job (TFJ, Distance of the Whole Run (DWR. The comparative experiments indicate that, the CRFNFP-based navigating system outperforms traditional local-map-based navigating systems in terms of all criterion. And the results also show that the CRFNFP algorithm does enhance the long-range perception for mobile robots and helps planning more efficient paths for the navigation.
Algorithmic Strategies in Combinatorial Chemistry
Energy Technology Data Exchange (ETDEWEB)
GOLDMAN,DEBORAH; ISTRAIL,SORIN; LANCIA,GIUSEPPE; PICCOLBONI,ANTONIO; WALENZ,BRIAN
2000-08-01
Combinatorial Chemistry is a powerful new technology in drug design and molecular recognition. It is a wet-laboratory methodology aimed at ``massively parallel'' screening of chemical compounds for the discovery of compounds that have a certain biological activity. The power of the method comes from the interaction between experimental design and computational modeling. Principles of ``rational'' drug design are used in the construction of combinatorial libraries to speed up the discovery of lead compounds with the desired biological activity. This paper presents algorithms, software development and computational complexity analysis for problems arising in the design of combinatorial libraries for drug discovery. The authors provide exact polynomial time algorithms and intractability results for several Inverse Problems-formulated as (chemical) graph reconstruction problems-related to the design of combinatorial libraries. These are the first rigorous algorithmic results in the literature. The authors also present results provided by the combinatorial chemistry software package OCOTILLO for combinatorial peptide design using real data libraries. The package provides exact solutions for general inverse problems based on shortest-path topological indices. The results are superior both in accuracy and computing time to the best software reports published in the literature. For 5-peptoid design, the computation is rigorously reduced to an exhaustive search of about 2% of the search space; the exact solutions are found in a few minutes.
Linear programming algorithms and applications
Vajda, S
1981-01-01
This text is based on a course of about 16 hours lectures to students of mathematics, statistics, and/or operational research. It is intended to introduce readers to the very wide range of applicability of linear programming, covering problems of manage ment, administration, transportation and a number of other uses which are mentioned in their context. The emphasis is on numerical algorithms, which are illustrated by examples of such modest size that the solutions can be obtained using pen and paper. It is clear that these methods, if applied to larger problems, can also be carried out on automatic (electronic) computers. Commercially available computer packages are, in fact, mainly based on algorithms explained in this book. The author is convinced that the user of these algorithms ought to be knowledgeable about the underlying theory. Therefore this volume is not merely addressed to the practitioner, but also to the mathematician who is interested in relatively new developments in algebraic theory and in...
A Survey on Star Identification Algorithms
Daniele Mortari; Benjamin B. Spratling
2009-01-01
The author surveys algorithms used in star identification, commonly used in star trackers to determine the attitude of a spacecraft. Star trackers are a staple of attitude determination systems for most types of satellites. The paper covers: (a) lost-in-space algorithms (when no a priori attitude information is available), (b) recursive algorithms (when some a priori attitude information is available), and (c) non-dimensional algorithms (when the star tracker calibration is not well-known). T...
Active noise cancellation algorithms for impulsive noise
Li, Peng; Yu, Xun
2012-01-01
Impulsive noise is an important challenge for the practical implementation of active noise control (ANC) systems. The advantages and disadvantages of popular filtered-X least mean square (FXLMS) ANC algorithm and nonlinear filtered-X least mean M-estimate (FXLMM) algorithm are discussed in this paper. A new modified FXLMM algorithm is also proposed to achieve better performance in controlling impulsive noise. Computer simulations and experiments are carried out for all three algorithms and th...
An algorithm for segmenting range imagery
Energy Technology Data Exchange (ETDEWEB)
Roberts, R.S.
1997-03-01
This report describes the technical accomplishments of the FY96 Cross Cutting and Advanced Technology (CC&AT) project at Los Alamos National Laboratory. The project focused on developing algorithms for segmenting range images. The image segmentation algorithm developed during the project is described here. In addition to segmenting range images, the algorithm can fuse multiple range images thereby providing true 3D scene models. The algorithm has been incorporated into the Rapid World Modelling System at Sandia National Laboratory.
Application of Chaos in Genetic Algorithms
Institute of Scientific and Technical Information of China (English)
YANG Li-Jiang; CHEN Tian-Lun
2002-01-01
Through replacing Gaussian mutation operator in real-coded genetic algorithm with a chaotic mapping, wepresent a genetic algorithm with chaotic mutation. To examine this new algorithm, we applied our algorithm to functionoptimization problems and obtained good results. Furthermore the orbital points' distribution of chaotic mapping andthe effects of chaotic mutation with different parameters were studied in order to make the chaotic mutation mechanismbe utilized efficiently.
A Deterministic and Polynomial Modified Perceptron Algorithm
Directory of Open Access Journals (Sweden)
Olof Barr
2006-01-01
Full Text Available We construct a modified perceptron algorithm that is deterministic, polynomial and also as fast as previous known algorithms. The algorithm runs in time O(mn3lognlog(1/ρ, where m is the number of examples, n the number of dimensions and ρ is approximately the size of the margin. We also construct a non-deterministic modified perceptron algorithm running in timeO(mn2lognlog(1/ρ.
Cultural Algorithm for Engineering Design Problems
Xuesong Yan
2012-01-01
Many engineering optimization problems can be state as function optimization with constrained, intelligence optimization algorithm can solve these problems well. Cultural Algorithms are a class of computational models derived from observing the cultural evolution process in nature, cultural algorithms in the optimization of the complex constrained functions of its superior performance. Experiment results reveal that the proposed algorithm can find better solutions when compared to other heuri...
Fast identification algorithms for forensic applications
Beekhof, Fokko Pieter; Voloshynovskyy, Svyatoslav; Koval, Oleksiy; Holotyak, Taras
2009-01-01
In this work a novel fast search algorithm is proposed that is designed to offer improved performance in terms of identification accuracy whilst maintaining acceptable speed for forensic applications involving biometrics and Physically Unclonable Functions. A framework for forensic applications is presented, followed by a review of optimal and existing fast algorithms. We show why the new algorithm has the power to outperform the other algorithms with a theoretic analysis and confirm this usi...
Distance Concentration-Based Artificial Immune Algorithm
Institute of Scientific and Technical Information of China (English)
LIU Tao; WANG Yao-cai; WANG Zhi-jie; MENG Jiang
2005-01-01
The diversity, adaptation and memory of biological immune system attract much attention of researchers. Several optimal algorithms based on immune system have also been proposed up to now. The distance concentration-based artificial immune algorithm (DCAIA) is proposed to overcome defects of the classical artificial immune algorithm (CAIA) in this paper. Compared with genetic algorithm (GA) and CAIA, DCAIA is good for solving the problem of precocity,holding the diversity of antibody, and enhancing convergence rate.
A Euclidean algorithm for integer matrices
DEFF Research Database (Denmark)
Lauritzen, Niels; Thomsen, Jesper Funch
2015-01-01
We present a Euclidean algorithm for computing a greatest common right divisor of two integer matrices. The algorithm is derived from elementary properties of finitely generated modules over the ring of integers.......We present a Euclidean algorithm for computing a greatest common right divisor of two integer matrices. The algorithm is derived from elementary properties of finitely generated modules over the ring of integers....
Implementation of Cryptographic Algorithm on FPGA
Prof. S. Venkateswarlu; Deepa G.M; G. Sriteja
2013-01-01
Advanced Encryption Standard (AES), a Federal Information Processing Standard (FIPS), is anapproved cryptographic algorithm that is used to protect electronic data. The AES can be programmed insoftware or built with hardware. The paper presents a hardware implementation of the AES algorithm onFPGA. The algorithm was implemented in FPGA using Spartan 3E starter kit and Xilinx ISE developmentsuite. The purpose of this attempt was to test the correctness of the implemented algorithm and to gaine...
Algorithms and Requirements for Measuring Network Bandwidth
Energy Technology Data Exchange (ETDEWEB)
Jin, Guojun
2002-12-08
This report unveils new algorithms for actively measuring (not estimating) available bandwidths with very low intrusion, computing cross traffic, thus estimating the physical bandwidth, provides mathematical proof that the algorithms are accurate, and addresses conditions, requirements, and limitations for new and existing algorithms for measuring network bandwidths. The paper also discusses a number of important terminologies and issues for network bandwidth measurement, and introduces a fundamental parameter -Maximum Burst Size that is critical for implementing algorithms based on multiple packets.
Automatic Algorithm Selection for Complex Simulation Problems
Ewald, Roland
2012-01-01
To select the most suitable simulation algorithm for a given task is often difficult. This is due to intricate interactions between model features, implementation details, and runtime environment, which may strongly affect the overall performance. An automated selection of simulation algorithms supports users in setting up simulation experiments without demanding expert knowledge on simulation. Roland Ewald analyzes and discusses existing approaches to solve the algorithm selection problem in the context of simulation. He introduces a framework for automatic simulation algorithm selection and
An algorithm for multiplication of Dirac numbers
Aleksandr Cariow; Galina Cariowa
2013-01-01
In this work a rationalized algorithm for Dirac numbers multiplication is presented. This algorithm has a low computational complexity feature and is well suited to parallelization of computations. The computation of two Dirac numbers product using the naïve method takes 256 real multiplications and 240 real additions, while the proposed algorithm can compute the same result in only 128 real multiplications and 160 real additions. During synthesis of the discussed algorithm we use the fact th...
A Direct Manipulation Language for Explaining Algorithms
Scott, Jeremy; Guo, Philip J.; Davis, Randall
2014-01-01
Instructors typically explain algorithms in computer science by tracing their behavior, often on blackboards, sometimes with algorithm visualizations. Using blackboards can be tedious because they do not facilitate manipulation of the drawing, while visualizations often operate at the wrong level of abstraction or must be laboriously hand-coded for each algorithm. In response, we present a direct manipulation (DM) language for explaining algorithms by manipulating visualized data structures. ...
Learning Intelligent Genetic Algorithms Using Japanese Nonograms
Tsai, Jinn-Tsong; Chou, Ping-Yi; Fang, Jia-Cen
2012-01-01
An intelligent genetic algorithm (IGA) is proposed to solve Japanese nonograms and is used as a method in a university course to learn evolutionary algorithms. The IGA combines the global exploration capabilities of a canonical genetic algorithm (CGA) with effective condensed encoding, improved fitness function, and modified crossover and…
Engineering a Cache-Oblivious Sorting Algorithm
DEFF Research Database (Denmark)
Brodal, Gerth Stølting; Fagerberg, Rolf; Vinther, Kristoffer
2007-01-01
This paper is an algorithmic engineering study of cache-oblivious sorting. We investigate by empirical methods a number of implementation issues and parameter choices for the cache-oblivious sorting algorithm Lazy Funnelsort, and compare the final algorithm with Quicksort, the established standard...
In-Trail Procedure (ITP) Algorithm Design
Munoz, Cesar A.; Siminiceanu, Radu I.
2007-01-01
The primary objective of this document is to provide a detailed description of the In-Trail Procedure (ITP) algorithm, which is part of the Airborne Traffic Situational Awareness In-Trail Procedure (ATSA-ITP) application. To this end, the document presents a high level description of the ITP Algorithm and a prototype implementation of this algorithm in the programming language C.
An algorithm for reduct cardinality minimization
AbouEisha, Hassan M.
2013-12-01
This is devoted to the consideration of a new algorithm for reduct cardinality minimization. This algorithm transforms the initial table to a decision table of a special kind, simplify this table, and use a dynamic programming algorithm to finish the construction of an optimal reduct. Results of computer experiments with decision tables from UCI ML Repository are discussed. © 2013 IEEE.
Biology-Derived Algorithms in Engineering Optimization
Yang, Xin-She
2010-01-01
Biology-derived algorithms are an important part of computational sciences, which are essential to many scientific disciplines and engineering applications. Many computational methods are derived from or based on the analogy to natural evolution and biological activities, and these biologically inspired computations include genetic algorithms, neural networks, cellular automata, and other algorithms.
An adaptive algorithm for noise rejection.
Lovelace, D E; Knoebel, S B
1978-01-01
An adaptive algorithm for the rejection of noise artifact in 24-hour ambulatory electrocardiographic recordings is described. The algorithm is based on increased amplitude distortion or increased frequency of fluctuations associated with an episode of noise artifact. The results of application of the noise rejection algorithm on a high noise population of test tapes are discussed.
Progress in lattice field theory algorithms
International Nuclear Information System (INIS)
I present a summary of recent algorithmic developments for lattice field theories. In particular I give a pedagogical introduction to the new Multicanonical algorithm, and discuss the relation between the Hybrid Overrelaxation and Hybrid Monte Carlo algorithms. I also attempt to clarify the role of the dynamical critical exponent z and its connection with 'computational cost'. (orig.)
Discrete Riccati equation solutions: Distributed algorithms
Directory of Open Access Journals (Sweden)
D. G. Lainiotis
1996-01-01
Full Text Available In this paper new distributed algorithms for the solution of the discrete Riccati equation are introduced. The algorithms are used to provide robust and computational efficient solutions to the discrete Riccati equation. The proposed distributed algorithms are theoretically interesting and computationally attractive.
Voronoi Particle Merging Algorithm for PIC Codes
Luu, Phuc T
2016-01-01
We present a new particle-merging algorithm for the particle-in-cell method. Based on the concept of the Voronoi diagram, the algorithm partitions the phase space into smaller subsets, which consist of only particles that are in close proximity in the phase space to each other. We show the performance of our algorithm in the case of magnetic shower.
On König's root finding algorithms
DEFF Research Database (Denmark)
Buff, Xavier; Henriksen, Christian
2003-01-01
In this paper, we first recall the definition of a family of root-finding algorithms known as König's algorithms. We establish some local and some global properties of those algorithms. We give a characterization of rational maps which arise as König's methods of polynomials with simple roots. We...
Successive combination jet algorithm for hadron collisions
Ellis, S D; Ellis, Stephen D.; Soper, Davision E.
1993-01-01
Jet finding algorithms, as they are used in $e^+ e^-$ and hadron collisions, are reviewed and compared. It is suggested that a successive combination style algorithm, similar to that used in $e^+ e^-$ physics, might be useful also in hadron collisions, where cone style algorithms have been used previously.
Inverse Computation and the Universal Resolving Algorithm
Institute of Scientific and Technical Information of China (English)
无
2001-01-01
We survey fundamental concepts for inverse programming and thenpresent the Uni v ersal Resolving Algorithm, an algorithm for inverse computation in a first-orde r , functional programming language. We discuss the key concepts of the algorithm, including a three-step approach based on the notion of a perfect process tree, and demonstrate our implementation with several examples of inverse computation.
Quantum Central Processing Unit and Quantum Algorithm
Institute of Scientific and Technical Information of China (English)
王安民
2002-01-01
Based on a scalable and universal quantum network, quantum central processing unit, proposed in our previous paper [Chin. Phys. Left. 18 (2001)166], the whole quantum network for the known quantum algorithms,including quantum Fourier transformation, Shor's algorithm and Grover's algorithm, is obtained in a unitied way.
A Hybrid Task Scheduling Algorithm in Grid
Institute of Scientific and Technical Information of China (English)
ZHANG Yan-mei; CAO Huai-hu; YU Zhen-wei
2006-01-01
Task scheduling in Grid has been proved to be NP- complete problem. In this paper, to solve this problem, a Hybrid Task Scheduling Algorithm in Grid (HTS) has been presented, which joint the advantages of Ant Colony and Genetic Algorithm.Compared with the related work, the result shows that the HTS algorithm significantly surpasses the previous approaches in schedule length ratio and speedup.
Trilateral market coupling. Algorithm appendix
International Nuclear Information System (INIS)
Market Coupling is both a mechanism for matching orders on the exchange and an implicit cross-border capacity allocation mechanism. Market Coupling improves the economic surplus of the coupled markets: the highest purchase orders and the lowest sale orders of the coupled power exchanges are matched, regardless of the area where they have been submitted; matching results depend however on the Available Transfer Capacity (ATC) between the coupled hubs. Market prices and schedules of the day-ahead power exchanges of the several connected markets are simultaneously determined with the use of the Available Transfer Capacity defined by the relevant Transmission System Operators. The transmission capacity is thereby implicitly auctioned and the implicit cost of the transmission capacity from one market to the other is the price difference between the two markets. In particular, if the transmission capacity between two markets is not fully used, there is no price difference between the markets and the implicit cost of the transmission capacity is null. Market coupling relies on the principle that the market with the lowest price exports electricity to the market with the highest price. Two situations may appear: either the Available Transfer Capacity (ATC) is large enough and the prices of both markets are equalized (price convergence), or the ATC is too small and the prices cannot be equalized. The Market Coupling algorithm takes as an input: 1 - The Available Transfer Capacity (ATC) between each area for each flow direction and each Settlement Period of the following day (i.e. for each hour of following day); 2 - The (Block Free) Net Export Curves (NEC) of each market for each hour of the following day, i.e., the difference between the total quantity of Divisible Hourly Bids and the total quantity of Divisible Hourly Offers for each price level. The NEC reflects a market's import or export volume sensitivity to price. 3 - The Block Orders submitted by the participants in
Optimisation of nonlinear motion cueing algorithm based on genetic algorithm
Asadi, Houshyar; Mohamed, Shady; Rahim Zadeh, Delpak; Nahavandi, Saeid
2015-04-01
Motion cueing algorithms (MCAs) are playing a significant role in driving simulators, aiming to deliver the most accurate human sensation to the simulator drivers compared with a real vehicle driver, without exceeding the physical limitations of the simulator. This paper provides the optimisation design of an MCA for a vehicle simulator, in order to find the most suitable washout algorithm parameters, while respecting all motion platform physical limitations, and minimising human perception error between real and simulator driver. One of the main limitations of the classical washout filters is that it is attuned by the worst-case scenario tuning method. This is based on trial and error, and is effected by driving and programmers experience, making this the most significant obstacle to full motion platform utilisation. This leads to inflexibility of the structure, production of false cues and makes the resulting simulator fail to suit all circumstances. In addition, the classical method does not take minimisation of human perception error and physical constraints into account. Production of motion cues and the impact of different parameters of classical washout filters on motion cues remain inaccessible for designers for this reason. The aim of this paper is to provide an optimisation method for tuning the MCA parameters, based on nonlinear filtering and genetic algorithms. This is done by taking vestibular sensation error into account between real and simulated cases, as well as main dynamic limitations, tilt coordination and correlation coefficient. Three additional compensatory linear blocks are integrated into the MCA, to be tuned in order to modify the performance of the filters successfully. The proposed optimised MCA is implemented in MATLAB/Simulink software packages. The results generated using the proposed method show increased performance in terms of human sensation, reference shape tracking and exploiting the platform more efficiently without reaching
FACE RECOGNITION BASED ON CUCKOO SEARCH ALGORITHM
Directory of Open Access Journals (Sweden)
VIPINKUMAR TIWARI
2012-07-01
Full Text Available Feature Selection is a optimization technique used in face recognition technology. Feature selection removes the irrelevant, noisy and redundant data thus leading to the more accurate recognition of face from the database.Cuckko Algorithm is one of the recent optimization algorithm in the league of nature based algorithm. Its optimization results are better than the PSO and ACO optimization algorithms. The proposal of applying the Cuckoo algorithm for feature selection in the process of face recognition is presented in this paper.
Bat Algorithm for Multi-objective Optimisation
Yang, Xin-She
2012-01-01
Engineering optimization is typically multiobjective and multidisciplinary with complex constraints, and the solution of such complex problems requires efficient optimization algorithms. Recently, Xin-She Yang proposed a bat-inspired algorithm for solving nonlinear, global optimisation problems. In this paper, we extend this algorithm to solve multiobjective optimisation problems. The proposed multiobjective bat algorithm (MOBA) is first validated against a subset of test functions, and then applied to solve multiobjective design problems such as welded beam design. Simulation results suggest that the proposed algorithm works efficiently.
A Novel Induction Algorithm for DM
Institute of Scientific and Technical Information of China (English)
无
2001-01-01
DM usually means an efficient knowledge discovery from database, and the immune algorithm is a biological theory-based and global searching algorithm. A novel induction algorithm is proposed here which integrates a power of individual immunity and an evolutionary mechanism of population. This algorithm does not take great care of discovering some classifying information, but unknown knowledge or a predication on higher level rules. Theoretical analysis and simulations both show that this algorithm is prone to the stabilization of a population and the improvement of entire capability, and also keeping a high degree of preciseness during the rule induction.
Ordered subsets algorithms for transmission tomography.
Erdogan, H; Fessler, J A
1999-11-01
The ordered subsets EM (OSEM) algorithm has enjoyed considerable interest for emission image reconstruction due to its acceleration of the original EM algorithm and ease of programming. The transmission EM reconstruction algorithm converges very slowly and is not used in practice. In this paper, we introduce a simultaneous update algorithm called separable paraboloidal surrogates (SPS) that converges much faster than the transmission EM algorithm. Furthermore, unlike the 'convex algorithm' for transmission tomography, the proposed algorithm is monotonic even with nonzero background counts. We demonstrate that the ordered subsets principle can also be applied to the new SPS algorithm for transmission tomography to accelerate 'convergence', albeit with similar sacrifice of global convergence properties as for OSEM. We implemented and evaluated this ordered subsets transmission (OSTR) algorithm. The results indicate that the OSTR algorithm speeds up the increase in the objective function by roughly the number of subsets in the early iterates when compared to the ordinary SPS algorithm. We compute mean square errors and segmentation errors for different methods and show that OSTR is superior to OSEM applied to the logarithm of the transmission data. However, penalized-likelihood reconstructions yield the best quality images among all other methods tested. PMID:10588288
Filtering algorithm for dotted interferences
Energy Technology Data Exchange (ETDEWEB)
Osterloh, K., E-mail: kurt.osterloh@bam.de [Federal Institute for Materials Research and Testing (BAM), Division VIII.3, Radiological Methods, Unter den Eichen 87, 12205 Berlin (Germany); Buecherl, T.; Lierse von Gostomski, Ch. [Technische Universitaet Muenchen, Lehrstuhl fuer Radiochemie, Walther-Meissner-Str. 3, 85748 Garching (Germany); Zscherpel, U.; Ewert, U. [Federal Institute for Materials Research and Testing (BAM), Division VIII.3, Radiological Methods, Unter den Eichen 87, 12205 Berlin (Germany); Bock, S. [Technische Universitaet Muenchen, Lehrstuhl fuer Radiochemie, Walther-Meissner-Str. 3, 85748 Garching (Germany)
2011-09-21
An algorithm has been developed to remove reliably dotted interferences impairing the perceptibility of objects within a radiographic image. This particularly is a major challenge encountered with neutron radiographs collected at the NECTAR facility, Forschungs-Neutronenquelle Heinz Maier-Leibnitz (FRM II): the resulting images are dominated by features resembling a snow flurry. These artefacts are caused by scattered neutrons, gamma radiation, cosmic radiation, etc. all hitting the detector CCD directly in spite of a sophisticated shielding. This makes such images rather useless for further direct evaluations. One approach to resolve this problem of these random effects would be to collect a vast number of single images, to combine them appropriately and to process them with common image filtering procedures. However, it has been shown that, e.g. median filtering, depending on the kernel size in the plane and/or the number of single shots to be combined, is either insufficient or tends to blur sharp lined structures. This inevitably makes a visually controlled processing image by image unavoidable. Particularly in tomographic studies, it would be by far too tedious to treat each single projection by this way. Alternatively, it would be not only more comfortable but also in many cases the only reasonable approach to filter a stack of images in a batch procedure to get rid of the disturbing interferences. The algorithm presented here meets all these requirements. It reliably frees the images from the snowy pattern described above without the loss of fine structures and without a general blurring of the image. It consists of an iterative, within a batch procedure parameter free filtering algorithm aiming to eliminate the often complex interfering artefacts while leaving the original information untouched as far as possible.
Algorithms versus architectures for computational chemistry
Partridge, H.; Bauschlicher, C. W., Jr.
1986-01-01
The algorithms employed are computationally intensive and, as a result, increased performance (both algorithmic and architectural) is required to improve accuracy and to treat larger molecular systems. Several benchmark quantum chemistry codes are examined on a variety of architectures. While these codes are only a small portion of a typical quantum chemistry library, they illustrate many of the computationally intensive kernels and data manipulation requirements of some applications. Furthermore, understanding the performance of the existing algorithm on present and proposed supercomputers serves as a guide for future programs and algorithm development. The algorithms investigated are: (1) a sparse symmetric matrix vector product; (2) a four index integral transformation; and (3) the calculation of diatomic two electron Slater integrals. The vectorization strategies are examined for these algorithms for both the Cyber 205 and Cray XMP. In addition, multiprocessor implementations of the algorithms are looked at on the Cray XMP and on the MIT static data flow machine proposed by DENNIS.
Modified nearest neighbor phase unwrapping algorithm
Institute of Scientific and Technical Information of China (English)
CHEN Jia-feng; CHEN Hai-qing; YANG Zhen-gang
2006-01-01
Phase unwrapping is so important in interferometry that it determines the veracity of the absolute phase value.Goldstein's branch-cut algorithm performs path-independent algorithm that uses a nearest neighbor heuristic to link and balance the residues based on identifying the residues.A modified nearest neighbor algorithm is presented based on the principle,the mathematic formula of the Goldstein's algorithm and in-depth analysis of the key problem of phase unwrapping.It not only holds the advantage of the Goldstein's algorithm but also solves the problem that the Goldstein's algorithm is incapable to be used at high residue densities.Therefore,it extends the application of the Goldstein's algorithm and enhances the precision of phase unwrapping.
OPTIMISED RANDOM MUTATIONS FOR EVOLUTIONARY ALGORITHMS
Directory of Open Access Journals (Sweden)
Sean McGerty
2014-07-01
Full Text Available To demonstrate our approaches we will use Sudoku puzzles, which are an excellent test bed for evolutionary algorithms. The puzzles are accessible enough for people to enjoy. However the more complex puzzles require thousands of iterations before an evolutionary algorithm finds a solution. If we were attempting to compare evolutionary algorithms we could count their iterations to solution as an indicator of relative efficiency. Evolutionary algorithms however include a process of random mutation for solution candidates. We will show that by improving the random mutation behaviours we were able to solve problems with minimal evolutionary optimisation. Experiments demonstrated the random mutation was at times more effective at solving the harder problems than the evolutionary algorithms. This implies that the quality of random mutation may have a significant impact on the performance of evolutionary algorithms with Sudoku puzzles. Additionally this random mutation may hold promise for reuse in hybrid evolutionary algorithm behaviours.
Comparison of fast discrete wavelet transform algorithms
Institute of Scientific and Technical Information of China (English)
MENG Shu-ping; TIAN Feng-chun; XU Xin
2005-01-01
This paper presents an analysis on and experimental comparison of several typical fast algorithms for discrete wavelet transform (DWT) and their implementation in image compression, particularly the Mallat algorithm, FFT-based algorithm, Short-length based algorithm and Lifting algorithm. The principles, structures and computational complexity of these algorithms are explored in details respectively. The results of the experiments for comparison are consistent to those simulated by MATLAB. It is found that there are limitations in the implementation of DWT. Some algorithms are workable only for special wavelet transform, lacking in generality. Above all, the speed of wavelet transform, as the governing element to the speed of image processing, is in fact the retarding factor for real-time image processing.
Role of Ranking Algorithms for Information Retrieval
Directory of Open Access Journals (Sweden)
Laxmi Choudhary
2012-07-01
Full Text Available As the use of web is increasing more day by day, the web users get easily lost in the web’s rich hyper structure. The main aim of the owner of the website is to give the relevant information according their needs to the users. We explained the Web mining is used to categorize users and pages by analyzing user’s behavior, the content of pages and then describe Web Structure mining. This paper includes different Page Ranking algorithms and compares those algorithms used for Information Retrieval. Different Page Rank based algorithms like Page Rank (PR, WPR (Weighted Page Rank, HITS (Hyperlink Induced Topic Selection, Distance Rank and EigenRumor algorithms are discussed and compared. Simulation Interface has been designed for PageRank algorithm and Weighted PageRank algorithm but PageRank is the only ranking algorithm on which Google search engine works.
Asynchronous Parallel Evolutionary Algorithms for Constrained Optimizations
Institute of Scientific and Technical Information of China (English)
无
2000-01-01
Recently Guo Tao proposed a stochastic search algorithm in his PhD thesis for solving function op-timization problems. He combined the subspace search method (a general multi-parent recombination strategy) with the population hill-climbing method. The former keeps a global search for overall situation,and the latter keeps the convergence of the algorithm. Guo's algorithm has many advantages ,such as the sim-plicity of its structure ,the higher accuracy of its results, the wide range of its applications ,and the robustness of its use. In this paper a preliminary theoretical analysis of the algorithm is given and some numerical experiments has been done by using Guo's algorithm for demonstrating the theoretical results. Three asynchronous paral-lel evolutionary algorithms with different granularities for MIMD machines are designed by parallelizing Guo's Algorithm.
Design and Implementation of Bidirectional Dijkstra Algorithm
Institute of Scientific and Technical Information of China (English)
付梦印; 李杰; 周培德
2003-01-01
Bidirectional Dijkstra algorithm whose time complexity is (1)/(8)O(n2) is proposed. The theory foundation is that the classical Dijkstra algorithm has not any directional feature during searching the shortest path. The algorithm takes advantage of the adjacent link and the mechanism of bidirectional search, that is, the algorithm processes the positive search from start point to destination point and the negative search from destination point to start point at the same time. Finally, combining with the practical application of route-planning algorithm in embedded real-time vehicle navigation system (ERTVNS), one example of its practical applications is given, analysis in theory and the experimental results show that compared with the Dijkstra algorithm, the new algorithm can reduce time complexity, and guarantee the searching precision, it satisfies the needs of ERTVNS.
A Robust Parsing Algorithm For Link Grammars
Grinberg, D; Sleator, D; Grinberg, Dennis; Lafferty, John; Sleator, Daniel
1995-01-01
In this paper we present a robust parsing algorithm based on the link grammar formalism for parsing natural languages. Our algorithm is a natural extension of the original dynamic programming recognition algorithm which recursively counts the number of linkages between two words in the input sentence. The modified algorithm uses the notion of a null link in order to allow a connection between any pair of adjacent words, regardless of their dictionary definitions. The algorithm proceeds by making three dynamic programming passes. In the first pass, the input is parsed using the original algorithm which enforces the constraints on links to ensure grammaticality. In the second pass, the total cost of each substring of words is computed, where cost is determined by the number of null links necessary to parse the substring. The final pass counts the total number of parses with minimal cost. All of the original pruning techniques have natural counterparts in the robust algorithm. When used together with memoization...
Decryption of pure-position permutation algorithms
Institute of Scientific and Technical Information of China (English)
赵晓宇; 陈刚; 张亶; 王肖虹; 董光昌
2004-01-01
Pure position permutation image encryption algorithms,commonly used as image encryption investigated in this work are unfortunately frail under known-text attack.In view of the weakness of pure position permutation algorithm,we put forward an effective decryption algorithm for all pure-position permutation algorithms.First,a summary of the pure position permutation image encryption algorithms is given by introducing the concept of ergodic matrices.Then,by using probability theory and algebraic principles,the decryption probability of pure-position permutation algorithms is verified theoretically; and then,by defining the operation system of fuzzy ergodic matrices,we improve a specific decryption algorithm.Finally,some simulation results are shown.
Smell Detection Agent Based Optimization Algorithm
Vinod Chandra S. S.
2016-09-01
In this paper, a novel nature-inspired optimization algorithm has been employed and the trained behaviour of dogs in detecting smell trails is adapted into computational agents for problem solving. The algorithm involves creation of a surface with smell trails and subsequent iteration of the agents in resolving a path. This algorithm can be applied in different computational constraints that incorporate path-based problems. Implementation of the algorithm can be treated as a shortest path problem for a variety of datasets. The simulated agents have been used to evolve the shortest path between two nodes in a graph. This algorithm is useful to solve NP-hard problems that are related to path discovery. This algorithm is also useful to solve many practical optimization problems. The extensive derivation of the algorithm can be enabled to solve shortest path problems.
Formal verification of a deadlock detection algorithm
Directory of Open Access Journals (Sweden)
Freek Verbeek
2011-10-01
Full Text Available Deadlock detection is a challenging issue in the analysis and design of on-chip networks. We have designed an algorithm to detect deadlocks automatically in on-chip networks with wormhole switching. The algorithm has been specified and proven correct in ACL2. To enable a top-down proof methodology, some parts of the algorithm have been left unimplemented. For these parts, the ACL2 specification contains constrained functions introduced with defun-sk. We used single-threaded objects to represent the data structures used by the algorithm. In this paper, we present details on the proof of correctness of the algorithm. The process of formal verification was crucial to get the algorithm flawless. Our ultimate objective is to have an efficient executable, and formally proven correct implementation of the algorithm running in ACL2.
Formal verification of a deadlock detection algorithm
Verbeek, Freek; 10.4204/EPTCS.70.8
2011-01-01
Deadlock detection is a challenging issue in the analysis and design of on-chip networks. We have designed an algorithm to detect deadlocks automatically in on-chip networks with wormhole switching. The algorithm has been specified and proven correct in ACL2. To enable a top-down proof methodology, some parts of the algorithm have been left unimplemented. For these parts, the ACL2 specification contains constrained functions introduced with defun-sk. We used single-threaded objects to represent the data structures used by the algorithm. In this paper, we present details on the proof of correctness of the algorithm. The process of formal verification was crucial to get the algorithm flawless. Our ultimate objective is to have an efficient executable, and formally proven correct implementation of the algorithm running in ACL2.
Kernel method-based fuzzy clustering algorithm
Institute of Scientific and Technical Information of China (English)
Wu Zhongdong; Gao Xinbo; Xie Weixin; Yu Jianping
2005-01-01
The fuzzy C-means clustering algorithm(FCM) to the fuzzy kernel C-means clustering algorithm(FKCM) to effectively perform cluster analysis on the diversiform structures are extended, such as non-hyperspherical data, data with noise, data with mixture of heterogeneous cluster prototypes, asymmetric data, etc. Based on the Mercer kernel, FKCM clustering algorithm is derived from FCM algorithm united with kernel method. The results of experiments with the synthetic and real data show that the FKCM clustering algorithm is universality and can effectively unsupervised analyze datasets with variform structures in contrast to FCM algorithm. It is can be imagined that kernel-based clustering algorithm is one of important research direction of fuzzy clustering analysis.
Microgenetic optimization algorithm for optimal wavefront shaping
Anderson, Benjamin R; Gunawidjaja, Ray; Eilers, Hergen
2015-01-01
One of the main limitations of utilizing optimal wavefront shaping in imaging and authentication applications is the slow speed of the optimization algorithms currently being used. To address this problem we develop a micro-genetic optimization algorithm ($\\mu$GA) for optimal wavefront shaping. We test the abilities of the $\\mu$GA and make comparisons to previous algorithms (iterative and simple-genetic) by using each algorithm to optimize transmission through an opaque medium. From our experiments we find that the $\\mu$GA is faster than both the iterative and simple-genetic algorithms and that both genetic algorithms are more resistant to noise and sample decoherence than the iterative algorithm.
Quantum Algorithm for the Toeplitz Systems
Wan, Lin-Chun; Pan, Shi-Jie; Gao, Fei; Wen, Qiao-Yan
2016-01-01
Solving the Toeplitz systems, which is to find the vector $x$ such that $T_nx = b$ given a $n\\times n$ Toeplitz matrix $T_n$ and a vector $b$, has a variety of applications in mathematics and engineering. In this paper, we present a quantum algorithm for solving the Toeplitz systems, in which a quantum state encoding the solution with error $\\epsilon$ is generated. It is shown that our algorithm's complexity is nearly linear in the condition number, and polylog in the dimensions $n$ and in the inverse error $\\epsilon^{-1}$. This implies our algorithm is exponentially faster than the best classical algorithm for the same problem if the condition number of $T_n$ is $O(\\textrm{poly}(\\textrm{log}\\,n))$. Since no assumption on the sparseness of $T_n$ is demanded in our algorithm, the algorithm can serve as an example of quantum algorithms for solving non-sparse linear systems.
Algorithms for Next Generation Networks
Cormode, Graham
2010-01-01
Data networking now plays a major role in everyday life and new applications continue to appear at a blinding pace. Yet we still do not have a sound foundation for designing, evaluating and managing these networks. This book covers topics at the intersection of algorithms and networking. It builds a complete picture of the current state of research on Next Generation Networks and the challenges for the years ahead. Particular focus is given to evolving research initiatives and the architecture they propose and implications for networking. Topics: Network design and provisioning, hardware issue
Computed laminography and reconstruction algorithm
Institute of Scientific and Technical Information of China (English)
QUE Jie-Min; YU Zhong-Qiang; YAN Yong-Lian; CAO Da-Quan; ZHAO Wei; TANG Xiao; SUN Cui-Li; WANG Yan-Fang; WEI Cun-Feng; SHI Rong-Jian; WEI Long
2012-01-01
Computed laminography (CL) is an alternative to computed tomography if large objects are to be inspected with high resolution.This is especially true for planar objects.In this paper,we set up a new scanning geometry for CL,and study the algebraic reconstruction technique (ART) for CL imaging.We compare the results of ART with variant weighted functions by computer simulation with a digital phantom.It proves that ART algorithm is a good choice for the CL system.
Algorithms for skiascopy measurement automatization
Fomins, Sergejs; Trukša, Renārs; KrūmiĆa, Gunta
2014-10-01
Automatic dynamic infrared retinoscope was developed, which allows to run procedure at a much higher rate. Our system uses a USB image sensor with up to 180 Hz refresh rate equipped with a long focus objective and 850 nm infrared light emitting diode as light source. Two servo motors driven by microprocessor control the rotation of semitransparent mirror and motion of retinoscope chassis. Image of eye pupil reflex is captured via software and analyzed along the horizontal plane. Algorithm for automatic accommodative state analysis is developed based on the intensity changes of the fundus reflex.
ALFA: Automated Line Fitting Algorithm
Wesson, R.
2015-12-01
ALFA fits emission line spectra of arbitrary wavelength coverage and resolution, fully automatically. It uses a catalog of lines which may be present to construct synthetic spectra, the parameters of which are then optimized by means of a genetic algorithm. Uncertainties are estimated using the noise structure of the residuals. An emission line spectrum containing several hundred lines can be fitted in a few seconds using a single processor of a typical contemporary desktop or laptop PC. Data cubes in FITS format can be analysed using multiple processors, and an analysis of tens of thousands of deep spectra obtained with instruments such as MUSE will take a few hours.
Data clustering algorithms and applications
Aggarwal, Charu C
2013-01-01
Research on the problem of clustering tends to be fragmented across the pattern recognition, database, data mining, and machine learning communities. Addressing this problem in a unified way, Data Clustering: Algorithms and Applications provides complete coverage of the entire area of clustering, from basic methods to more refined and complex data clustering approaches. It pays special attention to recent issues in graphs, social networks, and other domains.The book focuses on three primary aspects of data clustering: Methods, describing key techniques commonly used for clustering, such as fea
Algorithms for optimizing drug therapy
Directory of Open Access Journals (Sweden)
Martin Lene
2004-07-01
Full Text Available Abstract Background Drug therapy has become increasingly efficient, with more drugs available for treatment of an ever-growing number of conditions. Yet, drug use is reported to be sub optimal in several aspects, such as dosage, patient's adherence and outcome of therapy. The aim of the current study was to investigate the possibility to optimize drug therapy using computer programs, available on the Internet. Methods One hundred and ten officially endorsed text documents, published between 1996 and 2004, containing guidelines for drug therapy in 246 disorders, were analyzed with regard to information about patient-, disease- and drug-related factors and relationships between these factors. This information was used to construct algorithms for identifying optimum treatment in each of the studied disorders. These algorithms were categorized in order to define as few models as possible that still could accommodate the identified factors and the relationships between them. The resulting program prototypes were implemented in HTML (user interface and JavaScript (program logic. Results Three types of algorithms were sufficient for the intended purpose. The simplest type is a list of factors, each of which implies that the particular patient should or should not receive treatment. This is adequate in situations where only one treatment exists. The second type, a more elaborate model, is required when treatment can by provided using drugs from different pharmacological classes and the selection of drug class is dependent on patient characteristics. An easily implemented set of if-then statements was able to manage the identified information in such instances. The third type was needed in the few situations where the selection and dosage of drugs were depending on the degree to which one or more patient-specific factors were present. In these cases the implementation of an established decision model based on fuzzy sets was required. Computer programs
Data streams algorithms and applications
Muthukrishnan, S
2014-01-01
Data stream algorithms as an active research agenda emerged only over the past few years, even though the concept of making few passes over the data for performing computations has been around since the early days of Automata Theory. The data stream agenda now pervades many branches of Computer Science including databases, networking, knowledge discovery and data mining, and hardware systems. Industry is in synch too, with Data Stream Management Systems (DSMSs) and special hardware to deal with data speeds. Even beyond Computer Science, data stream concerns are emerging in physics, atmospheric
Complex fluids modeling and algorithms
Saramito, Pierre
2016-01-01
This book presents a comprehensive overview of the modeling of complex fluids, including many common substances, such as toothpaste, hair gel, mayonnaise, liquid foam, cement and blood, which cannot be described by Navier-Stokes equations. It also offers an up-to-date mathematical and numerical analysis of the corresponding equations, as well as several practical numerical algorithms and software solutions for the approximation of the solutions. It discusses industrial (molten plastics, forming process), geophysical (mud flows, volcanic lava, glaciers and snow avalanches), and biological (blood flows, tissues) modeling applications. This book is a valuable resource for undergraduate students and researchers in applied mathematics, mechanical engineering and physics.
Elementary algorithms from advanced mechanics
Chin, Siu A
2016-01-01
Most elementary numerical schemes found useful for solving classical trajectory problems are {\\it canonical transformations}. This fact should be make more widely known among teachers of computational physics and Hamiltonian mechanics. It is very surprising that in order to solve a simple second-order differential equation, one has to invoke the deepest part, the Poissonian formulation, of classical mechanics. From the perspective of advanced mechanics, there are no bewildering number of seemingly arbitrary elementary schemes based on Taylor's expansion. There are only {\\it two} canonical second-order algorithms, on the basis of which one can build numerical schemes of any order.
Direct Model Checking Matrix Algorithm
Institute of Scientific and Technical Information of China (English)
Zhi-Hong Tao; Hans Kleine Büning; Li-Fu Wang
2006-01-01
During the last decade, Model Checking has proven its efficacy and power in circuit design, network protocol analysis and bug hunting. Recent research on automatic verification has shown that no single model-checking technique has the edge over all others in all application areas. So, it is very difficult to determine which technique is the most suitable for a given model. It is thus sensible to apply different techniques to the same model. However, this is a very tedious and time-consuming task, for each algorithm uses its own description language. Applying Model Checking in software design and verification has been proved very difficult. Software architectures (SA) are engineering artifacts that provide high-level and abstract descriptions of complex software systems. In this paper a Direct Model Checking (DMC) method based on Kripke Structure and Matrix Algorithm is provided. Combined and integrated with domain specific software architecture description languages (ADLs), DMC can be used for computing consistency and other critical properties.
Ligand Identification Scoring Algorithm (LISA)
Zheng, Zheng; Merz, Kenneth M.
2011-01-01
A central problem in de novo drug design is determining the binding affinity of a ligand with a receptor. A new scoring algorithm is presented that estimates the binding affinity of a protein-ligand complex given a three-dimensional structure. The method, LISA (Ligand Identification Scoring Algorithm), uses an empirical scoring function to describe the binding free energy. Interaction terms have been designed to account for van der Waals (VDW) contacts, hydrogen bonding, desolvation effects and metal chelation to model the dissociation equilibrium constants using a linear model. Atom types have been introduced to differentiate the parameters for VDW, H-bonding interactions and metal chelation between different atom pairs. A training set of 492 protein-ligand complexes was selected for the fitting process. Different test sets have been examined to evaluate its ability to predict experimentally measured binding affinities. By comparing with other well known scoring functions, the results show that LISA has advantages over many existing scoring functions in simulating protein-ligand binding affinity, especially metalloprotein-ligand binding affinity. Artificial Neural Network (ANN) was also used in order to demonstrate that the energy terms in LISA are well designed and do not require extra cross terms. PMID:21561101
The GRAPE aerosol retrieval algorithm
Directory of Open Access Journals (Sweden)
G. E. Thomas
2009-11-01
Full Text Available The aerosol component of the Oxford-Rutherford Aerosol and Cloud (ORAC combined cloud and aerosol retrieval scheme is described and the theoretical performance of the algorithm is analysed. ORAC is an optimal estimation retrieval scheme for deriving cloud and aerosol properties from measurements made by imaging satellite radiometers and, when applied to cloud free radiances, provides estimates of aerosol optical depth at a wavelength of 550 nm, aerosol effective radius and surface reflectance at 550 nm. The aerosol retrieval component of ORAC has several incarnations – this paper addresses the version which operates in conjunction with the cloud retrieval component of ORAC (described by Watts et al., 1998, as applied in producing the Global Retrieval of ATSR Cloud Parameters and Evaluation (GRAPE data-set.
The algorithm is described in detail and its performance examined. This includes a discussion of errors resulting from the formulation of the forward model, sensitivity of the retrieval to the measurements and a priori constraints, and errors resulting from assumptions made about the atmospheric/surface state.
Region processing algorithm for HSTAMIDS
Ngan, Peter; Burke, Sean; Cresci, Roger; Wilson, Joseph N.; Gader, Paul; Ho, Dominic K. C.
2006-05-01
The AN/PSS-14 (a.k.a. HSTAMIDS) has been tested for its performance in South East Asia, Thailand), South Africa (Namibia) and in November of 2005 in South West Asia (Afghanistan). The system has been proven effective in manual demining particularly in discriminating indigenous, metallic artifacts in the minefields. The Humanitarian Demining Research and Development (HD R&D) Program has sought to further improve the system to address specific needs in several areas. One particular area of these improvement efforts is the development of a mine detection/discrimination improvement software algorithm called Region Processing (RP). RP is an innovative technique in processing and is designed to work on a set of data acquired in a unique sweep pattern over a region-of-interest (ROI). The RP team is a joint effort consisting of three universities (University of Florida, University of Missouri, and Duke University), but is currently being led by the University of Florida. This paper describes the state-of-the-art Region Processing algorithm, its implementation into the current HSTAMIDS system, and its most recent test results.
Digital Shaping Algorithms for GODDESS
Lonsdale, Sarah-Jane; Cizewski, Jolie; Ratkiewicz, Andrew; Pain, Steven
2014-09-01
Gammasphere-ORRUBA: Dual Detectors for Experimental Structure Studies (GODDESS) combines the highly segmented position-sensitive silicon strip detectors of ORRUBA with up to 110 Compton-suppressed HPGe detectors from Gammasphere, for high resolution for particle-gamma coincidence measurements. The signals from the silicon strip detectors have position-dependent rise times, and require different forms of pulse shaping for optimal position and energy resolutions. Traditionally, a compromise was achieved with a single shaping of the signals performed by conventional analog electronics. However, there are benefits to using digital acquisition of the detector signals, including the ability to apply multiple custom shaping algorithms to the same signal, each optimized for position and energy, in addition to providing a flexible triggering system, and a reduction in rate-limitation due to pile-up. Recent developments toward creating digital signal processing algorithms for GODDESS will be discussed. This work is supported in part by the U.S. D.O.E. and N.S.F.
Effects of visualization on algorithm comprehension
Mulvey, Matthew
Computer science students are expected to learn and apply a variety of core algorithms which are an essential part of the field. Any one of these algorithms by itself is not necessarily extremely complex, but remembering the large variety of algorithms and the differences between them is challenging. To address this challenge, we present a novel algorithm visualization tool designed to enhance students understanding of Dijkstra's algorithm by allowing them to discover the rules of the algorithm for themselves. It is hoped that a deeper understanding of the algorithm will help students correctly select, adapt and apply the appropriate algorithm when presented with a problem to solve, and that what is learned here will be applicable to the design of other visualization tools designed to teach different algorithms. Our visualization tool is currently in the prototype stage, and this thesis will discuss the pedagogical approach that informs its design, as well as the results of some initial usability testing. Finally, to clarify the direction for further development of the tool, four different variations of the prototype were implemented, and the instructional effectiveness of each was assessed by having a small sample participants use the different versions of the prototype and then take a quiz to assess their comprehension of the algorithm.
A GREEDY GENETIC ALGORITHM FOR UNCONSTRAINED GLOBAL OPTIMIZATION
Institute of Scientific and Technical Information of China (English)
ZHAO Xinchao
2005-01-01
The greedy algorithm is a strong local searching algorithm. The genetica lgorithm is generally applied to the global optimization problems. In this paper, we combine the greedy idea and the genetic algorithm to propose the greedy genetic algorithm which incorporates the global exploring ability of the genetic algorithm and the local convergent ability of the greedy algorithm. Experimental results show that greedy genetic algorithm gives much better results than the classical genetic algorithm.
A Quantum Algorithm for Finding a Hamilton Circuit
Institute of Scientific and Technical Information of China (English)
GUO Hao; LONG Gui-Lu; SUN Yang; XIU Xiao-Lin
2001-01-01
A quantum algorithm for solving the classical NP-complete problem - the Hamilton circuit is presented. The algorithm employs the quantum SAT and the quantum search algorithms. The algorithm is square-root faster than classical algorithm, and becomes exponentially faster than classical algorithm if nonlinear quantum mechanical computer is used.
Adaptive link selection algorithms for distributed estimation
Xu, Songcen; de Lamare, Rodrigo C.; Poor, H. Vincent
2015-12-01
This paper presents adaptive link selection algorithms for distributed estimation and considers their application to wireless sensor networks and smart grids. In particular, exhaustive search-based least mean squares (LMS) / recursive least squares (RLS) link selection algorithms and sparsity-inspired LMS / RLS link selection algorithms that can exploit the topology of networks with poor-quality links are considered. The proposed link selection algorithms are then analyzed in terms of their stability, steady-state, and tracking performance and computational complexity. In comparison with the existing centralized or distributed estimation strategies, the key features of the proposed algorithms are as follows: (1) more accurate estimates and faster convergence speed can be obtained and (2) the network is equipped with the ability of link selection that can circumvent link failures and improve the estimation performance. The performance of the proposed algorithms for distributed estimation is illustrated via simulations in applications of wireless sensor networks and smart grids.
Orbital objects detection algorithm using faint streaks
Tagawa, Makoto; Yanagisawa, Toshifumi; Kurosaki, Hirohisa; Oda, Hiroshi; Hanada, Toshiya
2016-02-01
This study proposes an algorithm to detect orbital objects that are small or moving at high apparent velocities from optical images by utilizing their faint streaks. In the conventional object-detection algorithm, a high signal-to-noise-ratio (e.g., 3 or more) is required, whereas in our proposed algorithm, the signals are summed along the streak direction to improve object-detection sensitivity. Lower signal-to-noise ratio objects were detected by applying the algorithm to a time series of images. The algorithm comprises the following steps: (1) image skewing, (2) image compression along the vertical axis, (3) detection and determination of streak position, (4) searching for object candidates using the time-series streak-position data, and (5) selecting the candidate with the best linearity and reliability. Our algorithm's ability to detect streaks with signals weaker than the background noise was confirmed using images from the Australia Remote Observatory.
Genetic algorithms and fuzzy multiobjective optimization
Sakawa, Masatoshi
2002-01-01
Since the introduction of genetic algorithms in the 1970s, an enormous number of articles together with several significant monographs and books have been published on this methodology. As a result, genetic algorithms have made a major contribution to optimization, adaptation, and learning in a wide variety of unexpected fields. Over the years, many excellent books in genetic algorithm optimization have been published; however, they focus mainly on single-objective discrete or other hard optimization problems under certainty. There appears to be no book that is designed to present genetic algorithms for solving not only single-objective but also fuzzy and multiobjective optimization problems in a unified way. Genetic Algorithms And Fuzzy Multiobjective Optimization introduces the latest advances in the field of genetic algorithm optimization for 0-1 programming, integer programming, nonconvex programming, and job-shop scheduling problems under multiobjectiveness and fuzziness. In addition, the book treats a w...
State transition algorithm for traveling salesman problem
Chunhua, Yang; Xiaojun, Zhou; Weihua, Gui
2012-01-01
Discrete version of state transition algorithm is proposed in order to solve the traveling salesman problem. Three special operators for discrete optimization problem named swap, shift and symmetry transformations are presented. Convergence analysis and time complexity of the algorithm are also considered. To make the algorithm simple and efficient, no parameter adjusting is suggested in current version. Experiments are carried out to test the performance of the strategy, and comparisons with simulated annealing and ant colony optimization have demonstrated the effectiveness of the proposed algorithm. The results also show that the discrete state transition algorithm consumes much less time and has better search ability than its counterparts, which indicates that state transition algorithm is with strong adaptability.
An adaptively spatial color gamut mapping algorithm
Institute of Scientific and Technical Information of China (English)
Xiandou Zhang; Haisong Xu
2009-01-01
To improve the accuracy of color image reproduction from displays to printers,an adaptively spatial color gamut mapping algorithm(ASCGMA)is proposed.In this algorithm,the compression degree of outof-reproduction-gamut color is not only related to the position of the color in CIELCH color space,but also depending on the neighborhood of the color to be mapped.The psychophysical experiment of pair comparison ks carried out to evaluate and compare this new algorithm with the HPMINDE and SGCK gamut mapping algorithms recommended by the International Commission on Illumination(CIE).The experimental results indicate that the proposed algorithm outperforms the algorithms of HPMINDE and SGCK except for the very dark images.
Algorithms for worst-case tolerance optimization
DEFF Research Database (Denmark)
Schjær-Jacobsen, Hans; Madsen, Kaj
1979-01-01
New algorithms are presented for the solution of optimum tolerance assignment problems. The problems considered are defined mathematically as a worst-case problem (WCP), a fixed tolerance problem (FTP), and a variable tolerance problem (VTP). The basic optimization problem without tolerances...... is denoted the zero tolerance problem (ZTP). For solution of the WCP we suggest application of interval arithmetic and also alternative methods. For solution of the FTP an algorithm is suggested which is conceptually similar to algorithms previously developed by the authors for the ZTP. Finally, the VTP...... is solved by a double-iterative algorithm in which the inner iteration is performed by the FTP- algorithm. The application of the algorithm is demonstrated by means of relatively simple numerical examples. Basic properties, such as convergence properties, are displayed based on the examples....
Cache-Oblivious Algorithms and Data Structures
DEFF Research Database (Denmark)
Brodal, Gerth Stølting
2004-01-01
Frigo, Leiserson, Prokop and Ramachandran in 1999 introduced the ideal-cache model as a formal model of computation for developing algorithms in environments with multiple levels of caching, and coined the terminology of cache-oblivious algorithms. Cache-oblivious algorithms are described...... as standard RAM algorithms with only one memory level, i.e. without any knowledge about memory hierarchies, but are analyzed in the two-level I/O model of Aggarwal and Vitter for an arbitrary memory and block size and an optimal off-line cache replacement strategy. The result are algorithms that automatically...... apply to multi-level memory hierarchies. This paper gives an overview of the results achieved on cache-oblivious algorithms and data structures since the seminal paper by Frigo et al....
A novel algorithm for satellite data transmission
Institute of Scientific and Technical Information of China (English)
无
2009-01-01
For remote sensing satellite data transmission,a novel algorithm is proposed in this paper.It integrates different type feature descriptors into multistage recognizers.In the first level,the dynamic clustering algorithm is used.In the second level,the improved support vector machines algorithm demonstrates its validity.In the third level,the shape matrices similarity comparison algorithm shows its excellent performance.The single child recognizers are connected in series,but they are independent of each other.Objects which are not recognized correctly by the lower level recognizers are then put into the higher level recognizers.Experimental results show that the multistage recognition algorithm improves the accuracy greatly with higher level feature descriptors and higher level recognizers.The algorithm may offer a new methodology for high speed satellite data transmission.
Analog Module Placement Design Using Genetic Algorithm
Institute of Scientific and Technical Information of China (English)
无
2003-01-01
This paper presents a novel genetic algorithm for analog module placement based on ageneralization of the two-dimensional bin packing problem. The genetic encoding and operators assure that allproblem constraints are always satisfied. Thus the potential problems of adding penalty terms to the costfunction are eliminated so that the search configuration space is drastically decreased. The dedicated costfunction is based on the special requirements of analog integrated circuits. A fractional factorial experimentwas conducted using an orthogonal array to study the algorithm parameters. A meta GA was applied todetermine the optimal parameter values. The algorithm was tested with several local benchmark circuits. Theexperimental results show that the algorithm has better performance than the simulated annealing approachwith satisfactory results comparable to manual placement. This study demonstrates the effectiveness of thegenetic algorithm in the analog module placement problem. The algorithm has been successfully used in alayout synthesis tool.
HUMAN-SIMULATING VEHICLE STEERING CONTROL ALGORITHM
Institute of Scientific and Technical Information of China (English)
XU Youchun; LI Keqiang; CHANG Ming; CHEN Jun
2006-01-01
A new vehicle steering control algorithm is presented. Unlike the traditional methods do,the algorithm uses a sigmoid function to describe the principle of the human driver's steering strategy.Based on this function, a human simulating vehicle steering model, human-simulating steering control(HS) algorithm is designed. In order to improve the adaptability to different environments, a parameter adaptive adjustment algorithm is presented. This algorithm can online modify the value of the key parameters of the HS real time. HS controller is used on a vehicle equipped with computer vision system and computer controlled steering actuator system, the result from the automatic vehicle steering experiment shows that the HS algorithm gives good performance at different speed, even at the maximum speed of 172 km/h.
Multicast Routing Based on Hybrid Genetic Algorithm
Institute of Scientific and Technical Information of China (English)
CAO Yuan-da; CAI Gui
2005-01-01
A new multicast routing algorithm based on the hybrid genetic algorithm (HGA) is proposed. The coding pattern based on the number of routing paths is used. A fitness function that is computed easily and makes algorithm quickly convergent is proposed. A new approach that defines the HGA's parameters is provided. The simulation shows that the approach can increase largely the convergent ratio, and the fitting values of the parameters of this algorithm are different from that of the original algorithms. The optimal mutation probability of HGA equals 0.50 in HGA in the experiment, but that equals 0.07 in SGA. It has been concluded that the population size has a significant influence on the HGA's convergent ratio when it's mutation probability is bigger. The algorithm with a small population size has a high average convergent rate. The population size has little influence on HGA with the lower mutation probability.
EPS Confidentiality and Integrity mechanisms Algorithmic Approach
Orhanou, Ghizlane; Bentaleb, Youssef; Laassiri, Jalal
2011-01-01
The Long Term Evolution of UMTS is one of the latest steps in an advancing series of mobile telecommunications systems. Many articles have already been published on the LTE subject but these publications have viewed the subject from particular perspectives. In the present paper, a different approach has been taken. We are interested in the security features and the cryptographic algorithms used to ensure confidentiality and integrity of the transmitted data. A closer look is taken to the two EPS confidentiality and integrity algorithms based on the block cipher algorithm AES: the confidentiality algorithm EEA2 and the integrity algorithm EIA2. Furthermore, we focused on the implementation of both algorithms in C language in respect to the specifications requirements. We have tested our implementations according to the testsets given by the 3rd Generation Partnership Project (3GPP) implementation document. Some examples of the implementation tests are presented bellow.
An Algorithmic Framework for Multiobjective Optimization
Ganesan, T.; Elamvazuthi, I.; Shaari, Ku Zilati Ku; Vasant, P.
2013-01-01
Multiobjective (MO) optimization is an emerging field which is increasingly being encountered in many fields globally. Various metaheuristic techniques such as differential evolution (DE), genetic algorithm (GA), gravitational search algorithm (GSA), and particle swarm optimization (PSO) have been used in conjunction with scalarization techniques such as weighted sum approach and the normal-boundary intersection (NBI) method to solve MO problems. Nevertheless, many challenges still arise especially when dealing with problems with multiple objectives (especially in cases more than two). In addition, problems with extensive computational overhead emerge when dealing with hybrid algorithms. This paper discusses these issues by proposing an alternative framework that utilizes algorithmic concepts related to the problem structure for generating efficient and effective algorithms. This paper proposes a framework to generate new high-performance algorithms with minimal computational overhead for MO optimization. PMID:24470795
New algorithms for evaluating parametric surface
Institute of Scientific and Technical Information of China (English)
无
2001-01-01
Through generalization of mathematical model of surface lofting program in the CONSURF system, the definitions for two generalized Ball surfaces and their recursive algorithms are given. Furthermore, the conversion al gorithms from Bézier surface to these two generalized Ball surfaces are presented. On the basis of these algorithms, two more efficient algorithms for evaluating parametric surfaces are also derived. One uses generalized Ball forms directly for evaluating surface, and the other converts the given Bézier surface to a generalized Ball surface firstly, and then evalu ates the surface. Both theoretical analysis and example computations show that the two new algorithms are more efficient than the de Casteljau algorithm. Especially when Wang-Ball surface is used, the time complexity is reduced from cubic to quadratic of the degree of the surface. If these algorithms are applied to displaying, interactive rendering, designing, intersection-finding, offsetting and approximating for surfaces, considerable economic results can be achieved.
A Comparative Study of AGN Feedback Algorithms
Wurster, James
2013-01-01
Modelling AGN feedback in numerical simulations is both technically and theoretically challenging, with numerous approaches having been published in the literature. We present a study of five distinct approaches to modelling AGN feedback within gravitohydrodynamic simulations of major mergers of Milky Way-sized galaxies. To constrain differences to only be between AGN feedback models, all simulations start from the same initial conditions and use the same star formation algorithm. Most AGN feedback algorithms have five key aspects: black hole accretion rate, energy feedback rate and method, particle accretion algorithm, black hole advection algorithm, and black hole merger algorithm. All models follow different accretion histories, with accretion rates that differ by up to three orders of magnitude at any given time. We consider models with either thermal or kinetic feedback, with the associated energy deposited locally around the black hole. Each feedback algorithm modifies the gas properties near the black ...
Fast algorithm on string cross pattern matching
Institute of Scientific and Technical Information of China (English)
Liu Gongshen; Li Jianhua; Li Shenghong
2005-01-01
Given a set U which is consisted of strings defined on alphabet ∑ , string cross pattern matching is to find all the matches between every two strings in U. It is utilized in text processing like removing the duplication of strings.This paper presents a fast string cross pattern matching algorithm based on extracting high frequency strings. Compared with existing algorithms including single-pattern algorithms and multi-pattern matching algorithms, this algorithm is featured by both low time complexityand low space complexity. Because Chinese alphabet is large and the average length of Chinese words is much short, this algorithm is more suitable to process the text written by Chinese, especially when the size of ∑ is large and the number of strings is far more than the maximum length of strings of set U.
Detecting Danger: The Dendritic Cell Algorithm
Greensmith, Julie; Cayzer, Steve
2010-01-01
The Dendritic Cell Algorithm (DCA) is inspired by the function of the dendritic cells of the human immune system. In nature, dendritic cells are the intrusion detection agents of the human body, policing the tissue and organs for potential invaders in the form of pathogens. In this research, and abstract model of DC behaviour is developed and subsequently used to form an algorithm, the DCA. The abstraction process was facilitated through close collaboration with laboratory- based immunologists, who performed bespoke experiments, the results of which are used as an integral part of this algorithm. The DCA is a population based algorithm, with each agent in the system represented as an 'artificial DC'. Each DC has the ability to combine multiple data streams and can add context to data suspected as anomalous. In this chapter the abstraction process and details of the resultant algorithm are given. The algorithm is applied to numerous intrusion detection problems in computer security including the detection of p...
A novel algorithm for satellite data transmission
Institute of Scientific and Technical Information of China (English)
ZHANG ShouJuan; ZHOU Ouan
2009-01-01
For remote sensing satellite data transmission, a novel algorithm is proposed in this paper. It integrates different type feature descriptors into multistage recognizers. In the first level, the dynamic clustering algorithm is used. In the second level, the improved support vector machines algorithm demonstrates its validity. In the third level, the shape matrices similarity comparison algorithm shows its excellent performance. The single child recognizers are connected in series, but they are independent of each other. Objects which are not recognized correctly by the lower level recognizers are then put into the higher level recognizers. Experimental results show that the multistage recognition algorithm improves the accuracy greatly with higher level feature descriptors and higher level recognizers. The algorithm may offer a new methodology for high speed satellite data transmission.
Review on Sorting Algorithms A Comparative Study
Directory of Open Access Journals (Sweden)
Khalid Suleiman Al-Kharabsheh
2013-09-01
Full Text Available There are many popular problems in different practical fields of computer sciences, database applications, Networks and Artificial intelligence. One of these basic operations and problems is sorting algorithm; the sorting problem has attracted a great deal of research. A lot of sorting algorithms has been developed to enhance the performance in terms of computational complexity. there are several factors that must be taken in consideration; time complexity, stability, memory space. Information growth rapidly in our world leads to increase developing sort algorithms .a stable sorting algorithms maintain the relative order of records with equal keys This paper makes a comparison between the Grouping Comparison Sort (GCS and conventional algorithm such as Selection sort, Quick sort, Insertion sort , Merge sort and Bubble sort with respect execution time to show how this algorithm perform reduce execution time.
A Hybrid Algorithm for Satellite Data Transmission Schedule Based on Genetic Algorithm
Institute of Scientific and Technical Information of China (English)
LI Yun-feng; WU Xiao-yue
2008-01-01
A hybrid scheduling algorithm based on genetic algorithm is proposed in this paper for reconnaissance satellite data transmission. At first, based on description of satellite data transmission request, satellite data transmission task modal and satellite data transmission scheduling problem model are established. Secondly, the conflicts in scheduling are discussed. According to the meaning of possible conflict, the method to divide possible conflict task set is given. Thirdly, a hybrid algorithm which consists of genetic algorithm and heuristic information is presented. The heuristic information comes from two concepts, conflict degree and conflict number. Finally, an example shows the algorithm's feasibility and performance better than other traditional algorithms.
Genetic algorithm-based wide-band deterministic maximum likelihood direction finding algorithm
Institute of Scientific and Technical Information of China (English)
无
2005-01-01
The wide-band direction finding is one of hit and difficult task in array signal processing. This paper generalizes narrow-band deterministic maximum likelihood direction finding algorithm to the wideband case, and so constructions an object function, then utilizes genetic algorithm for nonlinear global optimization. Direction of arrival is estimated without preprocessing of array data and so the algorithm eliminates the effect of pre-estimate on the final estimation. The algorithm is applied on uniform linear array and extensive simulation results prove the efficacy of the algorithm. In the process of simulation, we obtain the relation between estimation error and parameters of genetic algorithm.
Hierarchical matrices algorithms and analysis
Hackbusch, Wolfgang
2015-01-01
This self-contained monograph presents matrix algorithms and their analysis. The new technique enables not only the solution of linear systems but also the approximation of matrix functions, e.g., the matrix exponential. Other applications include the solution of matrix equations, e.g., the Lyapunov or Riccati equation. The required mathematical background can be found in the appendix. The numerical treatment of fully populated large-scale matrices is usually rather costly. However, the technique of hierarchical matrices makes it possible to store matrices and to perform matrix operations approximately with almost linear cost and a controllable degree of approximation error. For important classes of matrices, the computational cost increases only logarithmically with the approximation error. The operations provided include the matrix inversion and LU decomposition. Since large-scale linear algebra problems are standard in scientific computing, the subject of hierarchical matrices is of interest to scientists ...
Algorithms for Comparing Pedigree Graphs
Kirkpatrick, Bonnie; Finucane, Hilary; Jiang, Haitao; Zhu, Binhai; Karp, Richard M
2010-01-01
Pedigree graphs, which represent family relationships, are often constructed by collecting data from genealogical records to determine which pairs of people are parent and child. This process is expensive, and small mistakes in data collection--for example, one missing parent-child relationship--can cause large differences in the pedigree graphs created. In this paper, we introduce a simple pedigree definition based on a different type of data which is potentially easier to collect. This alternative characterization of a pedigree that describes a pedigree as a list of the descendants of each individual, rather than a list of parent-child relationships. We then introduce an algorithm that generates the pedigree graph from this list of descendants. We also consider the problem of comparing two pedigree graphs, which could be useful to evaluate the differences between pedigrees constructed via different methods. Specifically, this could be useful to evaluate pedigree reconstruction methods. We define the edit di...
Energy functions for regularization algorithms
Delingette, H.; Hebert, M.; Ikeuchi, K.
1991-01-01
Regularization techniques are widely used for inverse problem solving in computer vision such as surface reconstruction, edge detection, or optical flow estimation. Energy functions used for regularization algorithms measure how smooth a curve or surface is, and to render acceptable solutions these energies must verify certain properties such as invariance with Euclidean transformations or invariance with parameterization. The notion of smoothness energy is extended here to the notion of a differential stabilizer, and it is shown that to void the systematic underestimation of undercurvature for planar curve fitting, it is necessary that circles be the curves of maximum smoothness. A set of stabilizers is proposed that meet this condition as well as invariance with rotation and parameterization.
Scheduling theory, algorithms, and systems
Pinedo, Michael L
2016-01-01
This new edition of the well-established text Scheduling: Theory, Algorithms, and Systems provides an up-to-date coverage of important theoretical models in the scheduling literature as well as important scheduling problems that appear in the real world. The accompanying website includes supplementary material in the form of slide-shows from industry as well as movies that show actual implementations of scheduling systems. The main structure of the book, as per previous editions, consists of three parts. The first part focuses on deterministic scheduling and the related combinatorial problems. The second part covers probabilistic scheduling models; in this part it is assumed that processing times and other problem data are random and not known in advance. The third part deals with scheduling in practice; it covers heuristics that are popular with practitioners and discusses system design and implementation issues. All three parts of this new edition have been revamped, streamlined, and extended. The reference...
RED Algorithm based Iris Recognition
Directory of Open Access Journals (Sweden)
Mayuri M. Memane
2012-07-01
Full Text Available Human iris is one of the most reliable biometric because of its uniqueness, stability and non-invasive nature. Biometrics based human authentication systems are becoming more important as government & corporations worldwide deploy them in such schemes as access & border control, time & attendance record, driving license registration and national ID card schemes. For this various preprocessing steps are carried out on the iris image which also includes segmentation. Normalization deals with polar to rectangular conversion. The edges are detected using canny edge detector. Features are extracted using ridge energy direction algorithm. It uses two directional filters i.e. horizontal and vertical oriented. The final template is generated by comparing the two templates and considering the predominant edge. This final template is match with the stored one using hamming distance and the match ID is displayed.
Algorithmic synthesis using Python compiler
Cieszewski, Radoslaw; Romaniuk, Ryszard; Pozniak, Krzysztof; Linczuk, Maciej
2015-09-01
This paper presents a python to VHDL compiler. The compiler interprets an algorithmic description of a desired behavior written in Python and translate it to VHDL. FPGA combines many benefits of both software and ASIC implementations. Like software, the programmed circuit is flexible, and can be reconfigured over the lifetime of the system. FPGAs have the potential to achieve far greater performance than software as a result of bypassing the fetch-decode-execute operations of traditional processors, and possibly exploiting a greater level of parallelism. This can be achieved by using many computational resources at the same time. Creating parallel programs implemented in FPGAs in pure HDL is difficult and time consuming. Using higher level of abstraction and High-Level Synthesis compiler implementation time can be reduced. The compiler has been implemented using the Python language. This article describes design, implementation and results of created tools.
Stream Deniable-Encryption Algorithms
Directory of Open Access Journals (Sweden)
N.A. Moldovyan
2016-04-01
Full Text Available A method for stream deniable encryption of secret message is proposed, which is computationally indistinguishable from the probabilistic encryption of some fake message. The method uses generation of two key streams with some secure block cipher. One of the key streams is generated depending on the secret key and the other one is generated depending on the fake key. The key streams are mixed with the secret and fake data streams so that the output ciphertext looks like the ciphertext produced by some probabilistic encryption algorithm applied to the fake message, while using the fake key. When the receiver or/and sender of the ciphertext are coerced to open the encryption key and the source message, they open the fake key and the fake message. To disclose their lie the coercer should demonstrate possibility of the alternative decryption of the ciphertext, however this is a computationally hard problem.
Biomimetic use of genetic algorithms
Dessalles, Jean-Louis
2011-01-01
Genetic algorithms are considered as an original way to solve problems, probably because of their generality and of their "blind" nature. But GAs are also unusual since the features of many implementations (among all that could be thought of) are principally led by the biological metaphor, while efficiency measurements intervene only afterwards. We propose here to examine the relevance of these biomimetic aspects, by pointing out some fundamental similarities and divergences between GAs and the genome of living beings shaped by natural selection. One of the main differences comes from the fact that GAs rely principally on the so-called implicit parallelism, while giving to the mutation/selection mechanism the second role. Such differences could suggest new ways of employing GAs on complex problems, using complex codings and starting from nearly homogeneous populations.
Virtual Crystals and Kleber's Algorithm
Okado, Masato; Schilling, Anne; Shimozono, Mark
Kirillov and Reshetikhin conjectured what is now known as the fermionic formula for the decomposition of tensor products of certain finite dimensional modules over quantum affine algebras. This formula can also be extended to the case of q-deformations of tensor product multiplicities as recently conjectured by Hatayama et al. In its original formulation it is difficult to compute the fermionic formula efficiently. Kleber found an algorithm for the simply-laced algebras which overcomes this problem. We present a method which reduces all other cases to the simply-laced case using embeddings of affine algebras. This is the fermionic analogue of the virtual crystal construction by the authors, which is the realization of crystal graphs for arbitrary quantum affine algebras in terms of those of simply-laced type.
SLAP lesions: a treatment algorithm.
Brockmeyer, Matthias; Tompkins, Marc; Kohn, Dieter M; Lorbach, Olaf
2016-02-01
Tears of the superior labrum involving the biceps anchor are a common entity, especially in athletes, and may highly impair shoulder function. If conservative treatment fails, successful arthroscopic repair of symptomatic SLAP lesions has been described in the literature particularly for young athletes. However, the results in throwing athletes are less successful with a significant amount of patients who will not regain their pre-injury level of performance. The clinical results of SLAP repairs in middle-aged and older patients are mixed, with worse results and higher revision rates as compared to younger patients. In this population, tenotomy or tenodesis of the biceps tendon is a viable alternative to SLAP repairs in order to improve clinical outcomes. The present article introduces a treatment algorithm for SLAP lesions based upon the recent literature as well as the authors' clinical experience. The type of lesion, age of patient, concomitant lesions, and functional requirements, as well as sport activity level of the patient, need to be considered. Moreover, normal variations and degenerative changes in the SLAP complex have to be distinguished from "true" SLAP lesions in order to improve results and avoid overtreatment. The suggestion for a treatment algorithm includes: type I: conservative treatment or arthroscopic debridement, type II: SLAP repair or biceps tenotomy/tenodesis, type III: resection of the instable bucket-handle tear, type IV: SLAP repair (biceps tenotomy/tenodesis if >50 % of biceps tendon is affected), type V: Bankart repair and SLAP repair, type VI: resection of the flap and SLAP repair, and type VII: refixation of the anterosuperior labrum and SLAP repair.
A Cuckoo Search Algorithm for Multimodal Optimization
Erik Cuevas; Adolfo Reyna-Orta
2014-01-01
Interest in multimodal optimization is expanding rapidly, since many practical engineering problems demand the localization of multiple optima within a search space. On the other hand, the cuckoo search (CS) algorithm is a simple and effective global optimization algorithm which can not be directly applied to solve multimodal optimization problems. This paper proposes a new multimodal optimization algorithm called the multimodal cuckoo search (MCS). Under MCS, the original CS is enhanced with...
A NEW INEXACT SEQUENTIAL QUADRATIC PROGRAMMING ALGORITHM
Institute of Scientific and Technical Information of China (English)
倪勤
2002-01-01
This paper represents an inexact sequential quadratic programming (SQP ) algorithm which can solve nonlinear programming (NLP ) problems. An inexact solution of the quadratic programming subproblem is determined by a projection and contraction method such that only matrix-vector product is required. Some truncated criteria are chosen such that the algorithm is suitable to large scale NLP problem. The global convergence of the algorithm is proved.
Robustness of Tree Extraction Algorithms from LIDAR
Dumitru, M.; Strimbu, B. M.
2015-12-01
Forest inventory faces a new era as unmanned aerial systems (UAS) increased the precision of measurements, while reduced field effort and price of data acquisition. A large number of algorithms were developed to identify various forest attributes from UAS data. The objective of the present research is to assess the robustness of two types of tree identification algorithms when UAS data are combined with digital elevation models (DEM). The algorithms use as input photogrammetric point cloud, which are subsequent rasterized. The first type of algorithms associate tree crown with an inversed watershed (subsequently referred as watershed based), while the second type is based on simultaneous representation of tree crown as an individual entity, and its relation with neighboring crowns (subsequently referred as simultaneous representation). A DJI equipped with a SONY a5100 was used to acquire images over an area from center Louisiana. The images were processed with Pix4D, and a photogrammetric point cloud with 50 points / m2 was attained. DEM was obtained from a flight executed in 2013, which also supplied a LIDAR point cloud with 30 points/m2. The algorithms were tested on two plantations with different species and crown class complexities: one homogeneous (i.e., a mature loblolly pine plantation), and one heterogeneous (i.e., an unmanaged uneven-aged stand with mixed species pine -hardwoods). Tree identification on photogrammetric point cloud reveled that simultaneous representation algorithm outperforms watershed algorithm, irrespective stand complexity. Watershed algorithm exhibits robustness to parameters, but the results were worse than majority sets of parameters needed by the simultaneous representation algorithm. The simultaneous representation algorithm is a better alternative to watershed algorithm even when parameters are not accurately estimated. Similar results were obtained when the two algorithms were run on the LIDAR point cloud.
An Algorithmic Approach to Information and Meaning
Zenil, Hector
2011-01-01
I'll survey some of the aspects relevant to a philosophical discussion of information taking into account the developments of algorithmic information theory. I will propose that meaning is deep in Bennett's logical depth sense, and that algorithmic probability may provide the stability for a robust algorithmic definition of meaning, taking into consideration the interpretation and the receiver's own knowledge encoded in the story of a message.
Speech Segmentation Algorithm Based On Fuzzy Memberships
Luis D. Huerta; Jose Antonio Huesca; Julio C. Contreras
2010-01-01
In this work, an automatic speech segmentation algorithm with text independency was implemented. In the algorithm, the use of fuzzy memberships on each characteristic in different speech sub-bands is proposed. Thus, the segmentation is performed a greater detail. Additionally, we tested with various speech signal frequencies and labeling, and we could observe how they affect the performance of the segmentation process in phonemes. The speech segmentation algorithm used is described. During th...
GRID SCHEDULING USING ENHANCED ANT COLONY ALGORITHM
Mr. P.Mathiyalagan; U.R. Dhepthie; S.N. Sivanandam
2010-01-01
Grid computing is a high performance computing used to solve larger scale computational demands. Task scheduling is a major issue in grid computing systems. Scheduling of tasks is the NP hard problem. The heuristic approach provides optimal solution for NP hard problems .The ant colony algorithm provides optimal solution. The existing ant colony algorithm takes more time to schedule the tasks. In this paper ant colony algorithm improved by enhancing pheromone updating rule such that it schedu...
Hybrid evolutionary algorithms to solve scheduling problems
Minetti, Gabriela F.; Salto, Carolina; Bermúdez, Carlos; Fernandez, Natalia; Alfonso, Hugo; Gallard, Raúl Hector
2002-01-01
The choice of a search algorithm can play a vital role in the success of a scheduling application. Evolutionary algorithms (EAs) can be used to solve this kind of combinatorial optimization problems. Compared to conventional heuristics (CH) and local search techniques (LS), EAs are not well suited for fine-tuninf those structures, which are very close to optimal solutions. Therefore, in complex problems, it is essential to build hybrid evolutionary algorithms (HEA) by incorporating CH and/or ...
A New Fuzzy Adaptive Genetic Algorithm
Institute of Scientific and Technical Information of China (English)
FANG Lei; ZHANG Huan-chun; JING Ya-zhi
2005-01-01
Multiple genetic algorithms (GAs) need a large population size, which will take a long time for evolution.A new fuzzy adaptive GA is proposed in this paper. This algorithm is more effective in global search while keeping the overall population size constant. The simulation results of function optimization show that with the proposed algorithm, the phenomenon of premature convergence can be overcome effectively, and a satisfying optimization result is obtained.
Chaotic Rough Particle Swarm Optimization Algorithms
Alatas, Bilal; AKIN, ERHAN
2007-01-01
In this chapter chaotic rough PSO, CRPSO, algorithms that use rough decision variables and rough particles that are based on notion of rough patterns have been proposed. Different chaotic maps have been embedded to adapt the parameters of PSO algorithm. This has been done by using of chaotic number generators each time a random number is needed by the classical PSO algorithm. Twelve PSO methods have been proposed and four chaotic maps have been analyzed in the data mining application. It has ...
Adaptive Memory Coherence Algorithms in DSVM
Institute of Scientific and Technical Information of China (English)
周建强; 谢立; 等
1994-01-01
Based on the characteristics of distrubuted system and the behavior of parallel programs,this paper presents the fixed and randomized competitive memory coherence algorithms for distributed shared virtual memory.These algorithms exploit parallel programs' locality of reference and exhibit good competitive property.Our simulation shows that the fixed and randomized algorithms achieve better performance and higher stability than other strategies such as write-invalidate and write-update.
Monotonically convergent algorithms for bounded quantum controls
Turinici, Gabriel
2003-01-01
International audience Most of the numerical simulations in quantum (bilinear) control have used one of the monotonically convergent algorithms of Krotov (introduced by Tannor et al. (Tannor et al., 1992)) or of Zhu & Rabitz (Zhu and Rabitz, 1998). Recently(Maday and Turinici, 2002), new schemes have been designed that enlarge the class of monotonic algorithms. Within this context, this paper presents a new algorithm that implements a search for a bounded control with given bounds. Numeric...
Providing Statistical Algorithms as-a-Service
Coro, Gianpaolo; Pagano, Pasquale (ISTI-CNR); Candela, Leonardo
2013-01-01
In computational statistics, algorithms often have specialized implementations that address very specific problems. Every so often, these algorithms are applicable also to other problems than the original ones. Today, interest is growing towards modular and pluggable solutions that enable the repetition and validation of the experiments made by other scientists and allow the exploitation of those algorithms in other contexts. Furthermore, such procedures are requested to be remotely hosted an...
Visualization and animation of RBFS search algorithm
Lipovec, Darko
2011-01-01
We created a web application for better comprehension of the RBFS algorithm. We present RBFS algorithm and its properties and describe the Adobe Flash development platform, which we used for the development together with the tools for Flash animation and Flash Builder development environment. We present a graphical user interface and three animated examples where RBFS searches for an optimal solution. The behavior of the algorithm is illustrated using an animation of the pseudo-code and anima...
Fast Algorithm for N-2 Contingency Problem
Turitsyn, K. S.; Kaplunovich, P. A.
2013-01-01
We present a novel selection algorithm for N-2 contingency analysis problem. The algorithm is based on the iterative bounding of line outage distribution factors and successive pruning of the set of contingency pair candidates. The selection procedure is non-heuristic, and is certified to identify all events that lead to thermal constraints violations in DC approximation. The complexity of the algorithm is O(N[superscript 2]) comparable to the complexity of N-1 contingency problem. We validat...
A new algorithm for generalized fractional programs
Frenk, Hans; Barros, Ana; Schaible, S.; Zhang, Shuzhong
1996-01-01
textabstractA new dual problem for convex generalized fractional programs with no duality gap is presented and it is shown how this dual problem can be efficiently solved using a parametric approach. The resulting algorithm can be seen as “dual” to the Dinkelbach-type algorithm for generalized fractional programs since it approximates the optimal objective value of the dual (primal) problem from below. Convergence results for this algorithm are derived and an easy condition to achieve superli...
Designing a Computational Geometry Algorithms Library
Schirra, S.
1997-01-01
In these notes, which were originally written as lecture notes for Advanced School on Algorithmic Foundations of Geographic Information Systems, CISM, held in Udine, Italy, in September, 1996, we discuss issues related to the design of a computational geometry algorithms library. We discuss modularity and generality, efficiency and robustness, and ease of use. We argue that exact geometric computation is the most promising approach to ensure robustness in a geometric algorithms library. Many ...
Partial Evaluation of the Euclidian Algorithm
DEFF Research Database (Denmark)
Danvy, Olivier; Goldberg, Mayer
1997-01-01
-like behavior. Each of them presents a challenge for partial evaluation. The Euclidian algorithm is one of them, and in this article, we make it amenable to partial evaluation. We observe that the number of iterations in the Euclidian algorithm is bounded by a number that can be computed given either of the two...... arguments. We thus rephrase this algorithm using bounded recursion. The resulting program is better suited for automatic unfolding and thus for partial evaluation. Its specialization is efficient....
MM Algorithms for Geometric and Signomial Programming
Lange, Kenneth; Zhou, Hua
2010-01-01
This paper derives new algorithms for signomial programming, a generalization of geometric programming. The algorithms are based on a generic principle for optimization called the MM algorithm. In this setting, one can apply the geometric-arithmetic mean inequality and a supporting hyperplane inequality to create a surrogate function with parameters separated. Thus, unconstrained signomial programming reduces to a sequence of one-dimensional minimization problems. Simple examples demonstrate ...
Algorithm for Realistic Modeling of Graphitic Systems
Directory of Open Access Journals (Sweden)
A.V. Khomenko
2011-01-01
Full Text Available An algorithm for molecular dynamics simulations of graphitic systems using realistic semiempirical interaction potentials of carbon atoms taking into account both short-range and long-range contributions is proposed. Results of the use of the algorithm for a graphite sample are presented. The scalability of the algorithm depending on the system size and the number of processor cores involved in the calculations is analyzed.
Dimensionally Distributed Learning: Models and Algorithm
Zheng, Haipeng; Kulkarni, Sanjeev R.; Poor, H. Vincent
2008-01-01
This paper introduces a framework for regression with dimensionally distributed data with a fusion center. A cooperative learning algorithm, the iterative conditional expectation algorithm (ICEA), is designed within this framework. The algorithm can effectively discover linear combinations of individual estimators trained by each agent without transferring and storing large amount of data amongst the agents and the fusion center. The convergence of ICEA is explored. Specifically, for a two ag...
An object-oriented cluster search algorithm
Energy Technology Data Exchange (ETDEWEB)
Silin, Dmitry; Patzek, Tad
2003-01-24
In this work we describe two object-oriented cluster search algorithms, which can be applied to a network of an arbitrary structure. First algorithm calculates all connected clusters, whereas the second one finds a path with the minimal number of connections. We estimate the complexity of the algorithm and infer that the number of operations has linear growth with respect to the size of the network.
Accelerated Kaczmarz Algorithms using History Information
Ma, Tengfei
2016-01-01
The Kaczmarz algorithm is a well known iterative method for solving overdetermined linear systems. Its randomized version yields provably exponential convergence in expectation. In this paper, we propose two new methods to speed up the randomized Kaczmarz algorithm by utilizing the past estimates in the iterations. The first one utilize the past estimates to get a preconditioner. The second one combines the stochastic average gradient (SAG) method with the randomized Kaczmarz algorithm. It ta...
A NEW RECURSIVE ALGORITHM FOR MULTIUSER DETECTION
Institute of Scientific and Technical Information of China (English)
Wang Lei; Zheng Baoyu; Li Lei; Chen Chao
2009-01-01
Based on the synthesis and analysis of recursive receivers,a new algorithm,namely partial grouping maximization likelihood algorithm,is proposed to achieve satisfactory performance with moderate computational complexity.During the analysis,some interesting properties shared by the proposed procedures are described.Finally,the performance assessment shows that the new scheme is superior to the linear detector and ordinary grouping algorithm,and achieves a bit-error rate close to that of the optimum receiver.
An algorithm for multipication of Kaluza numbers
Cariow, Aleksandr; Cariowa, Galina; Łentek, Rafał
2015-01-01
This paper presents the derivation of a new algorithm for multiplying of two Kaluza numbers. Performing this operation directly requires 1024 real multiplications and 992 real additions. The proposed algorithm can compute the same result with only 512 real multiplications and 576 real additions. The derivation of our algorithm is based on utilizing the fact that multiplication of two Kaluza numbers can be expressed as a matrixvector product. The matrix multiplicand that participates in the pr...
An Incremental Approach to Automatic Algorithm Design
Institute of Scientific and Technical Information of China (English)
LUAN Shangmin; LI Wei
1999-01-01
This paper presents an incrementalapproach to automatic algorithm design, which can be described byalgebraic specifications precisely and conveniently. The definitions ofselection operator and extension operator which can be defined bystrategy relations and transformations are given in order to model theprocess of finding the solution of a problem. Also discussed is itsobject-oriented implementation. The functional specification and thedesign specification for an algorithm are given in one framework so thatthe correctness of the algorithm can be easily proved.
Flow enforcement algorithms for ATM networks
DEFF Research Database (Denmark)
Dittmann, Lars; Jacobsen, Søren B.; Moth, Klaus
1991-01-01
Four measurement algorithms for flow enforcement in asynchronous transfer mode (ATM) networks are presented. The algorithms are the leaky bucket, the rectangular sliding window, the triangular sliding window, and the exponentially weighted moving average. A comparison, based partly on teletraffic....... Implementations are proposed on the block diagram level, and dimensioning examples are carried out when flow enforcing a renewal-type connection using the four algorithms. The corresponding hardware demands are estimated aid compared...
EESA Algorithm in Wireless Sensor Networks
Pei Zhang; Lu Feng
2014-01-01
Since there are many problems of traditional extended clustering algorithm in wireless sensor network like short extended time, over energy consumption, too many deviated position the of cluster head nodes and so on, this paper proposes the EESA algorithm. The algorithm makes many improvements on the way of dividing clusters, strategy of electing the cluster head and construction method of data relay path, the two aspects of inter-cluster energy balance and energy balance among the cluster ar...
An Optimal Online Algorithm for Halfplane Intersection
Institute of Scientific and Technical Information of China (English)
WU Jigang; JI Yongchang; CHEN Guoliang
2000-01-01
The intersection of N halfplanes is a basic problem in computational geometry and computer graphics. The optimal offiine algorithm for this problem runs in time O(N log N). In this paper, an optimal online algorithm which runs also in time O(N log N) for this problem is presented. The main idea of the algorithm is to give a new definition for the left side of a given line, to assign the order for the points of a convex polygon, and then to use binary search method in an ordered vertex set. The data structure used in the algorithm is no more complex than array.
Fast Algorithm of Multivariable Generalized Predictive Control
Institute of Scientific and Technical Information of China (English)
Jin,Yuanyu; Pang,Zhonghua; Cui,Hong
2005-01-01
To avoid the shortcoming of the traditional (previous)generalized predictive control (GPC) algorithms, too large amounts of computation, a fast algorithm of multivariable generalized predictive control is presented in which only the current control actions are computed exactly on line and the rest (the future control actions) are approximately done off line. The algorithm is simple and can be used in the arbitary-dimension input arbitary-dimension output (ADIADO) linear systems. Because it dose not need solving Diophantine equation and reduces the dimension of the inverse matrix, it decreases largely the computational burden. Finally, simulation results show that the presented algorithm is effective and practicable.
Algorithms for Large, Sparse Network Alignment Problems
Bayati, Mohsen; Gleich, David F; Saberi, Amin; Wang, Ying
2009-01-01
We propose a new distributed algorithm for sparse variants of the network alignment problem that occurs in a variety of data mining areas including systems biology, database matching, and computer vision. Our algorithm uses a belief propagation heuristic and provides near optimal solutions for an NP-hard combinatorial optimization problem. We show that our algorithm is faster and outperforms or nearly ties existing algorithms on synthetic problems, a problem in bioinformatics, and a problem in ontology matching. We also provide a unified framework for studying and comparing all network alignment solvers.
Collaborative Error Registration Algorithm for Radar System
Institute of Scientific and Technical Information of China (English)
WU Ze-min; REN Shu-jie; LIU Xi
2009-01-01
Affected by common target selection, target motion estimation and time alignment, the radar system error registration algorithm is greatly limited in application. By using communication and time synchronization function of a data link network, a collaborative algorithm is proposed, which makes use of a virtual coordinates constructed by airplane to get high precision measurement source and realize effective estimation of the system error. This algorithm is based on Kalman filter and does not require high capacities in memory and calculation. Simulated results show that the algorithm has better convergence performance and estimation precision, no constrain on sampling period and accords with transfer characteristic of data link and tactical internet perfectly.
Highly Scalable Matching Pursuit Signal Decomposition Algorithm
National Aeronautics and Space Administration — In this research, we propose a variant of the classical Matching Pursuit Decomposition (MPD) algorithm with significantly improved scalability and computational...
A realizable quantum encryption algorithm for qubits
Institute of Scientific and Technical Information of China (English)
Zhou Nan-Run; Zeng Gui-Hua
2005-01-01
A realizable quantum encryption algorithm for qubits is presented by employing bit-wise quantum computation.System extension and bit-swapping are introduced into the encryption process, which makes the ciphertext space expanded greatly. The security of the proposed algorithm is analysed in detail and the schematic physical implementation is also provided. It is shown that the algorithm, which can prevent quantum attack strategy as well as classical attack strategy, is effective to protect qubits. Finally, we extend our algorithm to encrypt classical binary bits and quantum entanglements.
Distributed Algorithms for Time Optimal Reachability Analysis
DEFF Research Database (Denmark)
Zhang, Zhengkui; Nielsen, Brian; Larsen, Kim Guldstrand
2016-01-01
. We propose distributed computing to accelerate time optimal reachability analysis. We develop five distributed state exploration algorithms, implement them in \\uppaal enabling it to exploit the compute resources of a dedicated model-checking cluster. We experimentally evaluate the implemented...... algorithms with four models in terms of their ability to compute near- or proven-optimal solutions, their scalability, time and memory consumption and communication overhead. Our results show that distributed algorithms work much faster than sequential algorithms and have good speedup in general....
Hardware modules of the RSA algorithm
Directory of Open Access Journals (Sweden)
Škobić Velibor
2014-01-01
Full Text Available This paper describes basic principles of data protection using the RSA algorithm, as well as algorithms for its calculation. The RSA algorithm is implemented on FPGA integrated circuit EP4CE115F29C7, family Cyclone IV, Altera. Four modules of Montgomery algorithm are designed using VHDL. Synthesis and simulation are done using Quartus II software and ModelSim. The modules are analyzed for different key lengths (16 to 1024 in terms of the number of logic elements, the maximum frequency and speed.
Eigenvalue Decomposition-Based Modified Newton Algorithm
Directory of Open Access Journals (Sweden)
Wen-jun Wang
2013-01-01
Full Text Available When the Hessian matrix is not positive, the Newton direction may not be the descending direction. A new method named eigenvalue decomposition-based modified Newton algorithm is presented, which first takes the eigenvalue decomposition of the Hessian matrix, then replaces the negative eigenvalues with their absolute values, and finally reconstructs the Hessian matrix and modifies the searching direction. The new searching direction is always the descending direction. The convergence of the algorithm is proven and the conclusion on convergence rate is presented qualitatively. Finally, a numerical experiment is given for comparing the convergence domains of the modified algorithm and the classical algorithm.
Algorithms and networking for computer games
Smed, Jouni
2006-01-01
Algorithms and Networking for Computer Games is an essential guide to solving the algorithmic and networking problems of modern commercial computer games, written from the perspective of a computer scientist. Combining algorithmic knowledge and game-related problems, the authors discuss all the common difficulties encountered in game programming. The first part of the book tackles algorithmic problems by presenting how they can be solved practically. As well as ""classical"" topics such as random numbers, tournaments and game trees, the authors focus on how to find a path in, create the terrai
Optimized QoS Routing Algorithm
Institute of Scientific and Technical Information of China (English)
石明洪; 王思兵; 白英彩
2004-01-01
QoS routing is one of the key technologies for providing guaranteed service in IP networks. The paper focuses on the optimization problem for bandwidth constrained QoS routing, and proposes an optimal algorithm based on the global optimization of path bandwidth and hop counts. The main goal of the algorithm is to minimize the consumption of network resource, and at the same time to minimize the network congestion caused by irrational path selection. The simulation results show that our algorithm has lower call blocking rate and higher throughput than traditional algorithms.
Thermostat algorithm for generating target ensembles.
Bravetti, A; Tapias, D
2016-02-01
We present a deterministic algorithm called contact density dynamics that generates any prescribed target distribution in the physical phase space. Akin to the famous model of Nosé and Hoover, our algorithm is based on a non-Hamiltonian system in an extended phase space. However, the equations of motion in our case follow from contact geometry and we show that in general they have a similar form to those of the so-called density dynamics algorithm. As a prototypical example, we apply our algorithm to produce a Gibbs canonical distribution for a one-dimensional harmonic oscillator. PMID:26986320
Liu, Dong-sheng; Fan, Shu-jiang
2014-01-01
In order to offer mobile customers better service, we should classify the mobile user firstly. Aimed at the limitations of previous classification methods, this paper puts forward a modified decision tree algorithm for mobile user classification, which introduced genetic algorithm to optimize the results of the decision tree algorithm. We also take the context information as a classification attributes for the mobile user and we classify the context into public context and private context classes. Then we analyze the processes and operators of the algorithm. At last, we make an experiment on the mobile user with the algorithm, we can classify the mobile user into Basic service user, E-service user, Plus service user, and Total service user classes and we can also get some rules about the mobile user. Compared to C4.5 decision tree algorithm and SVM algorithm, the algorithm we proposed in this paper has higher accuracy and more simplicity. PMID:24688389
Bionic Intelligent Optimization Algorithm Based on MMAS and Fish-Swarm Algorithm
Jingjing Yang; Benzhen Guo; Jixiang Gou; Xiao Zhang
2013-01-01
With large number of ants, the ant colony algorithm would always take a long time or is rather difficult to find the optimal path from complex chapter path, further more, there exists a contradiction between stagnation, accelerated convergence and precocity. In this paper, we propose a new bionic optimization algorithm. The main idea of the algorithm is to introduce the horizons concept in the MMAS fish swarm algorithm, so it would take shorter time to find the optimal path with numerous ants...
Institute of Scientific and Technical Information of China (English)
Xianbin Wen; Hua Zhang; Jianguang Zhang; Xu Jiao; Lei Wang
2009-01-01
A novel method that hybridizes genetic algorithm (GA) and expectation maximization (EM) algorithm for the classification of syn-thetic aperture radar (SAR) imagery is proposed by the finite Gaussian mixtures model (GMM) and multiscale autoregressive (MAR)model. This algorithm is capable of improving the global optimality and consistency of the classification performance. The experiments on the SAR images show that the proposed algorithm outperforms the standard EM method significantly in classification accuracy.
ICESat Waveform Ground Processing Algorithm
Roberts, L.; Zwally, H.; Brenner, A. C.; Saba, J.; Yi, D.
2003-12-01
Gaussian to determine the mean surface elevation. We present algorithms that use single or double Gaussians to fit the return waveform and show how the mean elevation and surface characteristics are calculated from the functional fit. The initial estimates and covariance matrix are set to optimize the fit to the leading edge of the return waveform corresponding to the largest Gaussian peak. Over ice surfaces, two Gaussian peaks are allowed to account for the extended tail of the returns that have high forward scattering components, or two distinct surfaces in the footprint. Over land, up to six Gaussian peaks are allowed. The algorithm was fine tuned using the first 36 days of data, which included returns over the ice regions with high detector/amplifier saturation and strong atmospheric forward scattering.
New algorithm for OHSS prevention
Directory of Open Access Journals (Sweden)
Papanikolaou Evangelos G
2011-11-01
Full Text Available Abstract Ovarian hyperstimulation syndrome (OHSS still remains a life-threatening complication of in vitro fertilization treatment (IVF, keeping patients and especially those, who previously experienced OHSS, from attempting infertility treatment and childbearing. The recent implementation of four new modalities: the GnRH antagonist protocol, GnRH agonist (GnRHa triggering of ovulation, blastocyst transfer and embryo/oocyte vitrification, renders feasible the elimination of OHSS in connection with ovarian hyperstimulation for IVF treatment. The proposed current algorithm is based on the number of follicles developed after ovarian stimulation, setting a cut-off level at the development of 18 or more follicles. Further, fulfilling this criterion, the algorithm is based on four decision-making points: the final day of patient work-up, the day of triggering final oocyte maturation, day-1 post oocyte pick-up (OPU and day-5 post OPU. If the physician decides to administer hCG for final oocyte maturation regardless the type of analogue used, he has the option on day-1 to either freeze all embryos or to proceed to day-5. On this day, based on the clinical condition of the patient, a decision should be made to either transfer a single blastocyst or to vitrify all blastocysts available. However, this strategy will not guarantee an OHSS free luteal phase especially if a pregnancy occurs. If the physician decides to trigger ovulation with GnRHa, feasible only with the antagonist protocol, embryos can be cultured until day-5. On this day a transfer can be performed with no risk of OHSS and spare blastocysts may be vitrified. Alternatively, on day-1 or day-2 post OPU, all embryos could be frozen. Hopefully, in a near future, GnRHa triggering and vitrification of oocytes will become everyday practice. Only the combined use of a GnRH antagonist protocol with GnRHa triggering and subsequent single blastocyst transfer or embryo/oocyte freezing will completely
Control algorithms for dynamic attenuators
Energy Technology Data Exchange (ETDEWEB)
Hsieh, Scott S., E-mail: sshsieh@stanford.edu [Department of Radiology, Stanford University, Stanford, California 94305 and Department of Electrical Engineering, Stanford University, Stanford, California 94305 (United States); Pelc, Norbert J. [Department of Radiology, Stanford University, Stanford California 94305 and Department of Bioengineering, Stanford University, Stanford, California 94305 (United States)
2014-06-15
Purpose: The authors describe algorithms to control dynamic attenuators in CT and compare their performance using simulated scans. Dynamic attenuators are prepatient beam shaping filters that modulate the distribution of x-ray fluence incident on the patient on a view-by-view basis. These attenuators can reduce dose while improving key image quality metrics such as peak or mean variance. In each view, the attenuator presents several degrees of freedom which may be individually adjusted. The total number of degrees of freedom across all views is very large, making many optimization techniques impractical. The authors develop a theory for optimally controlling these attenuators. Special attention is paid to a theoretically perfect attenuator which controls the fluence for each ray individually, but the authors also investigate and compare three other, practical attenuator designs which have been previously proposed: the piecewise-linear attenuator, the translating attenuator, and the double wedge attenuator. Methods: The authors pose and solve the optimization problems of minimizing the mean and peak variance subject to a fixed dose limit. For a perfect attenuator and mean variance minimization, this problem can be solved in simple, closed form. For other attenuator designs, the problem can be decomposed into separate problems for each view to greatly reduce the computational complexity. Peak variance minimization can be approximately solved using iterated, weighted mean variance (WMV) minimization. Also, the authors develop heuristics for the perfect and piecewise-linear attenuators which do not requirea priori knowledge of the patient anatomy. The authors compare these control algorithms on different types of dynamic attenuators using simulated raw data from forward projected DICOM files of a thorax and an abdomen. Results: The translating and double wedge attenuators reduce dose by an average of 30% relative to current techniques (bowtie filter with tube current
Archimedean copula estimation of distribution algorithm based on artificial bee colony algorithm
Institute of Scientific and Technical Information of China (English)
Haidong Xu; Mingyan Jiang; Kun Xu
2015-01-01
The artificial bee colony (ABC) algorithm is a com-petitive stochastic population-based optimization algorithm. How-ever, the ABC algorithm does not use the social information and lacks the knowledge of the problem structure, which leads to in-sufficiency in both convergent speed and searching precision. Archimedean copula estimation of distribution algorithm (ACEDA) is a relatively simple, time-economic and multivariate correlated EDA. This paper proposes a novel hybrid algorithm based on the ABC algorithm and ACEDA cal ed Archimedean copula estima-tion of distribution based on the artificial bee colony (ACABC) algorithm. The hybrid algorithm utilizes ACEDA to estimate the distribution model and then uses the information to help artificial bees to search more efficiently in the search space. Six bench-mark functions are introduced to assess the performance of the ACABC algorithm on numerical function optimization. Experimen-tal results show that the ACABC algorithm converges much faster with greater precision compared with the ABC algorithm, ACEDA and the global best (gbest)-guided ABC (GABC) algorithm in most of the experiments.
Comparison of cone beam artifacts reduction: two pass algorithm vs TV-based CS algorithm
Choi, Shinkook; Baek, Jongduk
2015-03-01
In a cone beam computed tomography (CBCT), the severity of the cone beam artifacts is increased as the cone angle increases. To reduce the cone beam artifacts, several modified FDK algorithms and compressed sensing based iterative algorithms have been proposed. In this paper, we used two pass algorithm and Gradient-Projection-Barzilai-Borwein (GPBB) algorithm to reduce the cone beam artifacts, and compared their performance using structural similarity (SSIM) index. In two pass algorithm, it is assumed that the cone beam artifacts are mainly caused by extreme-density(ED) objects, and therefore the algorithm reproduces the cone beam artifacts(i.e., error image) produced by ED objects, and then subtract it from the original image. GPBB algorithm is a compressed sensing based iterative algorithm which minimizes an energy function for calculating the gradient projection with the step size determined by the Barzilai- Borwein formulation, therefore it can estimate missing data caused by the cone beam artifacts. To evaluate the performance of two algorithms, we used testing objects consisting of 7 ellipsoids separated along the z direction and cone beam artifacts were generated using 30 degree cone angle. Even though the FDK algorithm produced severe cone beam artifacts with a large cone angle, two pass algorithm reduced the cone beam artifacts with small residual errors caused by inaccuracy of ED objects. In contrast, GPBB algorithm completely removed the cone beam artifacts and restored the original shape of the objects.
An Improved Ant Colony Routing Algorithm for WSNs
Tan Zhi; Zhang Hui
2015-01-01
Ant colony algorithm is a classical routing algorithm. And it are used in a variety of application because it is economic and self-organized. However, the routing algorithm will expend huge amounts of energy at the beginning. In the paper, based on the idea of Dijkstra algorithm, the improved ant colony algorithm was proposed to balance the energy consumption of networks. Through simulation and comparison with basic ant colony algorithms, it is obvious that improved algorithm can effectively...
Supervised learning algorithms for visual object categorization
bin Abdullah, A.
2010-01-01
This thesis presents novel techniques for image recognition systems for better understanding image content. More specifically, it looks at the algorithmic aspects and experimental verification to demonstrate the capability of the proposed algorithms. These techniques aim to improve the three major c
LEARNING ALGORITHM OF STAGE CONTROL NBP NETWORK
Institute of Scientific and Technical Information of China (English)
Yan Lixiang; Qin Zheng
2003-01-01
This letter analyzes the reasons why the known Neural Back Promulgation (NBP)network learning algorithm has slower speed and greater sample error. Based on the analysis and experiment, the training group descending Enhanced Combination Algorithm (ECA) is proposed.The analysis of the generalized property and sample error shows that the ECA can heighten the study speed and reduce individual error.
Top Tagging by Deep Learning Algorithm
Akil, Ali
2015-01-01
In this report I will show the application of a deep learning algorithm on a Monte Carlo simulation sample to test its performance in tagging hadronic decays of boosted top quarks and compare what we get with the results of the application of some other algorithms.
BSA - exact algorithm computing LTS estimate
Klouda, Karel
2010-01-01
The main result of this paper is a new exact algorithm computing the estimate given by the Least Trimmed Squares (LTS). The algorithm works under very weak assumptions. To prove that, we study the respective objective function using basic techniques of analysis and linear algebra.
Heuristic estimates in shortest path algorithms
W.H.L.M. Pijls (Wim)
2006-01-01
textabstractShortest path problems occupy an important position in Operations Research as well as in Arti¯cial Intelligence. In this paper we study shortest path algorithms that exploit heuristic estimates. The well-known algorithms are put into one framework. Besides we present an interesting appli
Heuristic estimates in shortest path algorithms
Pijls, Wim
2006-01-01
textabstractShortest path problems occupy an important position in Operations Research as well as in Arti¯cial Intelligence. In this paper we study shortest path algorithms that exploit heuristic estimates. The well-known algorithms are put into one framework. Besides we present an interesting application of binary numbers in the shortest path theory.
On benchmarking Stochastic Global Optimization Algorithms
Hendrix, E.M.T.; Lancinskas, A.
2015-01-01
A multitude of heuristic stochastic optimization algorithms have been described in literature to obtain good solutions of the box-constrained global optimization problem often with a limit on the number of used function evaluations. In the larger question of which algorithms behave well on which typ
Initial borehole acoustic televiewer data processing algorithms
Energy Technology Data Exchange (ETDEWEB)
Moore, T.K.
1988-06-01
With the development of a new digital televiewer, several algorithms have been developed in support of off-line data processing. This report describes the initial set of utilities developed to support data handling as well as data display. Functional descriptions, implementation details, and instructions for use of the seven algorithms are provided. 5 refs., 33 figs., 1 tab.
Lyapunov Function Synthesis - Algorithm and Software
DEFF Research Database (Denmark)
Leth, Tobias; Wisniewski, Rafal; Sloth, Christoffer
2016-01-01
In this paper we introduce an algorithm for the synthesis of polynomial Lyapunov functions for polynomial vector fields. The Lyapunov function is a continuous piecewisepolynomial defined on simplices, which compose a collection of simplices. The algorithm is elaborated and crucial features...
A monotonically convergent algorithm for factals
KIERS, Henk A.L.; Takane, Yoshio; Mooijaart, Ab
1993-01-01
Takane, Young, and de Leeuw proposed a procedure called FACTALS for the analysis of variables of mixed measurement levels (numerical, ordinal, or nominal). Mooijaart pointed out that their algorithm does not necessarily converge, and Nevels proposed a new algorithm for the case of nominal variables.
Optical Sensor Based Corn Algorithm Evaluation
Optical sensor based algorithms for corn fertilization have developed by researchers in several states. The goal of this international research project was to evaluate these different algorithms and determine their robustness over a large geographic area. Concurrently the goal of this project was to...
Parallel Algorithm Solves Coupled Differential Equations
Hayashi, A.
1987-01-01
Numerical methods adapted to concurrent processing. Algorithm solves set of coupled partial differential equations by numerical integration. Adapted to run on hypercube computer, algorithm separates problem into smaller problems solved concurrently. Increase in computing speed with concurrent processing over that achievable with conventional sequential processing appreciable, especially for large problems.
Excursion-Set-Mediated Genetic Algorithm
Noever, David; Baskaran, Subbiah
1995-01-01
Excursion-set-mediated genetic algorithm (ESMGA) is embodiment of method of searching for and optimizing computerized mathematical models. Incorporates powerful search and optimization techniques based on concepts analogous to natural selection and laws of genetics. In comparison with other genetic algorithms, this one achieves stronger condition for implicit parallelism. Includes three stages of operations in each cycle, analogous to biological generation.
Modeling and Engineering Algorithms for Mobile Data
DEFF Research Database (Denmark)
Blunck, Henrik; Hinrichs, Klaus; Sondern, Joëlle;
2006-01-01
In this paper, we present an object-oriented approach to modeling mobile data and algorithms operating on such data. Our model is general enough to capture any kind of continuous motion while at the same time allowing for encompassing algorithms optimized for specific types of motion. Such motion...
Algorithmic Game Theory and Artificial Intelligence
Elkind, Edith; Nanyang Technological University; Leyton-Brown, Kevin; University of British Columbia
2010-01-01
We briefly survey the rise of game theory as a topic of study in artificial intelligence, and explain the term algorithmic game theory. We then de- scribe three broad areas of current inquiry by AI researchers in algorithmic game theory: game playing, social choice, and mechanism design. Finally, we give short summaries of each of the six articles appearing in this issue.
Kalman plus weights: a time scale algorithm
Greenhall, C. A.
2001-01-01
KPW is a time scale algorithm that combines Kalman filtering with the basic time scale equation (BTSE). A single Kalman filter that estimates all clocks simultaneously is used to generate the BTSE frequency estimates, while the BTSE weights are inversely proportional to the white FM variances of the clocks. Results from simulated clock ensembles are compared to previous simulation results from other algorithms.
Novel multi-objective optimization algorithm
Institute of Scientific and Technical Information of China (English)
Jie Zeng; Wei Nie
2014-01-01
Many multi-objective evolutionary algorithms (MOEAs) can converge to the Pareto optimal front and work wel on two or three objectives, but they deteriorate when faced with many-objective problems. Indicator-based MOEAs, which adopt various indicators to evaluate the fitness values (instead of the Pareto-dominance relation to select candidate solutions), have been regarded as promising schemes that yield more satisfactory re-sults than wel-known algorithms, such as non-dominated sort-ing genetic algorithm (NSGA-II) and strength Pareto evolution-ary algorithm (SPEA2). However, they can suffer from having a slow convergence speed. This paper proposes a new indicator-based multi-objective optimization algorithm, namely, the multi-objective shuffled frog leaping algorithm based on the ε indicator (ε-MOSFLA). This algorithm adopts a memetic meta-heuristic, namely, the SFLA, which is characterized by the powerful capa-bility of global search and quick convergence as an evolutionary strategy and a simple and effective ε-indicator as a fitness as-signment scheme to conduct the search procedure. Experimental results, in comparison with other representative indicator-based MOEAs and traditional Pareto-based MOEAs on several standard test problems with up to 50 objectives, show thatε-MOSFLA is the best algorithm for solving many-objective optimization problems in terms of the solution quality as wel as the speed of convergence.
A quantum Algorithm for the Moebius Function
Love, Peter
We give an efficient quantum algorithm for the Moebius function from the natural numbers to -1,0,1. The cost of the algorithm is asymptotically quadratic in log n and does not require the computation of the prime factorization of n as an intermediate step.
Analysis of RSA Algorithm using GPU Programming
Directory of Open Access Journals (Sweden)
Sonam Mahajan
2014-07-01
Full Text Available Modern-day computer security relies heavily on cry ptography as a means to protect the data that we ha ve become increasingly reliant on. The main researc h in computer security domain is how to enhance the speed of RSA algorithm. The computing capability of Graphic Processing Unit as a co-processor of the CPU can leverage massive-parallelism. This paper presents a novel algorithm for calculating modulo value that can process large power of numbers w hich otherwise are not supported by built-in data t ypes. First the traditional algorithm is studied. Secondl y, the parallelized RSA algorithm is designed using CUDA framework. Thirdly, the designed algorithm is realized for small prime numbers and large pr ime number . As a result the main fundamental problem of RSA algorithm such as speed and use of poo r or small prime numbers that has led to significant s ecurity holes, despite the RSA algorithm's mathemat ical soundness can be alleviated by this algorithm
Decoding Hermitian Codes with Sudan's Algorithm
DEFF Research Database (Denmark)
Høholdt, Tom; Nielsen, Rasmus Refslund
1999-01-01
We present an efficient implementation of Sudan's algorithm for list decoding Hermitian codes beyond half the minimum distance. The main ingredients are an explicit method to calculate so-called increasing zero bases, an efficient interpolation algorithm for finding the Q-polynomial, and a reduct...
Advancing-Front Algorithm For Delaunay Triangulation
Merriam, Marshal L.
1993-01-01
Efficient algorithm performs Delaunay triangulation to generate unstructured grids for use in computing two-dimensional flows. Once grid generated, one can optionally call upon additional subalgorithm that removes diagonal lines from quadrilateral cells nearly rectangular. Resulting approximately rectangular grid reduces cost per iteration of flow-computing algorithm.