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

A Modular Cost Analysis for Probabilistic Programs

PROCEEDINGS OF THE ACM ON PROGRAMMING LANGUAGES-PACMPL 2020年第OOPSLA期4卷 1–30页

作者： Avanzini, Martin Moser, Georg Schaper, Michael INRIA Sophia Antipolis Valbonne France Univ Innsbruck Innsbruck Austria

We present a novel methodology for the automated resource analysis of non-deterministic, probabilistic imperative programs, which gives rise to a modular approach. Program fragments are analysed in full independence. Moreover, the established results allow us to incorporate sampling from dynamic distributions, making our analysis applicable to a wider class of examples, for example the Coupon Collector's problem. We have implemented our contributions in the tool eco-imp, exploiting a constraint-solver over iterative refineable cost functions facilitated by off-the-shelf SMT solvers. We provide ample experimental evidence of the prototype's algorithmic power. Our experiments show that our tool runs typically at least one order of magnitude faster than comparable tools. On more involved examples, it may even be the case that execution times of seconds become milliseconds. At the same time we retain the precision of existing tools. The extensions in applicability and the greater efficiency of our prototype, yield scalability of sorts. This effects into a wider class of examples, whose expected cost analysis can be thus be performed fully automatically.

关键词： probabilistic programs average complexity automation modularity

来源：评论

学校读者我要写书评

暂无评论

MOMENT INEQUALITIES FOR RANDOM-VARIABLES IN COMPUTATIONAL GEOMETRY

引用

COMPUTING 1983年第2期30卷 111-119页

作者： DEVROYE, L School of Computer Science McGill University Burnside Hall 805 Sherbrooke St. West H3A 2K6 Montreal P.Q. Canada

LetX1,...,X n be independent identically distributedRd-valued random vectors, and letA n =A(X1,...,X n ) be a subset of {X1,...,X n }, invariant under permutations of the data, and possessing the inclusion property (X1∈A n impliesX1∈A i for alli≤n). For example, the convex hull, the collection of all maximal vectors, the set of isolated points and other structures satisfy these *** n be the cardinality ofA n . We show that for allp≥1, there exists a universal constantC p >0 such thatE(N p n )≤C p max (1,Ep) where. This complements Jensen's lower bound for thep-th moment:E(N p n )≥Ep(N n ).The inequality is applied to the expected time analysis of algorithms in computational geometry. We also give necessary and sufficient conditions onE(N n ) for linear expected time behaviour of divide-and-conquer methods for findingA n .

关键词： Moment inequalities computational geometry convex hull maximal vector divide and conquer average complexity analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

An average analysis of backtracking on random constraint satisfaction problems

引用

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 2001年第1期33卷 21-37页

作者： Xu, K Li, W Beijing Univ Aeronaut & Astronaut Dept Comp Sci & Engn Natl Lab Software Dev Environm Beijing 100083 Peoples R China

In this paper we propose a random CSP model, called Model GB, which is a natural generalization of standard Model B. This paper considers Model GB in the case where each constraint is easy to satisfy. In this case Model GB exhibits non-trivial behaviour (not trivially satisfiable or unsatisfiable) as the number of variables approaches infinity. A detailed analysis to obtain an asymptotic estimate (good to 1+o(1)) of the average number of nodes in a search tree used by the backtracking algorithm on Model GB is also presented. It is shown that the average number of nodes required for finding all solutions or proving that no solution exists grows exponentially with the number of variables. So this model might be an interesting distribution for studying the nature of hard instances and evaluating the performance of CSP algorithms. In addition, we further investigate the behaviour of the average number of nodes as r (the ratio of constraints to variables) varies. The results indicate that as r increases, random CSP instances get easier and easier to solve, and the base for the average number of nodes that is exponential in n tends to 1 as r approaches infinity. Therefore, although the average number of nodes used by the backtracking algorithm on random CSP is exponential, many CSP instances will be very easy to solve when r is sufficiently large.

关键词： analysis of algorithms average complexity backtracking algorithms CSP

来源：评论

学校读者我要写书评

暂无评论

A Computationally Efficient Delayless Frequency-Domain Adaptive Filter Algorithm

引用

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS II-EXPRESS BRIEFS 2013年第4期60卷 222-226页

作者： Yang, Feiran Wu, Ming Yang, Jun Chinese Acad Sci Inst Acoust State Key Lab Acoust Beijing 100190 Peoples R China Chinese Acad Sci Inst Acoust Key Lab Noise & Vibrat Res Beijing 100190 Peoples R China

In acoustic echo cancellation (AEC) systems, the partitioned block frequency-domain adaptive filter (PBFDAF) algorithm is commonly adopted to improve the computational efficiency and convergence rate. However, the PBFDAF algorithm introduces an inherent delay. Delayless PBFDAF algorithms have been proposed to tackle this issue. However, the complexity of the existing delayless PBFDAF algorithms is high. Some have high average complexity, but others have high peak complexity. A computationally efficient delayless PBFDAF algorithm is proposed in this letter to reduce both the average and peak complexity. Moreover, a delay compensation method is presented to compensate the error path delay and thus speed up the convergence rate. Simulation results demonstrate that the convergence and tracking performance of the new algorithm with delay compensation is comparable with that of the PBFDAF algorithm.

关键词： Adaptive filter average complexity delayless algorithm echo cancellation frequency-domain adaptive filter (FDAF) peak complexity

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT COMPUTATION OF THE MAXIMUM OF THE SUM OF 2 SEQUENCES AND APPLICATIONS

引用

