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

A note on extending equivalence theories of algorithms

Information Processing Letters 1974年第2期3卷 54-56页

作者： Kobayashi, Kojiro Department of Information Science Tokyo Institute of Technology Meguro-ku Tokyo 152 Oh-okayama Japan

来源：评论

学校读者我要写书评

暂无评论

AN equivalence BETWEEN 2 algorithms FOR QUADRATIC-PROGRAMMING

引用

MATHEMATICAL PROGRAMMING 1981年第2期20卷 152-165页

作者： PANG, JS Graduate School of Industrial Administration Carnegie-Mellon University 15213 Pittsburgh PA USA

In this paper, we demonstrate that the Van de Panne—Whinston symmetric simplex method when applied to a certain implicit formulation of a quadratic program generates the same sequence of primal feasible vectors as does the Von Hohenbalken simplicial decomposition algorithm specialized to the same program. Such an equivalence of the two algorithms extends earlier results for a least-distance program due to Cottle—Djang.

关键词： Column Generation equivalence of algorithms Quadratic Programming Simplicial Decomposition

来源：评论

学校读者我要写书评

暂无评论

equivalence OF SOME QUADRATIC-PROGRAMMING algorithms

引用

MATHEMATICAL PROGRAMMING 1984年第1期30卷 71-87页

作者： BEST, MJ Department of Combinatorics and Optimization University of Waterloo N2L 3G1 Waterloo Ontario Canada

We formulate a general algorithm for the solution of a convex (but not strictly convex) quadratic programming problem. Conditions are given under which the iterates of the algorithm are uniquely determined. The quadratic programming algorithms of Fletcher, Gill and Murray, Best and Ritter, and van de Panne and Whinston/Dantzig are shown to be special cases and consequently are equivalent in the sense that they construct identical sequences of points. The various methods are shown to differ only in the manner in which they solve the linear equations expressing the Kuhn-Tucker system for the associated equality constrained subproblems. equivalence results have been established by Goldfarb and Djang for the positive definite Hessian case. Our analysis extends these results to the positive semi-definite case.

关键词： Quadratic Programming equivalence of algorithms

来源：评论

学校读者我要写书评

暂无评论

Affinity functions in fuzzy connectedness based image segmentation II: Defining and recognizing truly novel affinities

引用

COMPUTER VISION AND IMAGE UNDERSTANDING 2010年第1期114卷 155-166页

作者： Ciesielski, Krzysztof Chris Udupa, Jayaram K. W Virginia Univ Dept Math Morgantown WV 26506 USA Univ Penn Dept Radiol MIPG Philadelphia PA 19104 USA

Affinity functions - the measure of how strongly pairs of adjacent spels in the image hang together represent the core aspect (main variability parameter) of the fuzzy connectedness (FC) algorithms, an important class of image segmentation schemas. In this paper, we present the first ever theoretical analysis of the two standard affinities, homogeneity and object-feature, the way they can be combined, and which combined versions are truly distinct from each other. The analysis is based on the notion of equivalent affinities, the theory of which comes from a companion Part I of this paper (Ciesielski and Udupa, in this issue) [11]. We demonstrate that the homogeneity based and object feature based affinities are equivalent, respectively, to the difference quotient of the intensity function and Rosenfeld's degree of connectivity. We also show that many parameters used in the definitions of these two affinities are redundant in the sense that changing their values lead to equivalent affinities. We finish with an analysis of possible ways of combining different component affinities that result in non-equivalent affinities. In particular, we investigate which of these methods, when applied to homogeneity based and object-feature based components lead to truly novel (non-equivalent) affinities, and how this is affected by different choices of parameters. Since the main goal of the paper is to identify, by formal mathematical arguments, the affinity functions that are equivalent, extensive experimental confirmations are not needed - they show completely identical FC segmentations - and as such, only relevant examples of the theoretical results are provided. Instead, we focus mainly on theoretical results within a perspective of the fuzzy connectedness segmentation literature. (C) 2009 Elsevier Inc. All rights reserved.

关键词： Affinity Fuzzy connectedness Image segmentation equivalence of algorithms

来源：评论

学校读者我要写书评

暂无评论

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

来源：评论

学校读者我要写书评

暂无评论

Parallel algorithms for Data Digital Filtering

引用

