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

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

计算机学报杂志研究论文

描述逻辑FL-循环术语集的语义及推理185-195

摘要：循环术语集是描述逻辑长期以来的研究难点，它的最基本的问题即语义及推理问题没有得到合理的解决，文中分析了描述逻辑循环术语集的研究现状和存在的问题，在Baader的基础上进一步研究了描述逻辑FL^-循环术语集的语义及推理问题．给出了FL^-循环术语集的语法、语义和不动点模型的构造方法．针对FL^-循环术语集的需要，提出了一种新的有限自动机，使用有限自动机给出了不动点语义和描述语义下FL^-循环术语集的可满足性和包含推理算法，证明了推理算法的正确性，并给出了推理算法的复杂性定理。

基于进化策略方法求任意函数的数值积分196-206

摘要：提出了两种基于进化策略求任意函数数值积分的新方法，其中方法一是基于混合基函数进化策略的数值积分算法；方法二是基于不等距点分割的进化策略数值积分算法．两种算法都采用适用于高维优化问题的单基因突变进化策略，使得该算法不但能计算通常意义下任意函数的定积分，而且能计算奇异函数积分和振荡函数积分．最后给出几个数值积分算例，并与传统数值积分方法作了比较，仿真结果分析表明，两种算法十分有效，能够快速有效地获得任意函数的数值积分值。

多项式等式型几何定理的可读证明207-213

摘要：目前的智能几何软件都使用基于搜索法的定理证明器作为推理引擎，其主要缺点是不能可读地证明涉及到几何量代数运算的几何定理，这极大地限制了智能几何软件的实际应用．对一类结论为几何量多项式等式的几何定理，文中提出了一种能给出可读证明的启发式搜索算法．该算法通过引入多项式的变形操作算子——标准项代换，把证明结论为多项式等式g=0的几何定理转化为寻找从g到0的标准项代换序列的搜索问题．采用Lisp语言实现了该算法，并做了30个结论为几何量等式的几何定理的推理实验．实验结果表明算法具有较高的推理效率。

一种具有精确边界的重复体识别算法214-219

摘要：当前大部分重复体识别算法不是依靠于已经标识的重复体数据库就是定义重复体为两个最大长度的相似序列，而没有一个严格的定义来平衡重复体的长度和频率．针对这些问题文中提出了一种基于局部序列比对算法BLAST变型且支持空位的快速识别重复体的RepeatSearcher算法．算法通过定义重复体的精确边界运用逐步扩展调和序列来识别重复体．算法使用C．briggsae基因组序列作为测试对象，并与当前通用的重复体识别算法RECON以及新近的识别算法RepeatScout做了比较分析．结果表明RepeatSearcher使每一条重复体序列具有了精确的边界，而且相对其它算法在没有损失精度的情况下，缩短了算法的运行时间．

基于泛化竞争和局部渗透机制的自组织网TSP问题求解方法220-227

摘要：旅行商问题（TSP）是组合优化中最典型的NP完全问题之一，具有很强的工程背景和应用价值．文章在分析了标准SOM（Self-Organizing Map）算法在求解TSP问题的不足和在寻求总体最优解的潜力的基础上，引入泛化竞争和局部渗透这两个新的学习机制，提出了一种新的SOM算法——渗透的SOM（Infiltrative SOM，ISOM）算法．通过泛化竞争和局部渗透策略的协同作用：总体竞争和局部渗透并举、先倾向总体竞争后倾向局部渗透、在总体竞争基础上的局部渗透，实现了在总体路径寻优指导下的局部路径优化，从而使所得路径尽可能接近最优解．通过对TSPLIB中14组TSP实例的测试结果及与KNIES、SETSP、Budinich和ESOM等类SOM算法的比较，表明该算法既简单又能使解的质量得到很大提高，同时还保持了解的良好的稳健特性。

用于约束多目标优化问题的双群体差分进化算法228-235

摘要：首先给出一种改进的差分进化算法，然后提出一种基于双群体搜索机制的求解约束多目标优化问题的差分进化算法．该算法同时使用两个群体，其中一个用于保存搜索过程中找到的可行解，另一个用于记录在搜索过程中得到的部分具有某些优良特性的不可行解，避免了构造罚函数和直接删除不可行解．此外，文中算法、NSGA-Ⅱ和SPEA的时间复杂度的比较表明，NSGA-Ⅱ最优，文中算法与SPEA相当．对经典测试函数的仿真结果表明，与NSGA-Ⅱ相比较，文中算法在均匀性及逼近性方面均具有一定的优势。