IEEE TRANSACTIONS ON COMPUTERS 1986年第7期35卷 651-653页

作者： KONRAD, V Hewlett-Packard Abstract Authors References Cited By Keywords Metrics Similar Download Citation Email Print Request Permissions 1+ b1 a2+ b2 ... an+ bn} trivially takes n additions. We show that if we are given the ranking for the a"s and the b"s separately then an algorithm exists which will..." property="og:description">

Computing max{a1+ b1, a2+ b2, ... ,an+ bn} trivially takes n additions. We show that if we are given the ranking for the a"s and the b"s separately, then an algorithm exists which will compute the maximum in ≅2n additions on the average. This can be generalized to yield an efficient algorithm to compute max{h(a1,b1), h(a2,b2),..., h(an, bn)} where h(x,y) is monotone increasing in x and y. Another generalization shows an efficient way of computing the maximum norm of a difference between two vectors. Applications are shown in pattern classification and computational geometry.

关键词： Analysis of algorithms average complexity computational geometry maximum norm pattern classification ranking

来源：评论

学校读者我要写书评

暂无评论

BACKTRACK - AN O(1) EXPECTED TIME ALGORITHM FOR THE GRAPH-COLORING PROBLEM

引用

INFORMATION PROCESSING LETTERS 1984年第3期18卷 119-121页

作者： WILF, HS Department of Mathematics University of Pennsylvania Philadelphia PA 19104 U.S.A.

The following NP-complete problem is considered: Given a graph G and a positive integer K, can the vertices of G be properly colored in K (or fewer) colors? It is shown that the backtrack search tree for this problem has an average of O(1) nodes, as V is equal to the absolute value of V(G) grows without bound. The NP-complete problem can thus be solved by an algorithm that certainly yields the correct answer. For example, a backtrack search tree for 3-coloring a graph has an average of approximately 197 nodes, averaged over all graphs of all sizes. This means that, typically, the algorithm will never even look at most of the input data and will stop with ''no.'' Although it is clear that this must happen often, it is noteworthy that it happens often enough that the few cases of exponentially long search time do not disturb the conclusion that the average search tree is of bounded size.

关键词： Algorithm graph coloring backtrack backtracking average complexity

来源：评论

学校读者我要写书评

暂无评论

Parametric random generation of deterministic tree automata

引用

THEORETICAL COMPUTER SCIENCE 2010年第38-39期411卷 3469-3480页

作者： Heam, Pierre-Cyrille Nicaud, Cyril Schmitz, Sylvain ENS Cachan LSV Cachan France CNRS Cachan France INRIA Cachan France CNRS Marne La Vallee France Univ Paris Est LIGM Marne La Vallee France INRIA Besancon France Univ Franche Comte LIFC F-25030 Besancon France

Uniform random generators deliver a simple empirical means to estimate the average complexity of an algorithm. We present a general rejection algorithm that generates sequential letter-to-letter transducers up to isomorphism. We also propose an original parametric random generation algorithm to produce sequential letter-to-letter transducers with a fixed number of transitions. We tailor this general scheme to randomly generate deterministic tree walking automata and deterministic top-down tree automata. We apply our implementation of the generator to the estimation of the average complexity of a deterministic tree walking automata to nondeterministic top-down tree automata construction we also implemented. (C) 2010 Elsevier B.V. All rights reserved.

关键词： Random generation average complexity Tree automaton

来源：评论

学校读者我要写书评

暂无评论

A NOTE ON CONTINUOUS SEARCH ALGORITHMS

引用

JOURNAL OF APPLIED PROBABILITY 1987年第1期24卷 277-280页

作者： GAREY, LE GUPTA, RD University of New Brunswick

Continuous random search methods with an average complexity given by O(log(1/ε)) for ε → 0 where ε is a given accuracy were presented in a recent paper. In this article an example of an O(log log(1/ε)) method is ... 详细信息

关键词： RANDOM SEARCH ROOT LOCATION METHODS average complexity

来源：评论

学校读者我要写书评

暂无评论

AN average-CASE ANALYSIS FOR A CONTINUOUS RANDOM SEARCH ALGORITHM

引用

ADVANCES IN APPLIED PROBABILITY 1985年第1期17卷 231-233页

作者： PFEIFER, D RHEIN WESTFAL TH AACHEN INST STAT & WIRTSCHAFTSMATHWULLNERSTR 3D-5100 AACHENFED REP GER

We give an upper bound for the average complexity (i.e. the expected number of steps until termination) for a continuous random search algorithm using results from renewal theory. It is thus possible to show that for a predefined accuracy ε, the average complexity of the algorithm is O(–log ε) for ε → 0 which is optimal up to a constant factor.

关键词： average complexity BINARY SEARCH RENEWAL THEORY

来源：评论

学校读者我要写书评

暂无评论

Probabilistic analysis of the pure literal heuristic for the satisfiability problem

引用

Annals of Operations Research 1984年第3期1卷 273-289页

作者： Franco, John Department of Computer Science Indiana University Bloomington 47405 IN United States

An algorithm for the SATISFIABILITY problem is presented and a probabilistic analysis is performed. The analysis is based on an instance distribution which is parametrized to simulate a variety of sample characteristics. The algorithm either correctly determines whether a given instance of SATISFIABILITY has a solution or gives up. It is shown that the algorithm runs in polynomial time and gives up with probability approaching zero as input size approaches infinity for a range of parameter values. This result is an improvement over the results in [3] and [4]. © 1984 J.C. Baltzer A.G., Scientific Publishing Company.

关键词： average complexity Davis-Putnam procedure heuristic pure literal satisfiability

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：