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

Exploiting structure in quantified formulas

JOURNAL OF algorithms-COGNITION INFORMATICS AND LOGIC 2002年第2期43卷 220-263页

作者： Stearns, RE Hunt, HB SUNY Albany Dept Comp Sci Albany NY 12222 USA

We study the computational problem "find the value of the quantified formula obtained by quantifying the variables in a sum of terms." The "sum" can be based on any commutative monoid, the "quantifiers" need only satisfy two simple conditions. and the variables can have any finite domain. This problem is a generalization of the problem "given a sum-of-products of terms, find the value of the sum" studied in [R.E. Stearns and H.B. Hunt III, SIAM J. Comput. 25 (1996) 448-476]. A data structure called a,,structure tree" is defined which displays information about "subproblems" that can be solved independently during the process of evaluating the formula. Some formulas have "good" structure trees which enable certain generic algorithms to evaluate the formulas in significantly less time than by brute force evaluation. By "generic allgorithm," we mean an algorithm constructed from uninterpreted function symbols, quantifier symbols, and monoid operations. The algebraic nature of the model facilitates a formal treatment of "local reductions" based on the "local replacement" of terms. Such local reductions "preserve formula structure" in the sense that structure trees with nice properties transform into structure trees with similar properties. These local reductions can also be used to transform hierarchical specified problems with useful structure into hierarchically specified problems having similar structure. (C) 2002 Elsevier Science (USA). All rights reserved.

关键词： quantified formulas generic algorithms satisfiability problems constraint satisfaction problems non-serial dynamic programming computational complexity channelwidth structure trees treewidth tree decompositions

来源：评论

学校读者我要写书评

暂无评论

ALGORITHM-ORIENTED generic LIBRARIES

引用

SOFTWARE-PRACTICE & EXPERIENCE 1994年第7期24卷 623-642页

作者： MUSSER, DR STEPANOV, AA HEWLETT PACKARD CORP SOFTWARE TECHNOL LABPALO ALTOCA 94303

We outline an approach to construction of software libraries in which generic algorithms (algorithmic abstractions) play a more central role than in conventional software library technology or in the object-oriented programming paradigm. Our approach is to consider algorithms first, decide what types and access operations they need for efficient execution, and regard the types and operations as formal parameters that can be instantiated in many different ways, as long as the actual parameters satisfy the assumptions on which the correctness and efficiency of the algorithms are based. The means by which instantiation is carried out is language dependent;in the C++ examples in this paper, we instantiate generic algorithms by constructing classes that define the needed types and access operations. By use of such compile-time techniques and careful attention to algorithmic issues, it is possible to construct software components of broad utility with no sacrifice of efficiency.

关键词： generic algorithms ALGORITHMIC ABSTRACTIONS SOFTWARE LIBRARIES ABSTRACT DATA TYPES C++ TEMPLATES

来源：评论

学校读者我要写书评

暂无评论

Introspective sorting and selection algorithms

引用

SOFTWARE-PRACTICE & EXPERIENCE 1997年第8期27卷 983-993页

作者： Musser, DR Computer Science Department Rensselaer Polytechnic Institute Troy NY 12180 U.S.A.

Quicksort is the preferred in-place sorting algorithm in many contexts, since its average computing time on uniformly distributed inputs is Theta(N log N), and it is in fact faster than most other sorting algorithms on most inputs. Its drawback is that its worst-case time bound is Theta(N-2). Previous attempts to protect against the worst case by improving the way quicksort chooses pivot elements for partitioning have increased the average computing time too much - one might as well use heapsort, which has a Theta(N log N) worst-case time bound, but is on the average 2-5 times slower than quicksort. A similar dilemma exists with selection algorithms (for finding the i-th largest element) based on partitioning. This paper describes a simple solution to this dilemma: limit the depth of partitioning, and for subproblems that exceed the limit switch to another algorithm with a better worst-case bound. Using heapsort as the 'stopper' yields a sorting algorithm that is just as fast as quicksort in the average case, but also has an Theta(N log N) worst case time bound. For selection, a hybrid of Hoare's FIND algorithm, which is linear on average but quadratic in the worst case, and the Blum-Floyd-Pratt-Rivest-Tarjan algorithm is as fast as Hoare's algorithm in practice, yet has a linear worst-case time bound. Also discussed are issues of implementing the new algorithms as generic algorithms, and accurately measuring their performance in the framework of the C++ Standard Template Library. (C) 1997 by John Wiley & Sons, Ltd.

