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

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

混合实时事务的延期单调速率调度算法及其可调度性分析289-294

摘要：对于含有实时和非实时两部分的混合实时应用,传统的单调速率调度算法(RM)已不再适用.为此,该文引入'混合实时事务'的概念,并针对这类事务提出一种延期单调速率调度算法(DRM);着重分析了DRM算法对混合实时事务的可调度性;进行了实验测试与性能分析比较.结果表明,事务集中混合实时事务占的比例越高,混合事务中非实时子事务占的比例越大,该算法的CPU使用率阈值就越高,且在各种情况下,DRM算法与RM算法相比性能都更优,最低情况也与之一样.

适用于嵌入式实时数据库系统的接纳控制机制IACM295-301

摘要：接纳控制机制IACM综合考虑事务的执行需求和价值,通过减少被系统接纳执行而过后又夭折的事务数量来减少资源浪费.与传统的依赖于事务优先级的抢占策略不同,在IACM中,只有高优先级事务的价值不小于被抢占事务的价值总和该事务才被接纳,其总体目标是使系统获得的价值最大;另外,IACM建立在基于替代的实时事务模型上,适用于嵌入式实时数据库系统.最后的模拟实验比较了各典型接纳控制策略的性能.

第五届汉语词汇语义学研讨会301-301

基于禁忌搜索算法求解全光网路由和波长分配问题302-309

摘要：该文是基于禁忌搜索算法对一类全光网路由和波长分配MAX-RWA问题进行求解.该文针对配置范围受限波长转换器的全光网,强化了MAX-RWA问题的优化目标.新的优化目标是保证连接数最多的情况下使用最少的波长转换器,从而尽可能地减少波长转换器引入的信号失真;简化了文献[7]中分层图的构造方法,并利用改进的分层图给出了MAX-RWA问题的整数线性规划和禁忌搜索算法的设计.仿真结果和理论上界的对比表明该文算法是稳定、有效的.

基于Ontology的Web内容二阶段半自动提取方法310-318

摘要：目前Web中的海量信息已经成为人们重要的信息来源,如何从大量半结构化或无结构的HTML网页中提取信息已成为目前的研究热点.但是Web页面的初始设计目的是为了方便用户浏览,而不是便于应用程序自动处理,如何实现一个精确的、应用广泛的提取系统面临很多困难.传统的方法可以粗略划分为基于交互产生的包装程序和自动生成的包装程序,但是基于交互产生的包装程序不具备普遍的应用性,基于自动生成的包装程序准确性不高.该文提出了一种新的二阶段基于语义的半自动提取方法,在保证提取准确性的前提下,尽可能减少交互操作,同时随着参与网站的增加,逐步提高包装程序生成的自动化.相对于目前的方法,该文方法同时考虑了包装程序提取结果的准确性和提取过程的应用普遍性.其有效性在原型系统中得到验证.应用该方法,已经成功提取了120万HTML页面.

IEEE／WIC／ACM2004网上智能与智能Agent技术联合国际会议（WI／IAT 2004）征文通知318-318

Mesh网络路由算法容错性的概率分析319-327

摘要：该文基于k-Mesh子网的概念提出了两个简单的基于局部信息和分布式的Mesh网络容错路由算法,并对其容错性进行概率分析;在每个结点具有独立的出错概率的假设条件下,推导出路由算法成功返回由正确结点组成的路径的概率.该文运用严格的数学推理,证明了Mesh网络结点出错概率只要控制在1.87%以内,则对于多达几十万个结点的Mesh网络,提出的路由算法具有99%的概率确保找到正确结点组成的路径.路由算法的时间复杂性是线性的.模拟结果表明路由算法所构造的路由路径长度非常接近于两结点之间的最优路径长度.

不同粒度世界的描述法——商空间法328-333

摘要：面对复杂对象,如何描述对象往往成为解决问题的基础,为此,该文提出了一种不同粒度世界的描述方法--商空间法.在商空间法中用一个三元组(X,f,T)描述一个问题,在其论域上引入等价关系R,对应于R的商集[X],然后将[X]当作新的论域,对它进行分析、研究,从而将问题表述成不同的粒度世界,进而达到简化问题、解决问题的目的.与粗糙集、决策树等方法相比较,商空间法具有更强的表达能力,它不仅可以定义多种不同的属性函数,而且可以描述论域中的元素、元素之间的相互关系(即结构)、运算等.该文介绍粒度世界的描写、划分法、粒度确定以及不同粒度世界的关系.最后给出了粒度世界的描述实例--互联网中的路由算法及称球游戏,以验证商空间方法的有效性.

一种抗差分功耗攻击的改进DES算法及其硬件实现334-338

摘要：该文在研究差分功耗分析(differential power analysis, DPA)模型的基础上,同时考虑DES算法的特点以及存储空间的局限性,提出了把MASK技术应用于DES算法线性部分的抗DPA攻击的改进DES算法,即DES-DPA算法,并以此为基础设计了防止DPA攻击的DES-DPA模块.此外从差分功耗攻击的原理上简要说明DES-DPA算法能够有效地防止功耗分析.结果表明在基于0.25μm标准单元库工艺下,DES-DPA 模块的综合规模为1914门,最大延时为9.57ns,可以工作于100MHz左右的频率下,各项性能指标均能满足智能卡和信息安全系统的要求.

UML实时活动图的形式化分析339-346

