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

An experimental analysis of self-adjusting computation

ACM SIGPLAN NOTICES 2006年第6期41卷 96-107页

作者： Acar, Umut A. Blelloch, Guy E. Blume, Matthias Tangwongsan, Kanat Carnegie Mellon Univ Pittsburgh PA 15213 USA

Dependence graphs and memoization can be used to efficiently update the output of a program as the input changes dynamically. Recent work has studied techniques for combining these approaches to effectively dynamize a wide range of applications. Toward this end various theoretical results were given. In this paper we describe the implementation of a library based on these ideas, and present experimental results on the efficiency of this library on a variety of applications. The results of the experiments indicate that the approach is effective in practice, often requiring orders of magnitude less time than recomputing the output from scratch. We believe this is the first experimental evidence that incremental computation of any type is effective in practice for a reasonably broad set of applications.

关键词： languages performance algorithms self-adjusting computation memoization dynamic dependence graphs dynamic algorithms computational geometry performance

来源：评论

学校读者我要写书评

暂无评论

What you see is what you code: A radically dynamic algorithm visualization development model for novice learners

What you see is what you code: A radically dynamic algorithm...

引用

IEEE Symposium on Visual Languages and Human-Centric Computing

作者： Hundhausen, CD Brown, JL Washington State Univ Sch Elect Engn & Comp Sci Visualizat & End User Programming Lab Pullman WA 99164 USA

ISBN: (纸本)0769524435

Pedagogical algorithm visualization systems produce graphical representations that aim to assist learners in understanding the dynamic behavior of computer algorithms. In order to foster active learning, educators have explored algorithm visualization systems that empower learners to construct their own visualizations of algorithms tinder study. Notably, these systems support a similar development model in which coding the algorithm is temporally distinct from viewing and interacting with the resulting visualization. To explore the benefits of narrowing the gap between coding an algorithm and viewing its visualization, we have implemented "What You See Is What You Code, " a novel, "radically dynamic" development model to facilitate learner-constructed algorithm visualizations. In this model, the line of algorithm code currently being edited is reevaluated on every edit, leading to the dynamic update of an accompanying visualizalion of the algorithm. Analysis of usability studies involving introductory computer science students suggests that the immediacy of the model's feedback can help novices to quickly identify and correct programming errors, and ultimately to understand their code's execution.

关键词： computer aided instruction computer science education program debugging program visualisation teaching active learning algorithm behavior understanding algorithm code code execution computer science students graphical representation learner assistance mo Debugging development model computer science education Visualization Graphic methods algorithms viewing visualization system dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

Quasi-fully dynamic algorithms for two-connectivity and cycle equivalence

引用

ALGORITHMICA 2002年第2期33卷 168-182页

作者： Korupolu, MR Ramachandran, V Univ Texas Dept Comp Sci Austin TX 78712 USA

We introduce a new class of dynamic graph algorithms called quasi-fully dynamic algorithms, which are much more general than backtracking algorithms and are much simpler than fully dynamic algorithms. These algorithms are especially suitable for applications in which a certain core connected portion of the graph remains fixed, and fully dynamic updates occur on the remaining edges in the graph, We present very simple quasi-fully dynamic algorithms with O(log n) worst-case time per operation for edge connectivity and O(log n) amortized time per operation for cycle equivalence, The former is deterministic while the latter is Monte-Carlo-type randomized. For 2-vertex connectivity, we give a deterministic quasi-fully dynamic algorithm with O(log(3)n) amortized time per operation. The quasi-fully dynamic algorithm we present for cycle equivalence (which has several applications in optimizing compilers) is of special interest since the algorithm is quite simple, and no special-purpose incremental or backtracking algorithm is known for this problem.

关键词： dynamic algorithms graph algorithms cycle equivalence connected graphs edge and vertex connectivity randomized algorithms compiler optimization

来源：评论

学校读者我要写书评

暂无评论

A dynamic scheduling algorithm with minimum context switches for spacecraft avionics systems

A dynamic scheduling algorithm with minimum context switches...

引用

IEEE Aerospace Conference

作者： Zolfaghari, B Iran Univ Sci & Technol Dept Comp Engn Tehran Iran

ISBN: (纸本)0780381556

