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

INFORMATION PROCESSING LETTERS 1993年第5期45卷 261-267页

作者： LEE, DT PAPADOPOULOU, E Department of Electrical Engineering and Computer Science Northwestern University Evanston IL 60208 USA

Given nodes s and t, the quickest path problem is to find a path p from s to t, such that the total transmission time in the communication network for sigma units of data, with sigma greater than or equal to zero, from s to t is minimum among all possible paths from s to t in the network. An algorithm was developed for the single pair quickest path problem with a certain time complexity as a function of sigma. An extension of this algorithm solves the single source i.e. one to all quickest path problem. The all-pairs quickest path problem for a particular sigma can be solved with a certain time complexity by applying the single source quickest path algorithm several times. The all-pairs quickest path problem is discussed as a function of sigma. The network is preprocessed in such a way that given any pair of nodes, the quickest path is found to transmit data between the nodes for sigma greater than or equal to zero. The time complexity and data structure are discussed.

关键词： DESIGN OF algorithms analysis of algorithms DATA STRUCTURES GRAPH algorithms SHORTEST PATHS

来源：评论

学校读者我要写书评

暂无评论

Probabilistic Arithmetic Automata and Their Applications

引用

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS 2012年第6期9卷 1737-1750页

作者： Marschall, Tobias Herms, Inke Kaltenbach, Hans-Michael Rahmann, Sven CWI Life Sci Grp NL-1098 XG Amsterdam Netherlands Univ Bielefeld Genome Informat Grp Fac Technol D-33594 Bielefeld Germany Swiss Fed Inst Technol Computat Syst Biol Grp Dept Biosyst Sci & Engn CH-4058 Basel Switzerland Univ Duisburg Essen Fac Med Inst Human Genet D-45122 Essen Germany

We present a comprehensive review on probabilistic arithmetic automata (PAAs), a general model to describe chains of operations whose operands depend on chance, along with two algorithms to numerically compute the distribution of the results of such probabilistic calculations. PAAs provide a unifying framework to approach many problems arising in computational biology and elsewhere. We present five different applications, namely 1) pattern matching statistics on random texts, including the computation of the distribution of occurrence counts, waiting times, and clump sizes under hidden Markov background models;2) exact analysis of window-based pattern matching algorithms;3) sensitivity of filtration seeds used to detect candidate sequence alignments;4) length and mass statistics of peptide fragments resulting from enzymatic cleavage reactions;and 5) read length statistics of 454 and IonTorrent sequencing reads. The diversity of these applications indicates the flexibility and unifying character of the presented framework. While the construction of a PAA depends on the particular application, we single out a frequently applicable construction method: We introduce deterministic arithmetic automata (DAAs) to model deterministic calculations on sequences, and demonstrate how to construct a PAA from a given DAA and a finite-memory random text model. This procedure is used for all five discussed applications and greatly simplifies the construction of PAAs. Implementations are available as part of the MoSDi package. Its application programming interface facilitates the rapid development of new applications based on the PAA framework.

关键词： Probabilistic automaton text model hidden Markov model pattern matching statistics clump string algorithm analysis of algorithms alignment seed peptide mass fingerprinting DNA sequencing dynamic programming

来源：评论

学校读者我要写书评

暂无评论

New results on the old k-opt algorithm for the traveling salesman problem

引用

SIAM JOURNAL ON COMPUTING 1999年第6期28卷 1998-2029页

作者： Chandra, B Karloff, H Tovey, C Univ New Haven Dept Comp Sci W Haven CT 06516 USA Georgia Tech Coll Comp Atlanta GA 30332 USA Georgia Tech Sch Ind & Syst Engn Atlanta GA 30332 USA

Local search with k-change neighborhoods is perhaps the oldest and most widely used heuristic method for the traveling salesman problem, yet almost no theoretical performance guarantees for it were previously known. This paper develops several results, some worst-case and some probabilistic, on the performance of 2- and k-opt local search for the traveling salesman problem, with respect to both the quality of the solution and the speed with which it is obtained.

