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

Dog bites postman: Point location in the moving Voronoi diagram and related problems

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 1998年第3期8卷 321-342页

作者： Devillers, O Golin, MJ INRIA F-06902 Sophia Antipolis France Hong Kong Univ Sci & Technol Kowloon Hong Kong

In this paper, we discuss two variations of the two-dimensional post-office problem that arise when the post-offices are n postmen moving with constant velocities. The first variation addresses the question: given a point q(0) and time t(0) who is the nearest postman to q(0) at time t(0)? We present a randomized incremental data structure that answers the query in expected O(log(2) n) time. The second variation views a query point as a dog searching for a postman to bite and finds the postman that a dog running with speed v(d) could reach first. While it is quite straightforward to design a data structure for the first problem, designing one for the second appears more difficult. We show that if the dog is quicker than all of the postmen then there is a nice correspondence between the problems. This correspondence will permit us to use the data structure developed for the first problem to solve the second one in O(log(2) n) time as well. The proposed structure is semi-dynamic, that is the set of postmen can be modified by inserting new postmen. A fully dynamic structure that also supports deletions can be obtained, but in that case the query time becomes O(log(3) n).

关键词： computational geometry moving points Voronoi Delaunay randomized algorithms dynamic algorithms localisation

来源：评论

学校读者我要写书评

暂无评论

Recursive algorithms for phylogenetic tree counting

引用

algorithms FOR MOLECULAR BIOLOGY 2013年第1期8卷 26-26页

作者： Gavryushkina, Alexandra Welch, David Drummond, Alexei J. Univ Auckland Dept Comp Sci Auckland 1 New Zealand Univ Auckland Allan Wilson Ctr Mol Ecol & Evolut Auckland 1 New Zealand

Background: In Bayesian phylogenetic inference we are interested in distributions over a space of trees. The number of trees in a tree space is an important characteristic of the space and is useful for specifying prior distributions. When all samples come from the same time point and no prior information available on divergence times, the tree counting problem is easy. However, when fossil evidence is used in the inference to constrain the tree or data are sampled serially, new tree spaces arise and counting the number of trees is more difficult. Results: We describe an algorithm that is polynomial in the number of sampled individuals for counting of resolutions of a constraint tree assuming that the number of constraints is fixed. We generalise this algorithm to counting resolutions of a fully ranked constraint tree. We describe a quadratic algorithm for counting the number of possible fully ranked trees on n sampled individuals. We introduce a new type of tree, called a fully ranked tree with sampled ancestors, and describe a cubic time algorithm for counting the number of such trees on n sampled individuals. Conclusions: These algorithms should be employed for Bayesian Markov chain Monte Carlo inference when fossil data are included or data are serially sampled.

关键词： Ranked tree Constraint tree Resolution Counting trees dynamic algorithms Bayesian tree prior Phylogenetics

来源：评论

学校读者我要写书评

暂无评论

INC - A LANGUAGE FOR INCREMENTAL COMPUTATIONS

引用

ACM TRANSACTIONS ON PROGRAMMING LANGUAGES AND SYSTEMS 1991年第2期13卷 211-236页

作者： YELLIN, DM STROM, RE IBM T. J. Watson Research Center Yorktown Heights NY IBM T. J. Watson Research Center Yorktown Heights NY

An incremental computation is one that is performed repeatedly on nearly identical inputs. Incremental computations occur naturally in many environments, such as compilers, language-based editors, spreadsheets, and formatters. This article describes a proposed tool for making it easy to write incremental programs. The tool consists of a programming language, INC, and a set of compile-time transformations for the primitive elements of INC. A programmer defines an algorithm in INC without regard to efficient incremental execution. The transformation automatically convert this algorithm into an efficient incremental algorithm. INC is a functional language. The implementation of an INC program is a network of processes. Each INC function is transformed into a process that receives and transmits messages describing changes to its inputs and outputs. We give an overview to the language and illustrate the incremental techniques employed by INC. We present the static and incremental complexity bounds for the primitive INC functions. We also present some example programs illustrating INC's flexibility.

关键词： LANGUAGES PERFORMANCE dynamic algorithms FINITE DIFFERENCING INCREMENTAL COMPLEXITY INCREMENTALITY STATIC COMPLEXITY

来源：评论

学校读者我要写书评

暂无评论

On the Domination Number of Cartesian Product of Two Directed Cycles

引用

JOURNAL OF APPLIED MATHEMATICS 2013年第unknown期2013卷 619695-1-619695-7页

作者： Shao, Zehui Zhu, Enqiang Lang, Fangnian Chengdu Univ Sch Informat Sci & Technol Chengdu 610106 Peoples R China Inst Higher Educ Sichuan Prov Key Lab Pattern Recognit & Intelligent Informat Chengdu 610106 Peoples R China Peking Univ Sch Elect Engn & Comp Sci Beijing 100871 Peoples R China

