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

32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

作者： Gulwani, S Necula, GC Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA

We describe a unified framework for random interpretation that generalizes previous randomized intraprocedural analyses, and also extends naturally to efficient interprocedural analyses. There is no such natural extension known for deterministic algorithms. We present a general technique for extending any intraprocedural random interpreter to perform a context-sensitive interprocedural analysis with only polynomial increase in running time. This technique involves computing random summaries of procedures, which are complete and probabilistically sound. As an instantiation of this general technique, we obtain the first polynomial-time randomized algorithm that discovers all linear relationships interprocedurally in a linear program. We also obtain the first polynomial-time randomized algorithm for precise interprocedural value numbering over a program with unary uninterpreted functions. We present experimental evidence that quantifies the precision and relative speed of the analysis for discovering linear relationships along two dimensions: intraprocedural vs. interprocedural, and deterministic vs. randomized. We also present results that show the variation of the error probability in the randomized analysis with changes in algorithm parameters. These results suggest that the error probability is much lower than the existing conservative theoretical bounds.

关键词： algorithms theory verification interprocedural analysis random interpretation randomized algorithm linear relationships uninterpreted functions interprocedural value numbering

来源：评论

学校读者我要写书评

暂无评论

A random graph approach to NMR sequential assignment 04

A random graph approach to NMR sequential assignment

引用

8th Annual International Conference on Computational Biology (RECOMB)

作者： Bailey-Kellogg, C Chainraj, S Pandurangan, G Dartmouth Coll Dept Comp Sci Sudikoff Lab 6211 Hanover NH 03755 USA Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

ISBN: (纸本)9781581137552

Nuclear magnetic resonance (NMR) spectroscopy allows scientists to study protein structure, dynamics and interactions in solution. A necessary first step for such applications is determining the resonance assignment, mapping spectral data to atoms and residues in the primary sequence. Automated resonance assignment algorithms rely on information regarding connectivity ( e. g., through-bond atomic interactions) and amino acid type, typically using the former to determine strings of connected residues and the latter to map those strings to positions in the primary sequence. Significant ambiguity exists in both connectivity and amino acid type information. This paper focuses on the information content available in connectivity alone and develops a novel random-graph theoretic framework and algorithm for connectivity-driven NMR sequential assignment. Our random graph model captures the structure of chemical shift degeneracy, a key source of connectivity ambiguity. We then give a simple and natural randomized algorithm for finding optimal assignments as sets of connected fragments in NMR graphs. The algorithm naturally and efficiently reuses substrings while exploring connectivity choices;it overcomes local ambiguity by enforcing global consistency of all choices. By analyzing our algorithm under our random graph model, we show that it can provably tolerate relatively large ambiguity while still giving expected optimal performance in polynomial time. We present results from practical applications of the algorithm to experimental datasets from a variety of proteins and experimental set-ups. We demonstrate that our approach is able to overcome significant noise and local ambiguity in identifying significant fragments of sequential assignments.

关键词： nuclear magnetic resonance (NMR) spectroscopy automated sequential resonance assignment random graph model randomized algorithm Hamiltonian path

来源：评论

学校读者我要写书评

暂无评论

A CLASS OF RANDOM NUMBER GENERATORS BASED ON WEYL SEQUENCE

引用

Applied Mathematics(A Journal of Chinese Universities) 2005年第4期20卷 483-490页

作者： Liang Heng Liu Qinghua Bai Fengshan Dept. of Math. Sci. Tsinghua Univ. Beijing 100084China.

The generation of good pseudo-random numbers is the base of many important fields in scientific computing, such as randomized algorithms and numerical solution of stochastic differential equations. In this paper, a class of random number generators （RNGs） based on Weyl sequence is proposed. The uniformity of those RNGs is proved theoretically. Statistical and numerical computations show the efficiency of the methods.

关键词： pseudo-random number randomized algorithm statistical test uniform distribution.

来源：评论

学校读者我要写书评

暂无评论

Duality between prefetching and queued writing with parallel disks

引用

SIAM JOURNAL ON COMPUTING 2005年第6期34卷 1443-1463页

