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

31st ACM Symposium on Parallelism in algorithms and Architecturess (SPAA)

作者： Pelc, Andrzej Yadav, Ram Narayan Univ Quebec Outaouais Dept Informat Gatineau PQ J8X 3X7 Canada Indian Inst Informat Technol Dept Comp Sci & Engn Dharwad Karnataka India

ISBN: (纸本)9781450361842

Two anonymous mobile agents navigate synchronously in an anonymous graph and have to meet at a node, using a deterministic algorithm. This is a symmetry breaking task called rendezvous, equivalent to the fundamental task of leader election between the agents. When is this feasible in a completely anonymous environment? It is known that agents can always meet if their initial positions are nonsymmetric, and that if they are symmetric and agents start simultaneously then rendezvous is impossible. What happens for symmetric initial positions with non-simultaneous start? Can symmetry between the agents be broken by the delay between their starting times? In order to answer these questions, we consider space-time initial configurations (abbreviated by STIC). A STIC is formalized as [(u, v), delta], where u and v are initial nodes of the agents in some graph and delta is a non-negative integer that represents the difference between their starting times. A STIC is feasible if there exists a deterministic algorithm, even dedicated to this particular STIC, which accomplishes rendezvous for it. Our main result is a characterization of all feasible STICs and the design of a universal deterministic algorithm that accomplishes rendezvous for all of them without any a priori knowledge of the agents. Thus, as far as feasibility is concerned, we completely solve the problem of symmetry breaking between two anonymous agents in anonymous graphs. Moreover, we show that such a universal algorithm cannot work for all feasible STICs in time polynomial in the initial distance between the agents.

关键词： Anonymous graph Anonymous agent Rendezvous Symmetry breaking universal algorithm

来源：评论

学校读者我要写书评

暂无评论

Fluid velocity based simulation of hydraulic fracture: a penny shaped modelpart I: the numerical algorithm

引用

MECCANICA 2018年第15期53卷 3615-3635页

作者： Peck, Daniel Wrobel, Michal Perkowska, Monika Mishuris, Gennady Aberystwyth Univ Aberystwyth Dyfed Wales AGH Univ Sci & Technol Krakow Poland EnginSoft SpA Trento Italy

In the first part of this paper, a universal fluid velocity based algorithm for simulating hydraulic fracture with leak-off, previously demonstrated for the PKN and KGD models, is extended to obtain solutions for a penny-shaped crack. The numerical scheme is capable of dealing with both the viscosity and toughness dominated regimes, with the fracture being driven by a power-law fluid. The computational approach utilizes two dependent variables;the fracture aperture and the reduced fluid velocity. The latter allows for the application of a local condition of the Stefan type (the speed equation) to trace the fracture front. The obtained numerical solutions are carefully tested using various methods, and are shown to achieve a high level of accuracy.

关键词： Penny-shaped crack Hydraulic fracture universal algorithm Power law fluid Leak-off Speed equation

来源：评论

学校读者我要写书评

暂无评论

universal Coding with Point Type Classes 51

Universal Coding with Point Type Classes

引用

51st Annual Conference on Information Sciences and Systems (CISS)

作者： Iri, Nematollah Kosut, Oliver Arizona State Univ Sch Elect Comp & Energy Engn Tempe AZ 85287 USA

ISBN: (纸本)9781509047802

With a customized characterization of types, every universal one-to-one coding algorithm can be described as follows: assign sequences to binary strings based on their type class sizes from smallest to largest. With this view, the universal coding problem is to optimally characterize types. In this paper, this Type Size approach is studied for universal source coding of an exponential family of distributions, using the most natural type class definition: two sequences are in the same type class if and only if they are indistinguishable in the sense that they have the same probability for every distribution in the family. This characterization is called the point type class. Exact third-order coding rate is derived for the resulting compression algorithm, revealing that the point type approach, while natural, is suboptimal compared to the quantized type method, which was previously proposed by the authors.

关键词： universal algorithm Fine asymptotics Data compression Finite blocklength analysis

来源：评论

学校读者我要写书评

暂无评论

The Markov Chain Tree Theorem in commutative semirings and the State Reduction algorithm in commutative semifields

引用

LINEAR ALGEBRA AND ITS APPLICATIONS 2015年 468卷 184-196页

作者： Gursoy, Buket Benek Kirkland, Steve Mason, Oliver Sergeev, Sergei Irish Ctr High End Comp Dublin 2 Ireland Natl Univ Ireland Maynooth Hamilton Inst Maynooth Kildare Ireland Univ Manitoba Dept Math Winnipeg MB R3T 2N2 Canada Univ Birmingham Sch Math Edgbaston B15 2TT W Midlands England

We extend the Markov Chain Tree Theorem to general commutative semirings, and we generalize the State Reduction algorithm to general commutative semifields. This leads to a new universal algorithm, whose prototype is the State Reduction algorithm which computes the Markov chain tree vector of a stochastic matrix. (C) 2014 The Authors. Published by Elsevier Inc.

关键词： Markov chain universal algorithm

来源：评论

学校读者我要写书评

暂无评论

The best choice problem for upward directed graphs

引用

DISCRETE OPTIMIZATION 2012年第3期9卷 200-204页

作者： Sulkowska, Malgorzata Wroclaw Univ Technol Inst Math & Comp Sci PL-50370 Wroclaw Poland

We consider a generalization of the best choice problem to upward directed graphs. We describe a strategy for choosing a maximal element (i.e., an element with no outgoing edges) when a selector knows in advance only the number n of vertices of the graph. We show that, as long as the number of elements dominated directly by the maximal ones is not greater than c(1)root n for some positive constant c(1) and the indegree of remaining vertices is bounded by a constant D, the probability p(n) of the right choice according to our strategy satisfies lim inf(n ->infinity) p(n) root n >= delta > 0, where delta is a constant depending on c(1) and D. (c) 2012 Elsevier B.V. All rights reserved.