Most of the process-scheduling algorithms, which can be exploited by spacecraft avionics systems, fall into one of the two main categories: static algorithms and dynamic algorithms. 12 Static algorithms assign priorities to processes before runtime. These algorithms bound the CPU utilization and require considerable information about the runtime parameters of processes in advance. These disadvantages encourage the spacecraft avionics system designers to exploit dynamic algorithms instead. But these algorithms have their own disadvantages. For example, these algorithms require so many context switches to schedule the processes. This causes a notable overhead in the runtime. One of the well-known dynamic algorithms is the MLF (Minimum Laxity First) algorithm. The MLF algorithm suffers from a serious problem (in addition to the need for so many context switches). This paper proposes a novel dynamic algorithm called Optimized MLF which is an attempt to solve the problems of the MLF algorithm in order to make it more applicable to spacecraft avionics systems. The performance of the proposed scheduling algorithm is evaluated through the use of mathematical modeling as well as simulation results. Both the mathematical model and simulation results show that the optimized MLF algorithm requires less context switches than the traditional MLF and makes the MLF algorithm more applicable to spacecraft avionics systems.

关键词： avionics space vehicle electronics dynamic scheduling optimisation mathematical analysis dynamic scheduling algorithm minimum context switches spacecraft avionics systems process scheduling algorithms CPU utilization minimum laxity first algorithm mathematical modeling avionics dynamic scheduling space vehicle electronics mathematical modeling mathematical analysis Scheduling algorithms dynamic algorithms Spacecraft Switches algorithms

来源：评论

学校读者我要写书评

暂无评论

dynamic algorithms for classes of constraint satisfaction problems

引用

THEORETICAL COMPUTER SCIENCE 2001年第1-2期259卷 287-305页

作者： Frigioni, D Marchetti-Spaccamela, AT Nanni, U Univ Aquila Dipartimento Ingn Elettr I-67040 Laquila Italy Univ Rome La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy

Many fundamental tasks in artificial intelligence and in combinatorial optimization can be formulated as a constant Satisfaction Problem (CSP). It is the problem of finding an assignment of values for a set of variables, each defined on a finite domain of feasible values, subject to a given collection of constraints. Each constraint is defined over a set of variables and specifies the allowed combinations of values as a collection of tuples. In general, the problem of finding a solution to a CSP is NP-complete, but in some cases it has shown to be polynomially solvable. We consider the dynamic version of some polynomially solvable constraint satisfaction problems, and present solutions that are better than recomputing everything from scratch after each update. The updates we consider are either restrictions, i.e., deletions of values from existing constraints and introduction of new constraints, or relaxations, i.e., insertions of values or deletions of constraints. (C) 2001 Elsevier Science B.V. All rights reserved.

关键词： constraint satisfaction problem network of constraints dynamic algorithms consistency backtrack-free search amortized complexity

来源：评论

学校读者我要写书评

暂无评论

Fully dynamic shortest paths in digraphs with arbitrary arc weights

引用

JOURNAL OF algorithms-COGNITION INFORMATICS AND LOGIC 2003年第1期49卷 86-113页

作者： Frigioni, D Marchetti-Spaccamela, A Nanni, U Univ Aquila Dipartimento Ingn Elettr I-67040 Laquila Italy Univ Roma La Sapienza Dipartimento Informat & Sistemist I-00198 Rome Italy

We propose a new solution for the fully dynamic single source shortest paths problem in a directed graph G = (N, A) with arbitrary arc weights, that works for any digraph and has optimal space requirements and query time. If a negative-length cycle is introduced in the subgraph of G reachable from the source during an update operation, then it is detected by the algorithm. Zero-length cycles are explicitly handled. We evaluate the cost of the update operations as a function of a structural property of G and of the number of the output updates. We show that, if G has a k-bounded accounting function (as in the case of digraphs with genus, arboricity, degree, treewidth or page number bounded by k), then the update procedures require O(min{m, k(.)n(A)}(.)logn) worst case time for weight-decrease operations, and O(min{m(.)logn, k(.)(n(A) + n(B))(.)logn + n}) worst case time for weight-increase operations. Here, n = \N\, in \A\, n(A) is the number of nodes affected by the input update, that is the nodes changing either the distance or the parent in the shortest paths tree, and n(B) is the number of nonaffected nodes considered by the algorithm that also belong to zero-length cycles. If zero-length cycles are not allowed, then n(B) is zero and the bound for weight-increase operations is O(min{m(.)logn, k(.)n(A)(.)logn + n}). Similar amortized bounds hold if we perform also insertions and deletions of arcs. (C) 2003 Elsevier Inc. All rights reserved.

关键词： shortest paths dynamic algorithms output complexity zero-length cycles

来源：评论

学校读者我要写书评

暂无评论

dynamic generation of discrete random variates

引用

THEORY OF COMPUTING SYSTEMS 2003年第4期36卷 329-357页

