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

DNA Computing, Computation complexity and Problem of Biological Evolution Rate

ACTA BIOTHEORETICA 2008年第4期56卷 285-295页

作者： Melkikh, Alexey V. Ural State Tech Univ Ekaterinburg 620002 Russia

An analogy between the evolution of organisms and some complex computational problems (cryptosystem cracking, determination of the shortest path in a graph) is considered. It is shown that in the absence of a priori information about possible species of organisms such a problem is complex (is rated in the class NP) and cannot be solved in a polynomial number of steps. This conclusion suggests the need for re-examination of evolution mechanisms. Ideas of a deterministic approach to the evolution are discussed.

关键词： DNA computing Undirected mutations algorithm complexity Deterministic evolution Probability of new species origin No Free Lunch Theorems

来源：评论

学校读者我要写书评

暂无评论

An algorithm for single-item economic lot-sizing problem with general inventory cost, non-decreasing capacity, and non-increasing setup and production cost

引用

OPERATIONS RESEARCH LETTERS 2008年第3期36卷 300-302页

作者： Chen, Shaoxiang Feng, Yi Kumar, Arun Lin, Bing Zhejiang Univ Sch Management Hangzhou 310058 Zhejiang Peoples R China Nanyang Technol Univ Nanyang Business Sch Singapore 639798 Singapore Nanyang Technol Univ Ctr Supply Chain Management Sch Mech & Aerosp Engn Singapore Singapore

This paper considers an economic lot-sizing model with non-decreasing capacity constraint, non-increasing setup cost and production cost, and a general inventory cost. We prove that when periodic starting inventory is not less than a certain critical value, it is optimal to produce nothing;this critical value can be computed easily which results in a new effective algorithm. (C) 2007 Elsevier B.V. All rights reserved.

关键词： production inventory dynamic programming algorithm algorithm complexity

来源：评论

学校读者我要写书评

暂无评论

An improved computational algorithm for finding the factorial

引用

MATHEMATICAL NOTES 2008年第5-6期83卷 783-789页

作者： Ladikov, A. V. Moscow State Univ Railway Engn MIIT Moscow Russia

In the present paper, we consider a method for improving the computational algorithm for finding the factorials of integers;this method linearly accelerates the computations. We also present several algorithms effecti... 详细信息

关键词： computational algorithm factorial algorithm complexity

来源：评论

学校读者我要写书评

暂无评论

THE CHOICE OF PARAMETERS IN ARC LENGTH algorithm

THE CHOICE OF PARAMETERS IN ARC LENGTH ALGORITHM

引用

International Conference on Apperceiving Computing and Intelligence Analysis

作者： Nie, Xiao-Wen Lu, Xian-Liang Xu, Hai-Mei Peng, Yong-Xiang Univ Elect Sci & Technol China Sch Engn & Comp Sci Chengdu 610054 Peoples R China

ISBN: (纸本)9781424434275

To improve the efficiency of the Arc Length (AL) algorithm, the paper presents a quantitative method to choose the parameters of AL. The paper analyzes the condition to guarantee the correctness of AL, and gives the approaches to set the parameters. Moreover, the latency of AL under the new method is discussed in detailed. The analysis and simulation shows that the latency of AL with the parameters chosen under the new method remains constant, while is not increasing as the size of network grows.

关键词： Distributed hash table (DHT) random sampling algorithm complexity

来源：评论

学校读者我要写书评

暂无评论

Selected multicriteria shortest path problems: An analysis of complexity, models and adaptation of standard algorithms

引用

INTERNATIONAL JOURNAL OF APPLIED MATHEMATICS AND COMPUTER SCIENCE 2007年第2期17卷 269-287页

作者： Tarapata, Zbigniew Mil Univ Technol Fac Cybernet Div Operat Res & Decis Support PL-00908 Warsaw Poland

