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

SORTING NUMBERS USING LIMITED SYSTOLIC COPROCESSORS

INFORMATION PROCESSING LETTERS 1987年第6期24卷 351-354页

作者： MULLER, H Institut für Informatik I Universität Karlsruhe P.O. Box 6380 7500 Karlsruhe Fed. Rep. Germany

A probabilistic algorithm is presented for sorting real numbers that allows a significant speed-up even under restricted parallelism. The machine model used consists of a random access machine to which 3 coprocessors are attached. The first 2 processors -- DISTRIBUTE and SORT -- are linear systolic arrays containing p processing elements. The 3rd coprocessor, RANDOM, produces a random number x between zero and one. The model is a sequential random access machine and is only augmented by some special purpose processors. The range for an improvement against sequential O(n log n) algorithms for sorting is somewhat small. The main open issue that remains is whether the time bound of Algorithm Sort can be obtained by any deterministic algorithm or can be proved impossible by giving lower bounds.

关键词： Sorting parallel computation probabilistic algorithms computational complexity

来源：评论

学校读者我要写书评

暂无评论

probabilistic PARALLEL algorithms FOR SORTING AND SELECTION

引用

SIAM JOURNAL ON COMPUTING 1985年第2期14卷 396-409页

作者： REISCHUK, R Univ Bielefeld Fakultaet fuer Mathematik Bielefeld West Ger Univ Bielefeld Fakultaet fuer Mathematik Bielefeld West Ger

probabilistic parallel algorithms are described to sort n keys and to select the k-smallest element among them. For each problem we construct a probabilistic parallel decision tree. The tree for selection finishes wit... 详细信息

O (\log n)

关键词： parallel algorithms probabilistic algorithms sorting selection parallel random access machines decision trees efficient algorithms

来源：评论

学校读者我要写书评

暂无评论

THE DESIGN AND ANALYSIS OF BUCKETSORT FOR BUBBLE MEMORY SECONDARY STORAGE

引用

IEEE TRANSACTIONS ON COMPUTERS 1985年第3期34卷 218-234页

作者： LINDSTROM, EE VITTER, JS BROWN UNIV DEPT COMP SCIPROVIDENCERI 02912

BucketSort is a new external sorting algorithm for very large files that is a substantial improvement over merge sorting with disks. BucketSort requires an associative secondary storage device, which can be realized by large disk drives with logic-per-track capabilities or by magnetic bubble memory (MBM). This paper describes and analyzes a hypothetical Bucket-Sort implementation that uses bubble memory. A new software marking technique is introduced that reduces the effective time for an associative search.

关键词： Analysis of algorithms associative memory database systems external sorting magnetic bubble memory probabilistic algorithms secondary storage vector processing

来源：评论

学校读者我要写书评

暂无评论

A SUCCESSFUL ALGORITHM FOR THE UNDIRECTED HAMILTONIAN PATH PROBLEM

引用

DISCRETE APPLIED MATHEMATICS 1985年第2期10卷 179-195页

作者： THOMPSON, GL SINGHAL, S Management Science Research Group Graduate School of Industrial Administration Garnegie-Mellon University Pittsburgh PA 15213 USA

In this paper a polynomial algorithm called the Minram algorithm is presented which finds a Hamiltonian Path in an undirected graph with high frequency of success for graphs up to 1000 nodes. It first reintroduces the concept described in [13] and then explains the algorithm. Computational comparison with the algorithm by Posa [10] is given. It is shown that a Hamiltonian Path is a spanning arborescence with zero ramification index. Given an undirected graph, the Minram algorithm starts by finding a spanning tree which defines a unique spanning arborescence. By suitable pivots it locates a locally minimal value of the ramification index. If this local minima corresponds to zero ramification index then the algorithm is considered to have ended successfully, else a failure is reported. Computational performance of the algorithm on randomly generated Hamiltonian graphs is given. The random graphs used as test problems were generated using the procedure explained in Section 6.1. Comparison with our version of the Posa algorithm which we call Posa-ran algorithm [10] is also made.

关键词： Hamiltonian Paths Hamiltonian Cycles ramification index heuristic probabilistic algorithms

来源：评论

学校读者我要写书评

暂无评论

FACTORIZATION OF MULTIVARIATE POLYNOMIALS OVER FINITE-FIELDS

引用

MATHEMATICS OF COMPUTATION 1985年第171期45卷 251-261页

作者： VONZURGATHEN, J KALTOFEN, E Department of Computer Science University of Toronto Toronto ON M5S 1A4 Canada

Abstract: We present a probabilistic algorithm that finds the irreducible factors of a bivariate polynomial with coefficients from a finite field in time polynomial in the input size, i.e., in the degree of the polynomial and log (cardinality of field). The algorithm generalizes to multivariate polynomials and has polynomial running time for densely encoded inputs. A deterministic version of the algorithm is also discussed, whose running time is polynomial in the degree of the input polynomial and the size of the field.

关键词： Polynomial factorization multivariate polynomials finite fields probabilistic algorithms

来源：评论

学校读者我要写书评

暂无评论