关键词： graph algorithms analysis of algorithms explicit machine computation and programs (in optimization heading) explicit machine computation and programs (in computer science heading)

来源：评论

学校读者我要写书评

暂无评论

SCHEDULING ON A HYPERCUBE

引用

INFORMATION PROCESSING LETTERS 1991年第6期40卷 323-328页

作者： SHEN, XJ REINGOLD, EM UNIV ILLINOIS DEPT COMP SCIURBANAIL 61801

We present a THETA(n2) worst-case-time algorithm to determine the minimum finishing time for a preemptive schedule of n independent jobs on a hypercube of fixed dimension.

关键词： HYPERCUBE SCHEDULING analysis of algorithms DESIGN OF algorithms COMPUTER ARCHITECTURE

来源：评论

学校读者我要写书评

暂无评论

Semi-online scheduling on two uniform machines with the known largest size

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2011年第4期21卷 393-408页

作者： Cai, Sheng-Yi Yang, Qi-Fan Zhejiang Univ Dept Math Hangzhou 310003 Zhejiang Peoples R China Wenzhou Univ Sch Math & Informat Sci Wenzhou 325035 Peoples R China

This paper investigates semi-online scheduling on two uniform machines with the known largest size. Denote by s (j) the speed of each machine, j=1,2. Assume 0 < s (1)a parts per thousand currency signs (2), and let... 详细信息

关键词： analysis of algorithms Scheduling Semi-online Competitive ratio Uniform machine

来源：评论

学校读者我要写书评

暂无评论

Engineering the Divide-and-Conquer Closest Pair Algorithm

引用

Journal of Computer Science & Technology 2007年第4期22卷 532-540页

作者：江铭辉古熙悠 Department of Computer Science Utah State University

We improve the famous divide-and-conquer algorithm by Bentley and Shamos for the planar closest-pair problem. For n points on the plane, our algorithm keeps the optimal O（n log n） time complexity and, using a circle-packing property, computes at most 7n/2 Euclidean distances, which improves Ge et al.＇s bound of （3n log n）/2 Euclidean distances. We present experimental results of our comparative studies on four different versions of the divide-and-conquer closest pair algorithm and propose two effective heuristics.

关键词： algorithmic engineering analysis of algorithms circle packing closest pair computational geometry

来源：评论

学校读者我要写书评

暂无评论

An Improved HEAPSORT Algorithm with nlogn-0.788928n Comparisons in the Worst Case

引用

Journal of Computer Science & Technology 2007年第6期22卷 898-903页

作者：王晓东吴英杰 College of Mathematics and Computer Science Fuzhou University

A new variant of HEAPSORT is presented in this paper. The algorithm is not an internal sorting algorithm in the strong sense, since extra storage for n integers is necessary. The basic idea of the new algorithm is similar to the classical sorting algorithm HEAPSORT, but the algorithm rebuilds the heap in another way. The basic idea of the new algorithm is it uses only one comparison at each node. The new algorithm shift walks down a path in the heap until a leaf is reached. The request of placing the element in the root immediately to its destination is relaxed. The new algorithm requires about n log n - 0.788928n comparisons in the worst case and n log n - n comparisons on the average which is only about 0.4n more than necessary. It beats on average even the clever variants of QUICKSORT, if n is not very small. The difference between the worst case and the best case indicates that there is still room for improvement of the new algorithm by constructing heap more carefully.

关键词： data structures analysis of algorithms heaps HEAPSORT

来源：评论

学校读者我要写书评

暂无评论

Locating phase transitions in computationally hard problems

引用

PRAMANA-JOURNAL OF PHYSICS 2010年第3期75卷 549-563页

作者： Ashok, B. Patra, T. K. Univ Hyderabad Adv Ctr Res High Energy Mat Hyderabad 500046 Andhra Pradesh India Univ Hyderabad Sch Phys Hyderabad 500046 Andhra Pradesh India

