计算机学报杂志 北大期刊 CSCD期刊 统计源期刊

计算机学报 2005年第09期杂志 文档列表

计算机学报杂志综论

反射中间件的研究与进展1407-1420

摘要：反射中间件是当前中间件技术研究中值得注意的一个新方向.它克服了传统中间件'黑箱'结构的缺陷,具有系统结构行为有序开放、可重配置等特点,能支持针对不同应用类型进行定制,可较好地适应动态变化的分布式环境和应用需求,已在移动计算、多媒体应用等多个领域展现出较好的应用前景.该文在介绍反射计算与反射系统基本知识的基础上,首先分析归纳了反射中间件的核心概念和基本原理,给出一个反射中间件的一般结构.在此基础上提出一个反射中间件分类与比较框架,涵盖了反射类型、反射时间、反射范围、实现机制等方面的内容,而后依据此框架对目前几种具有代表性的反射中间件系统作综述和比较.最后对该领域值得进一步研究的问题进行了分析和讨论.

计算机学报杂志研究论文与技术报告

签密方案在分布式协议中的应用1421-1430

摘要：该文基于可验证秘密共享思想和对Zheng的签密方案的必要修改,首次构造了一种不需要可信中心的门限签密方案.它能同时达到门限签名和加密的双重目的,实现代价仅和门限签名相当,并具有非否认性质.该文对当前一些分布式密钥分配协议做了分析,并基于Naor的基本思想,重点利用签密方案设计了协议SC-DKDS.与其它协议相比,该协议在减低实现成本等方面更为有效,因为它不需要认证信道、秘密信道及复杂的零知识证明等.该文还在RO(Random Oracle,随机预言)模型中给出了以上协议的安全性证明.

基于中间件的动态重配置容错对象管理框架1431-1439

摘要：该文从容错QoS角度出发,为现有的基于中间件的容错对象管理框架增加自适应特性.首先把动态重配置定义成容错属性集(及其实现)、计算环境和资源变化描述、动态调整算法三者之间的互动关系,然后采用反射模型和/订阅模型建立了一个动态重配置管理框架,可以使系统在发现计算环境的变化、定制动态调整算法等多方面得到有力的支持,为系统有效实施动态重配置奠定了基础.

一种基于实测的高维动态负载平衡方法1440-1446

摘要：针对大规模科学计算中的强非规则结构负载问题,作者开发出一种基于实测的动态负载平衡方法.首先,将由规则结构化网格组成的模拟区域剖分成多块;其次,把块的高维坐标转换成一维Hilbert空间填充曲线(HSFC)索引;然后,基于实测信息采用多层均权法剖分按一维HSFC索引排列的块;最后根据剖分信息重分配块以平衡负载.它把仅适用于一维的多层均权法扩展到二维和三维,并引入更多的实测信息和块数据结构.与ISP方法相比,该方法在64个CPU上提高负载平衡效率10%,在某MPP的500个CPU上模拟强非规则结构负载问题时,获得了88%的负载平衡效率和84%的并行效率.

基于四值语义的缺省逻辑1447-1458

摘要：基于公式变换,给出一组缺省理论的变换方法,将命题语言L中的缺省理论变换到对应的命题语言L+中,保证了所得到的缺省理论的所有扩张均不平凡,并通过一种弱变换可同时保证缺省扩张的存在性.为缺省理论定义了各种四值模型,使得缺省逻辑具有非单调超协调推理能力,并证明了L+中的缺省扩张与L中缺省理论的四值模型之间具有一一对应关系.四值模型描述了公式变换的语义,基于四值语义的缺省推理通过缺省理论的变换技术能在标准的缺省逻辑中实现.

M-GEP：基于多层染色体基因表达式编程的遗传进化算法1459-1466

摘要：该文提出了一种新的基于多层染色体基因表达式编程的遗传进化算法M-GEP,新算法引入了多层染色体的概念,利用染色体构建的层次调用模型对个体进行表达,在解决实际函数发现、电路进化等实际问题中取得了良好效果.该文主要贡献包括:(1)提出了基于多染色体的基因表达式编程算法(M-GEP);(2)建立了不同染色体的层次调用模型及存储结构;(3)提出并实现了基于染色体的重组算子和基因随机重组算子.对多基因GEP和单基因GEP的对比实验结果表明,平均进化辈数仅为后者的29%～81%.

