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

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

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

面向HDL描述基于路径覆盖的模拟矢量自动生成方法研究721-728

摘要：提出和实现了一种面向HDL描述基于路径覆盖的模拟矢量自动生成方法.该方法在约束生成时只考虑控制语句的条件表达式,可有效避免生成冗余约束;利用扩展的决策图模型解决了中间信号到初始输入的传播问题和信号依赖关系问题,以及处理各种HDL描述风格的问题;采用约束逻辑编程方法解决了由位、位向量和整型变量组成的约束系统的统一处理问题.实验结果表明该方法能加快模拟矢量生成速度,提高路径覆盖率.生成的模拟矢量也能用于低层次设计验证和故障模拟,加快了设计进度.将该方法的原型系统用于一个32位微处理器核RTL级验证,发现了RTL级设计描述中的错误.

基于三元数的三维广义M集表示及其绘制算法729-735

摘要：研究了基于三元数的三维广义Mandelbrot集表示方法.从理论上分析和证明了指数为正整数的三元数映射t←tm+ct,c∈T,m∈N,m≥2的三维广义M集所具有的性质.提出了基于周期检测的光线投射体绘制算法,根据属于M集的各离散点的周期值来定义其颜色、不透明度和法向量,并用Newton-Raphson方法来加速光线与M集的求交运算.用文中提出的体绘制算法绘制了三元数法和四元代数法所构造的三维M集.实验结果表明,与四元代数相比,用三元数来构造三维M集具有直观、快速、可控等优点.三元数法可以进一步推广到其它三维M集和J集的构造,从而为三维分形图的生成提供了一个新的有效途径.

基于无指导学习策略的无词表条件下的汉语自动分词736-742

摘要：探讨了基于无指导学习策略和无词表条件下的汉语自动分词方法,以期对研制开放环境下健壮的分词系统有所裨益.全部分词知识源自从生语料库中自动获得的汉字Bigram.在字间互信息和t-测试差的基础上,提出了一种将两者线性叠加的新的统计量md,并引入了峰和谷的概念,进而设计了相应的分词算法.大规模开放测试结果显示,该算法关于字间位置的分词正确率为85.88%,较单独使用互信息或t-测试差分别提高了2.47%和5.66%.

基于力场分析的主动轮廓模型743-749

摘要：传统Snake模型存在的缺点是, 其初始轮廓必须靠近图像中感兴趣目标的真实边缘,否则会得到错误结果,且由于Snake模型的非凸性,结果不能进入感兴趣目标的深凹部分,很容易陷入局部极小点.由此该文提出一种基于力场分析的主动轮廓模型,详细分析了基于欧氏距离变换的距离势能力场分布,归纳出感兴趣目标上真轮廓点与假轮廓点的判别标准.建立了由曲线能量到最终结果的有效方法,避免了Snake陷入局部极小点. 实验结果表明,该模型具有较大的捕获区域,能够进入感兴趣目标的深凹部分,准确提取感兴趣目标的轮廓. 与GVFSnake模型相比, 该模型具有很小的计算量.

面向纹理特征的真实感三维人脸动画方法750-757

摘要：纹理变化是人脸表情的重要组成部分,传统的人脸动画方法通常只是对纹理图像做简单的拉伸变换,没有考虑人脸细微纹理特征的变化,比如皱纹、酒窝等.该文提出了一种面向纹理特征变化的真实感三维人脸动画方法.给出局部表情比率图(Partial Expression Ratio Image,PERI)的概念及其获取方法,在此基础上,进一步给出了面向MPEG-4的PERI参数化与面向三维人脸动画的多方向PERI方法,前者通过有机结合MPEG-4的人脸动画参数(Facial Animation Parameter,FAP),实现人脸动画中细微表情特征的参数化表示;后者通过多方向PERI纹理特征调整方法,使得三维人脸模型在不同角度都具有较好的细微表情特征.该文提出的方法克服了传统人脸动画只考虑人脸曲面形变控制而忽略纹理变化的缺陷,实现面向纹理变化的具有细微表情特征的真实感三维人脸动画.实验表明,该文提出的方法能有效捕捉纹理变化细节,提高人脸动画的真实感.

一种适合于多播和单播的集成调度算法758-764

