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

作者： Joseph Tassaroti Carnegie Mellon University

学位级别：博士

Concurrency and randomization are difcult to use correctly when program- ming. Because programs that use them no longer behave deterministically, pro- grammers must take into account the set of all possible interactions and random choices that may occur. Tis dissertation describes a logic for reasoning about programs using both of these efects. Te logic extends a recent concurrent sep- aration logic with ideas from denotational semantics for probabilistic and non- deterministic choice, along with principles for probabilistic relational reasoning originally developed for sequential programs. Te resulting logic is used to verify probabilistic behaviors of a randomized concurrent counter algorithm and a two- level concurrent skip list. Te soundness of the logic, as well as the proofs of these examples, have been mechanized in Coq.

关键词： concurrency program logics separation logic randomized algorithms verifcation

来源：评论

学校读者我要写书评

暂无评论

Efficient spoken term discovery using randomized algorithms

Efficient spoken term discovery using randomized algorithms

引用

2011 IEEE Workshop on Automatic Speech Recognition and Understanding, ASRU 2011

作者： Jansen, Aren Van Durme, Benjamin Human Language Technology Center of Excellence Center for Language and Speech Processing Johns Hopkins University 3400 N. Charles St. Baltimore MD 21218 United States

ISBN: (纸本)9781467303675

Spoken term discovery is the task of automatically identifying words and phrases in speech data by searching for long repeated acoustic patterns. Initial solutions relied on exhaustive dynamic time warping-based searches across the entire similarity matrix, a method whose scalability is ultimately limited by the O(n2) nature of the search space. Recent strategies have attempted to improve search efficiency by using either unsupervised or mismatched-language acoustic models to reduce the complexity of the feature representation. Taking a completely different approach, this paper investigates the use of randomized algorithms that operate directly on the raw acoustic features to produce sparse approximate similarity matrices in O(n) space and O(n log n) time. We demonstrate these techniques facilitate spoken term discovery performance capable of outperforming a model-based strategy in the zero resource setting. © 2011 IEEE.

关键词： randomized algorithms similarity matrix Scalability Searches Acoustic models Acoustics

来源：评论

学校读者我要写书评

暂无评论

randomized algorithms for Comparison-based Search 11

Randomized Algorithms for Comparison-based Search

引用

Annual Conference on Neural Information Processing Systems

作者： Dominique Tschopp Suhas Diggavi Payam Delgosha Soheil Mohajer AWK Group Bern Switzerland University of California Los Angeles (UCLA) Los Angeles CA 90095 Sharif University of Technology Tehran Iran Princeton University Princeton NJ 08544

ISBN: (纸本)9781618395993

This paper addresses the problem of finding the nearest neighbor (or one of the R-nearest neighbors) of a query object q in a database of n objects, when we can only use a comparison oracle. The comparison oracle, given two reference objects and a query object, returns the reference object most similar to the query object. The main problem we study is how to search the database for the nearest neighbor (NN) of a query, while minimizing the questions. The difficulty of this problem depends on properties of the underlying database. We show the importance of a characterization: combinatorial disorder D which defines approximate triangle inequalities on ranks. We present a lower bound of Ω(D log n/D + D~2) average number of questions in the search phase for any randomized algorithm, which demonstrates the fundamental role of D for worst case behavior. We develop a randomized scheme for NN retrieval in O(D~3 log~2 n + D log~2 n log log n~D~3 ) questions. The learning requires asking O(nD~3 log~2 n + D log~2 n log log n~D~3) questions and O(n log~2 n/ log(2D)) bits to store.

关键词： randomized algorithms Nearest neighbor Database Information retrieval systems-Teletext and videotex Learning

来源：评论

学校读者我要写书评

暂无评论

randomized algorithms for the on-line minimum matching problem on Euclidean space

引用

INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS 1995年第1-2期58卷 19-32页

作者： Tsai, YT Tang, CY Chen, YY NATL TSING HUA UNIV DEPT COMP SCIHSINCHU 300TAIWAN

