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

计算机学报 2007年第02期杂志 文档列表

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

粗代数与三值Lukasiewicz代数161-167

摘要：在粗糙集的代数方法研究中一个重要的方面是从粗糙集的偶序对（（下近似集，上近似集））表示人手，通过定义偶序对的基本运算，从而构造出相应粗代数，并寻找能抽象表示偶序对性质的一般代数结构．其中最有影响的粗代数分别是粗双Stone代数、近似空间代数和粗Nelson代数，它们对应的一般代数分别是正则双Stone代数、预粗代数和半简单Nelson代数．文章证明了这三种粗代数都可以化为三值Lukasiewiez代数，从而将它们统一到了三值Lukasiewiez代数的框架下．并在此基础上，更直接地证明了一个近似空间中的所有粗糙集可构成一个三值Lukasiewicz代数．最后给出一个实例，说明了从一个信息系统得到其对应三值Lukasiewicz代数的过程．

关于学习空间及分类风险评价的非单调一致性168-175

摘要：允许经验风险不为0是现代模式分类器构造方法区别于传统模式分类器构造方法的标志．为了进一步研究分类器构造观点的变化对模式分类系统所产生的更深入的影响，拓展模式分类系统的学习空间，作者讨论了限制经验风险必须为0的传统模式分类系统在分类性能问题上所受的限制，分析了影响模式分类系统分类性能的关键因素，给出了学习空间可拓展的必要条件，并构造了一种投机学习方法，证明了学习空间可拓展的充分条件．同时，在实验中观察到，分类器评价与测试集上的分类风险是非一致单调的．这一结论对于模式识别及其应用研究是严峻的．

求解SAT问题的量子免疫克隆算法176-183

摘要：将量子计算应用于人工免疫系统中的克隆算子，提出了一种基于量子编码的免疫克隆算法（Quantum Inspired Immune Clonal Algorithm，QICA）来求解SAT问题，并从理论上证明了算法的全局收敛性．算法中采用量子位的编码方式来表达种群中的抗体，针对这种编码方式采用量子旋转门和动态调整旋转角度策略对抗体进行演化，加速原有克隆算子的收敛；利用克隆算子的局部寻优能力强的特点，在各个子群体间采用量子交叉操作来增强信息交流，提高种群的多样性防止早熟．实验中，用标准SATLIB库中的3700个不同规模的标准SAT问题对QICA的性能作了全面的测试，并与单纯的量子遗传算法和简单免疫克隆算法以及著名的WalkSAT和PFEA2算法进行比较，仿真实验表明：Q／CA具有更高的成功率和运算效率．对于具有250个变量、1065个子句的SAT问题，QICA也仅用了1．357s，显示出了优越的性能，

一种模糊概念格模型及其渐进式构造算法184-188

摘要：传统形式概念分析方法无法处理现实中模糊和不确定信息，因此，对模糊概念格及其信息表示的研究具有重要意义．文中提出了一种模糊概念格模型，提出了模糊形式背景中属性隶属度值的窗口截取方法，定义了模糊概念的模糊参数σ和λ，给出了模糊概念格渐进式构造算法，推导出了模糊参数σ和λ的渐进式计算公式．模糊参数σ和λ分别体现了概念外延对于属性的隶属度的均值和发散程度．在模糊概念格渐进式构造算法中引入两个中间参数以实现模糊参数的渐进式计算．最后，进行了算法性能评估实验，结果表明模糊概念格的这种渐进式构造算法在时间上和空间上都具有良好的性能，

分式线性神经网络及其非线性逼近能力研究189-199

摘要：提出了结构简单的分式线性神经网络，证明该种神经网络可无限逼近R^m上有界闭子集到R^n上的任意连续映射，同时，证实该种神经网络可无限逼近R^m上无界闭子集到R^n上的在无穷远有极限的任意连续映射，扩充了BP神经网络的非线性逼近能力；给出了实现分式线性神经网络逼近有界或无界区域上连续映射的反向传播算法．仿真实验表明所给出的反向传播算法可行有效．该结果为无界区域上的分类问题和决策问题的解决提供了理论基础．

相邻因素组合测试用例集的最优生成方法200-211

摘要：软件系统是一个复杂的逻辑系统，有很多因素可能影响系统的正常运行，组合测试可以对这些因素及其相互作用可能对系统产生的影响进行检测．针对一类只在相邻因素间存在相互作用的系统，文中提出了相邻因素组合测试的概念，分别给出了相邻因素两两（二维）组合覆盖表、相邻因素N（N≥2）维组合覆盖表和多重维数相邻因素组合覆盖表的生成算法，并证明了3个算法均可以生成数量最优的相邻因素组合测试用例集．最后通过实际应用场景，分析了相邻因素组合测试的应用价值．

