软件学报杂志 北大期刊 CSCD期刊 统计源期刊

软件学报 2005年第10期杂志 文档列表

软件学报杂志算法设计与分析

求解QAP问题的近似骨架导向快速蚁群算法1691-1698

摘要：QAP(quadratic assignment problem)问题是经典的组合优化问题之一,广泛应用于许多领域中.针对QAP问题,提出了一种新的蚁群算法--近似骨架导向的快速蚁群算法(ABFANT).该算法的基本原理是通过对局部最优解的简单相交操作得到QAP问题实例的近似骨架(approximate-backbone),利用这些近似骨架可以极大地缩小QAP问题的搜索空间,而同时不降低搜索的性能,最后对这个缩小后的搜索空间,直接用当前求解QAP问题最好的启发式算法之一-快速蚁群算法(FANT)求解得到问题的解.在QAPLIB中的典型实例上的实验结果表明,近似骨架导向的快速蚁群算法明显优于快速蚁群算法.此外,指出基于近似骨架的算法思想可以很容易地被移植到其他求解QAP问题的启发式算法中.

最大节约原则下单倍型推导问题的实用算法1699-1707

摘要：在疾病的易感基因研究和药物反应实验中,常常需要知道单倍型,而不仅仅是基因型数据.但是直接通过生物学实验手段来测定单倍型在时间和成本上消耗过大,所以在实验室里往往仅测得基因型,而通过一些计算手段来推导出单倍型.不同于Clark著名的单倍型推导模型,Gusfield和Wang等人提出了一种通过基因型样本推导单倍型的新模型.这种模型试图按照最大节约原则去寻找可以解释基因型样本的最小单倍型集合.这种基于节约原则的模型克服了Clark模型的一些缺陷.提出了节约原则模型的一个多项式时间的贪心算法以及一种把贪心策略和分支限界策略集合在统一框架下的复合算法.相对于Wang原来提出的分支限界完全算法,贪心的近似算法运行快得多,而且同时保持了比较准确的推导结果.新的复合算法也是一种完全算法.实验结果表明,与原来的分支限界算法相比,复合算法可以极大地提高运行效率以及可应用的实例规模.

软件学报杂志系统软件与软件工程

并发Java程序同步操作的有效删除1708-1716

摘要：同步操作是并发Java程序非常大的一部分开销.在现有程序分析方法的基础上,提出了一种精确而有效的冗余同步操作的静态删除方法.该方法分为基本处理和线程间时序分析两个阶段,充分考虑了控制流结构和线程交互时序对同步删除的影响.构造了一个Java编译器JTool,并在其上实现了同步删除算法.对于确定的单线程程序,同步删除率达到100%;对于多线程程序,同步删除率高于现有的分析工具.

基于分布式认知理论的扩展资源模型1717-1725

摘要：分布式认知理论通过协调人机对话,结合人和计算机各自的优势解决问题,在人机交互研究中扮演了指导者的角色.尽管分布式认知理论支持的资源模型在分析人机交互时取得了成功,但模型存在不能提供复杂用户任务支持、缺乏对模型中元素的准确定义等问题,在一定程度上导致了表现形式上的混乱.使用分布式认知理论构造了扩展资源模型,建立人机交互活动中的动作和表征之间的联系,从而指导界面的设计和实现.扩展资源模型从静态结构和交互策略两个方面对界面交互动作提供支持,在交互中减少人的认知负担.该研究对设计符合人的认知特点的界面具有一定的指导作用.

基于语法树的实时动态电压调节低功耗算法1726-1734

摘要：动态电压调节是一种有效的低功耗技术.使用这种技术,编译器指导的动态电压调节能够有效地降低系统功耗.提出了基于语言语法树的实时动态电压调节低功耗算法.该算法在静态程序最差时间分析方法的辅助下,通过在程序内部自动插入电压调节代码来实现电压调节.在RTLPower(real-time low-power)实时低功耗系统上完成了算法的实现,对嵌入式测试,程序集的初步测试证明该算法最大可节省50%的能量消耗.

基于事件约束的软件过程验证1735-1742

摘要：软件过程是以人为中心的系统,其特点是动态性和不断演化.既定过程模型在实际执行时往往有所偏差.基于E-CSPE(extended constraints on succeeding and proceeding events)约束实现过程验证和偏差测量.事件约束根据过程模型定义.过程实例执行被记录为事件序列.通过分析事件序列对事件约束的覆盖和违反结果,可以计算EPD(event constraint based process difference metric)和EAD(event constraint based activity deviation metric)指标.EPD指标可以反映过程执行与过程模型的偏差,EAD指标则为过程演化提供依据.

软件学报杂志默认