Suppose we are given two sets R and B, each of n points in the plane. Define the cost of a matching to be the teal distance of the edges in the, matching. The minimum matching problem on Euclidean space is to find a complete bipartite matching which has the minimum cost on Euclidean space. In this paper, we are interested in the on-line minimum matching problem on Euclidean space. We assume the set R is known, but the points of set B are revealed one by one. When a point of set B arrives, we must decide what match to make involving the point. None of the matches can be changed after they are made. The on-line minimum matching problem on Euclidean space tries to minimize the cost of the complete bipartite matching that we find. This paper proposes a family of randomized algorithms, Algorithm RM(m) (1 less than or equal to m less than or equal to n), for solving this problem. When a point in the set B arrived, Algorithm RM(m) randomly chooses at most m unmatched points in the set R, and adds the minimum edge between the arriving point and the chosen points to the matching. In each decision step, the algorithm only runs in O(m) time, which is superior to the known non-randomized algorithms for this problem. In this paper, we show that Algorithm RM(m) is not a competitive on-line algorithm for 1 less than or equal to m less than or equal to n-1. However, we further show that if 2n is large, the average cost incurred by Algorithm RM(m) (1 less than or equal to m less than or equal to n) is bounded by O(root n) times the average cost of the optimal Euclidean minimum matching.

关键词： analysis of algorithms on-line algorithms randomized algorithms the on-line minimum matching problem competitive analysis average case analysis

来源：评论

学校读者我要写书评

暂无评论

Soft fault diagnosis in analog electronic circuits: Sensitivity analysis by randomized algorithms.

Soft fault diagnosis in analog electronic circuits: Sensitiv...

引用

18th IEEE Instrumentation and Measurement Technology Conference (IMTC/2001)

作者： Alippi, C Catelani, M Fort, A Politecn Milan Dept Elect & Informat I-20133 Milan Italy

ISBN: (纸本)0780366468

In this paper a fault diagnosis technique for electronic analog circuits is described. Diagnosis is obtained by comparing input-output measurements with examples contained in a fault dictionary, by means of a neural classifier. A harmonic analysis is used, i.e. the test input stimuli are sinusoidal waves. A novel method for optimizing the fault dictionary construction is proposed. In particular, the stimuli selection is optimized by means of a sensitivity analysis of the Circuit Under Test -CUT- relying on a probabilistic approach based on randomized algorithms. This technique allows removing all the hypothesis assumed by the related literature. In fact it allows to remove the small perturbation assumption and presents a poly-time solution independently from the dimension of the perturbation..

关键词： randomized algorithms sensitivity analysis radial basis function networks fault diagnosis neural classifiers

来源：评论

学校读者我要写书评

暂无评论

randomized algorithms for Scheduling VMs in the Cloud

Randomized Algorithms for Scheduling VMs in the Cloud

引用

Annual IEEE International Conference on Computer Communications

作者： Javad Ghaderi Electrical Engineering Department Columbia University

ISBN: (纸本)9781467399548

We consider the problem of scheduling VMs (Virtual Machines) in a multi-server system motivated by cloud computing applications. VMs arrive dynamically over time and require various amounts of resources (e.g., CPU, Memory, Storage, etc.) for the duration of their service. When a VM arrives, it is queued and later served by one of the servers that has sufficient remaining capacity to serve it. The scheduling of VMs is subject to: (i) packing constraints, i.e., multiple VMs can be be served simultaneously by a single server if their cumulative resource requirement does not violate the capacity of the server, and (ii) non-preemption, i.e., once a VM is scheduled in a server, it cannot be interrupted or migrated to another server. To achieve maximum throughput, prior results hinge on solving a hard combinatorial problem (Knapsack) at the instances that all the servers become empty (the so-called global refresh times which require synchronization among the servers). The main contribution of this paper is that it resolves these issues. Specifically, we present a class of randomized algorithms for placing VMs in the servers that can achieve maximum throughput without preemptions. The algorithms are naturally distributed, have low complexity, and each queue needs to perform limited operations. Further, our algorithms display good delay performance in simulations, comparable to delay of heuristics that may not be throughput-optimal, and much better than the delay of the prior known throughput-optimal algorithms.

关键词： Servers randomized algorithms virtual machines Voltmeter server systems Queue

