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

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

来源：评论

学校读者我要写书评

暂无评论

CONVEX HULLS OF FINITE SETS OF POINTS IN 2 AND 3 DIMENSIONS

引用

COMMUNICATIONS OF THE ACM 1977年第2期20卷 87-93页

作者： PREPARATA, FP HONG, SJ UNIV ILLINOIS COORDINATED SCI LABURBANAIL 61801 IBM CORP SYST PROD DIVPOUGHKEEPSIENY 12602

Presents convex hulls of sets of points in two and three dimensions. Relevance of the convex hull on several problems in computer graphics, design automation, pattern recognition and operations research; Technique use... 详细信息

关键词： computational complexity convex hull optimal algorithms planar set of points spatial set of points

来源：评论

学校读者我要写书评

暂无评论

Efficient Algorithm for Adaptive Control for a Class of Mimo Plant

引用

IFAC Proceedings Volumes 1992年第14期25卷 251-254页

作者： A. Juditsky IRISA/INRIA Campus de Beaulieu 35042 Rennes France

An indirect adaptive control algorithm for a MIMO plant is studied. It is shown that Polyak - Ruppert estimation algorithm along with the simple dead-beat control law constitutes an adaptive control strategy that achi... 详细信息

关键词： adaptive control stochastic approximation optimal algorithms efficient control strategies

来源：评论

学校读者我要写书评

暂无评论

EFFICIENT PARALLEL algorithms FOR SOME GRAPH PROBLEMS

引用

COMMUNICATIONS OF THE ACM 1982年第9期25卷 659-665页

作者： CHIN, FY LAM, J CHEN, IN Univ. of Alberta Edmonton Alberta Canada Univ. of Alberta Edmonton Alberta Canada Univ. of Alberta Edmonton Alberta Canada

We study parallel algorithms for a number of graph problems, using the Single Instruction Stream-Multiple Data Stream model. We assume that the processors have access to a common memory and that no memory or data alignment time penalties are incurred. We derive a general time bound for a parallel algorithm that uses K processors for finding the connected components of an undirected graph. In particular, an O(log² n) time bound can be achieved using only K = n[n/log² n] processors. This result is optimal in the sense that the speedup ratio is linear with the number of processors used. The algorithm can also be modified to solve a whole class of graph problems with the same time bound and fewer processors than previous parallel methods. [ABSTRACT FROM AUTHOR]

关键词： SIMD complexity graph problems optimal algorithms parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

INTEGRALS WITH A KERNEL IN THE SOLUTION OF NON-LINEAR EQUATIONS IN N-DIMENSIONS

引用

JOURNAL OF THE ACM 1979年第2期26卷 239-249页

作者： KACEWICZ, B Department of Mathematics University of Warsaw 00901 Warsaw PK1N p 850 Poland

Iterations for solving the nonhnear equation F(x) = 0 in N-dimensional Banach space, [formula omitted], which use “integral mformatton with a kernel” are considered This information consists of the “standard reformation” [formula omitted], s, and the mtegral fo [formula omitted]dt where [formula omitted] IS an approximation to the solution, and yd depends on the standard mformatlon The existence of an iteration with order [formula omitted] IS shown, and ItS optimality is proved. © 1979, ACM. All rights reserved.

关键词： computational complexity integrals nonlinear equations numerical mathematics optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

A greedy hypercube-labeling algorithm 30

A greedy hypercube-labeling algorithm

引用

Proceedings of the 30th annual Southeast regional conference

作者： D. Bhagavathi C. E. Grosch S. Olariu Old Dominion University Norfolk VA

ISBN: (纸本)9780897915069

Due to its attractive topological properties, the hypercube multiprocessor has emerged as one of the architectures of choice when it comes to implementing a large number of computational problems. In many such applications, Gray-code labelings of the hypercube are a crucial prerequisite for obtaining efficient algorithms. We propose a greedy algorithm that, given an n-dimensional hypercube H with N=2n nodes, returns a Gray-code labeling of H , that is, a labeling of the nodes with binary strings of length n such that two nodes are neighbors in the hypercube if, and only if, their labels differ in exactly one bit. Our algorithm is conceptually very simple and runs in O(Nlog N) time being, therefore, optimal. As it turns out, with a few modifications our labeling algorithm can be used to recognize hypercubes as well.

关键词： hypercubes optimal algorithms greedy algorithms Gray-codes interconnection networks

来源：评论

学校读者我要写书评

暂无评论

MINIMUM LOCAL DISK COVER SETS FOR BROADCASTING IN HETEROGENEOUS MULTIHOP WIRELESS NETWORKS

