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

计算机学报 2008年第01期杂志 文档列表

计算机学报杂志综论

对等网络中的搭便车行为分析与抑制机制综述1-15

摘要：搭便车（free riding）行为在对等网络（Peer-to-Peer network）中日趋严重，它对网络健壮性、可用性和生命周期等造成了负面影响．设计、应用合理的搭便车行为抑制机制是当前对等网络研究的一个重要方向．文中首先描述搭便车行为的测量方法和发展趋势，然后分析搭便车行为的基本原理以及对对等网络性能的影响．依据数学建模和分析工具的差异，将已有搭便车行为抑制机制分为激励机制、博弈论方法、社会网络与经济模型三大类．文中归纳了三类抑制机制的建模方法，对其优、缺点进行了分析和比较，最后对搭便车行为抑制机制的未来研究方向进行了展望．

计算机学报杂志研究论文

循环ALCN—Tbox具有模型的条件16-23

摘要：分析了带循环定义的描述逻辑系统ALCN的研究现状和存在的问题，研究了循环ALCN—Tbox具有模型的条件，指出了Baader文中命题2．9（Let T be a terminology such that each cycle in GT contains an even number of negative arcs．Then T is monotone）的错误，并对该命题进行了修改，给出了循环ALCN～Tbox具有不动点模型（最小不动点模型和最大不动点模型）的条件．

一类根式不等式的有理化算法与机器证明24-31

摘要：文中讨论了一类根式不等式的有理等价问题．证明了这类根式不等式可等价转化为一组有理不等式．建立了一个算法RFD，并用Maple编程实现．对一个给定的这类根式不等式，RFD可自动快速地产生一组有理等价不等式．将RFD算法和差分代换方法相结合，给出了一大类具有相当难度的几何不等式的机器证明．此前该课题仅有的工作是杨路关于二次根式的结果．

一种在元素与颜色规模相近时的有效着色算法及其应用32-42

摘要：着色算法（color-coding）是求解NP难问题的重要手段之一．而在应用着色算法时，着色算法所产生的着色方案的规模极大地影响着问题的求解性能，故构造一个尽可能小的着色方案是着色算法所寻求的目标．目前存在的着色算法均基于完全散列函数，并要求元素数目n远大于颜色数目k，且k比较小，这个限制条件使得这些着色算法在一些实际情况下无法应用．该文主要研究在元素与颜色规模相近时（n≤2k）的有效着色算法，并着重分析在n≤2k情况下着色算法的性能．该文提出了一种基于划分思想的着色方案构造算法PBCC，证明了由PBCC产生的着色方案确实可以覆盖到所有的子集，并具体给出了可应用于（l，d）-（20，16）Motif查找问题的403种着色的构造方法．文章进一步分析了PBCC产生的着色方案规模，并证明了在n≤2k且n-k≥2的情况下，任何着色算法所产生的着色方案的规模｜S（n，k）｜都不小于（[n/2]n-k）＋[（n n-k）-（[n/2] n-k）2^n-k]／（2^n-k-2）．此外，文中也采用了渐进分析技术，证明了PBCC算法生成着色方案规模为O（e^2Rootof（e^x-e^μx＋1）（n-k）在n=2k的情况下结果是O（2．62^n-k）；同时，文中也证明了n≤2k情况下着色方案规模的下界为2^n-k．

结合位点进化距离与支持向量机的蛋白质分类方法43-50

摘要：生物信息学的一个关键的研究课题是理解细胞的分子机制，这依赖于对基因所决定的每一条蛋白质的含义或者功能的理解．一般通过与一条或多条功能已知的蛋白质的相似性比较来推测未知蛋白质的功能，其中，基于支持向量机的一些算法取得了很好的成果．SVM—pairwise算法是当前最好的基于支持向量机的算法中的一个，该方法利用两条序列的相似性来将蛋白质序列转化为固定长度的向量．文中提出了一种新的利用支持向量机算法对蛋白质序列进行分类的方法，这种方法使用位点进化距离代替两条序列的比对得分，该方法比SVM—pairwise有着显著的改善，在蛋白质结构分类数据库（SCOP）上进行的实验表明，该方法具有比SVM—pairwise更好的分类性能．

基于离散Hopfield网络求解极大独立集的茎区选择算法以及在RNA二级结构预测中的应用51-58