摘要：具有输入队列结构的路由器或交换机内部交换可以工作在线路速率上,适应了高速网络交换的要求.但现有输入队列调度方案将单播和多播流量分开考虑,使用不同的交换结构和调度算法,不适合网络中多播流和单播流并存的实际情况.该文提出一种不区分多播、单播分组,遵循同一入队策略和同一调度规则的集成调度算法EOPF(Extented Oldest Port First).仿真实验表明EOPF算法在各种多播和单播负载组成比例下始终保持高吞吐率,并能在全单播流量下达到100%吞吐率,适合于多播、单播混合存在的网络流量.

网络集群计算系统中的并行任务调度765-771

摘要：基于多处理机并行任务调度模型,探讨网络集群计算系统中的并行任务调度问题.首先证明了一般网络集群计算系统中调度算法的可近似性难度,然后提出了三种不同的启发式算法:最大长度优先调度算法、最大宽度优先调度算法和最大面积优先调度算法;然后根据大量的模拟实验对这些算法以及文献中已提出的调度算法进行了比较分析,结果表明该文的启发式算法比文献中的算法在性能上效果更好.

支持QoS的层次组播路由算法框架QHMR772-781

摘要：Internet规模的迅速扩大使QoS组播路由的复杂性增加.为此,该文提出了支持QoS的层次组播路由算法框架QHMR (QoS-based Hierarchical Multicast Routing).在HMR ( Hierarchical Multicast Routing) 层次划分的基础上,QHMR对网络的拓扑结构、带宽和组播树分布信息三者的聚集方法进行了定义,并设计了适用于层次网络的支持QoS的组播路由算法.实验结果表明,QHMR能显著减少路由器维护的信息以及路由器之间交换的协议分组,具有良好的可扩展性;同时,较之平面QoS组播路由,QHMR能够得到较理想的路由成功率和组播树代价.

序列模式图及其构造算法782-788

摘要：序列模式挖掘是数据挖掘的一个重要分支,在序列事务及有关信息处理中有着广泛的应用.目前已有许多序列模式模型及相应的挖掘算法.该文在对序列模式挖掘问题及挖掘算法进行分析的基础上,定义了一种称为序列模式图的序列模式框架,用于表示序列模式挖掘过程发现的所有序列模式.序列模式图是由离散状态的序列集到统一的图结构的桥梁,可以将序列模式挖掘结果统一到序列模式图中来.基于序列模式图进行研究可发现某些结构化的新知识,称之为后序列模式挖掘.文中还给出了序列模式图的有关性质及构造算法.

计算机学报杂志学术活动

“第八届中国人工智能联合学术会议暨农业专家系统学术研讨会”征文通知788-788

摘要：中国计算机学会人工智能与模式识别专业委员会、中国人工智能学会、中国自动化学会模式识别与机器智能专业委员会、中国高校人工智能学术研究会、中国软件行业协会人工智能分会、国家“八六三”计划计算机软硬件技术主题专家组、中国中文信息学会人工智能与教育专业委员会、国防科工委计算机专业组、国家农业信息化工程技术研究中心联合主办,由国防科学技术大学承办、中国科学院计算技术研究所协办的“第八届中国人工智能联合学术会议暨农业专家系统学术研讨会”,定于2 0 0 4年11月12～15日在湖南长沙召开,会议将正式出版论文集.现将征文通知如下:征文内容一、人工智能联合学术会议1.人工智能的逻辑基础、模糊理论、Age

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

基于核化原理的非线性典型相关判别分析789-795

摘要：典型相关判别分析是将传统的典型相关分析应用于判别问题,它是一类重要的特征提取算法,但其本质上只能提取数据的线性特征.应用统计学习理论中的核化原理可以将这样的线性特征提取算法推广至非线性特征提取算法.该文研究了如何将这一原理应用于典型相关判别分析,提出了基于核化原理的非线性典型相关判别分析,并且给出了求解该问题的一个自适应学习算法.数值实验表明,基于核化原理所导出的非线性典型相关判别分析比传统的典型相关判别分析更有效.另外,该文从理论上证明,所提出的新方法与Fisher核判别分析等价.

验证包含黑盒的电路设计的有效方法796-802

摘要：在超大规模集成电路设计中,为了进行早期的设计错误检测与调试或层次化验证,常常需要使用含黑盒的设计验证方法.该文提出了一种结合逻辑模拟和布尔可满足性的黑盒验证方法,用于验证设计中黑盒外部的功能正确性.该方法使用量化的合取范式(CNF)来表示电路中出现的未知约束,并且不需要修改电路结构,有效地节省了计算资源.此外,通过使用随机并行模拟增强了可满足性算法的错误检测能力.通过对ISCAS'85电路的实验表明了该方法不仅比以往同类算法速度快,而且具有较好的错误检测能力.