We discuss how phase-transitions may be detected in computationally hard problems in the context of anytime algorithms. Treating the computational time, value and utility functions involved in the search results in analogy with quantities in statistical physics, we indicate how the onset of a computationally hard regime can be detected and the transit to higher quality solutions be quantified by an appropriate response function. The existence of a dynamical critical exponent is shown, enabling one to predict the onset of critical slowing down, rather than finding it after the event, in the specific case of a travelling salesman problem (TSP). This can be used as a means of improving efficiency and speed in searches, and avoiding needless computations.

关键词： New applications of statistical mechanics analysis of algorithms heuristics phase transitions and critical phenomena

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT PARALLEL algorithms FOR STRING EDITING AND RELATED PROBLEMS: 收藏
分享
引用; SIAM JOURNAL ON COMPUTING 1990年第5期19卷 968-988页; 作者： APOSTOLICO, A ATALLAH, MJ LARMORE, LL MCFADDIN, S NASA AMES RES CTRADV COMP SCI RES INSTMOFFETT FIELDCA 94035 UNIV CALIF RIVERSIDE DEPT MATH & COMP SCIRIVERSIDECA 92521; The string editing problem for input strings x and y consists of transforming x into y by performing a series of weighted edit operations on x of overall minimum cost. An edit operation on x can be the deletion of a s... 详细信息; The string editing problem for input strings x and y consists of transforming x into y by performing a series of weighted edit operations on x of overall minimum cost. An edit operation on x can be the deletion of a symbol from x, the insertion of a symbol in x or the substitution of a symbol of x with another symbol. This problem has a well-known $O (| x | | y |)$; 关键词： 68Q25 string-to-string correction edit distances approximate string searching spelling correction longest common subsequence shortest paths grid graphs analysis of algorithms parallel computation cascading divide and conquer; 来源：评论; 学校读者我要写书评

暂无评论

On the performance of Dijkstra's third self-stabilizing algorithm for mutual exclusion and related algorithms

引用

DISTRIBUTED COMPUTING 2010年第1期23卷 43-60页

作者： Chernoy, Viacheslav Shalom, Mordechai Zaks, Shmuel Technion Israel Inst Technol Dept Comp Sci IL-32000 Haifa Israel TelHai Acad Coll IL-12210 Upper Galilee Israel

In Dijkstra (Commun ACM 17(11):643-644, 1974) introduced the notion of self-stabilizing algorithms and presented three such algorithms for the problem of mutual exclusion on a ring of n processors. The third algorithm is the most interesting of these three but is rather non intuitive. In Dijkstra (Distrib Comput 1:5-6, 1986) a proof of its correctness was presented, but the question of determining its worst case complexity-that is, providing an upper bound on the number of moves of this algorithm until it stabilizes-remained open. In this paper we solve this question and prove an upper bound of 3(13)/(18)n(2) + O(n) for the complexity of this algorithm. We also show a lower bound of 1(5)/(6)n(2) - O(n) for the worst case complexity. For computing the upper bound, we use two techniques: potential functions and amortized analysis. We also present a new-three state self-stabilizing algorithm for mutual exclusion and show a tight bound of (5)/(6)n(2) + O(n) for the worst case complexity of this algorithm. In Beauquier and Debas (Proceedings of the second workshop on self-stabilizing systems, pp 17.1-17.13, 1995) presented a similar three-state algorithm, with an upper bound of 5(3)/(4)n(2) + O(n) and a lower bound of (1)/(8)n(2) - O(n) for its stabilization time. For this algorithm we prove an upper bound of 1(1)/(2)n(2) + O(n) and show a lower bound of n(2) - O(n). As far Beauquier and Debas (Proceedings of the second workshop on self-stabilizing systems, pp 17.1-17.13, 1995) is better than the one in Dijkstra (Commun ACM 17(11): 643-644, 1974) and our algorithm is better than both.

关键词： analysis of algorithms Distributed computing Self-stabilization Mutual exclusion Ring Stabilization time Three-state algorithm Dijkstra's third algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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