生物信息挖掘中LIS算法研究*

探讨了生物信息挖掘中ó模式子序列问题的一个特例,即最长递增子序列(LIS)问题。对于LIS问题,分别用LCS算法、动态规划、动态规划结合二分法进行求解,并分析了这三种算法的时间和空间复杂度,对其中两种算法进行了实现,验证了时间和空间复杂性理论分析的正确性,最后得出了一种高效的LIS算法。     

一种改进的截断二进制指数后退冲突分解算法

传统的截断二进制指数后退冲突算法解决冲突问题时,每次都从指数1开始,而不管可能存在的冲突端数。相关文献基于已知冲突端口数而提出了一种动态改进算法,然而确定冲突端口数是很困难的。针对上述问题,本文提出了一种基于概率的动态设置初始窗口的改进算法,仿真实脸表明该算法是能有效降低冲突分解次数和分解时隙。     

有限信任显式传递P2P系统

P2P系统具有开放性和匿名性,这就使得恶意节点能够轻易地在网络中传播虚假的甚至有害的文件,从而损害了整个P2P系统的鲁棒性.针对该问题,文中提出了一种基于信任传递关系建立可信对等网络的算法,能够动态调整信任路径,隔离恶意节点和恶意节点集.实验表明即使在大量恶意节点相互合作的情况下,算法仍能有效地降低网络中虚假文件的下载数量.     

动态截断二进制指数后退冲突分解算法的研究

传统的截断二进制指数后退冲突算法解决冲突问题时,每次都将初始窗口设为2个时隙,而不管可能存在的冲突端数.已有学者基于已知冲突端口数而提出了一种动态改进算法,然而确定冲突端口数是很困难的.针对上述问题,本文提出了一种基于概率的动态设置初始窗口的改进算法,仿真实脸表明该算法是能有效降低冲突分解次数和分解时隙.     

非对称双向Base-k Chord

针对Base-k Chord的路由效率问题,本文对其finger表做出了非对称双向调整,即将其finger表奇数项保留为正向finger,偶数项finger对折到反向作为反向finger,调整后的finger表的大小不变.在此基础上提出了改进的路由算法,该算法每次选择离目标节点最近的finger进行路由.为了证明本文方法比2-Chord的对称双向finger方法更好,将2-Chord扩展成对称双向Base-k Chord,并与之进行了性能比较.实验分析发现,对称双向Base-k Chord的路由效率提升极小,非对称双向Base-k Chord有效地降低了平均路由跳数.     

无尺度、小世界Sierpinski网络统一模型

引入了单一参数的演化Sierpinski网络模型,统一了确定性和随机性两类Sierpinski网络模型。基于复杂网络理论提出的演化模型的一些特征能应用于对现实网络的研究。给出了推导度分布的算法和平均路径长度的仿真结果,数值仿真验证了理论分析的正确性,揭示了新网络模型的“小世界”特征。     

Bloom Filter研究进展

近年来,由于Bloom filter具有可压缩性和高效查询性,其在分布式数据库、网络缓存、对等网和信息检索等领域引起了越来越多的研究者关注。随着Bloom filter不同应用需求的出现,多种Bloom filter变体被提了出来,诸如:支持删除元素的CBF;可以统计频次型的SBF、DCF、dlCBF;大小可以动态伸长的DBF、SBF;压缩型BF等。本文对Bloom filter及其各种变体进行了介绍,并对其特点进行了分析比较,总结了它们各自的优势和不足,并进一步指出了Bloom filter未来的一些研究方向。     

信息检索中的相关反馈技术综述*

论述了信息检索中的向量空间模型、概率模型以及语言模型中所采用的相关反馈技术。其中主要介绍检索词的权重调整、查询扩展、文档相关反馈,以及语言模型中的查询语言模型和文档语言模型的调整。针对最近反馈方面的最新成果——基于term的反馈技术进行了探讨,指出了相关反馈在今后研究的方向,即提供个性化的如分层反馈和利用日志进行反馈,并讨论了相关反馈技术对检索性能的影响。     

兑换零钱问题的动态规划算法研究

兑换零钱问题是一个求解组合优化的问题。首先对兑换零钱问题进行了分析,证明了该问题满足动态规划的最优化原理,并给出了其动态规划解法;然后对本算法进行了时间复杂性和空间复杂性分析,得到时间复杂性由通常的动态规划算法的O（Mn2）提高到本算法的O（n3）,空间复杂性由通常的动态规划算法的O（Mn）提高到本算法的O（n2）,因此效率有了较大提高。最后通过实验对算法进行验证,证明了算法的高效性。该算法可以广泛应用于自动售货机。     

基于Bloom Filter的安全P2P共享模型

针对当前对等网中虚假文件的问题,提出了一种安全P2P共享模型(SPSM)。在该模型中为了激励节点共享自己的资源,引入虚拟货币(VC)以激励各个节点共享自己的资源;并在模型中引入了举报机制,即当网络中一个节点下载了虚假文件后就向CA(Certification Authorities,认证中心)举报提供虚假资源的节点,经CA甄别后将该恶意节点放入恶意节点集;为了节省存储空间,SPSM根据自身的特点,采用了Bloom Filter的变体DBF来存储恶意节点。为了验证提出的SPSM模型的有效性,将其与Trust模型进行了比较,结果表明SPSM模型比Trust模型更有效。