摘要：统一建模语言(UML)自从成为OMG规范后,应用越来越广泛.但UML没有精确的、形式化的语义阻碍了它的进一步发展.该文基于Petri网,给出带时间约束的UML活动图的形式化描述.与Petri网不同的是,Petri网的时间约束是在跃迁(transition)上,而作者将UML活动图的时间约束放在活动状态上.在此基础上,用整型时间的验证技术对实时活动图的时间性质加以分析,为实时系统的建模打下了基础.

第七届亚洲数字图书馆国际会议论文征文通知346-346

一类基于Bit承诺的安全电子拍卖模型347-351

摘要：在拍卖过程中如何保护投标者隐私和防止中标者反悔是设计安全电子拍卖系统的关键技术.该文首先综述了安全电子拍卖的研究现状和一些典型的方案设计,然后利用Bit承诺协议给出了一类实现安全密封电子拍卖的通用模型并构造了相应的实例.所给模型具有如下特点:(1)安全性好,能够满足投标者匿名、投标价保密、不可否认性和强可验证性等密封电子拍卖的所有安全性要求;(2)技术简单,仅使用了一个基本的Bit承诺协议,这不仅给编程实现带来很大方便,而且用户也易于理解和接受;(3)对可信赖第三方的依赖小;(4)模型还具有通用性,通过适当选取不同的单向函数,可得到不同的方案实例.

MPEG-2传送流传输方法的研究与改进352-356

摘要：高品质视频流媒体的传输在流媒体业务中占有很重要的地位,同时带来许多难题.以传统的恒定速率传输变比特率压缩的视频时,播放终端往往需要很大的缓存.PCR协助的恒定速率传输是一种新的恒定速率传输机制.这个方法的详细研究表明PCBR方法利用嵌入MPEG-2传送流的程序参考时钟来定期校正传送速率,是以较高传输速率为代价减少了缓存需求.因此对该方法进行了改进,通过缩小传输时间尺度来降低传送速率但没有增加额外的缓存需求,在NS通信系统仿真软件和实验平台的测试结果都表明,改进的方法能够更好服务于流媒体传输与终端回放.

VBR流式视频的最短路径率平滑传输算法357-364

摘要：预存储的变比特率(VBR)压缩的视频网上流式传输,提供实时视频服务.这种VBR视频呈现的突发性比特率变化特性使带宽预留和接纳控制等网络传输技术复杂化.一个行之有效的解决办法是在传输前对这种VBR视频在满足一定限制条件下进行比特率无损平滑.基于平面规划中的最短路径原理,针对存储的VBR压缩视频,文章提出了最短路径率平滑传输算法,并建立了一些相关概念.算法的结果被证明能同时满足多项优化指标:极小的峰值比特率、极大的谷值比特率及O(K)的时间复杂性,实验结果也显示算法是有效、可行的.

基于小波变换的自同步音频水印算法365-370

摘要：该文提出了一种基于DWT的自同步音频水印算法.该算法具有如下特点:(1)在隐藏水印信息的同时,嵌入一个同步信号,使水印具有自同步能力;(2)同步信号与水印隐藏于DWT域低频子带,在改善同步信号鲁棒性的同时,利用DWT的时频局部特性,有效地提高在变换域内搜索同步信号的效率,较好地解决了同步信号鲁棒性与其搜索计算量之间的矛盾.实验表明,所提出的方法在抵抗各种通用的音频处理和攻击(如高斯噪声、MP3压缩、重采样、重量化、裁剪等)方面具有良好的性能.

可恢复的脆弱数字图像水印371-376

摘要：该文提出一种用于图像内容认证和保护的脆弱数字图像水印算法.该算法不但可以检测定位出图像中任何细微的篡改,而且可以恢复较大面积的被篡改的图像数据.首先该文给出了一种被称之为基于块交叉交插RS编码的水印生成算法;随后使用基于块交叉交插RS码的校验符号作为水印并将其埋植到图像数据的最低位;最后利用基于块交叉交插RS解码实现水印信号检测以及对图像篡改数据的定位和恢复.此外该文算法使用由密码生成的掩膜图像参与水印信号的生成和检测,很好地保证了水印的安全性和保密性.经实验验证,该算法不但可以有效地检测出图像中被篡改内容的位置,而且能恢复被篡改的图像数据.

基于LMI方法的时滞细胞神经网络稳定性分析377-381

摘要：神经网络是一个复杂的大规模非线性系统,而时滞神经网络的动态行为更为丰富和复杂.现有的研究时滞神经网络稳定性的方法中最为流行的是Lyapunov方法.它把稳定性问题变为某些适当地定义在系统轨迹上的泛函,通过这些泛函相应的稳定性条件就可以获得.该文得到了时滞细胞神经网络渐近稳定性的一些充分条件.作者利用了泛函微分方程的Lyapunov-Krasovskii稳定性理论和线性矩阵不等式(LMI)方法,精炼和推广了一些已有的结果.它们比目前文献报道的结果更少保守.该文还给出了确定时滞细胞神经网络稳定性更多的判定准则.

基于接口参数的黑箱测试用例自动生成算法382-388

摘要：测试用例的选择与生成技术是软件测试尤其是黑箱测试的一个重要研究领域,测试用例的质量将直接决定软件测试的科学性和有效性.该文在一般的测试用例选择方法的基础上,提出了一种基于对接口参数进行组合覆盖的黑箱测试用例自动生成算法模型,据此可以生成一个对所有接口参数进行两两组合覆盖的测试用例表.并证明了该方法产生的测试用例具有数量少、能实现对接口参数最大限度组合覆盖的特点,从而可以在提高软件测试质量的同时,降低成本,提高效率.最后介绍了该算法在作者研究开发的测试数据生成工具中的实际效果.