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

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

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

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

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

摘要:软件过程是以人为中心的系统,其特点是动态性和不断演化.既定过程模型在实际执行时往往有所偏差.基于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指标则为过程演化提供依据.

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

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

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

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

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

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

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

摘要:提出了把动态多密门限体制应用于大规模选举的电子投票系统,它可以允许系统中存在多个监票人(机构).即使在选票的生成、加密、传输及解密、统计过程中存在自适应敌手,也不影响选举的正常进行,因此具有强壮性.提供的电子投票方案,无须调用多次交互式的零知识证明验证投票人的选举资格和监票人的身份,而是利用动态多密门体制方便地实现了选票的秘密性、广泛可验证性、公平性和匿名性,较之以前的投票方案具有较高的通信效率和安全性.

摘要:为了解决网上金融交易实时清算的快速确认问题,分析了典型的交易过程及安全特性,并基于椭圆曲线签名原理,提出了一种基于双线性映射的清算确认框架协议,使得对交易结果的确认可以递进进行,并在最终清算时一次完成,有效地实现了不可否认性和证据留存,避免了复杂的PKI体系和两两确认的繁琐过程,使真正的直通式处理和在线清算成为可能.

摘要:提出了一种基于加同态公钥密码算法的匿名数字指纹方案,并给出了具有匿名功能的公钥和私钥对的具体构造方法,从而使该匿名指纹方案在发现盗版的情况下,销售商不需要第三方的帮助就能鉴别出数字多媒体作品的非法分发者,解决版权纠纷时也不需要购买者参与并提供相关的秘密信息,从而达到实现两方审判的目的.分析结果表明,该方案具有用户匿名及不可关联、销售商的可保证安全性和用户的可保证安全性等特点.

摘要:软件流水是开发循环程序指令级并行性的技术,它通过并行执行连续的多个循环体来加快循环的执行速度.在软件流水中,循环体的重叠增加了寄存器需求,导致寄存器压力增大,当目标处理机所提供的寄存器不足时,软件流水可能失败.在Itanium处理机上评估了NAS和SPEC2000基准程序中的软件流水循环的寄存器需求,发现静态寄存器不足是造成软件流水失败的主要原因,提出了3种增加软件流水个数、提高软件流水有效性的算法:限制循环展开因子的算法(register sensitive unrolling,简称RSU)、堆栈寄存器分配算法(stacked registerallocation,简称SRA)以及变量类型转换的算法(variabletype conversion,简称VTC).RSU根据静态寄存器需求确定一个合理的展开因子,增加了软件流水的成功率;SRA和VTC分别使用空闲的堆栈寄存器和旋转寄存器来充当静态寄存器,提高了寄存器的利用率.在面向Itanium处理器的开放源码编译器ORC(open research compiler)上实现了这3种算法,通过NAS程序的测试比较了这3种算法的有效性,同时对它们的结合应用进行了研究和实验.

摘要:软件流水是一种重要的指令调度技术,它通过同时执行来自不同循环体的指令来加快循环的执行速度.随着处理机运行速度的逐渐提高,存储访问延迟成为性能提高的瓶颈.为了减轻存储系统影响,软件流水结合了一些存储优化技术,通过隐藏存储延迟来提高性能.提出了一种延迟可预测的模调度算法(foresighted latencymodulo scheduling,简称FLMS),它根据循环的特点来确定load指令延迟.实验结果表明,FLMS算法减少了阻塞时间,提高了程序性能.

摘要:软件流水能够加快循环的执行速度.模调度是一种被广泛采用的软件流水的启发式.为了改善存储系统,cache使用了分级机制,但这也带来了额外的存储延迟-cache代价.证明了模调度可能导致cache代价,并提出了一种可以避免模调度的cache代价的PCPMS(prevent cache penalty in modulo scheduling)算法.实验结果表明,PCPMS能够避免模调度中的cache代价,提高程序性能.

摘要:对国家自然科学基金近年来在自然语言处理领域资助的已结题项目进行了综述,内容涉及中文信息处理技术项目总结、自然语言处理应用技术项目总结以及少数民族语言信息处理技术项目总结.