关键词： Directed graph Secretary problem Best choice universal algorithm

来源：评论

学校读者我要写书评

暂无评论

A universal Online Caching algorithm Based on Pattern Matching

引用

algorithmICA 2010年第1期57卷 62-73页

作者： Pandurangan, Gopal Szpankowski, Wojciech Purdue Univ Dept Comp Sci W Lafayette IN 47907 USA

We present a universal algorithm for the classical online problem of caching or demand paging. We consider the caching problem when the page request sequence is drawn from an unknown probability distribution and the goal is to devise an efficient algorithm whose performance is close to the optimal online algorithm which has full knowledge of the underlying distribution. Most previous works have devised such algorithms for specific classes of distributions with the assumption that the algorithm has full knowledge of the source. In this paper, we present a universal and simple algorithm based on pattern matching for mixing sources (includes Markov sources). The expected performance of our algorithm is within 4+o(1) times the optimal online algorithm (which has full knowledge of the input model and can use unbounded resources).

关键词： Online computation Caching universal algorithm Stochastic model

来源：评论

学校读者我要写书评

暂无评论

A universal Scheme for Wyner-Ziv Coding of Discrete Sources

引用

IEEE TRANSACTIONS ON INFORMATION THEORY 2010年第4期56卷 1737-1750页

作者： Jalali, Shirin Verdu, Sergio Weissman, Tsachy CALTECH Ctr Math Informat Pasadena CA 91125 USA Princeton Univ Dept Elect Engn Princeton NJ 08544 USA Stanford Univ Dept Elect Engn Stanford CA 94305 USA

We consider the Wyner-Ziv (WZ) problem of lossy compression where the decompressor observes a noisy version of the source, whose statistics are unknown. A new family of WZ coding algorithms is proposed and their universal optimality is proven. Compression consists of sliding-window processing followed by Lempel-Ziv (LZ) compression, while the decompressor is based on a modification of the discrete universal denoiser (DUDE) algorithm to take advantage of side information. The new algorithms not only universally attain the fundamental limits, but also suggest a paradigm for practical WZ coding. The effectiveness of our approach is illustrated with experiments on binary images, and English text using a low complexity algorithm motivated by our class of universally optimal WZ codes.

关键词： Discrete denoising rate-distortion function sliding-window coding universal algorithm Wyner-Ziv coding

来源：评论

学校读者我要写书评

暂无评论

Improvement of Escape Time algorithm by No-Escape-Point

Improvement of Escape Time Algorithm by No-Escape-Point

引用

2010 4th International Conference on Intelligent Information Technology Application (IITA2010)

作者： FU Weina,LIU Shuai College of Software Changchun Institute of technology Changchun,China CHE Xiangjiua,WANG Zhengxuan College of Computer Science and Technology Jilin University Changchun,China

Escape time algorithm is an universal algorithm when creating fractal image.A class of algorithms based on escape time algorithm is *** this essay,combined with the feature of eventually periodic point of functions,we define a class of points as no-escape *** analyze the shortcomings of the classic algorithm,we improve the escape time algorithm base on the no-escape *** analyze the algorithm and put forward the best application scope for *** creating fractal figures,we find figures created by the two algorithms are consistent with each other except a few escape *** compare the complexity between the two algorithms and find the iteration times by the improved algorithm are less than escape time algorithm when creating the fractal *** do several experiments and find the improved algorithm is universal and it reduces time wasting.

关键词： fractal escape time compute efficiency universal algorithm no escape point

来源：评论

学校读者我要写书评

暂无评论

An automatic code generator for nonuniform random variate generation

引用

MATHEMATICS AND COMPUTERS IN SIMULATION 2003年第3-6期62卷 405-412页

作者： Leydold, J Derflinger, G Tirler, G Hörmann, W Univ Econ & Business Adm Dept Appl Stat & Data Proc A-1090 Vienna Austria Bogazici Univ IE Dept TR-80815 Bebek Turkey

There exists a vast literature on nonuniform random variate generators. Most of these generators are especially designed for a particular distribution. However, in pratice only a few of these are available to practioners. Moreover, for problems as (e.g.) sampling from the truncated normal distribution or sampling from fairly uncommon distributions there are often no algorithms available. In the last decade so called universal methods have been developed for these cases. The resulting algorithms are fast and have properties that make them attractive even for standard distributions. In this contribution we describe the concept of Automatic random variate generation where these methods are used to produce a single piece of code in a high level programming language. Using a web-based front-end to such a program this is an easy-to-use source for researchers and programmers for high quality generators for a large class of distributions. Using our UNURAN library we have implemented such a system, which is accessable at http://***/anuran. (C) 2003 IMACS. Published by Elsevier Science B.V. All rights reserved.

关键词： nonuniform random variate generation universal algorithm automatic code generator transformed density rejection continuous distribution

来源：评论

学校读者我要写书评

暂无评论

An automatic code generator for nonuniform random variate generation

An automatic code generator for nonuniform random variate ge...

引用

3rd IMACS Seminar on Monte Carlo Methods (MCM 2001)

作者： Leydold, J Derflinger, G Tirler, G Hörmann, W Univ Econ & Business Adm Dept Appl Stat & Data Proc A-1090 Vienna Austria Bogazici Univ IE Dept TR-80815 Bebek Turkey

关键词： nonuniform random variate generation universal algorithm automatic code generator transformed density rejection continuous distribution

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：