大规模时间序列数据库降维及相似搜索1467-1475

摘要：提出一种基于分段多项式表示(PPR)的时间序列数据库相似查询的系统化方法.PPR是一类基于线性多项式回归的正交变换.用PPR变换索引时间序列数据在理论上具备非漏报性质.文中分析了PPR的计算复杂性以及查询阈值的下界,并提出了一种衡量时间序列相似查询算法之查询效率的定量指标.与基于离散傅立叶变换(DFT)和离散小波变换(DWT)的时间序列相似查询算法所作的对比实验表明,所提算法可以用低的索引结构维数获得高的查询效率.

基于子句权重学习的求解SAT问题的遗传算法1476-1482

摘要：该文提出了一种求解SAT问题的改进遗传算法(SAT-WAGA).SAT-WAGA算法有多个改进性特点:将SAT问题的结构信息量化为子句权重,增加了学习算子和判定早熟参数,学习算子能根据求解过程中的动态信息对子句权重进行调整,以便防止遗传进程的早熟,同时,算法还采用了最优染色体保存策略,防止进化过程的发散.该文最后描述了实现包括SAT-WAGA等多个算法的实验系统,对选择最佳早熟判定参数值给出了一些有效的建议.实验结果表明:与一般遗传算法相比,SAT-WAGA算法在求解速度、成功率和求解问题的规模等方面都有明显的改善.

网络日志规模分析和用户兴趣挖掘1483-1496

摘要：文章围绕网络日志中是否蕴含用户访问Web的规律性特性以及如何利用这些特性,研究了日志规模与用户数、Web文档数以及单位用户访问的Web文档数的关系;通过用户对Web访问动机的分析得出结论:一定时间段的Web访问日志中蕴含了用户的稳定兴趣;利用日志中蕴含的用户稳定兴趣,提出了一个基于用户行为的相关文档检索模型和搜索引擎系统SISI.SISI的实际检索性能与分析检索模型所得结论一致:检索准确率和检索时间主要依赖于用户数,检索返回的记录数主要依赖于文档数.

一类弱集合覆盖问题的近似算法1497-1500

摘要：在近似算法领域,集合覆盖(Set Cover)是研究的比较早和比较透彻的问题之一.该文提出了一类与集合覆盖很相似的问题:集合击中和弱集合b -覆盖,并且给出了解决它们的近似算法,还证明了它们的不可近似性.

弱可逆有限自动机的分解1501-1507

摘要：有限自动机公开钥密码体制的提出进一步激励了有限自动机可逆性的研究.在有限自动机公开钥密码体制中首次提出了自动机化合的概念.易知,两个弱可逆有限自动机的化合仍然是一个弱可逆有限自动机并且它的延迟步数不大于前两个有限自动机延迟步数之和.然而,另一方面,如何将一个弱可逆有限自动机分解为两个弱可逆有限自动机的化合却是一个非常困难的问题.该文主要考虑了一类n元严格延迟τ步弱可逆有限自动机M的延迟步数的分解问题.给出了一类特殊的n元弱可逆有限自动机分解的条件和结果.首先证明了如果对M中的每个状态s有T(s,τ)枝等,则M可分解为τ个延迟1步弱可逆有限自动机的化合.然后证明了M可分解为一个τ-m步弱可逆有限自动机和m阶延迟元的充要条件是对M中的每个状态s有T(s,m)枝等.

一类Vague系统的万能逼近性1508-1513

摘要：基于规则的模糊系统在表示信息方面受到模糊集隶属度不能区分正面证据和反面证据的限制.对此,该文提出了基于Vague规则的一类Vague系统,它包括SISO和MISO Vague系统;证明了:对于定义在紧集上的连续函数f,存在一类Vague系统,其Vague关系ε-逼近f;Vague关系被去Vague化后,得到的系统输出万能逼近f.一类Vague系统增强了不确定信息的表示能力,扩大了万能逼近的适用范围并提供了更优良的实际的万能逼近器.

基于布尔剪枝的多值广义量词Tableau推理规则简化方法1514-1518