作者： Hutchinson, DA Sanders, P Vitter, JS Carleton Univ Dept Syst & Comp Engn Ottawa ON K1S 5B6 Canada Univ Karlsruhe Fak Informat D-76128 Karlsruhe Germany Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA Duke Univ Durham NC 27706 USA

Parallel disks promise to be a cost effective means for achieving high bandwidth in applications involving massive data sets, but algorithms for parallel disks can be difficult to devise. To combat this problem, we de. ne a useful and natural duality between writing to parallel disks and the seemingly more difficult problem of prefetching. We first explore this duality for applications involving read-once accesses using parallel disks. We get a simple linear time algorithm for computing optimal prefetch schedules and analyze the efficiency of the resulting schedules for randomly placed data and for arbitrary interleaved accesses to striped sequences. Duality also provides an optimal schedule for prefetching plus caching, where blocks can be accessed multiple times. Another application of this duality gives us the first parallel disk sorting algorithms that are provably optimal up to lower-order terms. One of these algorithms is a simple and practical variant of multiway mergesort, addressing a question that had been open for some time.

关键词： caching external memory sorting load balancing lower bound prefetching randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

randomized RANSAC with T_d,d test

引用

IMAGE AND VISION COMPUTING 2004年第10期22卷 837-842页

作者： Matas, J Chum, O Czech Tech Univ Dept Cybernet Ctr Machine Percept CZ-12135 Prague Czech Republic Univ Surrey CVSSP Guildford GU2 7XH Surrey England

Many computer vision algorithms include a robust estimation step where model parameters are computed from a data set containing a significant proportion of outliers. The RANSAC algorithm is possibly the most widely used robust estimator in the field of computer vision. In the paper we show that under a broad range of conditions, RANSAC efficiency is significantly improved if its hypothesis evaluation step is randomized. A new randomized (hypothesis evaluation) version of the RANSAC algorithm, R-RANSAC, is introduced. Computational savings are achieved by typically evaluating only a fraction of data points for models contaminated with outliers. The idea is implemented in a two-step evaluation procedure. A mathematically tractable class of statistical preverification test of samples is introduced. For this class of preverification test we derive an approximate relation for the optimal setting of its single parameter. The proposed pre-test is evaluated on both synthetic data and real-world problems and a significant increase in speed is shown. (C) 2004 Elsevier B.V. All rights reserved.

关键词： RANSAC randomized algorithm epipolar geometry estimation

来源：评论

学校读者我要写书评

暂无评论

Linear regression and filtering under nonstandard assumptions (arbitrary noise)

引用

IEEE TRANSACTIONS ON AUTOMATIC CONTROL 2004年第10期49卷 1830-1835页

作者： Granichin, O St Petersburg State Univ Dept Math & Mech St Petersburg 198904 Russia

This note is devoted to parameter estimation in linear regression and filtering, where the observation noise does not possess any "nice" probabilistic properties. In particular, the noise might have an "Unknown-but-bounded" deterministic nature. The basic assumption is that the model regressors (inputs) are random. Optimal rates of convergence for the modified stochastic approximation and least-squares algorithms are established under some weak assumptions. Typical behavior of the algorithms in the presence of such deterministic noise is illustrated by numerical examples.

关键词： filtering linear regression parameter estimation prediction randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

Certified dense linear system solving

引用

JOURNAL OF SYMBOLIC COMPUTATION 2004年第4期37卷 485-510页

作者： Mulders, T Storjohann, A Univ Waterloo Sch Comp Sci Waterloo ON N2L 3G1 Canada COMIT AG CH-8004 Zurich Switzerland

A randomized algorithm is given for solving a system of linear equations over a principal ideal domain. The algorithm returns a solution vector which has minimal denominator. A certificate of minimality is also computed. A given system has a Diophantine solution precisely when the minimal denominator is one. Cost estimates are given for systems over the ring of integers and ring of polynomials with coefficients from a field. (C) 2003 Elsevier Ltd. All rights reserved.

关键词： linear system solution diophantine system solution integer matrix polynomial matrix randomized algorithm Las Vegas

来源：评论

学校读者我要写书评

暂无评论

Randomization helps to perform independent tasks reliably

