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

COMBINING DIMENSIONALITY AND RATE OF GROWTH ARGUMENTS FOR ESTABLISHING LOWER BOUNDS ON THE NUMBER OF MULTIPLICATIONS AND DIVISIONS

引用

JOURNAL OF THE ACM 1979年第3期26卷 582-601页

作者： KEDEM, ZM Programs in Mathematical Sciences The University of Texas at Dallas Richardson TX

A new method for estabhshlng lower bounds on the number of multlphcatlons and divisions reqmred to compute rational functions is described The method is based on combining two known methods, dlmenstonahty and rate of growth The method is apphed to several problems and new lower bounds are obtained. © 1979, ACM. All rights reserved.

关键词： algebraic operations analysts of algorithms computational complexity counting methods dimensionality lower bounds multiplications optimality polynomials rate of growth rational functions

来源：评论

学校读者我要写书评

暂无评论

DYNAMIC PLACEMENT OF RECORDS IN LINEAR STORAGE

引用

JOURNAL OF THE ACM 1978年第3期25卷 421-434页

作者： MCKELLAR, AC WONG, CK IBM Thomas J Watson Research Center P.O. Box 218 Yorktown Heights NY IBM Thomas J Watson Research Center P.O. Box 218 Yorktown Heights NY

This paper considers allocation of space in a hnear storage medium when space must be allocated dynamically as customers arrive A heuristic is proposed for this problem and for a simple model of the resultmg reference sequence, we show that the average distance between consecutive references is asymptotically 7n/30, where n is the size of the storage For optimal static placement where one waits for all arrivals before any space allocation, the average distance is shown to be asymptotically 7n/30 For random placement, the average distance is asymptotically n/3 Thus, the heuristic is asymptotically optimal in a strong sense For reasonable values of n, we demonstrate that the heuristic is nearly as good as optimal static placement and much better than random placement. © 1978, ACM. All rights reserved.

关键词： analysts of algorithms asymptotically optimal algorithms concrete complexity dynamic allocation of storage space heuristics linear store minidisks minimization of disk seek time optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

LINEAR algorithms FOR ISOMORPHISM OF MAXIMAL OUTERPLANAR GRAPHS

引用

JOURNAL OF THE ACM 1979年第4期26卷 603-610页

作者： BEYER, T JONES, W MITCHELL, S UNIV LOUISVILLE LOUISVILLE KY 40208 USA

Two hnear algorithms are presented for solvmg the isomorphism problem for maximal outerplanar graphs (mops) These algorithms present improvements over corresponding hnear algorithms for planar graph isomorphism when apphed to mops The algorithms are based on a code for a mop G which is obtained from a umque Hamdtoman cycle m G The first involves a strmg-matchmg automaton and the second involves the removal of vertices of degree two m layers untd either an edge or triangular face remains. © 1979, ACM. All rights reserved.

关键词： analysts of algorithms graph theory isomorphism maximal outerplanar graphs

来源：评论

学校读者我要写书评

暂无评论

On the Average Number of Maxima in a Set of Vectors and Applications

引用

Journal of the ACM (JACM) 1978年第4期25卷 536-543页

作者： Bentley, J.L. Kung, H.T. Schkolnick, M. Thompson, C.D. Department of Computer Science Carnegie-Mellon University Pittsburgh PA 15213 United States IBM Research Laboratory San Jose CA United States

A maximal vector of a set is one which is not less than any other vector m all components We derive a recurrence relation for computing the average number of maxunal vectors in a set of n vectors m d-space under the assumpUon that all (nl) a relative ordermgs are equally probable. Solving the recurrence shows that the average number of maxmaa is O((ln n)d-1) for fixed d We use this result to construct an algorithm for finding all the maxima that have expected running tmae hnear m n (for sets of vectors drawn under our assumptions) We then use the result to find an upper bound on the expected number of convex hull points m a random point set. © 1978, ACM. All rights reserved.

关键词： analysts of algorithms average number of maxtma convex hulls dynamtc programming expected-tsme algorithms maxtma of a set of vectors

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：