2001, 12(5):633-644.
摘要:Post-WIMP界面作为继当前的主流界面范式——WIMP界面后的下一代界面范式,它和WIMP界面有着很大的不同,通过使用虚拟现实、语音交互、手势交互等技术,它能够提供更加自然高效的交互方式.然而,它却难以构造.为了有效地构造Post-WIMP界面,在构造之前不考虑实现细节,而在一个抽象的层次上描述它是一个较好的方法.首先,分析了Post-WIMP界面的交互本质,交互混合性是Post-WIMP界面一个最为重要的特点.从形式化系统的角度分析Post-WIMP界面,通过将Post-WIMP界面抽象为混合系统能够更为准确和严格地分析Post-WIMP界面的特性.混合自动机是用于描述混合系统的形式化工具,将Post-WIMP界面建模为一组相互协作的混合自动机.设计了一基于混合自动机理论的半形式化语言LEAFF作为Post-WIMP界面的描述工具.LEAFF通过结合文本描述和图形描述描述Post-WIMP界面中的交互行为,能够准确地反映交互中的控制关系、时序关系.给出了对两个典型Post-WIMP界面——虚拟现实交互和笔式交互的描述实例,同时讨论了Post-WIMP界面中交互并行性的描述、交互实时性的验证和从描述到实际交互系统构造的转换.
2001, 12(5):645-649.
摘要:基于小波图像编码的金字塔式小波分解后各子带系数的统计特性,提出一种改进的λ迭代比特分配算法,该算法使用λ序列的概念简化了传统λ迭代法的最优值求解过程.实验证明该改进算法在限定压缩比的小波图像编码中能够大大加快比特分配算法的收敛速度.
2001, 12(5):650-655.
摘要:研究了有理曲面的hybrid多项式逼近和Hermite多项式逼近的关系.在权系数的某些假定下,得到hybrid多项式逼近和Hermite多项式逼近均收敛的充分必要条件.
2001, 12(5):656-658.
摘要:1975年,Lander证明在P≠NP假设下存在一个语言属于NP-NPC-P(NPI).但Lander给出语言并不是一个自然的语言因在该语言的构造中需运行所有多项式时间的图灵机.迄今为止,还没有自然的语言被证明在P≠NP假设下属于NPI,并且在P≠NP假设下寻找一个属于NPI的自然语言是一个重要的未解决问题.作者部分解决了此长期未解决的问题.定义了2+f(m)-HAST模型.基于该模型,给出了在P≠NP假设下NP-NPC-P中自然问题的一个候选者.已证明在P≠NP假设下它不属于NPC并且在更强但合理的假设下它的确属于NPI.
王士同 , J.F. Baldwin , T.P. Martin
2001, 12(5):659-667.
摘要:基于传统的CMAC神经网络和局部加权回归技术,提出了与传统CMAC(cerebellar model articulation computer)有着同样存储空间量的改进的新CMAC网络New-CMAC,它具有传统的输出和具有其微分信息的输出,因而更适合于自动控制.接着,又提出了其新的学习算法,并研究了其学习收敛性.
2001, 12(5):668-676.
摘要:提出了一种鲁棒性好的数字图像水印算法.算法采用Hilbert扫描顺序,用考虑HVS(human visual system)特性的噪声阈值矩阵作为叠加水印信号的掩模插入水印,并具有水印强度自适应调节特性.水印检测算法还可加入自动校正模块,大大提高了判决的准确性.在描述算法的基础上,给出了实验结果及攻击分析.实验结果表明,该算法具有较强的透明性和鲁棒性,水印检测结果准确,并且算法的计处量小.
2001, 12(5):677-688.
摘要:在计算机软件领域,超大规模集成电路技术的迅猛发展迫切需要高性能CAD工具——电子设计自动化(EDA)软件工具的支持.与物理设计相关的CAD技术称为布图设计,总体布线是布图设计中一个极为重要的环节.目前,在深亚微米、超深亚微米工艺下的超大规模、甚大规模集成电路设计中,性能驱动总体布线算法已成为布图设计中的一个国际研究热点.针对这一热点,分析了性能驱动总体布线算法研究中亟待解决的关键技术,并详细阐述了国内外的重要相关研究工作进展情况.
2001, 12(5):689-697.
摘要:网络通信中的软件开销是目前影响机群系统性能的瓶颈,为了提高机群系统的通信性能,提出了一种用于机群系统的用户层快速消息传递机制ULFM(user-levelfastmessage),并在TH-GBNet上加以实现.ULFM以通信缓冲区的管理为核心设计了一种易于实现的用户层网络访问接口,通过综合采用用户层网络接口访问、零拷贝数据传递、精简通信协议等技术,可以有效地降低机群系统的通信开销,为应用程序提供实际的低延迟、高带宽的通信性能.在TH-GBNet的实现中,ULFM节点间16字节数据包的单向延迟减小到仅为6μs,2K字节数据包的带宽达40MB/s.
2001, 12(5):698-705.
摘要:交互式并行化系统通过提供友好的交互功能并引入用户知识来协助程序的并行化,是解决自动并行化能力不足的一条有效途径.描述了一个并行化系统交互环境TIPSIE(interactive en vironment of Tsinghua interactive parallelizing system),并就构造该环境的性能预测、增量编译和数据相关查询等关键技术进行了讨论.实验结果表明,这些技术能够有效地提高系统的并行化能力和效率.
2001, 12(5):706-710.
摘要:缩短程序的执行时间是并行处理的首要目标,有效的任务分配算法是实现这一目标的关键,对机群系统来说更是如此.研究机群系统上针对结构化并行控制机制的任务调度问题,并基于贪心算法、粒度控制、反馈式分派的原则,提出近优的任务调度算法SSA(sub-optimal scheduling algorithm).实验结果表明,在机群环境下,该算法的并行计算性能与其他算法相比均有所提高.
2001, 12(5):711-720.
摘要:使用支持向量机理论计算海量数据的支持向量是相当困难的.为了解决这个问题,提出了基于邻域原理计算支持向量的方法.在对支持向量机原理与邻域原理比较分析的基础上讨论了以下问题:(1)构建了从样本空间经过特征空间到扩维空间的复合内积函数,给出计算支持向量的邻域思想;(2)将支持向量机的理论建立在距离空间上,设计出了计算支持向量的邻域算法,从而把该算法理解为简化计算二次规划的方法;(3)实验结果说明,邻域原理可以有效地解决对海量数据计算支持向量的问题.
2001, 12(5):721-728.
摘要:组播通信路由技术是视频广播、计算机会议、CSCW()等新型分布式计算的关键技术.提出了基于分布式遗传算法的共享树组播路由算法,包括包交换的网络组播树的建立、组播树的动态维护和计算满足特定时延和时延抖动限制的近似斯坦利最小树算法等.利用它可以实现在给定网络和组播需求的情况下,在组成员间寻找动态的组播树,并使该树覆盖所有的成员,并约束网络费用达到最小.进而解决树状路由的建立以及树状路由的动态维护等问题.
2001, 12(5):729-734.
摘要:联盟形成是多Agent系统中的一个关键问题.人们寻求能极大化联盟值的总和的联盟结构,但通常情况下可能的联盟结构的数目太大,以致不允许进行穷尽搜索而找出最优解.给出了一个算法,可在最小搜索量内保证找到一个与最优解相距在一个限界内的联盟结构.然后,这个任一时间算法进一步搜索,渐进地给出越来越低的限界,并急剧地降低这个限界,在这一阶段,此算法明显地优于由Sandholm等人给出的算法.
2001, 12(5):735-741.
摘要:现有的OODBMS(object-oriented database management systems)的数据模型基本上可以分为两类:传统的强类型和非传统的弱类型.前者的特征是所有具有同样结构(模式)和行为(方法)的对象组成一个类,对象的含义由对象所属类的模式解释,故类的定义必须先于其对象的定义;后者的特征是“无模式”,即对象是“自我描述”的,因此无须为对象预先定义模式.指出了这两类模型的主要优缺点,并证实:为了充分适应有效而灵活的动态对象操作,有必要在传统的强类型模型和非传统的弱类型模型之间寻求某种折衷.为此,提出了一个基于概念聚类机制(conceptual clustering mechanism,简称CCM)的数据模型.这种新的动态模型已成功地应用于一个面向对象的VDBMS(video database management system).
2001, 12(5):742-750.
摘要:回顾了遗传算法的理论研究状况,介绍了NoFreeLunch定理,描述了遗传算法的通用框架,构造了遗传算法的性能分析矩阵,并通过模拟实验分析了一系列遗传算法的性能.实验表明,这种评价算法性能的方法切实可行,可操作性好,具有一定的通用性.
2001, 12(5):751-757.
摘要:TCP/IP协议本身只提供“Best-Effort”级别的服务,而对QoS支持很少.基于此,提出一种基于TCP/IP协议的自适应QoS协商机制,其基本思想是基于资源预留协议RSVP(resource reservation protocol).在提出QoS请求时进行QoS映射,然后启动适应性函数和资源管理函数进行协商,直到获得一组在当前资源状况下最佳的QoS指标为止.然后介绍了应用GQoS实现自适应QoS协商的基本步骤以及重要数据结构和函数.实验结果表明,应用该方法可以根据网络资源的变化,自适应地调整QoS参数.
2001, 12(5):758-767.
摘要:随着仿真应用在广度及深度上的发展,基于因特网的分布交互仿真成为未来的发展方向.其面临的主要挑战之一是系统可扩缩性问题.采用高效的数据过滤机制是解决问题的有效手段.首先讨论了分布交互仿真存在的可扩缩性问题,介绍了HLA(high level yarchitecture)框架下数据过滤机制的原理、实现及存在的问题.针对大规模系统过滤匹配计算量大的问题,提出了一种基于路径空间层次划分方法.该方法利用空间位置关系知识进行启发式搜索,从而排除大量不相关区域的匹配计算,有效地降低了过滤机制的计算复杂度.
2001, 12(5):768-775.
摘要:PnP问题是计算机视觉、摄影测量学乃至数学领域的一个经典问题.系统地研究了P5P问题,用代数方法证明了下述结论:当5个控制点中任意3点不共线时,P5P问题最多有两个解,并且解的上限可以达到.同时给出了有惟一解和有两个解的代数条件以及求解P5P问题的具体算法.在物体定位、机器人导航等领域具有比较重要的应用价值.
2001, 12(5):776-782.
摘要:工作流的失败处理和失败恢复是工作流管理系统的重要组成部分.提出了一种新的基于对象的工作流模型,在此模型下设计了工作流失败处理和失败恢复的策略.与传统方法相比,新策略考虑了工作步骤之间的控制依赖和数据依赖,并且对工作步骤应用的具体实现方式进行了探讨,以提高工作流失败处理和失败恢复的效率.
2001, 12(5):783-789.
摘要:对灰度图进行一般线性和非线性平滑会极大程度地模糊拐角,使得多尺度方法难以用于拐角检测.由于非线性多尺度CB(contour-based)形态滤波算子具有很好的拐角保持特性,而且能使拐角满足单调性,即当尺度增大时拐角数不增加.用CB形态滤波器对灰度图进行滤波,构成CB形态学尺度空间,以实现对拐角的多尺度检测.理论分析和实验结果证明了这种分析方法的有效性.