Improved Parallel Three-List Algorithm for the Knapsack Problem without Memory Conflicts

Based on the two-list algorithm and the parallel three-list algorithm, an improved parallel three-list algorithm for knapsack problem is proposed, in which the method of divide and conquer, and parallel merging without memory conflicts are adopted. To find a solution for the n-element knapsack problem, the proposed algorithm needs O（2^3n/8） time when O（2^3n/8） shared memory units and O（2^n/4） processors are available. The comparisons between the proposed algorithm and 10 existing algorithms show that the improved parallel three-fist algorithm is the first exclusive-read exclusive-write （EREW） parallel algorithm that can solve the knapsack instances in less than O（2^n/2） time when the available hardware resource is smaller than O（2^n/2） , and hence is an improved result over the past researches.     

A NEW RSA CRYPTOSYSTEM HARDWARE IMPLEMENTATION BASED ON MONTGOMERY‘S ALGORITHM

IntroductionData security is becoming a more and more im-portantissue nowadays with the ever- creasing pop-ularity of electronical communication[1] . The fun-damental security requirements include confiden-tiality,authentication,data integrity,and nonre-pudiation.To provide such security services,mostsystems use public key cryptography. Among thevarious public key cryptography algorithms,theRSA cryptosystem is the bestknown,most versa-tile,and widely used public key cryptosystem to-day.In pu…     

一类带θ(t)型核的奇异积分算子的有界性

为了解决θ(t)型奇异积分算子在Lipschitz空间上的有界性问题,通过将标准的奇异积分核K(x,y)改为θ(t)型核K(x,y),得到θ(t)型奇异积分算子Tf(x)=∫K(x,y)f(y)dμ(y)在μ为非双倍测度时,算子Tε在Lipschitz空间上的一个等价条件:‖Tε1‖Λβ≤c1 Tε:Λβ→Λβ有界且‖Tε‖Λβ→Λβ≤c2。     

A Polynomial Time Algorithm for Checking Regularity of Totally Normed Process Algebra

A polynomial algorithm for the regularity problem of weak and branching bisimilarity on totally normed process algebra(PA) processes is given. Its time complexity is O(n3+ mn), where n is the number of transition rules and m is the maximal length of the rules. The algorithm works for totally normed basic process algebra(BPA) as well as basic parallel process(BPP).     

求解背包问题的一种新的近似算法

给出了求解背包问题的一种新的近似算法,这一算法是一种改进的贪婪算法,即将部分枚举法与贪婪算法相结合.从而使其具有更好的性能保证.同时,从理论上证明了这一算法的可靠性.最后,通过具体算例验证了算法的有效性.     

Heuristic Quasi-physical Algorithm for Protein Structure Prediction

A three-dimensional off-lattice protein model with two species of monomers, hydrophobic and hydrophilic, is studied. Enligh- tened by the law of reciprocity among things in the physical world, a heuristic quasi-physical algorithm for protein structure prediction problem is put forward. First, by elaborately simulating the movement of the smooth elastic balls in the physical world, the algorithm finds low energy configurations for a given monomer chain. An ＂off-trap＂ strategy is then proposed to get out of local minima. Experimental results show promising performance. For all chains with lengths 13≤n ≤55, the proposed algorithm finds states with lower energy than the putative ground states reported in literatures. Furthermore, for chain lengths n = 21, 34, and 55, the algorithm finds new low energy configurations different from those given in literatures.     

遗传算法在求解背包问题中的应用

对决策优化的经典背包问题进行了研究,提出了应用遗传算法对该模型进行求解,两例背包问题实例研究表明,遗传算法优化结果较其它方法都更合理。     

Parallel Distributed Implementation of Truss Optimization on a Local Area Network