引用

INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE 2012年第5期23卷 1147-1172页

作者： Chen, Guaning Yi, Chih-Wei Sun, Min-Te Liu, Fang-Chu Lan, Wei-Chi Kainan Univ Dept Informat Management Tao Yuan 33857 Taiwan Natl Chiao Tung Univ Dept Comp Sci Hsinchu 30010 Taiwan Natl Cent Univ Dept Comp Sci & Informat Engn Tao Yuan 32001 Taiwan

The concept of forwarding sets is widely adopted in many broadcast protocols for wireless multihop networks to alleviate the broadcast storm problem. In these protocols, after receiving a broadcast message, each node that is requested to relay the message instructs a subset of its 1-hop neighbors, a.k.a. the forwarding set, to further relay it. In this paper, we propose to use the Minimum Local Disk Cover Set (MLDCS) as the forwarding set in heterogeneous multihop wireless networks, where nodes may have different transmission ranges. We show that the minimum local disk cover set of a node in heterogeneous networks is equivalent to its skyline set, and then we propose a divide-and-conquer algorithm with the optimal time complexity to compute the skyline set locally and statelessly. Moreover, unlike other forwarding heuristics, the proposed algorithm requires only 1-hop neighbor information. This helps to reduce the forwarding set formation latency and thus will be more suitable for environments with a frequently changed network topology, such as vehicular ad hoc networks.

关键词： Minimum disc cover optimal algorithms applications in multihop networks

来源：评论

学校读者我要写书评

暂无评论

Logic optimization by output phase assignment in dynamic logic synthesis 96

Logic optimization by output phase assignment in dynamic log...

引用

Proceedings of the 1996 IEEE/ACM international conference on Computer-aided design

作者： Ruchir Puri Andrew Bjorksten Thomas E. Rosser IBM Thomas J. Watson Research Center Yorktown Heights NY IBM Corporation 11400 Burnet Road Austin TX

ISBN: (纸本)9780818675973

Domino logic is one of the most popular dynamic circuit configurations for implementing high-performance logic designs. Since domino logic is inherently noninverting, it presents a fundamental constraint of implementing logic functions without any intermediate inversions. Removal of intermediate inverters requires logic duplication for generating both the negative and positive signal phases, which results in significant area overhead. This area overhead can be substantially reduced by selecting an optimal output phase assignment, which results in a minimum logic duplication penalty for obtaining inverter-free logic. In this paper, we present this previously unaddressed problem of output phase assignment for minimum area duplication in dynamic logic synthesis. We give both optimal and heuristic algorithms for minimizing logic duplication.

关键词： logic optimization logic functions domino logic heuristic algorithms logic duplication area overhead optimal algorithms logic design dynamic logic synthesis minimum logic duplication penalty output phase assignment inverters

来源：评论

学校读者我要写书评

暂无评论

On the optimality of Some Set algorithms

引用

Journal of the ACM (JACM) 1972年第4期19卷 649-659页

作者： Reingold, Edward M. University of Illinois at Urbana-Champaign Department of Computer Science Urbana IL 61801 United States

The establishment of lower bounds on the number of comparisons necessary to solve various combinatorial problems is considered. Some of the new results are : (a) given two finite sets of real numbers, A and B, where n = max ( | A |, | B |), O(*** n) comparisons are required to determine if A = B, even when comparisons are allowed between linear functions of the numbers;and (b) the maximum of a set of n real numbers cannot be computed in fewer than n - 1 comparisons if comparisons of only linear functions of the numbers are permitted, but the maximum can be computed in Ilog2n] comparisons if comparisons are allowed between exponential functions of the numbers. © 1972, ACM. All rights reserved.

关键词： determining set equality maximum of a set optimal algorithms

来源：评论

学校读者我要写书评

暂无评论

Bridging supervised learning and test-based co-optimization

The Journal of Machine Learning Research

引用

The Journal of Machine Learning Research 2017年第1期18卷

作者： Elena Popovici Icosystem Corp. Cambridge MA

This paper takes a close look at the important commonalities and subtle differences between the well-established field of supervised learning and the much younger one of cooptimization. It explains the relationships between the problems, algorithms and views on cost and performance of the two fields, all throughout providing a two-way dictionary for the respective terminologies used to describe these concepts. The intent is to facilitate advancement of both fields through transfer and cross-pollination of ideas, techniques and results. As a proof of concept, a theoretical study is presented on the connection between existence / lack of free lunch in the two fields, showcasing a few ideas for improving computational complexity of certain supervised learning approaches.

关键词： active learning co-optimization free lunch optimal algorithms supervised learning

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：