引用

RANDOM STRUCTURES & algorithmS 2004年第1期24卷 11-41页

作者： Chlebus, BS Kowalski, DR Univ Colorado Dept Comp Sci & Engn Denver CO 80217 USA Warsaw Univ Inst Informat PL-02097 Warsaw Poland

This paper is about algorithms that schedule tasks to be performed in a distributed failure-prone environment, when processors communicate by message-passing, and when tasks are independent and of unit length. The processors work under synchrony and may fail by crashing. Failure patterns are imposed by adversaries. Linearly-bounded adversaries may fail up to a constant fraction of the processors. Weakly-adaptive adversaries have to select, prior to the start of an execution, a subset of processors to be failure-prone, and then may fail only the selected processors, at arbitrary steps, in the course of the execution. Strongly adaptive adversaries have a total number of failures as the only restriction on failure patterns. The measures of complexity are work, measured as the available processor steps, and communication, measured as the number of point-to-point messages. A randomized algorithm is developed, that attains both O(n log*n) expected work and O(n log*n) expected communication, against weakly-adaptive linearly-bounded adversaries, in the case when the numbers of tasks and processors are both equal to n. This is in contrast with performance of algorithms against strongly-adaptive linearly-bounded adversaries, which has to be Omega(n log n/log log n) in terms of work. (C) 2003 Wiley Periodicals, Inc.

关键词： distributed algorithm randomized algorithm message passing crash failures adaptive adversary independent tasks load balancing lower bound

来源：评论

学校读者我要写书评

暂无评论

Global value numbering using random interpretation 04

Global value numbering using random interpretation

引用

31st Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages

作者： Gulwani, S Necula, GC Univ Calif Berkeley Dept Elect Engn & Comp Sci Berkeley CA 94720 USA

ISBN: (纸本)9781581137293

We present a polynomial time randomized algorithm for global value numbering. Our algorithm is complete when conditionals are treated as non-deterministic and all operators are treated as uninterpreted functions. We are not aware of any complete polynomial-time deterministic algorithm for the same problem. The algorithm does not require symbolic manipulations and hence is simpler to implement than the deterministic symbolic algorithms. The price for these benefits is that there is a probability that the algorithm can report a false equality. We prove that this probability can be made arbitrarily small by controlling various parameters of the algorithm. Our algorithm is based on the idea of random interpretation, which relies on executing a program on a number of random inputs and discovering relationships from the computed values. The computations are done by giving random linear interpretations to the operators in the program. Both branches of a conditional are executed. At join points, the program states are combined using a random affine combination. We discuss ways in which this algorithm can be made more precise by using more accurate interpretations for the linear arithmetic operators and other language constructs.

关键词： global value numbering Herbrand equivalences random interpretation randomized algorithm uninterpreted functions

来源：评论

学校读者我要写书评

暂无评论

An efficient randomized algorithm for detecting circles

引用

COMPUTER VISION AND IMAGE UNDERSTANDING 2001年第2期83卷 172-191页

作者： Chen, TC Chung, KL Natl Taiwan Univ Sci & Technol Inst Comp Sci & Informat Engn Dept Informat Management Sect 4 Taipei 10672 Taiwan

Detecting circles from a digital image is very important in shape recognition. In this paper, an efficient randomized algorithm (RCD) for detecting circles is presented, which is not based on the Hough transform (HT). Instead of using an accumulator for saving the information of the related parameters in the HT-based methods, the proposed RCD does not need an accumulator. The main concept used in the proposed RCD is that we first randomly select four edge pixels in the image and define a distance criterion to determine whether there is a possible circle in the image: after finding a possible circle, we apply an evidence-collecting process to further determine whether the possible circle is a true circle or not. Some synthetic images with different levels of noises and some realistic images containing circular objects with some occluded circles and missing edges have been taken to test the performance. Experimental results demonstrate that the proposed RCD is faster than other HT-based methods for the noise level between the light level and the modest level. For a heavy noise level, the randomized HT could be faster than the proposed RCD, but at the expense of massive memory requirements. (C) 2001 Academic Press.

关键词： circle detection Hough transform randomized algorithm

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：