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

计算机学报 2004年第10期杂志 文档列表

计算机学报杂志综述

基于内容的三维模型检索综述1297-1310

摘要：对当前基于内容的三维模型检索技术的国际研究现状及进展进行了广泛而深入的综述.探讨和分析了基于内容的三维模型检索技术的系统框架及其关键方法,重点介绍其中的模型坐标标准化、特征提取与索引、相似性匹配、查询方式与用户界面等方面的基本内容,并进行了适当分类.分析总结了现有的基于内容的三维模型检索系统及搜索引擎的典型实例.最后,对现有研究中存在的难点问题及其未来的发展方向进行了展望.

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

多物理并行数值模拟中的两层紧耦合联接算法1311-1319

摘要：复杂物理现象通常由多类复杂的物理过程紧耦合构成,其数值模拟也通常由适用不同物理过程的多类并行应用程序紧耦合完成.如何设计这些物理过程之间的联接算法,既要保证程序之间数据传递的高效,又要保证程序各自运行和总体模拟的高效,还要保证程序各自开发的独立,是一个值得研究的课题.该文基于广泛应用于高温高压多物理研究中的辐射流体力学和中子输运多物理并行数值模拟,在非结构网格上,提出了两种联接算法:完全松散联接算法和两层紧耦合联接算法,前者侧重于实现程序各自运行的高效和开发的独立,后者在前者的基础上,还权衡了数据传递和总体模拟的高效.在两台并行机的数百个处理机上,通信复杂度分析和数值实验结果表明两个算法均是有效的,可推广适用于辐射或中子输运与其他流体力学的多物理并行数值模拟应用中.特别地,两层紧耦合联接算法是高效可扩展的,取得了近似最优的并行性能.

高性能微处理器微体系结构级功耗模型及分析1320-1327

摘要：基于Itanium 2微处理器体系结构提出单时钟和多时钟域两种基准模型;对处理器的电路级特性进行微体系结构级抽象,建立了参数化的峰值功耗估算模型;提出事件调度算法,实现了多时钟域处理器系统的行为级模,拟;以IMPACT工具集作为模拟引擎实现了处理器的动态功耗模拟模型.与其它同类模型Wattch相比,该模型能够支持多时钟系统的模拟,峰值功耗估算精度高了约3%,而模拟速度提高了42%.通过实验说明了多时钟域的功耗特性,在一种多电压和频率环境下,多时钟域处理器的功耗和能量分别降低了21%和38%.该模型可以很好地应用到体系结构级低功耗研究设计.

挖掘最大频繁模式的新方法1328-1334

摘要：由于其内在的计算复杂性,挖掘密集型数据集的频繁模式完全集非常困难,解决方案之一是挖掘最大频繁模式集.该文在频繁模式完全集挖掘算法OpportuneProject基础上,提出了挖掘最大频繁模式的新算法MOP.它采用宽度与深度优先相结合的混合搜索策略,能恰当地选择不同的支持集表示和投影方法,将闭合性剪裁和一般性剪裁相结合,并适时前窥,实现搜索与剪裁效率最优化.实验表明,MOP效率是MaxMiner的2～8倍,比MAFIA高2个数量级以上.

不变矩稳定性及基于多级特征模型的目标识别研究1335-1340

摘要：从成像过程和实际应用角度研究影响目标不变矩稳定性的各种因素,包括有限观测区域、高斯模糊和离散化处理以及在这些因素影响下不变矩的变化规律和误差.理论分析和实验还证明各不变矩自身的稳定特性不仅与阶数而且与其次数有关.这些研究和分析表明建立多尺度目标特征模型的必要性,可为不变矩在实际成像识别系统中正确有效地应用提供重要的理论和实验依据.

组合优化多智能体进化算法1341-1353

摘要：提出了一种新的组合优化方法--组合优化多智能体进化算法.该方法将智能体固定在网格上,而每个智能体为了增加自身能量将与其邻域展开竞争,同样智能体也可进行自学习来增加能量.理论分析证明算法具有全局收敛性.在实验中,作者分别用强联接、弱联接、重叠联接等各种类型的欺骗函数对算法的性能进行了全面的测试,并将算法用于解决具有树状等级结构的问题.比较结果表明文中算法所需的计算量远远小于其它方法,具有较快的收敛速度.为了测试算法解决大规模问题的能力,作者还将算法用于解决上千维的欺骗问题和等级问题,结果表明该文算法的计算复杂度与问题规模成多项式的关系.此外,将算法用于上千维的欺骗问题和等级问题,在国内外还均未见报到.