摘要：Tableau作为自动推理的有效方法之一在许多领域中有重要的应用.该文作者在已提出的布尔剪枝方法基础上,对含广义量词(交和并)规则的简化方法进行研究,建立了一套含广义量词的一阶多值逻辑公式的简化Tableau推理方法.通过实例分析,对简化前后结果对比表明,改进后的Tableau方法,在推理效率上有很大的提高.

一种新的基于构造型神经网络分类算法1519-1523

摘要：该文提出一种基于构造型神经网络的最大密度覆盖分类算法,该算法直接从样本数据本身入手,通过引入一个密度估计函数对样本数据进行聚类分析,找出同类样本中具有最大密度的样本数据点,然后在特征空间里作超平面与球面相交,得到一个球面领域覆盖,从而将神经网络训练问题转化为点集覆盖问题.该算法有效地克服了传统神经网络训练时间长、学习复杂的问题,同时也考虑了神经网络规模的优化问题,实验证明了该算法的有效性.

典型相关分析的理论及其在特征融合中的应用1524-1533

摘要：利用典型相关分析的思想,提出了一种基于特征级融合的组合特征抽取新方法.首先,探讨了将典型分析用于模式识别的理论构架,给出了其合理的描述.即先抽取同一模式的两组特征矢量,建立描述两组特征矢量之间相关性的判据准则函数,然后依此准则求取两组典型投影矢量集,通过给定的特征融合策略抽取组合的典型相关特征并用于分类.其次,解决了当两组特征矢量构成的总体协方差矩阵奇异时,典型投影矢量集的求解问题,使之适合于高维小样本的情形,推广了典型相关分析的适用范围.最后,从理论上进一步剖析了该方法之所以能有效地用于识别的内在本质.该方法巧妙地将两组特征矢量之间的相关性特征作为有效判别信息,既达到了信息融合之目的,又消除了特征之间的信息冗余,为两组特征融合用于分类识别提出了新的思路.在肯考迪亚大学CENPARMI手写体阿拉伯数字数据库和FERET人脸图像数据库上的实验结果证实了该方法的有效性和稳定性,而且识别结果优于已有的特征融合方法及基于单一特征进行识别的方法.

一种基于误差控制的网格多分辨模型生成算法1534-1540

摘要：提出一种网格多分辨模型生成算法.该算法以最大误差L∞控制的网格简化算法为基础,通过删除边和拆分点操作进行向下和向上采样,将网格模型表示为由一个低分辨率的网格和一系列修改操作组成的多分辨模型.同其它算法相比,该算法在初始向下采样时,重点考虑了简化误差对模型精度的影响.在生成网格多分辨模型时,该算法将细化操作分解为对网格模型的几何修改信息和各细化操作之间的关系信息,确保了多分辨模型的健壮性.该算法可通过三角片数和简化误差两种方法来调整网格模型分辨率,实验结果证明了本算法的有效性.

基于最优位置计算的快速亚像素运动估计1541-1548

摘要：亚像素运动估计是提高视频压缩性能的有效方法,但当前普遍采用的亚像素全搜索算法不仅运算复杂度极高而且随亚像素精度的增加插值存储开销成指数级增长.该文提出了一种快速算法,该算法首先利用整像素运动估计的中间结果直接计算出最优亚像素位置,并在此基础上将最终搜索点数减少到2个以下,避免了传统方法的逐点搜索比较,不仅大幅度提高了搜索速度,且插值存储开销趋近于零.实验结果表明该算法以极小的搜索代价取得了与全搜索相当的效果.

DCT域半易损水印技术1549-1557

摘要：该文提出了一种DCT域半易损水印技术用于图像内容认证.水印嵌入算法基于DCT域的JPEG压缩不变特性,对一定质量的JPEG压缩是稳健的.水印比特包括认证比特和恢复比特.认证比特是块自嵌入的,可以对不可接受的图像篡改进行准确的检测和定位,而恢复比特则可以对篡改的图像进行一定程度的恢复.该文还分析了DCT变换过程中取整误差的影响,从理论上证明了水印嵌入算法中迭代过程的收敛性.实验结果证明了该半易损水印可以容许一定程度的JPEG压缩和AWGN噪声,对局部发生的篡改可以有效地检测、精确定位并进行内容恢复.