多Agent动态影响图及其一种近似推理算法研究236-244

摘要：针对多Agent影响图不能建模动态环境和多Agent马尔可夫决策过程难以表示Agents之间结构关系的问题，提出一种新决策模型——多Agent动态影响图（MADIDs）．为了能有效地对MADIDs进行推理，提出一种扩展的BK（EBK）近似推理算法，其扩展体现在三个方面：在BK算法中加入效用结点的边际化操作，加入分割团来减小BK算法的推理误差，使用MADIDs分层分解所生成的联合树来降低推理的复杂性．在模型实例上的实验结果显示了MADIDs模型和EBK算法的有效性。

多智能体系统时态认知规范高效符号模型检测的算法研究245-252

摘要：Clarke和McMillan提出了利用mu演算和OBDDs符号模型检测时态逻辑的方法,这些方法是非常有效的，能用于验证许多具有极大状态空间的实际系统（状态个数可以超过10^20）．但是，这些方法不能检测知识逻辑．而时态认知逻辑能更精确地描述分布式领域中系统和协议的规范．文章首先讨论了Kripke结构和mu演算的扩展，然后提出了利用扩展mu演算和OBDDs符号模型检测时态认知逻辑的方法。

无线传感器网络中节点非均匀分布的能量空洞问题253-261

摘要：节点非均匀分布策略能缓解无线传感器网络中的能量空洞问题．文中从理论上探讨这种策略，证明在节点非均匀分布的圆形网络中，如果节点持续向Sink节点发送数据，能量空洞现象将无法避免，而当节点数目满足一定关系时，网络中能够实现次优能耗均衡．文中提出一种节点非均匀分布策略及相应的路由算法用于实现这种次优能耗均衡，模拟结果显示网络生存周期终止时，处于网络内部的节点几乎达到了能耗均衡。

Adhoc网络寻路阶段的合作激励机制研究262-269

摘要：如何激励属于不同利益最大化实体的自私节点合作是当前Adhoe网络研究中的一个热点问题．现有的自私节点检测和激励机制主要针对数据传输阶段，不能适应寻路阶段的特点．文中基于邻居节点中继和生成的路由请求包之间的统计关系，提出了一种适用于按需路由协议寻路阶段的自私行为检测和惩罚机制，并利用博弈论工具将其建模为噪声环境下的重复囚徒困境博弈，对算法激励合作的有效性进行分析．理论分析和仿真结果显示，该算法能够有效地惩罚寻路中的自私行为，促进节点合作。

一种基于推荐证据的有效抗攻击P2P网络信任模型270-281

摘要：提出一种基于推荐证据的对等网络（Peer-to—Peer，P2P）信任模型RETM（Recommendation Evidencebased Trust Modelfor P2P networks），解决了基于推荐的信任模型中普遍存在的在汇聚推荐信息时无法处理不确定性信息以及强行组合矛盾推荐信息引起的性能下降问题，同时，RETM采取推荐证据预处理措施，在合成之前有效过滤了无用的以及误导性的推荐信息，使得该模型具有一定的抗攻击性能．在推荐信息的查找问题上，RETM提出了基于反馈信息的概率查找算法，该算法在降低了网络带宽开销的情况下，提高了信息查询的准确率．实验证明RETM较已有的信任机制在系统成功交易率、模型的安全性等问题上有较大改进。

基于逆向分层的网格工作流调度算法282-290

摘要：有向无环图DAG（Directed Acrylic Graph）描述的工作流时间费用优化问题是计算网格下一个基本的且难以求解的问题．通过分析DAG图中活动的并行和同步完成特征，采取由后向前方法将活动逆向分层（Bottom Level，BL），将工作流截止期转化为层截止时间，提出截止期约束的逆向分层费用优化算法DBL（Deadline Bottom Level）．算法中同层活动的开始时间不同于DTL（Deadline TopLevel）算法中设置相同的策略，而是分别由其前驱活动确定，时间浮差被平均分配到各分层，以尽量增大活动的费用优化区间．通过大量模拟实验将DBL和MCP（minimum Critical Path）、DTL两算法比较，结果表明DTL将MCP的平均费用降低15．62％，而DBL将MCP的平均费用降低24．74％．最后讨论了截止期和分组参数对算法性能的影响。

