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

Interactive foundations of computing

THEORETICAL COMPUTER SCIENCE 1998年第2期192卷 315-351页

作者： Wegner, P Brown Univ Dept Comp Sci Providence RI 02912 USA

The claim that interactive systems have richer behavior than algorithms is surprisingly easy to prove. Turing machines cannot model interaction machines (which extend Turing machines with interactive input/output) because interaction is not expressible by a finite initial input string. Interaction machines extend the Chomsky hierarchy, are modeled by interaction grammars, and precisely capture fuzzy concepts like open systems and empirical computer science. Computable functions cannot model real-world behavior because functions are too strong an abstraction, sacrificing the ability to model time and other real-world properties to realize formal tractability. Part I of this paper examines extensions to interactive models for algorithms, machines, grammars, and semantics, while Part II considers the expressiveness of different forms of interaction. Interactive identity machines are already more powerful than Turing machines, while noninteractive parallelism and distribution are algorithmic. The extension of Turing to interaction machines parallels that of the lambda to the pi calculus. Asynchronous and nonserializable interaction are shown to be more expressive than sequential interaction (multiple streams are more expressive than a single stream). In Part III, it is shown that interaction machines cannot be described by sound and complete first-order logics (a form of Godel incompleteness), and that incompleteness is inherently necessary to realize greater expressiveness. In the final section the robustness of interactive models in expressing open systems, programming in the large, graphical user interfaces, and agent-oriented artificial intelligence is compared to the robustness of Turing machines. Less technical discussion of these ideas may be found in [25-27]. Applications of interactive models to coordination, objects and components, patterns and frameworks, software engineering, and AI are examined elsewhere [28, 29]. The propositions P1-P36 embody the principa

关键词： turing machines interaction coordination time on-line algorithms grammars process models games logic models incompleteness constraints emergent behavior empirical computer science

来源：评论

学校读者我要写书评

暂无评论

An improvement on El-Yaniv-Fiat-Karp-Turpin's money-making bi-directional trading strategy

引用

INFORMATION PROCESSING LETTERS 1998年第1期66卷 27-33页

作者： Dannoura, E Sakurai, K Kyushu Univ Dept Comp Sci & Commun Engn Higashi Ku Fukuoka 81281 Japan

If we are forced to choose from several alternatives in the areasof finance, economics, and operations research, with no secureknowledge of future events, then the use of an on-line system can aidour decision. Thus, on-line algorithms are required, which receive Asequence of requests and perform an immediate Action in response toeach request. A measure of the Efficiency of an on-line algorithm isits competitive Ratio: a comparison of the performance of the on-lineAlgorithm to the performance of an optimal off-line Algorithm foreach sequence of requests. The off-line Algorithm has full knowledgeof future requests.

关键词： algorithms on-line algorithms competitive analysis financial games two-way currency trading

来源：评论

学校读者我要写书评

暂无评论

Parameterized on-line open-end bin packing

引用

COMPUTING 1998年第3期60卷 267-273页

作者： Zhang, G Zhejiang Univ Inst Math Hangzhou 310027 Peoples R China

This note deals with a new variant of bin packing, the so-called open-end bin packing problem in which a bin can be filled to a level exceeding its capacity by its last item if it is not full immediately before the last is packed. We investigate the on-line version of this problem and give best possible algorithms for parametric cases.

关键词： bin packing on-line algorithms asymptotic worst-case performance ratio

来源：评论

学校读者我要写书评

暂无评论

How to learn an unknown environment I: The rectilinear case

引用

JOURNAL OF THE ACM 1998年第2期45卷 215-245页

作者： Deng, XT Kameda, T Papadimitriou, C City Univ Hong Kong Dept Comp Sci Hong Kong Hong Kong Simon Fraser Univ Sch Comp Sci Burnaby BC V5A 1S6 Canada Univ Calif Berkeley Dept Comp Sci Berkeley CA 94720 USA

We consider the problem faced by a robot that must explore and learn an unknown room with obstacles in it. We seek algorithms that achieve a bounded ratio of the worst-case distance traversed in order to see all visible points of the environment (thus creating a map), divided by the optimum distance needed to verify the map, if we had it in the beginning. The situation is complicated by the fact that the latter off-line problem (the problem of optimally verifying a map) is NP-hard. Although we show that there is no such "competitive" algorithm for general obstacle courses, we give a competitive algorithm for the case of a polygonal room with a bounded number of obstacles in it. We restrict ourselves to the rectilinear case, where each side of the obstacles and the room is parallel to one of the coordinates, and the robot must also move either parallel or perpendicular to the sides. (In a subsequent paper, we will discuss the extension to polygons of general shapes.) We also discuss the off-line problem for simple rectilinear polygons and find an optimal solution (in the L-1 metric) in polynomial time, in the case where the entry and the exit are different points.

关键词： competitive algorithms computational geometry gallery tour L1 metric on-line algorithms polygon with obstacles shortest path

来源：评论

学校读者我要写书评

暂无评论

Uniform multipaging reduces to paging

引用

INFORMATION PROCESSING LETTERS 1998年第1期67卷 9-12页

作者： Liberatore, V Rutgers State Univ Dept Comp Sci New Brunswick NJ 08903 USA

Multipaging is the paging problem when more than one page can be requested at each step (Feuerstein, 1997). In the uniform cost model, a paging algorithm is charged for the number of pages loaded from disk to fast memory. In this note, we establish a general reduction from uniform multipaging to paging. As a consequence, we obtain the first strongly competitive randomized algorithm for uniform multipaging. (C) 1998 Published by Elsevier Science B.V. All rights reserved.