关键词： quicksort heapsort sorting algorithms introspective algorithms hybrid algorithms generic algorithms STL

来源：评论

学校读者我要写书评

暂无评论

Evolution and development of a multicellular organism: Scalability, resilience, and neutral complexification

引用

ARTIFICIAL LIFE 2006年第3期12卷 381-409页

作者： Federici, Diego Downing, Keith Norwegian Univ Sci & Technol Dept Comp & Informat Sci N-7491 Trondheim Norway

To increase the evolvability of larger search spaces, several indirect encoding strategies have been proposed. Among these, multicellular developmental systems are believed to offer great potential for the evolution of general, scalable, and self-repairing organisms. We reinforce this view, presenting the results achieved by such a model and comparing it against direct encoding. Extra effort has been made to make this comparison both general and meaningful. Embryonal stages, a generic method showing increased evolvability and applicable to any developmental model, are introduced. Development with embryonal stages implements what we refer to as direct neutral complexification: direct genotype complexification by neutral duplication of expressed genes. The results show that, even for high-complexity evolutionary targets, the developmental model proves more scalable. The model also shows emergent self-repair, which is used to produce highly resilient organisms.

关键词： generic algorithms development scalability fault tolerance neutral complexification

来源：评论

学校读者我要写书评

暂无评论

Multiperiod Coordination of Local Voltage Controllers and Energy Storage for Voltage Regulation in Distribution Feeder-Connected Renewable Energy Sources

引用

IRANIAN JOURNAL OF SCIENCE AND TECHNOLOGY-TRANSACTIONS OF ELECTRICAL ENGINEERING 2019年第3期43卷 531-544页

作者： Petinrin, J. O. Shaaban, Mohamed Fed Polytech Sch Engn Dept Elect Elect Engn Ede Osun State Nigeria Univ Malaysia Sarawak Dept Elect & Elect Engn Fac Engn Kota Samarahan 94300 Sarawak Malaysia

Connection of renewables to the distribution system is growing very rapidly. The inherent uncertainty of renewable energy sources, however, can potentially introduce operational conflicts, disrupting the typical operation pattern of local voltage regulation devices and causing system voltage rise beyond the acceptable limits. This paper describes a joint platform to maintain voltage regulation in a distribution network incorporating a large share of PV energy sources. With an objective to improve the voltage profile and minimize feeder losses, the operation of local voltage controllers and energy storage is coordinated. An optimization approach, based on the genetic algorithm, is developed to find out the optimal settings of the load tap-changing transformers and switched shunt capacitors, as well as the optimal dispatch of energy storage. The proposed method is applied to the IEEE 123 test feeder, using time series analysis over a daily, 24h, simulation period. Test results clearly exhibit that the close coordination between the voltage control devices and energy storage scales back system energy losses, minimizes the interaction among local voltage controllers and prevents reverse power flow. It consequently upholds the voltage at the customer terminals within the statutory limits, under high penetration levels of solar-fueled generation.

关键词： Energy storage generic algorithms Load tap changer Renewable energy sources PV generation Voltage control

来源：评论

学校读者我要写书评

暂无评论

A space efficient algorithm for group structure computation

引用

MATHEMATICS OF COMPUTATION 1998年第224期67卷 1637-1663页

作者： Teske, E Tech Univ Darmstadt Inst Theoret Informat D-64283 Darmstadt Germany

We present a new algorithm for computing the structure of a finite abelian group, which has to store only a fixed, small number of group elements, independent of the group order. We estimate the computational complexity by counting the group operations such as multiplications and equality checks. Under some plausible assumptions, we prove that the expected run time is O(root n) (with n denoting the group order), and we explicitly determine the O-constants. We implemented our algorithm for ideal class groups of imaginary quadratic orders and present experimental results.

关键词： generic algorithms group structure computation Pollard's rho-method class groups

来源：评论

学校读者我要写书评

暂无评论

On improvements of the r-adding walk in a finite field of characteristic 2