A two-level optimization method for the design of complex truss and parallel distributed implementation on a LAN is presented using parallel virtual machine (PVM) for Win 32 as message passing between PCs. The volumes of truss are minimized by decomposing the original optimization problem into a number of bar optimization problems executed concurrently and a coordinate optimization problem, subject to constraints on nodal displacements, and stresses, buckling and crippling of bars, etc. The system sensitivity analysis that derives the partial derivatives of displacements and stresses with respect to areas are also performed in parallel so as to shorten the analysis time. The convergence and the speedup performances as well as parallel computing efficiency of the method are investigated by the optimization examples of a 52-bar planar truss and a 3 126-bar three-diraensional truss. The results show that the ideal speedup is obtained in the cases of 2 PCs for the 3 126-bar space truss optimization, while no speedup is observed for the 52-bar truss. It is concluded that (1) the parallel distributed algorithm proposed is efficient on the PC-based LAN for the coarsegrained large optimization problem; (2) to get a high speedup, the problem granularity should match with the network granularity;and (3) the larger the problem size is, the higher the parallel efficiency is.     

An Enhanced NEH Method in Solving Permutation Flow Shop Problem

This paper proposed an enhanced NEH with full insertion moves to solve the permutation flow shop problem.The characteristics of the original NEH are investigated and analyzed,and it is concluded that the given method would be promising to find better solutions,while the cost would be increased.Fast makespan calculating method and eliminating non-promising permutation policy are introduced to reduce the evaluation effort.The former decreases the time complexity from O(n4m) to O(n3m),which is an acceptable cost for medium and small size instances considering the obtained solution quality.The results from computational experience show that the latter also can eliminate a lot of non-promising solutions.     

基于OpenMP的并行遗传算法求解SAT问题

为了提高SAT （boolean satisfiability） 问题求解效率,在OpenMP （open multi-processing） 编程框架下,将遗传算法与局部搜索算法结合,改进了混合遗传算法中的选择算法,将原有选择操作的时间复杂度降低到O(N)级别. 算法采用OpenMP中的编译制导语句#pragma omp parallel粗粒度并行化驱动混合遗传算法,采用#pragma omp single语句块实现了子种群间个体的同步迁移操作. 与同类算法HCGA （hybrid cloud genetic algorithm）比较分析表明:改进算法HGA （hybrid genetic algorithm）以及并行后的混合遗传算法CGPHGA （coarse-grained parallel hybrid genetic algorithm）在求解成功率和求解效率上都有显著提高,部分问题求解成功率提高达5倍.      

THE PARALLEL RECURSIVE AP ADAPTIVE ALGORITHM BASED ON VOLTERRA SERIES

Aiming at the nonlinear system identification problem, a parallel recursive affine projection （AP） adaptive algorithm for the nonlinear system based on Volterra series is presented in this paper. The algorithm identifies in parallel the Volterra kernel of each order, recursively estimate the inverse of the autocorrelation matrix for the Volterra input of each order, and remarkably improve the convergence speed of the identification process compared with the NLMS and conventional AP adaptive algorithm based on Volterra ,series. Simulation results indicate that the proposed method in this paper is efficient.     

基于类间和类内方差的快速二维阈值分割法

为了提高二维阈值分割法的处理速度,提出二维类间方差最大法的快速实现方法.首先,将二维最佳阈值（s*,t*）的求解拆分成两个一维最佳阈值s*和t*的求解,并引入类内距离的定义,提出新的最佳阈值判别式.其次,将原二维直方图分成M×M个区域,合并每个区域为一点,并构建新的二维直方图,在其上应用本文改进的阈值判别式D（s*,t*）求解,得到分割阈值所在的区域编号.最后,在该区域内再次使用D（s*,t*）求解得到原始图像的最佳分割阈值.理论分析及针对不同信噪比的多幅图像的实验结果表明,本文方法的分割错误率低于原始二维Otsu法,且将原算法的时间复杂度由O（L4）降为O（L1/2）,空间复杂度由S（L2）降为S（2L）.      

Parallel processing based on ship maneuvering in identification of interaction force coefficients

The parallel processing based on the free running model test was adopted to predict the interac-tion force coefficients (flow straightening coefficient and wake fraction) of ship maneuvering. And the multi-population genetic algorithm (MPGA) based on real coding that can contemporarily process the data of freerunning model and simulation of ship maneuvering was applied to solve the problem. Accordingly the optimalindividual was obtained using the method of genetic algorithm. The parallel processing of multi-populationsolved the prematurity in the identification for single population, meanwhile, the parallel processing of the dataof ship maneuvering (turning motion and zigzag motion) is an attempt to solve the coefficient drift problem.In order to validate the method, the interaction force coefficients were verified by the procedure and thesecoefficients measured were compared with those ones identified. The maximum error is less than 5%, and theidentification is an effective method.     