Petri网的一类禁止状态问题的混合型监控器算法设计291-298

摘要：针对广义互斥约束下Petri网的不可控影响子网为状态机的一类禁止状态问题，给出了观测器的设计方法，并基于观测器得到了求解最大允许控制策略的算法．利用观测器将广义互斥约束简化为单禁止库所约束，并将存在不可控变迁的问题简化为相当于变迁全部可控的问题，这有效地解决了不可控变迁带来的计算复杂性问题．最后，利用一个地铁交通调度示例验证和说明该监控器设计方法．

一种基于活跃周期的低端口数低能耗寄存器堆设计299-308

摘要：多端口寄存器堆有助于挖掘指令级和线程级并行性，但同时带来面积、能耗和访间时间的压力．文章面向超标量和SMT处理器，给出了一种方法，即通过增加一个小的活跃值堆（Active Value File，AVF）选择性地保存处于活跃周期（从产生到最后一次使用之间）的物理寄存器值．AVF结构可分担主寄存器堆的访问压力并降低端口数目，实现简单且具有写过滤的特点．在获得较大幅度能耗降低的同时不影响时钟频率且IPC损失较小。

使用取指策略控制同时多线程处理器中个体线程的性能309-317

摘要：当前，对同时多线程（Simultaneous Multithreading，SMT）处理器取指策略的研究大都集中在总体性能的优化上．文中提出一种新颖的SMT处理器取指策略（Controlling Performance of Individual Thread，CPIT），用于控制个体线程的执行．结果表明，对于模拟的所有负载，CPIT在94％以上的情况下都能保证受控线程获得期望性能．而对于失败的情况，受控线程的平均性能偏差不超过1．25％．此外，CPIT策略对处理器总体性能的影响并不大．与ICOUNT这种以优化性能为目标的取指策略相比，总体性能的平均降低不超过3％，而除受控线程外的其他线程的性能平均只降低了1．75％。

一种数据并行中的群通信优化策略318-328

摘要：群通信是影响大规模数据并行系统效率的关键因素，其主要发生在程序不同阶段间的数组重分布与循环划分后的数组重映射这两种情况．在一次通信中显著影响群通信效率常被忽视的因素是消息冲突和消息长度的不一致．因为它们会导致进程间大量的空闲等待时间．然而以前的研究要么不能完全避免消息冲突，要么针对某些特殊情况．对此，提出了在数组分布为Block_Cyclic（k）情况下的一种更具有普遍适用性的通信调度策略CSS．通过证明表明该策略能使一个通信步内的消息互不冲突且消息长度尽量相等．从而最小化通信调度生成时间和实际通信时间．最后的测试结果也表明，与传统的通信优化算法和MPI_Alltoallv实现相比，CSS策略使得通信效率得以明显提高。

H．264／AVC码率控制优化算法329-339

摘要：提出了一种新颖的编码特性预测机制，较为充分地利用了视频信源的时空相关性，改进了率失真建模的有效性；利用Lagrangian优化理论推导出两种率失真优化的位分配方案，并实现了相应的码率控制算法，即线性模型算法和二次模型算法．大量实验数据表明：线性模型算法和二次模型算法的编码效率基本上相同，而前者的码率控制能力稍优于后者；和H．264／AVC参考软件中所采用的JVTG012码率控制算法相比，两种新算法在获得更高编码效率的同时，能够更加准确地控制输出码率。

基于变分和小波变换的图像放大算法340-345

摘要：为了更好地放大图像，利用小波变换的思想，提出了一种变分和小波变换相结合的图像放大算法．该算法的思想是先构造一个用Besov范数估计图像正则性的变分泛函，然后在小波域中最小化变分泛函得到放大图像．小波变换后的高频分量具有丰富的细节边缘信息，因而能够重构出高质量的图像，而且小波的引入使得文中新算法具有运行时间短、速度快的特点，与传统的插值放大图像不同，该算法是用变分的思想进行图像放大，理论分析和实验仿真表明，该算法能达到和样条插值同样的放大效果。