摘要：提出了一种利用离散Hopfield网络求解图论极大独立集的启发式算法，并将其应用于RNA-2级结构的茎区选择和预测当中．算法通过映射RNA序列的茎区为无向图中的节点，将预测RNA二级结构的问题转化为求解图的极大独立集的问题．定义了合理的能量变化函数，利用离散Hopfield网络进行迭代，以获得能量最优的预测结构．文中将算法与传统的最大匹配数算法以及最小自由能算法在运行时间上进行比较，并且选择特定的序列在茎区和碱基对水平上进行精度测试，结果证明该算法在效率和精度上具有一定的优势．算法的时间复杂性为max{O（n^2），O（N^2）），空间复杂度为O（N^2），其中”为RNA序列长度，N为RNA的茎区段个数．

一类具有大线性复杂度的四值低相关序列集59-64

摘要：对正整数N=OMod4，该文构造出了首类周期为2^N-1的四值低相关d-齐次序列集，并完全确定了它们的相关值分布．新构造的这类序列具有大线性复杂度，而且每一条序列的线性复杂度被精确地计算出．同已有的序列集相比，该文构造的序列的优点是在具有低相关性和较大的集合容量的同时，还具有很大的线性复杂度．这类新序列适用于密码系统和CDMA通信系统．

面向多自治域网格的信息服务模型及其实现65-76

摘要：网格是实现分布异构资源共享的有效模式，而信息服务实现系统服务与资源的有效管理，是网格系统的重要组成部分．ChinaGrid是由多个自治域组成的大规模网格，现有的信息服务不能满足此类系统特性与应用需求．文中提出网格信息服务体系GISA2．0，强化了域自治管理和资源信息的安全性．GISA2．0实现了可扩展的网格信息模型和面向服务、支持多种监控信息聚集的层次化信息管理框架．提出了基于分布XPath引擎的多域资源信息检索机制，实现了安全、快速和用户相关的虚拟全局资源视图．

基于分片的XML快速结构连接算法77-90

摘要：结构连接作为XML查询的重要部分，对查询性能来说起着非常重要的作用．目前有几种结构连接算法已经被提出，例如Stack—Tree、XR—tree．这些算法主要集中在节点之间关系的确定上．与之不同，作者从分片的角度去解决结构连接问题，首先把节点间的关系引申到分片之间的关系，从而得出各分片之间的一些性质，再利用分片间的性质来提高结构连接操作的性能．文中提出了一种基于分片的结构连接算法和两种优化方法，实验表明该算法在性能上要优于Stack—Tree算法和XR—tree算法．设计了一个简单而又高效的索引结构来存储分片结果，实验结果表明该索引结构的维护代价要小于XR—tree的维护代价．

基于相似关系的数据库分类不一致程度评价91-103

摘要：作为挖掘算法选择和评价的标准之一，数据集的分类不一致程度一直是分类规则研究中的一项重要内容．然而随着人们对不完备数据集数据挖掘的深入，建立在等价关系上的基于信息熵的评价方法已难以满足实际需要．文中在利用相似关系的基础上，结合证据理论，给出一种基于信任度与似然度的信息粒构建方法，同时构建了类似于不协调度和混淆度的系统分类不一致程度评价方法，并对其相关性质等进行分析与证明．由算例分析可以看出，文中研究结果能够较好地描述缺失环境下的系统分类不一致程度，同时当数据集不存在缺失时，该研究与以往研究具有相同结果．

一种新的业务过程管理模型104-111

摘要：通过对工作流本质的探讨和对WfMC工作流参考模型的分析，提出了在分解业务过程控制逻辑与应用逻辑的基础上，进一步将控制逻辑分解为路由逻辑与资源管理逻辑的思想．提出了描述资源管理逻辑的资源管理模型．基于资源管理模型提出一种新的过程管理模型BRM，给出了基于BRM的业务过程管理系统的系统框架和功能模块．与WfMC工作流参考模型的对比表明：BRM模块更清晰，柔性更突出，分解粒度更小．

基于运动趋势的自适应垂直切换算法及其性能评价112-119

摘要：采用不同的无线接入技术的多种网络的融合可以提高无线传输性能，为移动用户提供随时随地的网络连接。垂直切换足异构无线网络相互融合的基础．在垂直切换过程中，切换判定是一个非常重要的环节，直接决定切换性能．文中给出了常用的迟滞电平算法和驻留定时器算法中切换判定条件的形式化表达，并对其进行了性能分析．在此基础上，提出了一种自适应的垂直切换算法，通过分析节点的运动趋势，自适应地调节切换触发条件，有效提高垂直切换性能。所涉及的运算均为初等计算，算法简单，适用于低能量、低运算能力的移动设备．仿真实验表明，该算法的综合性能优于迟滞电平算法和驻留定时器算法．

一类非规则并行应用问题的通信集生成算法120-126

摘要：非规则计算是大规模并行应用中普遍存在和影响效率的关键问题．在基于分布式内存的数据并行范例中，如何针对非规则数组引用，有效地生成本地内存访问序列和通信集，是并行编译生成SPMD结点程序所必须解决的重要问题．文中针对两重嵌套循环中，下一层循环边界是上一层循环变量的线性或非线性函数，数组下标是两层循环变量的非线性函数这样一类包含非规则数组引用的并行应用问题，提出了一种在编译时生成通信集的代数算法．并且针对cyclic（k）数据分布和线性对齐模板，借助整数格概念，给出了编译时全局地址和本地地址之间的转换方法．文中还给出了相应的经过通信优化的SPMD结点程序．最后通过实例验证了算法的正确性．该算法的意义在于避免了传统Inspector／Executor非规则计算模型中的Inspector阶段，从而节省了运行时Inspector阶段通过穷举下标生成通信集的巨大开销．

寄存器堆互连的VLIW结构及其指令调度算法127-132

摘要：超长指令字（Very Long Instruction Word，Vuw）处理器一般采用总线互连的多簇结构，每个簇中的功能单元共享一个本地寄存器堆，簇间采用总线传输数据，以避免功能单元增多时，全连通结构的延时、面积和功耗的快速增长；但簇间数据共享时的拷贝和延时，使得处理器在性能上有所下降．文中提出了一种寄存器堆互连的多簇VLIW结构，采用寄存器堆来连接各个簇，从而可以避免簇间数据传输的延时和额外的数据拷贝操作．同时也提出了针对这种结构的指令调度算法，以提高指令调度的性能．实验结果表明，与全连通的VLIW结构相比，寄存器堆互连结构在性能上仅有13％左右的性能下降，代码长度则基本不变；这都优于总线互连的多簇结构．

一种流处理器体系结构MASA及其在流体力学计算中的评测133-141

摘要：提出了面向科学计算的64位流体系结构——MASA，它具有强局域性、并行性、解耦合访存操作和计算操作等特征，特别适合于计算密集型的并行应用．作者使用时钟精确的模拟器评测了流体力学中的典型应用在MASA上的运行性能，结果表明MASA在500MHz的情况下能够获得比1．6GHz的Iantium2近4倍的加速，证实了流体系结构在高性能计算领域的极大潜力．

低信噪比多目标检测的贪心算法142-150

摘要：针对SNR≤2dB的弱目标的检测问题，提出基于贪心原则的边检测边跟踪算法．通过可扩展节点完成状态更新，然后沿着航迹进行能量的累加，最后利用似然比检验确定目标．预处理阶段设计的时空滤波器，一方面通过混合核估计的空域滤波器去相关杂波，另一方面通过沿着时间轴的投影分割抑制噪声，将搜索空间压缩了80％以上．此外利用非参数统计理论对残差图像进行了独立性与正态性的验证．通过与传统的动态规划方法的实验对比分析表明，该算法的时间复杂度可以降低到mn，不仅具有速度上的优势，而且还可以保证比前者更高的检测率和更低的虚警．

一种新的基于在线采样的多物体跟踪方法151-160

摘要：跟踪多个运动物体，尤其是在遮挡过程中跟踪多个运动物体，是计算机视觉领域一个重要但具有挑战性的问题．该文提出了一种新的在线采样、更新学习和分类的跟踪框架来处理多物体跟踪问题、首先，对遮挡发生前若干帧的各物体进行块采样，作为训练样本进行在线分类器设计．各帧的物体区域也在线进行块采样，并用这些分类器来进行分类标号．如果遮挡没有发生，一些新的训练样本被添加用来更新分类器．当遮挡发生时，根据标号结果，前景区域被分割成多个目标物体．和以往方法相比，新方法不依赖于一些假设条件，如场景深度信息、物体的先验模型（比如形状、种类、区域内颜色各向同性、运动规律等），具有更好的适应能力．实验结果验证了该文方法的稳定性和有效性、

时空谱点源目标自适应滤波检测算法161-169

摘要：针对复杂背景下的点源弱目标检测问题，根据Wiener-Hopf方程在自适应滤波算法中的应用原理，提出了一种新的利用时间／空间／谱段的多维信息融合自适应滤波算法（ASTS filter）．该方法的研究主要有3个步骤：首先研究时域、空域突出和多谱段融合的性质，然后构造出针对运动弱点目标的滤波模板，最后将自适应RLS滤波器应用于有缓动背景下的多谱红外图像检测中．由于普通的RLS滤波器应用于图像处理采用的是像素点信息作为输入参数，其造成矩阵运算计算量过大、处理时间长等缺点，而将点目标进行空间、时间、谱段特征提取后的信息作为输入参数，不仅避免了大型矩阵的运算，还可获得更高的信杂比增益．通过大量实验数据，证明本算法具有优良的滤波性能，同时突破了点目标运动的轨迹限制．与其它算法的效果和计算量进行比较，证明文中算法更为快捷、有效和灵活．