作者： Matias, Y Vitter, JS Ni, WC Tel Aviv Univ Dept Comp Sci IL-69978 Tel Aviv Israel Purdue Univ Dept Comp Sci W Lafayette IN USA TBCommerce Network Corp Pomona CA 91768 USA

We present and analyze efficient new algorithms for generating a random variate distributed according to a dynamically changing set of N weights. The base version of each algorithm generates the discrete random variate in O(log* N) expected time and updates a weight in O(2(log)* (N)) expected time in the worst case. We then show how to reduce the update time to O(log* N) amortized expected time. We finally show how to apply our techniques to a lookup-table technique in order to obtain expected constant time in the worst case for generation and update. We give parallel algorithms for parallel generation and update having optimal processor-time product. Besides the usual application in computer simulation, our method can be usedto perform constant-time prediction in prefetching applications. We also apply our techniques to obtain an efficient dynamic algorithm for maintaining an approximate heap of N elements, in which each query is required to return an element whose value is within an epsilon multiplicative factor of the maximal element value. For epsilon = 1/polylog(N), each query, insertion, or deletion takes O(log log log N) time.

关键词： logs refresh time algorithms Elements Computer Simulation nitrogen dynamic algorithms logarithm (log) Parallel algorithms

来源：评论

学校读者我要写书评

暂无评论

dynamic location management for mobile computing

引用

TELECOMMUNICATION SYSTEMS 2003年第1-4期22卷 169-187页

作者： Subrata, R Zomaya, AY Univ Sydney Sch Informat Technol Sydney NSW 2006 Australia Univ Western Australia Dept Elect & Elect Engn Parallel Comp Res Lab Nedlands WA 6907 Australia

This paper presents a dynamic and individualized location update scheme that considers each user's mobility patterns. The mobility patterns are used to create individualized location areas for each user. The proposed scheme is flexible and can be used in network with arbitrary cell topologies. The scheme, along with other existing schemes is simulated using realistic users' mobility and call arrival patterns, and network topology. The simulated environment consists of 90 cells representing the geographical area of the San Francisco bay, and 66,550 mobile users representing the typical classes of users that are normally present in a real cellular network. Results show the proposed scheme gives lower overall signaling costs, resulting in savings on the limited radio bandwidth that may have otherwise been used for location updates and paging.

关键词： dynamic algorithms location management mobile computing wireless networks

来源：评论

学校读者我要写书评

暂无评论

Maintenance of a piercing set for intervals with applications

引用

ALGORITHMICA 2003年第1期36卷 59-73页

作者： Katz, MJ Nielsen, F Segal, M Ben Gurion Univ Negev Dept Comp Sci IL-84105 Beer Sheva Israel SONY Comp Sci Labs Inc FRL Shinagawa Ku Tokyo 1410022 Japan Ben Gurion Univ Negev Dept Commun Syst Engn IL-84105 Beer Sheva Israel

We show how to maintain efficiently a minimum piercing set for a set S of intervals on the line, under insertions and deletions to/from S. A linear-size dynamic data structure is presented, which enables us to compute a new minimum piercing set following an insertion or deletion in time O(c(S) log \S\), where c(S) is the size of the new minimum piercing set. We also show how to maintain a piercing set for S of size at most (1 + epsilon)c(S), for 0 < epsilon less than or equal to 1, in (O) over bar((log\S\)/epsilon) amortized time per update. We then apply these results to obtain efficient solutions to the following three problems: (i) the shooter location problem, (ii) computing a minimum piercing set for arcs on a circle, and (iii) dynamically maintaining a box cover for a d-dimensional point set.

关键词： geometric optimization piercing set dynamic algorithms

来源：评论

学校读者我要写书评

暂无评论

dynamic algorithms for graphs of bounded treewidth

引用

ALGORITHMICA 2000年第3-4期27卷 292-315页

作者： Hagerup, T Goethe Univ Frankfurt Fachbereich Informat D-60054 Frankfurt Germany

The formalism of monadic second-order (MS) logic has been very successful in unifying a large number of algorithms for graphs of bounded treewidth. We extend the elegant framework of MS logic from static problems to dynamic problems, in which queries about MS properties of a graph of bounded treewidth are interspersed with updates of vertex and edge labels. This allows us to unify and occasionally strengthen a number of scattered previous results obtained in an ad hoc manner and to enable solutions to a wide range of additional problems to be derives automatically. As an auxiliary result of independent interest, we dynamize a data structure of Chazelle for answering queries about products of labels along paths in a tree with edges labeled by elements of a semigroup.

关键词： dynamic algorithms graph algorithms treewidth monadic second-order logic path queries

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：