检索结果-内蒙古大学图书馆

analysis of permutation routing algorithms

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2000年第2期125卷 249-256页

作者： Békési, J Galambos, G Hajnal, P Juhasz Gyula Teachers Training Coll Dept Comp Sci H-6701 Szeged Hungary Attila Jozsef Univ Bolyai Inst Szeged Hungary

In this paper we analyze some permutation routing algorithms for different kinds of mesh architectures. First we give lower and upper bounds for the expected number of steps of the basic greedy algorithm on linear and two-dimensional arrays without bus. Finally we present lower bounds for the number of steps of arbitrary on-line or off-line algorithms on rectangular meshes with buses. (C) 2000 Elsevier Science B.V. All rights reserved.

关键词： parallel processing network communication analysis of algorithms mesh architecture permutation routing

来源：评论

学校读者我要写书评

暂无评论

SOME analysis TECHNIQUES FOR ASYNCHRONOUS MULTIPROCESSOR algorithms

引用

IEEE TRANSACTIONS ON SOFTWARE ENGINEERING 1979年第1期5卷 24-31页

作者： ROBINSON, JT Department of Computer Science Carnegie-Mellon University

An Asynchronous multiprocessor system with k or more processors sharing a common memory through a switch or connecting network can be used to execute a task that has been broken down into a set of subtasks. A precedence relation exists among tasks when some subtasks cannot begin until others are finished. This waiting by subtasks causes inefficiency in an algorithm. Efficient algorithms must achieve a balance between low process communication and high adaptability to process speed variations. Processes in the static algorithm select either an initial task or a task not already selected, go dormant when no task is to be selected, execute the selected task, and activate a dormant process. Static decomposition algorithms are suited for loosely coupled computer networks because they require little process communication, and can be described by task-graphs.

关键词： Sorting analysis of algorithms Asynchronous Multiprocessors Merging Order Statistics Parallel Processing Probability Theory Queueing Models

来源：评论

学校读者我要写书评

暂无评论

Regularity of the Euclid Algorithm;application to the analysis of fast GCD algorithms

引用

JOURNAL OF SYMBOLIC COMPUTATION 2009年第7期44卷 726-767页

作者： Cesaratto, Eda Clement, Julien Daireaux, Benoit Lhote, Loick Maume-Deschamps, Veronique Vallee, Brigitte Univ Caen CNRS GREYC UMR 6072 F-14032 Caen France ENSICAEN Caen France Consejo Nacl Invest Cient & Tecn RA-1033 Buenos Aires DF Argentina Univ Nacl Gral Sarmiento Inst Desarrollo Humano Buenos Aires DF Argentina IrisRes Ctr Stavanger Norway Univ Lyon 1 ISFA F-69365 Lyon France