有向基因组移位排序问题的O（n^2）快速算法1354-1360

摘要：有向基因组移位排序问题在计算生物学研究中占有重要位置.以前最好的算法时间复杂度为O(n2logn).该文给出一个有向基因组移位排序的新多项式算法,将移位排序的时间复杂度改进为O(n2).算法改进的关键在于找到一种寻找有效合理移位的新方法,通过在最小子排列中删除无关顶点确定一个合理移位是否有效,从而将寻找一个有效移位的时间复杂度改进为O(n),总时间复杂度由此降为O(n2).

基于逻辑程序的安全协议验证1361-1368

摘要：安全协议本质上是分布式并发程序,可以自然地描述为多个子进程的并发合成系统.将安全协议对应的并发合成系统抽象为逻辑程序进行消解,能够对安全协议无穷多个会话的交叠运行进行验证.该文提出了安全协议逻辑程序中逻辑规则的一个分类方法,基于该分类方法提出了安全协议逻辑程序不动点的迭代计算方法.逻辑规则的分类优化了安全协议逻辑程序不动点的迭代计算和安全性质验证过程中的计算.由于安全协议逻辑程序不动点迭代计算过程不一定终止,文中提出了每进行k≥1步安全协议逻辑程序不动点迭代计算验证一次安全性质的验证策略.

数字产品中新的无诬陷的2-安全码1369-1378

摘要：该文研究的是两类防盗版码--TA码和安全码.作者利用等距等重码构造了新的2-TA码和2-安全码,并通过分别级联前面得到的两个2-安全码与一个Reed-Solomon码得到了两个2-安全码.当码字的个数相同时,这两个码的码长比Boneh等人的方法中的级联码的码长要短.这两个码应用Koetter-Vardy软判断列表算法作为追踪算法,与Boneh等人的追踪算法相比,这个新的追踪算法不会诬陷别的用户;与Barg等人的算法相比,这个追踪算法在许多情况下一定可以找到两个叛徒,并且算法失败的概率非常小.

视点合成中重叠需求的不一致优先级处理1379-1387

摘要：对多视点方法来说,各视点不同的利益观可能导致视点之间的重叠需求相对于不同视点优先级设定方面的不一致性.该文主要讨论了视点合成中重叠需求不一致优先级的处理策略和方法.首先作者对需求优先级以及重叠需求相对于不同视点优先级的不一致性等概念给出了严格的定义.其次,对于IEEE推荐标准,作者分别采用格和乘积格来表示重叠需求相对于各视点和合成视点的优先级,借助于乘积格的准布尔特性实现对不一致优先级的容忍策略;最后对基于精确度量设定优先级的情形,采用平均策略确定重叠需求相对于合成视点的综合度量,重新设定重叠需求相对于合成视点的优先级,从而解决这种不一致性.

基于增量可满足性的等价性检验方法1388-1394

摘要：组合验证是数字集成电路形式化设计验证的重要方面.该文提出了一种基于增量布尔可满足性的组合等价性检验方法,通过合理选择候选等价结点和增量可满足性算法来提高算法性能,并通过对内部等价结点的置换及将等价关系转化为相应的合取范式公式,避免了误判的发生,又能缩小验证程序的搜索空间.针对ISCAS'85电路的实验结果表明,该文提出的方法比以往同类方法更快、更强健.

基于语义关系查询扩展的文档重构方法1395-1401

摘要：已知文档与用户查询之间相同概念不同表达形式造成的词不匹配问题是影响信息检索效果的重要原因之一.该文提出了根据词之间的语义关系进行扩展和替换的文档重构方法.它与传统的查询扩展不同,实现了同一概念信息的聚集,是更接近于人类进行信息查找的思维方法.进一步地,研究给出一种有效的实时文档重构检索策略,解决了文档重构方法在实际应用中的可行性.在标准测试数据集上的实验表明,基于查询扩展的文档重构方法不仅比不扩展的最佳性能始终有14%～23.4%的提高,而且比相对应的传统查询扩展方法也有约16%的提高.

Ad Hoc网络QoS多播路由协议1402-1407

