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

Ordinary interactive small-step algorithms, I

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC 2006年第2期7卷 363-419页

作者： Blass, Andreas Gurevich, Yuri Univ Michigan Dept Math Ann Arbor MI 48109 USA Microsoft Res Redmond WA 98052 USA

This is the first in a series of articles extending the abstract state machine thesis - that arbitrary algorithms are behaviorally equivalent to abstract state machines - to algorithms that can interact with their environments during a step rather than only between steps. In the present work, we describe, by means of suitable postulates, those interactive algorithms that (1) proceed in discrete, global steps;(2) perform only a bounded amount of work in each step;(3) use only such information from the environment as can be regarded as answers to queries;and (4) never complete a step until all queries from that step have been answered. We indicate how a great many sorts of interaction meet these requirements. We also discuss in detail the structure of queries and replies and the appropriate definition of equivalence of algorithms. Finally, motivated by our considerations concerning queries, we discuss a generalization of first-order logic in which the arguments of function and relation symbols are not merely tuples of elements but orbits of such tuples under groups of permutations of the argument places.

关键词： algorithms theory sequential algorithms interaction postulates equivalence of algorithms abstract state machines

来源：评论

学校读者我要写书评

暂无评论

Asymptotic optimality of degree-greedy discovering of independent sets in Configuration Model graphs

引用

STOCHASTIC PROCESSES AND THEIR APPLICATIONS 2021年 131卷 122-150页

作者： Jonckheere, Matthieu Saenz, Manuel Univ Buenos Aires Inst Calculo CONICET Buenos Aires DF Argentina Univ Buenos Aires Math Dept FCEyN Buenos Aires DF Argentina

Finding independent sets of maximum size in fixed graphs is well known to be an NP-hard task. Using scaling limits, we characterise the asymptotics of sequential degree-greedy explorations and provide sufficient conditions for this algorithm to find an independent set of asymptotically optimal size in large sparse random graphs with given degree sequences. In the special case of sparse Erdos-Renyi graphs, our results allow to give a simple proof of the so-called e-phenomenon identified by Karp and Sipser for matchings and to give an alternative characterisation of the asymptotic independence number. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Random graphs sequential algorithms Maximum independent sets Hydrodynamic limits

来源：评论

学校读者我要写书评

暂无评论

NUMERICAL EXPERIMENTS WITH ABS algorithms FOR LINEAR-SYSTEMS ON A PARALLEL MACHINE

引用

JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS 1989年第3期60卷 375-392页

作者： BERTOCCHI, M 1.Dipartimento di Matematica Statistica Informatica e Applicazioni Istituto Universitario Bergamo Italy

Numerical results are obtained on sequential and parallel versions of ABS algorithms for linear systems for both full matrices andq-band matrices. The results using the sequential algorithm on full matrices indicate the superiority of a particular implementation of the symmetric algorithm. The condensed form of the algorithm is well suited for implementation in a parallel environment, and results obtained on the IBM 4381 system favor a synchronous implementation over the asynchronous one. Results are obtained from sequential implementations of theLU, Cholesky, and symmetric algorithms of the ABS class forq-band matrices able to reduce memory storage. A simple parallelization of do-loops for calculating components gives interesting performances.

关键词： Linear systems of equations direct methods for dense matrices andq-band matrices sequential algorithms parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

Data skeletons: simultaneous estimation of multiple quantiles for massive streaming datasets with applications to density estimation

引用

STATISTICS AND COMPUTING 2007年第4期17卷 311-321页

作者： McDermott, James P. Babu, G. Jogesh Liechty, John C. Lin, Dennis K. J. Penn State Univ Dept Stat University Pk PA 16802 USA Penn State Univ Dept Marketing & Stat University Pk PA 16802 USA Penn State Univ Dept Supply Chain & Informat Syst University Pk PA 16802 USA