易错视频传输中基于带宽-失真代价最小化准则的部分重传算法212-224

摘要：针对视频传输系统主要关注的两个因素：传输所用的总体带宽和终端最终的解码失真，提出带宽-失真（BD）代价函数的概念，给出B—D关系定理及其证明．利用视频数据本身存在的时空相关的特点，进一步提出了基于最小化B—D代价的部分重传机制．实验结果及分析表明，相对于尽力而为ARQ机制，所提出的算法有如下几个特点：（1）在保持终端接收质量基本不变的前提下，能有效减少带宽（可达20％以上）；（2）在低比特率情形下性能比高比特率下的性能要好，所以更适合于低比特应用；（3）对运动平缓和纹理平滑的视频序列更为有效．

TTA-EC：一种基于传输触发体系结构的ECC整体算法处理器225-233

摘要：以传输触发体系结构（TTA）为基础，为支持大数运算扩展寄存器堆，增加模乘单元以加速模乘操作，提出一种ECC整体算法处理器TTA—EC．该处理器具有如下特点：（1）利用TTA工具链，可快速开发出基于TTA-EC的完整ECC公钥系统；（2）模乘单元将以基数为处理字长的高基数Montgomery算法与行共享流水结构相结合，具有良好的可扩展性；（3）流水单元实现矢量乘操作，并同时支持GF（p）和GF（2^n）双有限域；（4）通过调整总线宽度和流水单元个数，可满足不同性能／面积约束．在0．18μm 1P6MCMOS工艺下，其高性能和紧缩面积版本的规模分别为117．4K和40．6K，可分别在0．87ms和7．83ms内完成一次GF（p）或GF（2^n）上的192位EC标量乘运算，峰值功耗分别为242．1mW和28．5mW．

网络风险评估中网络节点关联性的研究234-240

摘要：在网络风险评估领域中，为了提高评估的准确性，很多研究工作中都引入了网络节点间的连通性，然而，这种性质还不足以表达出各节点间基于物理连通关系之上的某种特殊的逻辑关系，如一方对另一方独有资源的控制关系．为此，文中引入了网络节点关联性（NNC）的概念，通过对实践过程中若干种访问情景的分析，提出了NNC的分类方法，然后讨论了NNC的发现方法，并举例阐明了NNC在网络风险评估中的应用及作用．通过深入地分析和对比可以看出，利用NNC可以将若于孤立的弱点联系起来，有助于分析网络的安全风险；此外，NNC在包含各协议层连通性的基础上丰富了网络节点间独有的特权关系，利用NNC也有助于提高检测网络弱点和网络攻击的准确性．

基于RSA密码体制的门限签名241-247

摘要：在一个（t，n）门限签名体制中，原始签名者可以将他的签名权利以门限的方式委托给”个签名者，至少t个签名者合作，可以产生相应的签名，而任何少于t个签名者则不能．目前已经有很多基于离散对数问题的门限签名方案，但是并没有出现一个真正意义上的基于RSA密码体制的门限签名方案．鉴于RSA在理论及应用中的重要性，基于RSA构造门限签名体制是必要的．文中借助于RSA秘密共享的思想，构造了一个安全、有效的RSA门限签名方案．在文中的方案中，没有使用可信权威，所有的秘密参数都是由参与者分布式产生的．

保护私有信息的叉积协议及其应用248-254

摘要：叉积是计算几何中关于线段算法的核心。在计算叉积的算法中，若输入的点或线段由不同的用户提供且无须保护这些用户的隐私时，可以假设至少有一个用户能够获得所有的输入信息，从而用传统的方法解决问题．但是，当用户输入数据的隐私需要得到保护时，传统算法或对传统算法做简单改进均不能满足要求，而需要设计新的模式来解决问题。对此提出了半诚实模型下保护私有信息的点线叉积计算协议。讨论和分析了其安全性与正确性，并且以保护私有信息的线段相交判定为例说明了其用途．

基于可达关系的安全协议保密性分析255-261