UET系统在m台处理机上的一种调度算法及其性能分析

本文介绍了一种UET系统中有效的调度算法,其时间复杂性函数为O(na(n)+e)。该算法对m=2台处理机的调度为最优,而对m≥3台处理机上的未确定调度子问题,其解与最优解之比的最小上界为2-2/m,它也是一个近似程度相当好的有效算法。     

基于CUDA的快速LBP纹理背景建模算法

针对复杂条件下背景建模这一视频检测领域的难点,提出一种基于Nvidia CUDA架构图形处理器(GPU)的快速LBP纹理直方图背景建模算法,算法根据GPU的并发结构和硬件特点,采用纹理存储和分页存储方式,利用共享内存与多点访问技术,提高数据访问效率,降低了算法复杂度.实验结果表明,相比CPU实现,GPU方式能够明显改善实时性能,平均加速比在30x左右,帧处理速度达到40 f/s以上.     

运输问题原设－对偶算法的一个改进

本文对运输问题的原设－对偶算法运用推拉流思想进行改进,得到一个拟多项式时间算法。该算法使用的数据结构简单,运行时间界为Ｏ（Ｕ＿ｎ（ｍ＋ｎ）￣３）,其中ｍ为产地数目,ｎ为销地数口,Ｕ表示整体待运量。      

Dynamic Tabu Search Algorithm for Solving Departure Scheduling Problem

IntroductionWith the rapid development of air traffic, the in-creasing demand of air travel has made the airlinespurchase more aircrafts. Under these circumstances,large amounts of congestion are incurred at major air-ports. According to the related data[…     

Poincaré Inequalities on a Countable Set E and Ω={x:0≤x_i≤a, i=1,2,…,n}

IntroductionPoincaréinequalitiesarewidelyappliedinmanyfieldssuchasstochasticanalysis,functionalanalysisandeigenvalueestimate. AlotofresultsaboutPoincaréinequalitieshavebeenobtained[1-4], mostofthemwerebasedontheboundeddomaininndimen sionalEuclideanspace…     

优化端元提取方法的高光谱混合像元分解

高光谱图像的混合像元分解将原始图像分解为多种纯净地物及相应的丰度,端元提取是混合像元分解的关键技术. 针对传统算法计算速度慢、搜索范围较大的特点,基于改进的ICA （independent component analysis）算法以及优化的候选端元判断方法,提出了一种优化的混合像元分解方法. 首先使用改进的算法优化端元提取方法;然后利用相邻像素的光谱特征和空间特征信息,结合并行算法对候选端元进行优化;最后利用真实的高光谱数据对该方法的性能进行了验证. 验证结果表明:该方法能有效提高端元提取精度,降低复杂度,与经典的端元提取算法N-FINDER相比,准确度提高了3.55%,解混后得到的地物分类精度有了明显改善（总体分类精度提高了2.88%）.      

һ�ද̬����·������ģ�ͺ����׶��㷨

针对一类动态车辆路径问题,分析4种主要类型动态信息对传统车辆路径问题的本质影响,将动态车辆路径问题(Dynamic Vehicle Routing Problem, DVRP)转化为多个静态的多车型开放式车辆路径问题(The Fleet Size and Mixed Open Vehicle Routing Problem, FSMOVRP),并进一步转化为多个带能力约束车辆路径问题(Capacitated Vehicle Routing Problem, CVRP),基于CVRP模型建立了DVRP模型;然后,在分析DVRP问题特点基础上,提出两阶段算法,第一阶段基于利用K-d trees对配送区域进行分割的策略,提出了复杂度仅为O(nlogn)的快速构建型算法,第二阶段通过分析算法搜索解空间结构原理,设计混合局部搜索算法;最后,基于现有12个大规模CVRP标准算例,设计并求解36个DVRP算例。求解结果表明了模型和两阶段算法的有效性。