集群动态负载平衡系统的性能评价803-811

摘要：该文使用随机Petri网对集群动态负载平衡系统建立了一个抽象模型.通过细化模型中的节点本地处理部分对5种动态负载平衡算法的性能进行了分析,并讨论了集群负载特性对动态负载平衡系统性能的影响.最后得出的主要结论有:(1)动态负载平衡算法可以取得比静态负载平衡算法更好的性能;(2)与传统的只考虑CPU就绪队列的负载平衡算法相比,考虑了各种I/O请求队列的负载平衡算法可以取得更好的性能;(3)即使在极端的集群负载特性中,集群动态负载平衡算法仍然能取得比较理想的性能,因此实现即使是十分简单的集群动态负载平衡系统也是很有必要的.

模糊动态抢占调度算法812-818

摘要：针对不确定任务特征,提出应用模糊理论进行动态抢占调度.用语言模糊集来描述任务的不确定特征和不同的优先级等级,利用最大隶属度原理确定任务的优先级等级,采用优先调度高优先级等级任务的调度策略提高重要任务的调度成功率,实现具有不确定任务特征的抢占调度.与传统的EDF和LSF算法相比较,仿真表明,所提算法能够提高重要任务的调度成功率,并降低重要任务的截止期错失率;同时,任务间的平均切换次数大大小于LSF的平均切换次数,而与EDF保持相当.该方法可应用于计算机控制系统的控制任务调度,并借鉴于其它具有不确定任务特征或具有有限优先级等级的实时调度问题研究中.

异构盘阵中最优Stripe Unit Size选择技术819-827

摘要：缓解计算机IO子系统瓶颈的有效手段是采用磁盘阵列.配置时,SUS(Stripe Unit Size)的选择对盘阵性能的影响非常关键,而以往对异构盘阵的SUS的选择研究较少,该文推导出了确定异构盘阵最优SUS的方程,具体工作如下:首先,该文采用close队列网络模型来描述异构盘阵负载;然后,从该模型推导出系统数据输率解析表达式.根据该表达式和异构盘阵中设备的特性,可求出使传输率最大的SUS.最后,研究中进行了大量的模拟试验,模拟试验表明在并发的进程数大于10时,所推导的结论与模拟结果非常吻合.

计算机学报杂志短文

一种新的快速块运动估计的分级筛选法828-832

摘要：提出了一种新的分级筛选法用于快速的块匹配运动估计.该方法中最佳匹配块通过若干个筛选过程得到,每个筛选过程用不同大小级别的子块作为基元进行匹配.在初始的级别中用很少的运算代价通过简单的特征匹配先淘汰一部分候选匹配块;然后在上一级剩余的候选块中,逐级用更加细致的特征继续筛选;直至找到最佳匹配块.对不同运动复杂性的视频的实验表明,在搜索范围为(-7,7)×(-7,7)的情况下,分级筛选法不仅在速度上比一些常见的快速运动估计方法要快,而且估计精度与全搜索法非常相近.

基于克隆策略的重构动态组播路由算法833-837

摘要：为了充分利用日趋紧张的网络资源,该文提出了基于克隆策略的重构动态组播路由,其基本思想是根据组播成员加入或离开网络而造成对树局部范围的损伤程度来决定是否对该部分进行重构,重构是通过先删除重构区域内的所有链路和节点,然后用克隆算法对该区域重新选择路由.实验结果表明:(1)重构的动态组播树在性能上比不重构的动态组播树好;(2)重构的组播树代价随着重构阈值λ的增大而增大.

Ad Hoc网络按需路由协议的改进838-844

摘要：DSR和AODV路由协议是两种用于ad hoc网络的按需路由协议,随着网络负荷的增加,协议的性能下降很快.针对这一问题,该文对节点链路层的性能进行了分析,提出了一种均衡流量的改进方法.在该方法中,路由层根据节点链路层当前的负荷状态决定是拒绝或接受收到的路由请求,弥补了上层协议仅反映端到端网络状态的不足,直接反映了网络中节点的当前状况,避免了网络的局部拥塞,均衡了网络流量.仿真结果表明,无论对DSR协议还是AODV协议,采用该算法均明显地提高了网络效率.并且由于该算法简单易行,因此具有实用性.