摘要：借助形式化的方法或工具分析安全协议是非常必要而且行之有效的．进程演算具有强大的描述能力和严格的语义．能够精确刻画安全协议中各个参与者之间的交互行为．作者以进程演算为基础，嵌入消息推理系统以弥补进程演算固有的缺乏数据结构支持的特点，尝试地提出了一个基于可达关系的安全协议保密性分析模型．基于此模型，形式化地描述了安全协议的保密性，证明了一定限制条件下的可判定性．并且以TMN协议为例，给出了该模型的实例研究．

基于中介面加快光线跟踪计算262-271

摘要：提出一种新的光线跟踪方法，以提高光线找到相交面片的效率．它在场景中生成一些面积较大的规褴中介面片，然后为中介面上的每个点建立一个场，以记录到达该点的不同方向的光线将相交的面片．由此,光线跟踪时，一条光线可方便地找到相交的中介面，并通过查找中介面上所记录的内容，就能得到它所相交的面片．与已有方法相比，新方法不仅能很好加速主光线与阴影光线的计算，而且能很好地加速反射、折射等二次光线的计算．它能在GPU上方便地实现，并能有效地处理动态场景．

基于图形硬件的纹理图像编码与实时绘制算法272-280

摘要：真实感绘制对于细节的要求越来越高，应用程序通常采用多幅或大幅分辨率很高的纹理图像，有限的内存空间就成了一个制约的瓶颈．针对纹理图像的特点和可编程图形硬件的特殊要求，该文提出了一种新的面向绘制的编码算法——增量式纹理编码算法及相应的解压绘制算法，有效地解决了纹理存储容量和真实感之间的矛盾，并利用可编程图形硬件实现了实时解压绘制，该算法在图像压缩编码过程中，动态添加码表内容，只有当已有码表内容不能表示当前图像区域时，才增加码表内容．这种方法不仅能够对于自相似性较强的纹理图像取得很高的压缩比，而且由于码表的动态更新特性，可以对图像序列进行流式编码．在绘制纹理时，该算法充分利用了现有可编程图像硬件的特性，实现了实时解压绘制．文中分别对于静态图像和动态图像序列进行了实验，结果显示，此方法能灵活有效地对各类纹理图像进行编码．

压缩链码的研究281-287

摘要：对图像处理及模式识别中的链码技术进行研究．首先针对具有二位码长的顶点链码只有3个码值的情况，在不增加码长的情况下对其增加了一个码值，大大提高了其表达能力．其次，同样根据顶点链码的上述冗余情况对其进行了不等长编码压缩．然后，在上述两种改进链码的基础上，根据大量的统计数据提出了一种基于Huffman编码的新的压缩链码．文中还提出了一种对链码的评价方法．最后，用该评价方法和对实际图像的实验测试对所提出的链码和4种已有链码进行了理论上和实用方面的比较．比较的结果显示该文提出的压缩链码效率最高．

图像线状模式的有限混合模型及其EM算法288-296

摘要：针对能够用回归模型刻画的图像特征，提出一个有限混合识别模型．该模型由有限个回归类构成，每个类的模型误差可以是正态的，也可以是满足一定条件的任意分布．文中给出了估计线性回归类参数的EM算法，该算法町推广到高维情形．

LEO卫星环境下的SNACKTCP性能分析297-304

摘要：由于空间LEO（Low Earth Orbit）卫星通信网络受环境、通信链路、能源等诸多方面的制约，已经非常成熟的地面计算机网络协议在空间LEO卫星通信环境下是无法直接应用的．SNACKTCP（Selective Negative Acknowledgment TCP）是解决原有TCP不能适用于空间LEO卫星通信的改进方案，然而是否完全能在LEO卫星通信网络下应用还有待于进一步研究．作者在研究该改进协议的基础上进行NS2环境下的仿真模拟实验，比较分析了SNACKTCP和传统TCP的性能，还有针对性地进行了线路非对称模拟实验结果分析和链路误码率变化实验结果分析．证实了SNACKTCP在LEO卫星通信环境下的优良性能，并发现了其仍存在的问题，进而指出了实验的下一步研究方向．

计算机学报杂志短文

基因表达式编程初始种群的多样化策略305-310

摘要：基因表达式编程（Gene Expression Programming，GEP）算法是遗传家族的新成员，被广泛用于知识发现，其初始种群的质量对进化效率和进化结果至关重要．为了产生优势初始种群，提出了基因空间均匀分布策略（Gene Space Balance Strategy，GSBS），证明了描述编码空间量化性质的GEP编码空间定理．实验表明，GSBS提高进化效率超过20％．GSBS算法的思想还可以应用于其它进化计算中。