CYBERNETICS AND SYSTEMS ANALYSIS 2023年第1期59卷 39-48页

作者： Yadzhak, M. S. Natl Acad Sci Ukraine Pidstryhach Inst Appl Problems Mech & Math Lvov Ukraine Ivan Franko Natl Univ Lviv Lvov Ukraine

The paper proposes parallel algorithms for solving digital filtering problems of different dimensions using modern universal computers. Theoretical estimates of the complexity and speedup are obtained, which confirm the high efficiency of these algorithms. Some of the proposed parallel algorithms are implemented using computers with a multi-core processor, and real estimates of the speedup are obtained, which agree well with theoretical ones.

关键词： digital filtering parallel algorithm computation speedup limited parallelism equivalence of algorithms computing system

来源：评论

学校读者我要写书评

暂无评论

Ordinary interactive small-step algorithms, III

引用

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC 2007年第3期8卷 16–es页

作者： Blass, Andreas Gurevich, Yuri Univ Michigan Ann Arbor MI 48109 USA

This is the third in a series of three articles extending the proof of 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. As in the first two articles of the series, we are concerned here with ordinary, small-step, interactive algorithms. This means that the algorithms: (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. After reviewing the previous articles' definitions of such algorithms, of behavioral equivalence, and of abstract state machines (ASMs), we prove the main result: Every ordinary, interactive, small-step algorithm is behaviorally equivalent to an ASM. We also discuss some possible variations of and additions to the ASM semantics.

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

来源：评论

学校读者我要写书评

暂无评论

Computing Equivalent Affinity Classes in a Fuzzy Connectedness Framework

引用

ACTA CYBERNETICA 2014年第4期21卷 609-628页

作者： Gulyas, Gergely Dombi, Jozsef

The equivalence of affinities in fuzzy connectedness (FC) is a novel concept which gives us the ability to study affinity functions and their precise connection with FC algorithms. Two seminal papers by Ciesielski and Udupa create a strong theoretical background and provide some useful practical examples. Our intention here is to investigate this concept further because from a practical viewpoint if we are able to determine the equivalence classes for a given set of affinity functions and narrow it down to a much smaller set of nonequivalent affinities, then the set can be used more effectively in an optimization framework which searches for the best affinity function or parameters for a special task. In other words, we can find the best configuration for a set of given hardware or an image set with special characteristics. From a theoretical perspective, we are interested in the complexity of this problem, i.e. determining equivalence classes. Here, an affinity operator is used which is a function of a given parameter and maps different parameter values for different affinity functions. Our first questions, namely how many different meaningful, non-equivalent affinities there are and how we can enumerate them, led us to a general problem of how the equivalent affinities partition the parameter's domain and how the corresponding equivalence classes can be determined. We will provide a general algorithm schema to construct special algorithms which are able to compute the equivalence classes. We will also analyze a special but very common scenario of when the affinity operator combines two affinities (e.g. a homogeneity and an object feature-based affinity) using an aggregation operator (e.g. weighted average) and the particular parameter defines the weights of the affinities. Based on the general algorithm schema, we propose algorithms for this special case and we determine their complexity as well. These algorithms will be tested on two sets of medical images, namel

关键词： Fuzzy Connectedness Affinity Functions equivalence of Affinities Image Segmentation equivalence of algorithms

来源：评论

学校读者我要写书评

暂无评论

Ordinary interactive small-step algorithms, II

引用

ACM TRANSACTIONS ON COMPUTATIONAL LOGIC 2007年第3期8卷 15–es页

作者： Blass, Andreas Gurevich, Yuri Univ Michigan Ann Arbor MI 48109 USA

This is the second in a series of three articles extending the proof of 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. As in the first article of the series, we are concerned here with ordinary, small-step, interactive algorithms.,This means that the algorithms: (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. After reviewing the previous article's formal description of such algorithms and the definition of behavioral equivalence, we define ordinary, interactive, small-step abstract state machines (ASMs). Except for very minor modifications, these are the machines commonly used in the ASM literature. We define their semantics in the framework of ordinary algorithms and show that they satisfy the postulates for these algorithms. This material lays the groundwork for the final article in the series, in which we shall prove the Abstract State Machine thesis for ordinary, intractive, small-step algorithms: All such algorithms are equivalent to ASMs.

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

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：