摘要：随着高性能网络、移动网络及Internet的不断发展,具有QoS约束的多播路由技术已成为网络及分布式系统领域的一个重要研究课题.该文研讨了Ad Hoc网络中具有QoS约束的多播路由问题,其中主要包含延迟、带宽、代价等QoS约束.文中描述了一种适应于研究Ad Hoc网络QoS多播路由的网络模型,提出了Ad Hoc网络中一种具有QoS约束的多播路由协议(QMRP).文中给出了该协议的正确性证明和复杂性分析.仿真实验结果表明,该协议较其它协议更适合于网络状态变化比较频繁的环境以及实时多媒体应用,优化了多播树的代价.QMRP为Ad Hoc网络QoS约束多播路由提供了一种新的有效途径.

计算机支持的协同编著系统中的同步问题1408-1414

摘要：随着Internet的高速发展,计算机支持的协同工作的研究近来备受关注.同步机制是计算机支持的协同工作中的一个核心问题,但目前这方面还缺少有效的描述手段.同步问题在文中称为自动更新问题.该文提出了带子元素群组自动机和带子元素组件自动机的概念,并利用这两个概念给出了同步问题的形式化描述,明确提出并解决了计算机支持的协同编著系统中的自动更新问题原型.

多目标演化算法的收敛性研究1415-1421

摘要：基于群体搜索的演化算法求解多目标优化问题有独特的优势,多目标演化算法已有的研究大多为算法的设计和数值试验效果的比较,理论研究往往被忽视.该文讨论了多目标演化算法的收敛性问题,针对一种网格化的简单易于实现的多目标演化算法模型定义了多目标演化算法强收敛和弱收敛等概念,给出了判断算法收敛性的一般性条件;在变异算子为高斯变异、目标函数连续的条件下,证明了提出的算法强收敛.数值实验验证了算法的可行性和有效性.

计算机学报杂志短文

组织进化算法求解SAT问题1422-1428

摘要：基于组织的概念设计了一种新的进化算法--求解SAT问题的组织进化算法(Organizational Evolutionary Algorithm for SAT problem,OEASAT).OEASAT将SAT问题分解成若干子问题,然后用每个子问题形成一个组织,并根据SAT问题的特点设计了三种组织进化算子--自学习算子、吞并算子和分裂算子以引导组织的进化.根据组织的适应度,将所有组织分成两个种群--最优种群和非最优种群,然后用进化的方式来控制各算子,以协调各组织间的相互作用.OEASAT通过先解决子问题,再协调相冲突变量的方式来求解SAT问题.由于子问题的规模较小,相对于原问题来说较容易解决,这样就达到了降低问题复杂度的目的.实验用标准SATLIB库中变量个数从20～250的3700个不同规模的标准SAT问题对OEASAT的性能作了全面的测试,并与著名的WalkSAT和RFEA2的结果作了比较.结果表明,OEASAT具有更高的成功率和更高的运算效率.对于具有250个变量、1065个子句的SAT问题,OEASAT仅用了1.524s,表现出了优越的性能.

来自双线性配对的新的多签名、多签名和多多签名体制1429-1435

摘要：作者提出三类新的来自双线性配对的涉及多个签名人的签名体制.第一类称为多签名体制,它允许一组原始签名人授权给一个签名人来代表他们;第二类称为多签名体制,意思是一个原始签名人可以授权给一组签名人来代表他(她);第三类称为多多签名体制,因为在此体制中,多个原始签名人把他们的签名权利委托给一组签名人.作为准备,作者提出了基于Hess的基于身份签名体制的多签名体制,这是第一个来自双线性配对的基于身份的多签名体制,后两类签名体制将用到它.关于作者提出的新体制,最重要的一点是在这三类体制中,签名的长度均独立于原始签名人或签名人的个数.它们的验证也与一般的签名类似.

利用分子格对粗糙集理论进行推广1436-1440

摘要：粗糙集模型的推广是粗糙集理论研究的重要内容,该文将分子格引入到粗糙集理论中作为基本代数系统,在分子格中定义了一个从分子到一般元素的映射,并通过该映射定义了更为一般和抽象的下近似算子和上近似算子▲.文中还研究了映射为一般映射、外展映射、对称映射和内缩映射时所定义近似算子的性质.当映射为一般映射时得到的性质表明文中分子格基础上构造的代数系统(L,∧,∨,(),▲ ,0,1)是粗糙集代数(2U,∩,∪,～,L,H)的抽象和推广;而当映射为外展映射、对称映射和内缩映射时,得到了分别与模态逻辑中公理D、公理B和公理4及它们的对偶相对应的性质.