The paper presents selected multicriteria (multiobjective) approaches to shortest path problems. A classification of multiobjective shortest path (MOSP) problems is given. Different models of MOSP problems are discussed in detail. Methods of solving the formulated optimization problems are presented. An analysis of the complexity of the presented methods and ways of adapting of classical algorithms for solving multiobjective shortest path problems are described. A comparison of the effectiveness of solving selected MOSP problems defined as mathematical programming problems (using the CPLEX 7.0 solver) and multi-weighted graph problems (Using modified Dijkstra's algorithm) is given. Experimental results of using the presented methods for multicriteria path selection in a terrain-based grid network are given.

关键词： multiobjective shortest path stochastic shortest path algorithm complexity routing problem terrain-based modeling approximation algorithm

来源：评论

学校读者我要写书评

暂无评论

Weight-proportional space partitioning using adaptive Voronoi diagrams

引用

GEOINFORMATICA 2007年第3期11卷 383-405页

作者： Reitsma, Rene Trubin, Stanislav Mortensen, Eric Oregon State Univ Coll Business Corvallis OR 97331 USA Oregon State Univ Sch Elect Engn & Comp Sci Corvallis OR 97331 USA

Traditional application of Voronoi diagrams for space partitioning results in Voronoi regions, each with a specific area determined by the generators' relative locations and weights. Particularly in the area of information space (re)construction, however, there is a need for inverse solutions;i.e., finding weights that result in regions with predefined area ratios. In this paper, we formulate an adaptive Voronoi solution and propose a raster-based optimization method for finding the associated weight set. The solution consists of a combination of simple, fixed-point iteration with an optional spatial resolution refinement along the regions' boundaries using quadtree decomposition. We present the corresponding algorithm and its complexity analysis. The method is successfully tested on a series of ideal-typical cases and the interactions between the adaptive technique and boundary resolution refinement are explored and assessed.

关键词： information space space partitioning Voronoi diagrams adaptive algorithm area-weight proportional fixed-point iteration quadtree decomposition optimization spatial resolution algorithm complexity

来源：评论

学校读者我要写书评

暂无评论

complexity analysis on elliptic scalar multiplication

Complexity analysis on elliptic scalar multiplication

引用

International Computer Conference on Wavelet Active Media Technology and Information Processing

作者： Wang Qingxian Shang Mingsheng Sun Shixin Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 610054 Peoples R China

ISBN: (纸本)9812700420

Elliptic scalar multiplication is the most cost operation of the elliptic curve cryptosystems. The fast implementation of Elliptic Curve Cryptography mainly depends on the fast computation of elliptic scalar multiplication kP. This paper analysis and compare the complexity of the "add and double methods" and Montgomery methods. We show that the Montgomery methods has more cost than the "add-and-double" method if the ratio of the cost of field inversion and field multiplication is more than 2 under the affine coordinate representations without concern the cost of field adding and field squaring in GF(2(m)). In fact, the ration of I and M is more than 7 as the size of binary field is not less than 128, which means that the algorithm 3.1 outperforms the algorithm 3.2.

关键词： Elliptic Curve Cryptography (ECC) scalar multiplication add-and-double Montgomery algorithm algorithm complexity

来源：评论

学校读者我要写书评

暂无评论

Time-domain analysis methodology for large-scale RLC circuits and its applications

引用

Science in China(Series F) 2006年第5期49卷 665-680页

作者： LUO Zuying CAI Yici Sheldon X.-D Tan HONG Xianlong WANG Xiaoyi PAN Zhu FU Jingjing Department of Computer Science and Technology Tsinghua University Beijing 100084 China College of Information Science and Technology Beijing Normal University Beijing 100875 China Department of Electrical Engineering University of California at Riverside Riverside CA92521 USA

With soaring work frequency and decreasing feature sizes, VLSI circuits with RLC parasitic components are more like analog circuits and should be carefully analyzed in physical design. However, the number of extracted RLC components is typically too large to be analyzed efficiently by using present analog circuit simulators like SPICE. In order to speedup the simulations without error penalty, this paper proposes a novel methodology to compress the time-descritized circuits resulted from numerical integration approximation at every time step. The main contribution of the methodology is the efficient structure-level compression of DC circuits containing many current sources, which is an important complement to present circuit analysis theory. The methodology consists of the following parts： 1） An approach is proposed to delete all intermediate nodes of RL branches. 2） An efficient approach is proposed to compress and back-solve parallel and serial branches so that it is error-free and of linear complexity to analyze circuits of tree topology. 3） The Y to πtransformation method is used to error-free reduce and back-solve the intermediate nodes of ladder circuits with the linear complexity. Thus, the whole simulation method is very accurate and of linear complexity to analyze circuits of chain topology. Based on the methodology, we propose several novel algorithms for efficiently solving RLC-model transient power/ground （P/G） networks. Among them, EQU-ADI algorithm of linear-complexity is proposed to solve RLC P/G networks with mesh-tree or mesh-chain topologies. Experimental results show that the proposed method is at least two orders of magnitude faster than SPICE while it can scale linearly in both time- and memory-complexity to solve very large P/G networks.

关键词： RLC circuits analog circuit analysis time-domain analysis PIG networks algorithm complexity

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for k maximum sums

引用

algorithmICA 2006年第1期46卷 27-41页

作者： Bengtsson, Fredrik Chen, Jingsen Lulea Univ Technol Dept Comp Sci & Elect Engn S-97187 Lulea Sweden

We study the problem of computing the k maximum sum subsequences. Given a sequence of real numbers (x(1), x(2),..., x(n)) and an integer parameter k, 1 <= k <= 1/2n(n - 1), the problem involves finding the k largest values of Sigma(j)(l=t) x(l) for 1 <= 1 <= j <= n. The problem for fixed k = 1, also known as the maximum sum subsequence problem, has received much attention in the literature and is linear-time solvable. Recently, Bae and Takaoka presented a Theta (nk)-time algorithm for the k maximum sum subsequences problem. In this paper we design an efficient algorithm that solves the above problem in O(min{k + n log(2) n, n root k}) time in the worst case. Our algorithm is optimal for k = Omega(n log(2) n) and improves over the previously best known result for any value of the user-defined parameter k < 1. Moreover, our results are also extended to the multi-dimensional versions of the k maximum sum subsequences problem;resulting in fast algorithms as well.

关键词： maximum subsequence maximum subarray maximum sum algorithm design algorithm complexity

来源：评论

学校读者我要写书评

暂无评论

Efficient algorithms for k maximum sums

引用

15th Annual International Symposium on algorithms and Computation

作者： Bengtsson, Fredrik Chen, Jingsen Lulea Univ Technol Dept Comp Sci & Elect Engn S-97187 Lulea Sweden

ISBN: (纸本)9783540241317

关键词： maximum subsequence maximum subarray maximum sum algorithm design algorithm complexity

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：