Denote by gamma(G) the domination number of a digraph G and C-m square C-n the Cartesian product of C-m and C-n, the directed cycles of length m, n >= 2. In 2010, Liu et al. determined the exact values of gamma(C-m square C-n) for m = 2, 3, 4, 5, 6. In 2013, Mollard determined the exact values of gamma(C-m square C-n) for m = 3k + 2. In this paper, we give lower and upper bounds of gamma(C-m square C-n) with m = 3k + 1 for different cases. In particular, inverted right perpendicular(2k + 1)n/2inverted left perpendicular <= gamma(C3k+1 square C-n) <= left perpendicular(2k + 1)n/2right perpendicular + k Based on the established result, the exact values of gamma(C-m square C-n) are determined for m = 7 and 10 by the combination of the dynamic algorithm, and an upper bound for gamma(C-13 square C-n) is provided.

关键词： On the Domination Number of Cartesian Product Two Directed Cycles Mentoring Upper bound Authoritarianism dynamic algorithms Cartesian product Exact

来源：评论

学校读者我要写书评

暂无评论

Discrete versus Continuous algorithms in dynamics of Affective Decision Making

引用

algorithms 2023年第9期16卷 416-416页

作者： Yukalov, Vyacheslav I. Yukalova, Elizaveta P. Joint Inst Nucl Res Bogolubov Lab Theoret Phys Dubna 141980 Russia Univ Sao Paulo Inst Fis Sao Carlos CP 369 BR-13560970 Sao Carlos Brazil Joint Inst Nucl Res Lab Informat Technol Dubna 141980 Russia

The dynamics of affective decision making is considered for an intelligent network composed of agents with different types of memory: long-term and short-term memory. The consideration is based on probabilistic affective decision theory, which takes into account the rational utility of alternatives as well as the emotional alternative attractiveness. The objective of this paper is the comparison of two multistep operational algorithms of the intelligent network: one based on discrete dynamics and the other on continuous dynamics. By means of numerical analysis, it is shown that, depending on the network parameters, the characteristic probabilities for continuous and discrete operations can exhibit either close or drastically different behavior. Thus, depending on which algorithm is employed, either discrete or continuous, theoretical predictions can be rather different, which does not allow for a uniquely defined description of practical problems. This finding is important for understanding which of the algorithms is more appropriate for the correct analysis of decision-making tasks. A discussion is given, revealing that the discrete operation seems to be more realistic for describing intelligent networks as well as affective artificial intelligence.

关键词： dynamic algorithms affective decision making dynamic decision making affective artificial intelligence probabilistic networks intelligent networks

来源：评论

学校读者我要写书评

暂无评论

The effect of delays in the Economic Dispatch Problem for smart grid architectures

The effect of delays in the Economic Dispatch Problem for sm...

引用

American Control Conference

作者： Christoforos Somarakis Dipankar Maity John S. Baras Applied Mathematics Dept. The Institute for Systems Research University of Maryland College Park 20742 USA Electrical & Computer Engineering Dept. The Institute for Systems Research University of Maryland College Park 20742 USA

ISBN: (纸本)9781467386838

We consider the Economic Dispatch Problem (EDP) in power systems for a smart-grid friendly environment. We develop a consensus based decentralized optimization algorithm that evolves in a time-varying communication network that suffers from multiple propagation time-dependent delays. This paper, being an improvisation of an earlier work of ours, addresses the effects of time dependent delays in a fully decentralized network. We show analytically and by simulation that propagation delays may not only affect the performance of the dynamic algorithm that solves the EDP but can also destabilize the system.

关键词： Delays Heuristic algorithms Optimization Generators Mathematical model Stability analysis Smart grids Smart grids Heuristic algorithms dynamos delay Stability analysis Mathematical Model Electronic Data Processing Dispatching dynamic algorithms Propagation delay Improvisation networks(communications)

来源：评论

学校读者我要写书评

暂无评论

First-Order Logic with Counting At Least, Weak Hanf Normal Forms Always Exist and Can Be Computed! 17

First-Order Logic with Counting At Least, Weak Hanf Normal F...

引用

Annual ACM/IEEE Symposium on Logic in Computer Science

作者： Dietrich Kuske Nicole Schweikardt TU Ilmenau Humboldt-Universitat zu Berlin

ISBN: (纸本)9781509030194