We consider the problem of density estimation when the data is in the form of a continuous stream with no fixed length. In this setting, implementations of the usual methods of density estimation such as kernel density estimation are problematic. We propose a method of density estimation for massive datasets that is based upon taking the derivative of a smooth curve that has been fit through a set of quantile estimates. To achieve this, a low-storage, single-pass, sequential method is proposed for simultaneous estimation of multiple quantiles for massive datasets that form the basis of this method of density estimation. For comparison, we also consider a sequential kernel density estimator. The proposed methods are shown through simulation study to perform well and to have several distinct advantages over existing methods.

关键词： sequential quantile estimation sequential density estimation online algorithms sequential algorithms cubic spline

来源：评论

学校读者我要写书评

暂无评论

Watershed transform: Definitions, algorithms and parallelization strategies

引用

Fundamenta Informaticae 2000年第1期41卷 187-228页

作者： Roerdink, Jos B.T.M. Meijster, Arnold

The watershed transform is the method of choice for image segmentation in the field of mathematical morphology. We present a critical review of several definitions of the watershed transform and the associated sequential algorithms, and discuss various issues which often cause confusion in the literature. The need to distinguish between definition, algorithm specification and algorithm implementation is pointed out. Various examples are given which illustrate differences between watershed transforms based on different definitions and/or implementations. The second part of the paper surveys approaches for parallel implementation of sequential watershed algorithms.

关键词： mathematical morphology parallel implementation sequential algorithms watershed definition watershed transform

来源：评论

学校读者我要写书评

暂无评论

BISTABLE BIORDERS: A sequential DOMAIN THEORY

引用

LOGICAL METHODS IN COMPUTER SCIENCE 2007年第2期3卷

作者： Laird, James Univ Sussex Dept Informat Brighton BN1 9RH E Sussex England

We give a simple order-theoretic construction of a Cartesian closed category of sequential functions. It is based on bistable biorders, which are sets with a partial order the extensional order - and a bistable coherence, which captures equivalence of program behaviour, up to permutation of top (error) and bottom (divergence). We show that monotone and bistable functions (which are required to preserve bistably bounded meets and joins) are strongly sequential, and use this fact to prove universality results for the bistable biorder semantics of the simply-typed lambda-calculus (with atomic constants), and an extension with arithmetic and recursion. We also construct a bistable model of SPCF, a higher-order functional programming language with non-local control. We use our universality result for the lambda-calculus to show that the semantics of SPCF is fully abstract. We then establish a direct correspondence between bistable functions and sequential algorithms by showing that sequential data structures give rise to bistable biorders, and that each bistable function between such biorders is computed by a sequential algorithm.

关键词： Domain Theory sequentiality Functional Programming Universality Full Abstraction sequential algorithms

来源：评论

学校读者我要写书评

暂无评论

sequential community mode estimation

引用

PERFORMANCE EVALUATION 2021年 152卷

作者： Jain, Shubham Anand Goenka, Shreyas Bapna, Divyam Karamchandani, Nikhil Nair, Jayakrishnan Indian Inst Technol Dept Elect Engn Mumbai Maharashtra India

We consider a population, partitioned into a set of communities, and study the problem of identifying the largest community within the population via sequential, random sampling of individuals. There are multiple sampling domains, referred to as boxes, which also partition the population. Each box may consist of individuals of different communities, and each community may in turn be spread across multiple boxes. The learning agent can, at any time, sample (with replacement) a random individual from any chosen box;when this is done, the agent learns the community the sampled individual belongs to, and also whether or not this individual has been sampled before. The goal of the agent is to minimize the probability of mis-identifying the largest community in a fixed budget setting, by optimizing both the sampling strategy as well as the decision rule. We propose and analyse novel algorithms for this problem, and also establish information theoretic lower bounds on the probability of error under any algorithm. In several cases of interest, the exponential decay rates of the probability of error under our algorithms are shown to be optimal up to constant factors. The proposed algorithms are further validated via simulations on real-world datasets. (C) 2021 Elsevier B.V. All rights reserved.

关键词： Mode estimation Limited precision sampling sequential algorithms Fixed budget Multi-armed bandits

来源：评论

学校读者我要写书评

暂无评论

COMPUTING THE ALL-PAIRS LONGEST CHAINS IN THE PLANE