关键词： design of algorithms on-line algorithms competitive analysis paging

来源：评论

学校读者我要写书评

暂无评论

On competitive on-line paging with lookahead

引用

THEORETICAL COMPUTER SCIENCE 1998年第1-2期209卷 365-375页

作者： Breslauer, D Aarhus Univ Dept Comp Sci Ctr Danish Natl Res Fdn BRICS DK-8000 Aarhus C Denmark

This paper studies two methods for improving the competitive efficiency of on-line paging algorithms: in the first, the on-line algorithm can use more pages;in the second, it is allowed to have a lookahead, or in other words, some partial knowledge of the future. The paper considers a new measure for the lookahead size as well as Young's resource-bounded lookahead and proves that both measures have the attractive property that the competitive efficiency of an on-line algorithm with k extra pages and lookahead l depends on k + l. Hence, under these measures, an on-line algorithm has the same benefit from using an extra page or knowing an extra bit of the future. (C) 1998-Elsevier Science B.V. All rights reserved.

关键词： on-line algorithms paging lookahead competitive analysis

来源：评论

学校读者我要写书评

暂无评论

On-line bin-stretching 2nd

On-line bin-stretching

引用

2nd International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM 98)

作者： Azar, Y Regev, O Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel

ISBN: (纸本)354065142X

We are given a sequence of items that can be packed into m unit size bins. In the classical bin packing problem we fix the size of the bins and try to pack the items in the minimum number of such bins. In contrast, in the bin-stretching problem we fix the number of bins and try to pack the items while stretching the size of the bins as least as possible. We present two on-line algorithms for the bin-stretching problem that guarantee a stretching factor of 5/3 for any number m of bins. We then combine the two algorithms and design an algorithm whose stretching factor is 1.625 for any m. The analysis for the performance of this algorithm is tight. The best lower bound for any algorithm is 4/3 for any m greater than or equal to 2. We note that the bin-stretching problem is also equivalent to the classical scheduling (load balancing) problem in which the Value of the makespan (maximum load) is known in advance.

关键词： on-line algorithms approximation algorithms bin-stretching load balancing scheduling bin-packing

来源：评论

学校读者我要写书评

暂无评论

On-line path planning with optimal C-space discretization

On-line path planning with optimal C-space discretization

引用

IEEE/RSJ International Conference on Intelligent Robots and Systems

作者： Henrich, D Wurll, C Worn, H Univ Karlsruhe Dept Comp Sci Inst Proc Control & Robot D-76128 Karlsruhe Germany

ISBN: (纸本)0780344650

This paper is based on a path planning approach we reported earlier for industrial robot arms with 6 degrees of freedom in an on-line given 3D environment. It has online capabilities by searching in an implicit and descrete configuration space and detecting collisions in the Cartesian workspace by distance computation based on the given CAD model. Here, we present different methods for specifying the C-space discretization. Besides the usual uniform and heuristic discretization, we investigate two versions of an optimal discretization for an user-predefined Cartesian resolution. The different methods are experimentally evaluated. Additionally, we provide a set of 3-dimensional benchmark problems for a fair comparison of path planner. For each benchmark, the run-times of our planner are between only 3 and 100 seconds on a Pentium PC with 133 MHz.

关键词： industrial robots path planning on-line algorithms search algorithms discretization

来源：评论

学校读者我要写书评

暂无评论

Off-line algorithms for the list update problem

引用

INFORMATION PROCESSING LETTERS 1996年第2期60卷 75-80页

作者： Reingold, N Westbrook, J AT&T BELL LABS MURRAY HILLNJ 07974 YALE UNIV DEPT COMP SCINEW HAVENCT 06520

Optimum off-line algorithms for the list update problem are investigated, The list update problem involves implementing a dictionary of items as a linear list. Several characterizations of optimum algorithms are given;these lead to optimum algorithm which runs in time Theta 2(n)(n - 1)!m, where n is the length of the list and m is the number of requests. The previous best algorithm, an adaptation of a more general algorithm due to Manasse et al. (1988), runs in time Theta(n!)(2)m.

关键词： sequential search list update on-line algorithms off-line algorithms competitive analysis analysis of algorithms

来源：评论

学校读者我要写书评

暂无评论

algorithms for on-line strip packing

引用

INFORMATION PROCESSING LETTERS 1997年第4期63卷 171-175页

作者： Csirik, J Woeginger, GJ GRAZ TECH UNIV INST MATH BA-8010 GRAZAUSTRIA UNIV SZEGED DEPT COMP SCIH-6720 SZEGEDHUNGARY

In the strip packing problem, the goal is to pack a set of rectangles into a vertical strip of unit width so as to minimize the total height of the strip needed. For the on-line version of this problem, Baker and Schwarz introduced the class of so-called shelf algorithms. One of these shelf algorithms, FFS, is the current champion for on-line strip packing. The asymptotic worst case ratio of FFS can be made arbitrarily close to 1.7. We show that no shelf algorithm for on-line strip packing can have an asymptotic worst case ratio better than h(infinity) approximate to 1.69103. Moreover, we introduce and analyze another on-line shelf algorithm whose asymptotic worst case ratio comes arbitrarily close to h(infinity). (C) 1997 Elsevier Science B.V.

关键词： analysis of algorithms combinatorial problems on-line algorithms competitive analysis worst case analysis strip packing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：