计算机研究与发展杂志 北大期刊 CSCD期刊 统计源期刊

计算机研究与发展 2008年第Z1期杂志 文档列表

基于正则表达式的应用层协议识别加速-

摘要：在当今网络中,传统的采用端口进行协议识别已越来越无法满足需求.采用了正则表达式进行协议识别,并对其匹配正确性和速度进行了优化.通过将NFA匹配引擎转换为DFA匹配引擎,不仅减少了其状态数,还提高了匹配的速度;在匹配方式上提出了3种匹配方式,并加以测试比较,并与One-Pass扫描算法相结合.通过对DARPA数据集进行测试,验证加速后的匹配正确性比L7-filter高,匹配速度则可达到其6.5倍.

线性μ-演算交换深度的可判定性及其复杂度1-6

摘要：模态μ-演算被十分广泛地应用在模型验证技术中.影响模态μ-演算检验复杂度的主要瓶颈来源于规约公式的交换深度.讨论了线性μ-演算交换深度的可判定性以及求解复杂度.证明了线性μ-演算交换深度是可判定的;同时证明了对于长为l的公式判定及求解的复杂度为2O(l logl).

求解长方体Packing问题的高效算法7-10

摘要：对典型的NP难度问题--著名的长方体Packing问题,通过观察体会人类几千年来在砌石头下围棋等活动中形成的经验和智慧,受到谚语"金角银边草肚皮"的启发,并将它发展提高到"价值最高钻石穴",提出了一种最大穴度的占角动作优先处理的拟人算法.计算了Loh和Nee提出的15个代表性的算例,算法在合理的时间内得出了高空间利用率的布局,其精度达到了国际先进的纪录.

结合预测机制和QoS约束的网格资源调度算法的研究11-16

摘要：资源调度是网格计算领域中的研究热点之一.以达到最优的资源利用率和提高用户对服务的满意程度为目标,定义了资源QoS约束和形式化描述;在任务完成期限和网络带宽的双重属性约束下结合预测机制,提出了网格资源调度算法Senior;应用GridSim工具包实现了相关的调度算法,并对调度算法仿真结果中的数据进行了分析和比较,验证了Senior调度算法在解决类似问题的优势.

演化算法的最优轨道分析17-20

摘要：基于最优控制理论,提出了演化算法的一种最优轨道分析方法.将演化算法描述成一个动力系统,定义了它的时间最优控制模型.运用著名的Pontryagain极大值原理,分析了演化算法的最优轨道,并利用矩阵范数理论对最优轨道进行了一些理论估计.同时将理论分析结果应用于演化算法的设计之中,导出了一种新的选择策略和终止条件.

网格环境下的静态启发式任务调度算法21-25

摘要：针对网格环境中应用程序常为复杂的计算密集型的并行分布式应用程序,提出了一个新的基于复制和插入的启发式任务调度算法(duplication-and-insertion-based scheduling,DIBS),可以同时执行多个应用程序,利用决定路径对任务进行排序,缩短了应用程序总的执行时间,该算法还平衡了处理器间的负载.实验结果表明,该算法更加符合网格的复杂环境,能够更好地满足不同用户的实际需要.

基于最小聚类划分的K-means聚类(1+ε)近似算法26-30

摘要：k-means聚类算法是解决聚类问题的一个常用方法.近年来,国外许多学者对该问题的近似常数算法和(1+ε)近似算法进行了研究.利用Kumar等人随机取样技术对于基于最小聚类划分k-means提出一个(1+ε)随机近似算法.该算法利用随机取样技术从集合中求出部分取样点,再对随机取样点进行组合找出每个聚类的部分点,将该部分点的质心点作为相应子聚类簇的质心点.通过多次运行该算法可以以较高概率求出k-means聚类的1+ε近似值.

无线网络中的在线信道分配问题31-34

摘要：研究一个无线网络中信道分配的最大化问题.对该问题的离线版本给出了一个O(n2)时间的算法.对在线问题的一般情况,证明了k-look-ahead算法的下界至少为(k+2)*/(k+1);还给出了一个竞争比为2的1-look-ahead算法.

基于分层遗传算法的网格任务调度策略35-39

摘要：针对传统的网格任务调度算法存在的缺陷,提出了用分层遗传算法来实现对网格任务调度策略的优化.在构造分层遗传算法时引入了SGA,AGA和CHC算法. SGA采用基本的遗传操作,保证了种群的多样性;AGA对交叉概率和变异概率的动态调整,保证了遗传算法的收敛性;CHC算法强调优良个体的保留,加快了遗传算法的收敛速度;分层遗传算法在吸收了这3种算法优点的基础上进行优化.实验结果表明,分层遗传算法在结果精度和收敛速度上都较其他算法有较大程度的提高.

无向平面单位容量网络中的最大流40-42

摘要：无向平面单位容量网络中的最大流问题在VLSI设计等领域中有广泛的应用.针对无向平面单位容量网络的特点, 给出这类网络中一个O(n)时间的最大流算法, 比一般平面网络中O(nlog n)时间的最大流算法快log n倍.

