超立方体网络中任务调度的一个新近似算法

本文研究超立方体中的多处理器任务调度问题,我们研究LDLPT算法并指出为什么这种算法对一些实例具有最差的逼近度,然后提出一种类似装箱算法的新算法-BPA算法,证明该算法和LDLPT算法在相互最差逼近度中具有互补性质,最后,组合这两种算法的基本方法提出了一种求解问题的新算法-CBPA算法,并证明新算法具有比LDLPT算法更好的逼近度。     

随机图点覆盖1度顶点核化算法分析

将随机图引入参数计算领域,利用随机图统计和概率分布等特性,从全局和整体上研究参数化点覆盖问题1度点核化过程中问题的核及度分布演变的内在机制和变化规律,并得出关于随机图1度点核化强度与顶点平均度关系及随机图点覆盖问题的决策与度分布关系的两个重要推论.最后分别从MIPS和BIND提取数据进行1度核化实验和分析.初步结果表明,对随机图点覆盖问题的分析方法不仅具有理论上的意义,而且随着问题随机度的大小而对问题有不同程度的把握能力.     

带权Matching和Packing问题的一种固定参数可解算法

带权的m-D MATCHING和m-SET PACKING问题(m≥3)以前是用近似算法来求解的.本文首先根据参数计算理论对这两个带权问题进行了参数化定义,然后运用最新的着色技术和动态规划技术对带权的m-SET PACKING问题设计了一个时间复杂度为O*(12.8mk)的固定参数可解算法, 接着在此基础上利用问题本身的结构特点对带权的m-D MATCHING问题提出了一个时间复杂度为O*(12.8(m-1)k)的固定参数可解算法,表明带权的m-SET PACKING问题和带权的m-D MATCHING问题都是固定参数可解的.     

关于实际构造最大带宽路径算法的研究

建立最大带宽路径一直是网络路由研究，尤其是在最近的网络QoS路由研究中的基本问题，在以往的文献中，有人提出了利用修改的Dijkstra算法或修改的Bellman-Ford算法来构建最大带宽路径。该文给出了一个简单的证明，指出了最大生成树与最大带宽路径之间的特殊关系，证明了可以使用修改的Kruskal算法来构建最大带宽路径，文中给出了修改的Kruskal算法，并且与已有的Kijkstra算法作了性能上的比较，尽管从理论上说，Dijstra算法和Kruskal算法的时间复杂度具有同样的阶，但在多种不同网络结构上的模拟测试结果表明，用Kruskal算法构建最大带宽路径的实际运行比Dijkstra算法至少要快3倍，而且在实际上比Dijkstra算法更简单，灵活。     

一种基于最少片段删除模型重建单体型的粒子群优化算法

利用最少片段删除(MFR)模型研究了个体单体型重建的算法.利用单核苷酸多态性(SNP)位点杂合率低的特性,引入了一种短粒子编码方式,提出了一种重建单体型的粒子群优化算法P-MFR.利用国际人类基因组单体型图计划发布的CEPH样本(祖籍是北欧或西欧的美国犹他州人)中60个个体在1号染色体上的单体型进行实验分析,实验结果显示,与以往求解MFR模型的算法相比较,P-MFR算法能够获得更高重建率的单体型.此外,由于采用了较短的粒子位置编码方式,P-MFR算法在重建长单体型时仍具有较高的执行效率,有很好的实用价值.     

基于求传递闭包的Warshall算法的改进

围绕传递闭包分析比较了著名的Warshall算法,给出了一个三角形算法。当关系矩阵是稀疏矩阵时,该算法比Warshall快。     

基于比特承诺的电子拍卖方案

在拍卖过程中如何保护投标者隐私和防止中标者反悔是设计安全电子拍卖系统的关键问题,也是目前网上拍卖系统急需解决的问题。文章利用伪随机数产生理论和比特承诺机制的优点,给出了一个实现随机标价的密封式电子拍卖方案。该方案除了满足投标者匿名、投标价保密、不可否认性、强可验证性等安全要求外,还具有技术简单、通信量小、随机标价、限时强迫兑现等优点。     

重路由匿名通信系统中基于秘密共享的重路由算法

重路由匿名通信系统主要采用重路由机制来提供匿名保护．已有的下一跳重路由方式具有抗攻击能力弱且通信延时大等缺陷．提出基于秘密共享的重路由算法,用于在下一跳路由中实现端到端的加密,从而有效增大恶意成员的攻击难度．理论分析表明,抗攻击能力达到与源路由方式同等水平．并且,由于发送者能有效控制路由长度,因而能保证良好的通信性能．     

具有大量错误结点的超立方体网络中的高效路由算法的设计与讨论

该文提出了容错超立方体网络的一个很自然的机关报概念;局部连通性;讨论了两种类型的局部连通性;大局中部k-维子立方体连通性和局部子立方体连通性;一个局部连通的超立方体网络可容许大量错误结点且能确保超立方体网络是全局连通的;给出了满足局部连通性条件的超立方体网络中的几个高效的容错路由算法,文中的容错路由算法是分布式的和基于局部信息的,因而具有很强的实际意义。     

QoS路由算法性能评价模型的研究

QoS是新一代网络所必须支持的重要特性之一。在QoS的研究中,网络路由算法是至关重要的。本文基于当前世界上在QoS路由算法研究上的主要结果,建立起一个系统的QoS路由算法的性能评价体系,提出了评价指标参数,并详细介绍网络模拟器R－NS的设计模型和实现方法。