引用

JOURNAL OF DISCRETE MATHEMATICAL SCIENCES & CRYPTOGRAPHY 2016年第1期19卷 13-38页

作者： Abdullah, Ansari Gajera, Hardik Mahalanobis, Ayan Savitribai Phule Pune Univ Interdisciplinary Sch Sci Comp Pune Maharashtra India Dhirubhai Ambani Inst Informat & Commun Technol Gandhinagar Gujarat India Indian Inst Sci Educ & Res Pune Dr Homi Bhabha Rd Pune Maharashtra India

It is currently known from the work of Shoup and Nechaev that a generic algorithm to solve the discrete logarithm problem in a group of prime order must have complexity at least k root N where N is the order of the group. In many collision search algorithms this complexity is achieved. So with generic algorithms one can only hope to make the k smaller. This k depends on the complexity of the iterative step in the generic algorithms. The root N comes from the fact there is about root N iterations before a collision. So if we can find ways that can reduce the amount of work in one iteration then that is of great interest and probably the only possible modification of a generic algorithm. The modified r-adding walk allegedly does just that. It claims to reduce the amount of work done in one iteration of the original r-adding walk. In this paper we study this modified r-adding walk, we critically analyze it and we compare it with the original r-adding walk.

关键词： r-adding walk Discrete logarithm problem generic algorithms

来源：评论

学校读者我要写书评

暂无评论

Deterministic versus nondeterministic time and lower bound problems

引用

JOURNAL OF THE ACM 2003年第1期50卷 91-95页

作者： Stearns, RE SUNY Albany Dept Comp Sci Albany NY 12222 USA

Because many problems of general interest have natural nondeterministicalgorithms and because computers act deterministically, it is important to understand therelationship between deterministic and nondeterministic time. Specifically, it is important tounderstand how quickly a deterministic computing device can determine the outcome of anondeterministic calculation. So far, we have no general techniques that work any better than tryingall step-by-step simulations, an exponential method. The most famous question concerningdeterminism versus nondeterminism is the P = NP question. However, this is a different question than"what is the relationship?" and it is possible that significant progress about the relationship canbe achieved without answering the P = NP question. Thanks to efficient reductions from Turingmachine simulation to SAT, the relationship question can be posed as a question about SAT. Theproblem of proving a nontrivial lower bound on the time required to solve SAT is just an instance ofthe larger problem of proving lower bounds for any natural problem. It is suggested that a study ofgeneric problems might be a fruitful approach toward insights on such problems.

关键词： theory algorithms computational complexity generic algorithms generic problems nondeterminism NP-completeness power index SAT time complexity

来源：评论

学校读者我要写书评

暂无评论

Designing mathematical libraries based on requirements for theorems

引用

ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE 2003年第1-3期38卷 193-209页

作者： Schwarzweller, C Univ Tubingen Wilhelm Schickard Inst Comp Sci D-72076 Tubingen Germany

Theorems can be considered independent of abstract domains;a theorem rather depends on a set of properties necessary to prove the theorem correct. Following this observation theorems can be formulated and proven more generally thereby improving reuse of mathematical theorems. We discuss how this view influences the design of mathematical libraries and illustrate our approach with examples written in the Mizar language. We also argue that this approach allows for both stating requirements of generic algorithms and checking whether particular instantiations of generic algorithms are semantically correct.

关键词： mechanized reasoning reuse of theorems requirements for theorems mathematical libraries the Mizar system generic algorithms

来源：评论

学校读者我要写书评

暂无评论

Structural properties of the progressive hedging algorithm

引用

Annals of Operations Research 1991年第1期31卷 445-455页

作者： Wallace, Stein W. Helgason, Thorkell Haugesund Maritime College Haugesund N-5500 Skåregaten 103 Norway University of Iceland Reykjavík S-107 Dunhagi 3 Iceland

This short note discusses some structural properties of the progressive hedging algorithm. It is based on the finite case, but allows for event trees that are unbalanced and where the nodes can have a varying number of children. generic procedures and a generic record definition for the algorithms are presented. © 1991 J.C. Baltzer A. G. Scientific Publishing Company.

关键词： data structures generic algorithms progressive hedging algorithm scenario aggregation Stochastic programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：