来源：评论

学校读者我要写书评

暂无评论

randomized algorithms for Optimal Robust Performance Controller Design

Randomized Algorithms for Optimal Robust Performance Control...

引用

第十九届中国控制会议

作者： Chunlei Song Long Wang Lin Huang Center for Systems and Control Department of Mechanics and Engineering Science Peking University, Beijing, 100871, P.R.China

In this paper efficient randomized algorithms are constructed to solve optimal robust performance controller design problems. The randomized algorithms here are based on a property from statistical learning theory known as uniform convergence of empirical means (UCEM). It is argued that in order to assess the performance of a controller as the plant varies over a prespecified family, it is better to use the average performance of the controller as the objective function to be minimized, rather than its worst-case performance. The approach is illustrated to be efficient through an example.

关键词： randomized algorithms statistical learning theory optimal robust performance controller design

来源：评论

学校读者我要写书评

暂无评论

randomized algorithms for Robustness Analysis:a Distributed Approach

Randomized Algorithms for Robustness Analysis:a Distributed ...

引用

Joint 48th IEEE Conference on Decision and Control and 28th Chinese Control Conference

作者： Giuseppe Carlo Calafiore Dipartimento di Automatica e Informatica Politecnico di Torino

randomized algorithms are a useful tool for analyzing the performance of complex uncertain systems. Their implementation requires the generation of a large number N of random samples representing the uncertainty scenarios, and the corresponding evaluation of system performance. When N is very large and/or performance evaluation is costly or time consuming, it can be necessary to distribute the computational burden of such algorithms among many cooperating computing units. This paper studies distributed versions of randomized algorithms for expected value and probability estimation over a network of computing nodes with possibly time-varying communication links. Explicit a-priori bounds are provided for the sample and communication complexity of these algorithms in terms of number of local samples, number of computing nodes and communication iterations.

关键词： randomized algorithms Probabilistic robustness Distributed estimation Consensus and agreement problems

来源：评论

学校读者我要写书评

暂无评论

Weighted randomized algorithms for efficient load balancing in distributed computing environments

引用

Materials Today: Proceedings 2020年 33卷 3782-3786页

作者： Maniza Hijab Avula Damodaram CSED MJCET Hyderabad India School of Information Technology JNTU Hyderabad India

randomized algorithms for resource choice make use of information concerning the spread of their keyed-in data by using random samples. This can effectively improve resource utilization but can create a load imbalance naturally due to the randomness of its input space. For specific problems it is helpful to use a helper to direct the solution space in the right direction. In this paper, to enact effective resource utilization combined with optimized load balancing, a weighted randomized resource assignment algorithm is proposed. The simulation results using standard workload format datasets reveal that the proposed algorithm outperforms existing solutions in average resource utilization by 8% to 12% while improving on load balance by 5% to 11%.

关键词： Grid computing Load balancing randomized algorithms Resource utilization Task scheduling

来源：评论

学校读者我要写书评

暂无评论

Combinatorial structure and randomized subexponential algorithms for infinite games

引用

THEORETICAL COMPUTER SCIENCE 2005年第3期349卷 347-360页

作者： Björklund, H Vorobyov, S Uppsala Univ Dept Informat Technol SE-75105 Uppsala Sweden

The complexity of solving infinite games, including parity, mean payoff, and simple stochastic, is an important open problem in verification, automata, and complexity theory. In this paper, we develop an abstract setting for studying and solving such games, based on function optimization over certain discrete structures. We introduce new classes of recursively local-global (RLG) and partial recursively local-global (PRLG) functions, and show that strategy evaluation functions for simple stochastic, mean payoff, and parity games belong to these classes. In this setting, we suggest randomized subexponential algorithms appropriate for RLG- and PRLG-function optimization. We show that the subexponential algorithms for combinatorial linear programming, due to Kalai and Matousek, Sharir, Welzl, can be adapted for optimizing the RLG- and PRLG-functions. (c) 2005 Elsevier B.V. All rights reserved.

关键词： mean payoff games simple stochastic games parity games Pseudo-Boolean optimization completely unimodal functions combinatorial linear programming randomized algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：