There exist fast variants of the gcd algorithm which are all based on principles due to Knuth and Schonhage. On inputs of size n, these algorithms use a Divide and Conquer approach, perform FFT multiplications with complexity mu(n) and stop the recursion at a depth slightly smaller than lg n. A rough estimate of the worst-case complexity of these fast versions provides the bound O(mu(n) log n). Even the worst-case estimate is partly based on heuristics and is not actually proven. Here, we provide a precise probabilistic analysis of some of these fast variants, and we prove that their average bit-complexity on random inputs of size n is (sic) (mu(n) log n), with a precise remainder term, and estimates of the constant in the (sic)-term. Our analysis applies to any cases when the cost mu(n) is of order Omega(n log n), and is valid both for the FFT multiplication algorithm of Schonhage-Strassen, but also for the new algorithm introduced quite recently by Furer [Furer, M., 2007. Faster integer Multiplication. In: Proceedings of STOC'07, pp. 57-66]. We view such a fast algorithm as a sequence of what we call interrupted algorithms, and we obtain two main results about the (plain) Euclid Algorithm, which are of independent interest. We precisely describe the evolution of the distribution of numbers during the execution of the (plain) Euclid Algorithm, and we exhibit an (unexpected) density psi which plays a central role since it always appears at the beginning of each recursive call. This strong regularity phenomenon proves that the interrupted algorithms are locally "similar" to the total algorithm. This ultimately leads to the precise evaluation of the average bit-complexity of these fast algorithms. This work uses various tools, and is based on a precise study of generalised transfer operators related to the dynamical system underlying the Euclid Algorithm. (C) 2008 Elsevier Ltd. All rights reserved.

关键词： Euclid algorithm Divide and conquer algorithms Fast multiplication analysis of algorithms Transfer operators Perron formula

来源：评论

学校读者我要写书评

暂无评论

Dynamical analysis of a class of Euclidean algorithms

引用

THEORETICAL COMPUTER SCIENCE 2003年第1-3期297卷 447-486页

作者： Vallée, B Univ Caen GREYC F-14032 Caen France

We develop a general framework for the analysis of algorithms of a broad Euclidean type. The average-case complexity of an algorithm is seen to be related to the analytic behaviour in the complex plane of the set of elementary transformations determined by the algorithm. The methods rely on properties of transfer operators suitably adapted from dynamical systems theory. As a consequence, we obtain precise average-case analyses of algorithms for evaluating the Jacobi symbol of computational number theory fame, thereby solving conjectures of Bach and Shallit. These methods also provide a unifying framework for the analysis of an entire class of gcd-like algorithms together with new results regarding the probable behaviour of their cost functions. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： analysis of algorithms average-case complexity Euclidean algorithms dynamical systems transfer operators functional analysis

来源：评论

学校读者我要写书评

暂无评论

IMPLEMENTATION AND analysis OF BINOMIAL QUEUE algorithms

引用

SIAM JOURNAL ON COMPUTING 1978年第3期7卷 298-319页

作者： BROWN, MR

The binomial queue, a new data structure for implementing priority queues that can be efficiently merged, was recently discovered by Jean Vuillemin; we explore the properties of this structure in detail. New methods of representing binomial queues are given which reduce the storage overhead of the structure and increase the efficiency of operations on it. One of these representations allows any element of an unknown priority queue to be deleted in log time, using only two pointers per element of the queue. A complete analysis of the average time for insertion into and deletion from a binomial queue is performed. This analysis is based on the result that the distribution of keys in a random binomial queue is also the stationary distribution obtained after repeated insertions and deletions.

关键词： analysis of algorithms binomial queue priority queue heap

来源：评论

学校读者我要写书评

暂无评论

Dynamical analysis of a class of Euclidean algorithms

Dynamical analysis of a class of Euclidean algorithms

引用

4th Latin American Theoretical Informatics International Conference (LATIN 2000)

作者： Vallée, B Univ Caen GREYC F-14032 Caen France

关键词： analysis of algorithms average-case complexity Euclidean algorithms dynamical systems transfer operators functional analysis

来源：评论

学校读者我要写书评

暂无评论

analysis on the Use of A* and Dijkstra's algorithms for Intelligent School Transport Route Optimization System 18

Analysis on the Use of A* and Dijkstra's Algorithms for Inte...

引用

4th Annual International Conference on HCI and UX (CHIuXiD)

作者： Lacorte, Alice M. Chavez, Enrico P. Technol Inst Philippines Manila Manila Philippines

ISBN: (纸本)9781450364294

This paper aims to present the results of the analysis on the use of A* and Dijkstra's algorithms as applied in the proposed route optimization model towards the development of a mobile application system for intelligent school transport. The study made use of a user-constructed simulation tool to test how each algorithm will work as applied in the proposed school transport system named EESCOOL which once developed can be useful in most schools and universities in the Philippines. Sample test cases of graphs with seven and 26 nodes or vertices and an anomaly (which refers to additional weight which represents any traffic situation) were considered in running the simulation tests. Results showed that A* algorithm performed better with shorter expected time of arrival (ETA) as compared to Dijkstra's algorithm during normal traffic situations and on small graph. Meanwhile, the use of Dijkstra's algorithm appeared to generate shorter ETA when it encountered anomalies in the traffic situations in either small or large graph. Therefore, it is suggested based from the results of the study to use both algorithms in the proposed intelligent school transport system, EESCOOL taking into considerations two major parameters in the proposed design for EESCOOL such as traffic conditions and number of nodes. The findings of the study may also be considered in some future work such as designing an intelligent mechanism to automatically shift the use of both algorithms during normal or unusual traffic situations for effective route optimization technique which can be applied not only in the school transport system but also in various smart intelligent transport systems.

关键词： Path-finding algorithms Route optimization Shortest path analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

Statistical properties of a class of randomized binary search algorithms

引用

PERFORMANCE EVALUATION 2025年 168卷

作者： Xia, Ye Univ Florida Dept Comp & Informat Sci & Engn Gainesville FL 32611 USA

In this paper, we analyze the statistical properties of a randomized binary search algorithm and its variants. These algorithms have applications in caching and load balancing in distributed environments such as peer-to-peer networks, cloud storage, data centers, and content distribution networks. The basic discrete version of the problem is as follows. Suppose there are m servers, numbered 1, 2, ... , m, out of which the first k servers are marked as special, where k is unknown. These k servers may contain a particular file or service that clients want. The objective is to select one of the marked servers uniformly at random. Considering the intended applications, we impose the constraint that there is no central controller to facilitate the selection process. We start with a basic algorithm: In each step, the client requesting the service chooses a number y uniformly at random from 1, 2, ... , x, where x is the number chosen in the previous step, initially set to m in the first step. A query is then sent to server y asking whether y is marked. If the answer is yes, the algorithm returns y;otherwise, the process is repeated with x <- y. In this paper, we primarily consider two batch versions of this algorithm in which multiple numbers are chosen in each step and multiple queries are made in parallel. We derive the mean and variance (exact and/or asymptotic) for the number of search steps in each version of the algorithm, and when possible, we give its distribution. Additionally, we analyze the access pattern of queries across the entire search space.

关键词： analysis of algorithms Parallel and distributed algorithms Randomized binary search algorithm Distributed search Load balancing

来源：评论

学校读者我要写书评

暂无评论

Generating Random Permutations by Coin Tossing: Classical algorithms, New analysis, and Modern Implementation

引用

ACM TRANSACTIONS ON algorithms 2017年第2期13卷 24-24页

作者： Bacher, Axel Bodini, Olivier Hwang, Hsien-Kuei Tsai, Tsung-Hsi Univ Paris 13 Inst Galilee UMR CNRS 7030 LIPN 99 Ave Jean Baptiste Clement F-93430 Villetaneuse France Acad Sinica Inst Stat Sci 128Sect 2Acad Rd Taipei 115 Taiwan

Several simple, classical, little-known algorithms in the statistics and computer science literature for generating random permutations by coin tossing are examined, analyzed, and implemented. These algorithms are either asymptotically optimal or close to being so in terms of the expected number of times the random bits are generated. In addition to asymptotic approximations to the expected complexity, we also clarify the corresponding variances, as well as the asymptotic distributions. A brief comparative discussion with numerical computations in a multicore system is also given.

关键词： Random permutation uniform distribution random number generator analysis of algorithms generating functions Mellin transform asymptotic distribution variance hardware random number generator multithreading

来源：评论

学校读者我要写书评

暂无评论

analysis of random sequential message passing algorithms for approximate inference

引用

JOURNAL OF STATISTICAL MECHANICS-THEORY AND EXPERIMENT 2022年第7期2022卷 073401-073401页

作者： Cakmak, Burak Lu, Yue M. Opper, Manfred Tech Univ Berlin Artificial Intelligence Grp D-10587 Berlin Germany Harvard Univ John Paulson Sch Engn & Appl Sci Cambridge MA 02138 USA Univ Birmingham Ctr Syst Modelling & Quantitat Biomed Birmingham B15 2TT W Midlands England

We analyze the dynamics of a random sequential message passing algorithm for approximate inference with large Gaussian latent variable models in a student-teacher scenario. To model nontrivial dependencies between the latent variables, we assume random covariance matrices drawn from rotation invariant ensembles. Moreover, we consider a model mismatching setting, where the teacher model and the one used by the student may be different. By means of dynamical functional approach, we obtain exact dynamical mean-field equations characterizing the dynamics of the inference algorithm. We also derive a range of model parameters for which the sequential algorithm does not converge. The boundary of this parameter range coincides with the de Almeida Thouless (AT) stability condition of the replica-symmetric ansatz for the static probabilistic model.

关键词： analysis of algorithms machine learning message-passing algorithms statistical inference

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：