《2005年度计算机科学技术发展报告》征稿启事1725-1725

敬告作者1756-1756

欢迎加入中国计算机学会1841-1841

第2届中国可信计算与信息安全学术会议CTCIS2006征文通知1852-1852

《软件学报》投稿指南-F0003

软件学报杂志计算机网络与信息安全

可证明安全性理论与方法研究1743-1756

摘要：论述了可证明安全性理论在安全方案与安全协议的设计与分析中的应用,内容主要包括:什么是可证明安全性,可证明安全性理论涉及到的一些基本概念,RO(random oracle)模型方法论的基本思想及其在公钥加密和数字签名等方案中的应用研究进展,标准模型下可证明安全性理论在公钥加密和数字签名等方案中的应用研究进展,以及可证明安全性理论在会话密钥分配协议的设计与分析中的应用研究进展.

一种电子商务协议形式化分析方法1757-1765

摘要：提出了一种新颖的形式化方法,可以用于分析电子商务协议的安全性质,例如可追究性和公平性.与以前的工作相比较,主要贡献在于:(1)对协议主体的拥有集合给出了形式化定义,且主体的初始拥有集合只依赖于环境;(2)将协议的初始状态假设集合分为3类:基本假设集合、可信假设集合和协议理解假设集合,避免了因非形式化的初始假设而产生的分析错误;(3)对可信假设作细粒度的形式化规范,揭示协议的内涵;(4)建立公理系统,使新方法更为严格与合理.

应用层组播的最小延迟生成树算法1766-1773

摘要：实时传输是应用层组播技术的一个主要应用领域,对网络延迟有严格的限制.保证低延迟组播成功的关键在于构建高效的应用层组播树,研究构建最小延迟应用层组播树的算法.首先分析影响延迟的3个因素:链路的传输时间、结点的发送/转发时间和结点度,然后把求解应用层组播树的问题抽象成对边和点都带权的有向图求解"度约束最小延迟生成树"的问题,同时证明这个问题属于NP-hard,并且提出了两类启发式近似算法:基于度的算法和基于最大延迟路径的算法.最后通过模拟实验说明了所提出算法的有效性.

多级安全DBMS的通用审计策略模型1774-1783

摘要：提出了一种基于多级安全数据库管理系统的通用审计策略模型.该模型具有丰富的表达能力,既可以表达基于时间的审计策略,也可以实现基于规则的审计策略推衍.通过引入对象的属性谓词,还可以表达细粒度的审计策略.证明了该模型的可判定性,并给出了判定任意一个事件是否需要审计的算法.

串空间理论扩展1784-1789

摘要：现有的串空间模型由于没有抽象更多的密码学原语,因此不能分析较复杂的安全协议.希望通过对串空间理论的扩展使其充分地表达较多的密码学原语,以满足分析复杂安全协议的需要.对入侵串轨迹增加了签名、签名验证和HMAC(keyed-hashing for message authentication code)函数模型,重新定义了理想概念并对衍生出的相关命题和定理进行了证明.扩展的诚实理想分析模型不仅继承了原理论的性质,而且适合分析含丰富密码原语的协议,如JFK和IKE2.

面向点对点的安全可靠存储系统1790-1797

摘要：利用P2P的方法实现了一个共享和合作的安全存储系统,其中参与节点运行Paramecium协议或其他兼容的DHT(distributed hash table)协议形成自组织覆盖层,维护系统的组织结构和提供路由服务.由于该系统为开放式结构,引入了基于PKI的安全认证机制以确保用户数据的授权访问.用户数据和副本标示的绑定支持了安全的数据自修复;副本类型的引入提供了安全的共享写.初步的分析和实验表明,该P2P系统在现实条件下,在消耗较低的维护带宽的同时维持了较高的可靠性并提供了较好的读写性能.

DCT变换域乘嵌入图像水印的检测算法1798-1804

摘要：目前大多数水印算法采用线性相关的方法检测水印,但是,当原始媒体信号不服从高斯分布,或者水印不是以加嵌入方式嵌入到待保护的媒体对象中时,该方法存在一定的问题.数字水印的不可感知性约束决定了水印检测是一个弱信号检测问题,利用这一特性,首先从图像DCT(discrete cosine transform)交流变换系数的统计特性出发,应用广义高斯分布来建立其统计分布模型,然后将水印检测问题转化为二元假设检验问题,以非高斯噪声中弱信号检测的基本理论作为乘嵌入水印的理论检测模型,推导出优化的乘嵌入水印检测算法,并对检测算法进行了实验.结果表明,对于未知嵌入强度的乘水印的盲检测,提出的水印检测器具有良好的检测性能.因此,该检测器能在数字媒体数据的版权保护方面得到了实际的应用.