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

optimal Parallel algorithm for the Knapsack Problem Without Memory Conflicts

Journal of Computer Science & Technology 2004年第6期19卷 760-768页

作者： Ken-LiLi Ren-FaLi Qing-HuaLi SchoolofComputerandCommunication HunanUniversityChangsha410082P.R.China SchoolofComputerScienceandTechnology HuazhongUniversityofScienceandTechnologyWuhan430074P.R.China

The knapsack problem is well known to be NP-complete. Due to its importance in cryptosystem and in number theory, in the past two decades, much effort has been made in order to find techniques that could lead to practical algorithms with reasonable running time. This paper proposes a new parallel algorithm for the knapsack problem where the optimal merging algorithm is adopted. The proposed algorithm is based on anEREW-SIMD machine with shared memory. It is proved that the proposed algorithm is both optimal and the first without memory conflicts algorithm for the knapsack problem. The comparisons of algorithm performance show that it is an improvement over the past researches. Keywords knapsack problem - NP-complete - parallel algorithm - optimal algorithm - memory conflict Supported by the National Natural Science Foundation of China under Grant No.60273075, the National High Technology Development 863 Program of China under Grant No.863-306-ZD-11-01-06. Ken-Li Li received his B.S. and M.S. degrees in mathematics from National University of Defense Technology and Central South University in 1995 and 2000 respectively and he is now a Ph.D. candidate in computer software and theory at Huazhong University of Science and Technology. His main research interests include parallel computing and combinatorial optimization. Ren-Fa Li received his Ph.D. degree in computer software and theory at Huazhong University of Science and Technology, and he is concurrently a professor and Ph.D. supervisor in School of Computer and Communication, Human University. His main research interests include network computing. Qing-Hua Li received his M.S. degree in computer science from Huazhong University of Science and Technology in 1981, and he is concurrently a professor and Ph.D. supervisor in School of Computer Science and Technology, Huazhong University of Science and Technology. His current research interests include parallel processing, combinatorial optimization, and grid comp

关键词： knapsack problem NP-complete parallel algorithm optimal algorithm memory conflict

来源：评论

学校读者我要写书评

暂无评论

Comments on "An optimal algorithm for Testing Stuck-at Faults in Random Access Memories"

引用

IEEE Transactions on Computers 1979年第3期C-28卷 258-261页

作者： Nair IBM Thomas J. Watson Research Center Yorktown Heights NY USA