ON APPROXIMATION algorithms FOR =P: 收藏
分享
引用; SIAM JOURNAL ON COMPUTING 1985年第4期14卷 849-861页; 作者： STOCKMEYER, L; The theme of this paper is to investigate to what extent approximation, possibly together with randomization, can reduce the complexity of problems in Valiant’s class # P. In general, any function in # P can be appro... 详细信息; The theme of this paper is to investigate to what extent approximation, possibly together with randomization, can reduce the complexity of problems in Valiant’s class # P. In general, any function in # P can be approximated to within any constant factor by a function in the class $Δ_{3}^{p}$; 来源：评论; 学校读者我要写书评

暂无评论

ASYNCHRONOUS CONSENSUS AND BROADCAST PROTOCOLS

引用

JOURNAL OF THE ACM 1985年第4期32卷 824-840页

作者： BRACHA, G TOUEG, S Department of Computer Science Cornell University 405 Upson Hall Ithaca NY Department of Computer Science Cornell University 405 Upson Hall Ithaca NY

A consensus protocol enables a system of n asynchronous processes, some of which are faulty, to reach agreement. There are two kinds of faulty processes: fail-stop processes that can only die and malicious processes that can also send false messages. The class of asynchronous systems with fair schedulers is defined, and consensus protocols that terminate with probability 1 for these systems are investigated. With fail-stop processes, it is shown that ⌈(n + 1)/2⌉ correct processes are necessary and sufficient to reach agreement. In the malicious case, it is shown that ⌈(2n + 1)/3⌉ correct processes are necessary and sufficient to reach agreement. This is contrasted with an earlier result, stating that there is no consensus protocol for the fail-stop case that always terminates within a bounded number of steps, even if only one process can fail. The possibility of reliable broadcast (Byzantine Agreement) in asynchronous systems is also investigated. Asynchronous Byzantine Agreement is defined, and it is shown that ⌈(2n + 1)/3⌉ correct processes are necessary and sufficient to achieve it.

关键词： Agreement problem asynchronous system Byzantine Generals problem consensus problem distributed computing fault tolerance impossibility proof probabilistic algorithms reliability

来源：评论

学校读者我要写书评

暂无评论

A probabilistic LOWER BOUND FOR CHECKING DISJOINTNESS OF SETS

引用

INFORMATION PROCESSING LETTERS 1984年第1期19卷 51-53页

作者： MANBER, U Department of Computer Science University of Wisconsin Madison WI 53706 U.S.A.

The question of how much time speedup can be achieved by permitting an algorithm to contain probabilistic choices and a small probability of error is considered. It is proved that, for a particular problem determining whether 2 sets are disjoint, the speedup is limited to a constant. A probabilistic lower bound is proved. This result extends the probabilistic lower bound result for the case of equal size sets and corrects an old error in the literature. A model of computation based on decision trees is used; the proof techniques are very similar to those introduced by Manber and Tompa (1982).

关键词： probabilistic algorithms lower bounds decision trees

来源：评论

学校读者我要写书评

暂无评论

SOME OBSERVATIONS ON THE probabilistic algorithms AND NP-HARD PROBLEMS

引用

INFORMATION PROCESSING LETTERS 1982年第1期14卷 39-43页

作者： KO, KI Department of Computer Science University of Houston Houston TX 77004 U.S.A.

Two sets of investigators have recently discovered polynomial time probabilistic algorithms with small error probability for a problem in NP conjoined with co-NP. The discovery raises the question whether probabilistic algorithms perhaps are more powerful than nondeterministic ones. More specifically, a question arises about the possibilities for discovering a polynomial time probabilistic algorithm with small error probability for some NP-hard problem. Through an analysis that draws from the work that led to the recent discovery, it is concluded that all NP-hard optimization problems have some probabilistic algorithms with small error bounds.

关键词： probabilistic algorithms polynomial time computation nondeterminism polynomial time hierarchy

来源：评论

学校读者我要写书评

暂无评论

EXPECTED-TIME COMPLEXITY RESULTS FOR HIERARCHIC CLUSTERING algorithms WHICH USE CLUSTER CENTERS

引用

INFORMATION PROCESSING LETTERS 1983年第5期16卷 237-241页

作者： MURTAGH, F Department of Computer Science University College Dublin Dublin 4 Ireland

Hierarchic clustering algorithms are being used for structuring and interpreting data; however, their practical use hinges on fast algorithms for implementing them. Although such algorithms exist, they suffer from 2 disadvantages - the ''chaining'' effect and the lack of a natural definition of ''cluster representative'' or cluster center. Widely used clustering methods that do not suffer from this 2nd disadvantage are the median method, the centroid method, and Ward's minimum variance method. Some recent algorithmic improvements in these methods have succeeded in making them computationally more efficient and of greater practical interest. These results are extended through the examination of fast expected-time results. For the median and centroid methods, where the cardinality of clusters is not used in the definition of dissimilarity between cluster centers, the expected-time performance is O(N). The expected time complexity of Ward's method is upper-bounded by O(N log N).

关键词： probabilistic algorithms dynamic searching nearest neighbours

来源：评论

学校读者我要写书评

暂无评论

全选清除本页清除全部题录导出标记到“检索档案”

共18页 << < 9 10 11 12 13 14 15 16 17 18 > >>

回到顶部

执行限定条件

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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