We introduce the logic FOCN(P) which extends first-order logic by counting and by numerical predicates from a set P, and which can be viewed as a natural generalisation of various counting logics that have been studied in the literature. We obtain a locality result showing that every FOCN(P)-formula can be transformed into a formula in Hanf normal form that is equivalent on all finite structures of degree at most d. A formula is in Hanf normal form if it is a Boolean combination of formulas describing the neighbourhood around its tuple of free variables and arithmetic sentences with predicates from P over atomic statements describing the number of realisations of a type with a single centre. The transformation into Hanf normal form can be achieved in time elementary in d and the size of the input formula. From this locality result, we infer the following applications: (1)The Hanf-locality rank of first-order formulas of bounded quantifier alternation depth only grows polynomially with the formula size. (2)The model checking problem for the fragment FOC(P) of FOCN(P) on structures of bounded degree is fixed-parameter tractable (with elementary parameter dependence). (3)The query evaluation problem for fixed queries from FOC(P) over fully dynamic databases of degree at most d can be solved efficiently: there is a dynamic algorithm that can enumerate the tuples in the query result with constant delay, and that allows to compute the size of the query result and to test if a given tuple belongs to the query result within constant time after every database update.

关键词： FOCN(P) Hanf normal transformation formula tuple Formal logic FIRST ORDER dynamic algorithms Normal

来源：评论

学校读者我要写书评

暂无评论

Lattice Data Analytics: The Poset of Irreducibles and the MacNeille Completion

Lattice Data Analytics: The Poset of Irreducibles and the Ma...

引用

IEEE International Conference on Intelligent Data Acquisition and Advanced Computing Systems

作者： George Markowsky Linda Markowsky Missouri Science & Technology University of Maine

ISBN: (纸本)9781728140704

Automated and semi-automated systems that derive actionable information from massive, heterogeneous datasets are essential for many applications. The reasoning of such systems must be as clear as possible in order to earn our trust. Lattices have begun to play a key role in computer science finding applications in distributed computing, programming languages, concurrency theory, and data mining, thereby justifying G. C. Rota's belief that lattice theory will play an important role in 21st Century mathematics. In some instances, researchers must deal with posets that are not necessarily lattices and the question arises how these posets can be embedded in lattices. A classic way to answer this question is to construct the MacNeille completion of the lattice, which is the most compact way to embed a poset into a lattice. In 1973 G. Markowsky introduced the poset of irreducibles construction in his dissertation and demonstrated that this was a very compact way to represent a lattice. In addition, the poset of irreducibles has many of the properties of the poset of join-irreducibles of distributive lattices that was introduced by G. Birkhoff and described in his book. In this paper, we show how to construct the poset of irreducibles for the MacNeille completion of a poset efficiently. We conclude with some applications of these ideas.

关键词： Poset of irreducibles Lattice data analytics MacNeille completion dynamic algorithms Poset dynamic algorithms crystal lattices Completion lattice theory

来源：评论

学校读者我要写书评

暂无评论

Improved Deterministic algorithms for Decremental Reachability and Strongly Connected Components

引用

ACM TRANSACTIONS ON algorithms 2013年第3期9卷 27-27页

作者： Lacki, Jakub Univ Warsaw Inst Informat PL-02097 Warsaw Poland

This article presents a new deterministic algorithm for decremental maintenance of the transitive closure in a directed graph. The algorithm processes any sequence of edge deletions in O(mn) time and answers queries in constant time. Previously, such time bound has only been achieved by a randomized Las Vegas algorithm. In addition to that, a few decremental algorithms for maintaining strongly connected components are shown, whose time complexity is O(n(1.5)) for planar graphs, O(n log n) for graphs with bounded treewidth and O(mn) for general digraphs.

关键词： algorithms dynamic algorithms decremental algorithms graph algorithms graphs strongly connected components transitive closure

来源：评论

学校读者我要写书评

暂无评论

Adaptive Clustering and CSI Acquisition for FDD Massive MIMO Systems with Two-level Precoding

Adaptive Clustering and CSI Acquisition for FDD Massive MIMO...

引用

IEEE Wireless Communications and Networking Conference

作者： Apostolos Destounis Marco Maso Mathematical and Algorithmic Sciences Lab Huawei Technologies France Research Center

ISBN: (纸本)9781467398152

In this paper, we target a massive multiple-input/multiple-output (MIMO) system operating in frequency-division duplexing (FDD) mode, assuming the adoption of a two-level linear precoding strategy at the BS. We propose a novel strategy to effectively acquire the channel state information (CSI) at the base station (BS). In particular, we devise a cross-layer dynamic algorithm for user grouping, CSI acquisition and user scheduling that takes into account fairness considerations, application characteristics and quality of service (QoS) constraints of the users. We assess the merit of the proposed algorithm for a proportional fairness objective by comparing its performance with what is achieved by a relevant baseline algorithm in which user grouping is static and based only on the second order statistics, i.e., joint space division and multiplexing (JSDM). Our numerical findings illustrate that the proposed algorithm outperforms the baseline in terms of both fairness and speed of convergence to a steady state, and for different network topologies.

关键词： multiple input multiple output systems Network topology disc drives dynamic algorithms prediction coding Bahamas Quality of service space division User groups BASELINE

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：