引用

INTERNATIONAL JOURNAL OF COMPUTATIONAL GEOMETRY & APPLICATIONS 1995年第3期5卷 257-271页

作者： ATALLAH, MJ CHEN, DZ PURDUE UNIV DEPT COMP SCIW LAFAYETTEIN 47907 UNIV NOTRE DAME DEPT COMP SCI & ENGNNOTRE DAMEIN 46556

Many problems on sequences and on special kinds of graphs involve the computation of longest chains passing points in the plane. Given a set S of n points in the plane, we consider the problem of computing the matrix of longest chain lengths between all pairs of points in S, and the matrix of ''parent'' pointers that describes the n longest chain trees. We present a simple sequential algorithm for computing these matrices. Our algorithm runs in O(n(2)) time, and hence is optimal. We also present a rather involved parallel algorithm that computes these matrices in O((log n)(2)) time using O(n(2)/log n) processors in the CREW PRAM model. These matrices enable us to report, in O(1) time, the length of a longest chain between any two points in S by using one processor, and the actual chain by using k processors, where k is the number of points of S on that chain. The space complexity of the algorithms is O(n(2)).

关键词： COMPUTATIONAL GEOMETRY CREW PRAM INCREASING CHAINS LONGEST PATHS MONGE MATRICES PARALLEL algorithms sequential algorithms

来源：评论

学校读者我要写书评

暂无评论

Optimizing regular computations based on neural networks and Graph Traversal 14

Optimizing regular computations based on neural networks and...

引用

14th International Symposium on Intelligent Systems

作者： Mohammed, O. T. Heidari, M. S. Paznikov, A. A. St Petersburg Electrotech Univ LETI Dept Comp Sci Knowledge & Discovery Ul Prof Popova 5 St Petersburg 197376 Russia

In recent days we can see that multicore computers have the ability to easily manipulate digit numbers however as numbers get bigger the computation becomes more complex, the reason is that the size of both CPU registers and buses is limited. As a result, the arithmetic operations such as addition, subtraction, multiplication, and division for CPU become more complex to perform. For solving the problem of how to do computation on big digit numbers, a number of algorithms have been developed. However, the existing algorithms are noticeably slow because they operate on bits individually and are designed to run over single-core computers only. In this paper, an AI model is presented that performs a computation on tokens of 8 -digit numbers to assist boost the CPU computation performance.. (C) 2021 The Authors. Published by Elsevier B.V.

关键词： Node iteration algorithms sequential algorithms Parallel algorithms Neural networks

来源：评论

学校读者我要写书评

暂无评论

METHODOLOGY OF DATA DECOMPOSITION AND FORMAL SYNTHESIS OF COMPOSITION FORMS FOR REPRESENTATION OF DIGITAL SIGNAL PROCESSING BASIC OPERATIONS 24

METHODOLOGY OF DATA DECOMPOSITION AND FORMAL SYNTHESIS OF CO...

引用

24th International Crimean Conference Microwave & Telecommunication Technology (CriMiCo)

作者： Klimova, O. V. Russian Acad Sci Ural Branch Inst Engn Sci 34 Komsomolskaya Str Ekaterinburg 620219 Russia

ISBN: (纸本)9789663354125

The problem of parallel algorithm development is considered. The main content of a solution presented is development of formal law of information formation on parallel algorithm structures. The way proposed of a solution search is characterized initially by a single view on algorithmic and architectural subsystems of a parallel computation system. The main peculiarity of the solution presented is synthesis of general description of sequential and parallel algorithms for digital signal processing operations. The basis for solution presented is developed methodology of data decomposition. The main peculiarities of methodology presented are its functional nature and the general approach to data decomposition of any dimension. The basic steps of methodology presented are considered. The methodology is the basis for development of the formal model of the parallel computation organization. The synthesis method of composition form for digital signal processing basic operations is considered.

关键词： parallel algorithms signal processing algorithmic subsystems architectural subsystems data decomposition digital signal processing parallel algorithm development parallel computation system sequential algorithms

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：