一种基于消解的变量极小不可满足子公式的提取方法43-47

摘要：变量极小不可满足(VMU)问题是极小不可满足(MU)问题的一个扩充和延伸.着重研究VMU子公式的提取算法.首先从理论上比较MU和VMU的基本性质,并分析了目前流行的MU子公式提取算法.研究Davis-Putman-消解的基本性质,给出一个判定变量极小不可满足公式的充分必要条件,进而提出一个基于消解的VMU子公式提取算法.此算法可以使用ZBDDs压缩存储消解式,并实现单步多重消解.

K分组合型Bloom Filter方法的设计48-52

摘要：Bloom Filter是一种采用位向量表示数据集合并利用Hash函数支持有效数据查找的方法.它能够很好地判定某个元素是否属于给定的集合.拆分型Bloom Filter是Bloom Filter的一种改进,它能较好地缓解分布式环境下集合元素动态增长导致的查找误称率增大问题.作为一种新的K分组合型Bloom Filter,通过与Bloom Filter和拆分型Bloom Filter比较分析的结果表明,该方法能够在误称率、向量空间和平均判定时间3个指标中得到较好的平衡.

顶点覆盖问题线性内核算法53-56

摘要：参数复杂性作为算法研究的一个重要分支近10年在国际上受到了广泛的关注,线性内核问题作为参数复杂性研究的一类重要问题被广泛研究.主要给出了顶点覆盖问题的线性内核算法,在国内首次从理论上证明了顶点覆盖问题存在线性内核.算法首先通过顶点覆盖问题的2近似算法,将图的顶点集合分成两个顶点集合A,B,进而通过一系列规约将原始图的顶点覆盖问题转换到新图的顶点覆盖问题,然后证明了新图的顶点数目至多为2k,并且2k是这个问题的下界(k为参数具体定义见文章).

基于图的分解与合并的静态事务调度算法57-61

摘要：在各种数据系统的处理中,总有一系列相对独立而相互关联的事务系列组成.如何合理地安排这样的事务的顺序,一直是数据系统优化中存在的问题.该问题的一般化形式是一个NP问题,可以归约为一个点、边均有权值的图上有多输入、多输出问题,寻找时间代价最小且使得点和边尽可能满足容量需求的最短路径.为此,考虑一种基于图的分解与合并的计算方法,利用一种新的算法,并从理论上分析其优良性.

最大边染色的指数时间算法62-66

摘要：最近,凤旺森,张立昂,曲婉玲,王捍贫对源于无线Mesh网络中的一个新的计算问题--最大边染色问题--提出了常数比近似算法.最大边染色问题要求对图的所有边染色,满足对任一顶点v,与其相关联的所有边所染的颜色种数不超过正整数q(q≥2),求使用颜色种数最多的染色方案.然而,他们并没有给出该问题的任何精确算法.提出了几个指数时间的精确算法并分析了它们的复杂度.对完全图可以在多项式时间内找到精确解.

Pollard p-1因子分解的DNA计算机算法67-71

摘要：如何有效地对大整数进行因子分解是数学上的一个难题.给出了基于分子生物技术的因子分解问题的DNA计算机算法.算法以Pollard p-1算法为基础,利用DNA分子生物操作完成加、减、乘、除运算,实现平方-乘以及欧几里德算法,产生并得到最终解.基于分子生物学的实验表明,该算法是可行和有效的.

一种面向网格计算的分布式匿名协作算法72-80

摘要：基于TCG提出的可信计算技术为网格协作安全性提出一种匿名分组身份验证算法,该算法可以非常可靠地解决网格计算平台之间的身份匿名验证问题.算法使用一个硬件模块TPM解决远程的身份验证,并通过TPM机制可以提供可靠的匿名验证和平台认证功能.算法中所有涉及的验证过程都是基于匿名机制实现的,除了实现匿名验证机制以外,算法还提供一套完整标记恶意网络实体的方法.提出了网格计算中虚拟分组的匿名认证平台架构,并在此架构基础上分成5步实现匿名验证算法,然后说明了算法在一种对等计算平台的应用实例,与GT2,GT3,GT4以及信任管理进行安全性的比较,并设计一个实验评价其性能.

绝热量子搜索算法中的纠缠与能量分析81-86

摘要：为了进一步研究量子纠缠与量子计算速度及能量的关系,通过计算von Neumann纠缠熵,分析了时间复杂度分别为O(N )和O(1)的绝热量子搜索算法的量子纠缠度随时间的变化关系,并对两者进行了比较.实验结果表明,量子纠缠对绝热量子计算的运行时间具有明显的影响,较大的纠缠可以导致更短的运行时间,反之亦然.同时对纠缠与能量的关系给出了一般性解释,即注入能量导致系统的纠缠增大,并因此缩短算法的运行时间.此外还分析了纠缠与量子系统初态的关系.实验表明系统初态形式不同,其纠缠度也不一样.初态为等幅叠加态的算法涉及的纠缠度明显大于初态为非等幅叠加态的算法.