An efficient, optimal test sequence for detecting multiple stuck-at faults in random access memories (RAM's) for any decoder implementation is presented. Another algorithm which does not assume any particular wire... 详细信息

关键词： Wired Logic Behavior Arbitrary Decoder Implementation Fault Detection Multiple Stuck At Faults optimal algorithm Random Access Memories

来源：评论

学校读者我要写书评

暂无评论

A randomized time-work optimal parallel algorithm for finding a minimum spanning forest

引用

SIAM JOURNAL ON COMPUTING 2002年第6期31卷 1879-1895页

作者： Pettie, S Ramachandran, V Univ Texas Dept Comp Sci Austin TX 78712 USA

We present a randomized algorithm to find a minimum spanning forest (MSF) in an undirected graph. With high probability, the algorithm runs in logarithmic time and linear work on an exclusive read exclusive write (EREW) PRAM. This result is optimal w.r.t. both work and parallel time, and is the first provably optimal parallel algorithm for this problem under both measures. We also give a simple, general processor allocation scheme for tree-like computations.

关键词： parallel algorithm minimum spanning tree optimal algorithm EREW PRAM

来源：评论

学校读者我要写书评

暂无评论

An optimal multiplication algorithm on reconfigurable mesh

引用

IEEE TRANSACTIONS ON PARALLEL AND DISTRIBUTED SYSTEMS 1997年第5期8卷 521-532页

作者： Jang, JW Park, H Prasanna, VK SAMSUNG ELECT CO LTD SEOULSOUTH KOREA UNIV SO CALIF DEPT EE SYSTEEB 200CLOS ANGELESCA 90089

An O(1) time algorithm to multiply two N-bit binary numbers using an N x N bit-model of reconfigurable mesh is shown. It uses optimal mesh size and it improves previously known results for multiplication on the reconfigurable mesh. The result is obtained by using novel techniques for data representation and data movement and using multidimensional Rader Transform. The algorithm is extended to result in AT(2) optimality over 1 less than or equal to T less than or equal to root N in a variant of the bit-model of VLSI.

关键词： integer multiplication reconfigurable mesh optimal algorithm area-time trade off VLSI architecture

来源：评论

学校读者我要写书评

暂无评论

An Orbit Maneuver optimal algorithm Based On Time Performance Index

An Orbit Maneuver Optimal Algorithm Based On Time Performanc...

引用

2010亚太航空航天技术研讨会

作者： Xu Kaichuan~*,Wang Jianxin,Zhao Zilong,Wang Mingxin Department of Helicopter Mechanical Engineering,Army Aviation Institute,Beijing 101123,China

In space battle application,orbital design is the most important part:such as design for intercepting orbit,meanwhile,considering the optimization of intercepting orbit,it has very important meanings to design an intercepting orbit with minimal flight *** the way of analytic method and using optimal algorithm,on the premise of Keplerian orbit under two-body hypothesis and one-off impulse orbit maneuver,this paper discusses design for optimal intercepting orbit with minimal flight time under constraint of the magnitude of initial velocity impulse,and gets the optimal launch point(or orbit-changing point) on initial orbit by iterative search *** gives the mathematic model and process of calculation in the paper,and by means of model simulation in three different cases,we prove that it is a simple,quick and effective arithmetic for orbital *** believe that it would provide more reference for orbit optimal design in space application.

关键词： orbital design minimal flight time intercepting orbit optimal algorithm Keplerian orbit

来源：评论

学校读者我要写书评

暂无评论

Improved RFID Middleware Architecture and optimal algorithm based on Internet of Things

引用

INTERNATIONAL JOURNAL OF FUTURE GENERATION COMMUNICATION AND NETWORKING 2016年第11期9卷 263-274页

作者： Qu, Weiqing Qi, Yuedou Zhang, Qi Zhou, Chunliang Ningbo Dahongying Univ Ningbo 315175 Zhejiang Peoples R China

Internet of things is a wireless data communications technology, while radio frequency identification (RFID) is an emerging technology in the automatic identification of the Internet of things. In fact, it means the use of RFID system identification technology through the Internet to achieve the application of information interconnection and sharing. In this paper, the author analyzes an improved RFID middleware architecture and optimal algorithm based on internet of things. Through the analysis of RFID middleware technology, we put forward an optimized load balancing algorithm. The results show that the optimization algorithm is superior to the existing algorithms in the average time of load balancing and label processing.

关键词： RFID middleware optimal algorithm Internet of things Load balancing mechanism

来源：评论

学校读者我要写书评

暂无评论

K-Dimensional optimal Parallel algorithm for the Solution of a General Class of Recurrence Equations

引用

Journal of Computer Science & Technology 1995年第5期10卷 417-424页

作者：高庆狮刘志勇 The Institute of Intelligence Language and Computer Science Beijing University of Science and Technology Beijing Institute of Computing Technology The Chinese Academy of Sciences Beijing

This paper proposes a parallel algorithm, called KDOP (K-Dimensionaloptimal Parallel algorithm), to solve a general class of recurrence equations efficiently. The KDOP algorithm partitions the computation into a series of sub-computations, each of which is executed in the fashion that all the processors work simultaneously with each one executing an optimal sequential algorithm to solve a subcomputation task. The algorithm solves the equations in O(N/p)steps in EREW PRAM model (Exclusive Read Exclusive Write Parallel Ran-dom Access Machine model) using poptimal algorithm (itsspeedup is O(p)) in the case of poptimal speedup for this problem was previously achieved only in the case of palgorithm can be implemented on machines with multiple processing elements or pipelined vector machines with parallel memory systems.

关键词： Parallel algorithm optimal algorithm first-order linear recurrence equations recursive doubling algorithm tridiagonal systems of linear equations

来源：评论

学校读者我要写书评

暂无评论

optimal Interpolation algorithm Research Based on Quasi-Hermite Space Curve

Optimal Interpolation Algorithm Research Based on Quasi-Herm...

引用

International Conference on Advanced Design and Manufacturing Engineering (ADME 2011)

作者： Liang, Changchun Fan, Liuqun Qi, Dangjin Yi, Gang Miao, Zhuang Tongji Univ Shanghai 200092 Peoples R China Shenyang Machine Tool Grp Co Ltd Shenyang Peoples R China

ISBN: (纸本)9783037852163

According to the principle of parametric curve paths CNC interpolating, a real-time interpolation algorithm based on algebraic index of the micro-segment spline is presented. It's used to solve the problems of Hermite polynomial interpolation algorithm, which are commonly slow recursive algorithm, poor accuracy of approximation and the limitations of constant parameters increment interpolation. And the constant interpolation is achieved by fitting a first-order Taylor Formula. Simulation results show that the algorithm shortens the interpolation time and also improve the interpolation accuracy;meanwhile, it maintains the stability of the feed rate.

关键词： CNC Quasi-Hermite Spline Constant Arc Increment Interpolation optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

optimal parallel algorithm for the knapsack problem without memory conflicts

Optimal parallel algorithm for the knapsack problem without ...

引用

4th International Conference on Parallel and Distributed Computing, Applications and Technologies (PDCAT 2003)

作者： Li, KL Li, QH Wang-Hui Jiang, SY Huazhong Univ Sci & Technol Sch Comp Sci & Technol Wuhan 430074 Peoples R China

ISBN: (纸本)0780378407

The knapsack problem is very important in cryptosystem and in number theory. This paper proposes a new parallel algorithm for the knapsack problem where the method of divide and conquer is adopted. Basing on an EREW-SIMD machine with shared memory, the proposed algorithm utilizes O(2(n/4))(1-epsilon) processors, 0less than or equal to epsilon less than or equal to 1, and O(2(n)) memory to find a solution for the n-element knapsack problem in time O(2(n/4) (2(n/4))epsilon). Thus the cost of the proposed parallel algorithm is O(2(n)), which is optimal, and an improved result over the past researches. Keywords: Knapsack problem, parallel algorithm, optimal algorithm, memory conflicts.

关键词： knapsack problem parallel algorithm optimal algorithm memory conflicts

来源：评论

学校读者我要写书评

暂无评论

An optimal algorithm for slab designing of fixed weight slabs

Beijing Keji Daxue Xuebao/Journal of University of Science a...

引用

Beijing Keji Daxue Xuebao/Journal of University of Science and Technology Beijing 2008年第10期30卷 1179-1183页

作者： Xi, Yang Li, Tieke School of Economics and Management University of Science and Technology Beijing Beijing 100083 China Business School Beijing Institute of Fashion Technology Beijing 100029 China

A kind of slab designing problem was brought forward, in which the weight of slabs is fixed and the customer order demand specifications of weight and width are interval values. A multi-objective model to minimize the number of slabs and the total surplus weight was built. Based on the idea of the order-slab matrix and the compatible set of slabs, a two-stage optimal algorithm was proposed to solve the problem. In the algorithm, the first stage is to minimize the number of slabs, and the second stage is to minimize the total surplus weight. For this algorithm, the optimal nature was proved theoretically and an application case was given based on practical data.

关键词： Customer order Interval value optimal algorithm Slab designing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：