求解旅行商问题的循环局部搜索算法的运行时间和性能分布分析

旅行商问题（Traveling Salesman Problem，TSP）是组合优化中最典型的NP难问题之一，长期以来人们都在寻求快速高效的近似算法以在合理的计算时间内准确地解决大规模问题，并设计出许多高效实用的启发式和宏启发式算法，其中循环LK算法是性能最好和最具代表性的算法之一．作者研究了该算法的运行时间分布：通过对TSPLIB中大量不同规模的TSP实例的运行时间分布的统计分析和拟合，发现求解TSP问题的循环LK算法的运行时间分布很好地服从Weibull分布，并进一步给出了该分布对求解TSP问题的物理意义．作者同时首次给出了循环LK算法求解TSP问题得到的解的性能分布以及由此得到的一些有实际指导意义的结论．     

异构环境下MPI程序Cache访问的单机模拟

Cache模拟工具可以在单机上模拟运行于异构环境下的并行程序的Cache访问。用户依照自己的需求指定Cache模型参数及替换算法，对每个进程中的某一段进行模拟，使并行程序中每个或每组子进程/线程分别对应一个Cache模型，从而同时得到每个或每组子进程/线程的Cache访问参数。使用单机Cache模拟环境降低了并行程序的Cache模拟对实际并行环境的依赖。同时，用户还可以很方便地在其基础上扩展并使用自行开发的替换算法或进程通信模块功能，适应了不同用户对并行程序Cache模拟工具的需要。     

基于Agent网格计算性能的实时调节

由于网格环境中资源的动态性、非独占性、异构性、分布性和网络通信延迟的不确定性等因素导致了应用程序的复杂和低效,难以达到预期的性能。为了实时调整和改进并行和分布式应用的性能,该文研究采用Agent技术设计一种系统模型,利用Agent收集应用各种性能参数,然后利用Agent的智能性,加以分析综合并实时调整,使应用程序更加适应网格的动态环境,获得更高的性能。     

基于曙光5000并行机的远程并行调试器

并行调试对并行程序开发非常重要,然而传统的远程并行调试方式是采用登录(telnet)命令通过命令行的文本界面进行,非常繁杂。本文介绍了为曙光3000系统设计实现的远程并行调试器RPB(Remote Parallel Debugger)。RPB实现了完全并行调试等功能,并且具备图形用户界面,用户界面采用Java语言和Swing工具包实现,具备平台独立的特点。RPB采用客户端/服务器模式,客户端和服务器之间的通信采用当今流行的CORBA中间件技术。RPB支持通过局域网或广域网远程调试并行机上的程序,屏蔽了客户平台的差异和并行机地理位置上的差异,因而大大提高了并行机的好用性。     

有色装箱问题的在线近似算法

有色装箱问题是经典装箱问题的推广,它在多处理器实时计算机系统的任务调度等实际问题中有着很强的应用背景,提出了求解有色装箱问题的KC－A算法,它首先对输入物品进行分类预处理,然后在同一类内部使用经典装箱问题的近似策略A,给出了KC－A算法最坏情况渐近性能比的下界,分析了当选用的算法A是著名装相算法NF,FF,BF,WF时KC－A算法的最坏情况渐近性能比和平均性能比,给出了实验结果,并指出KC－FF表现出相对更好的实验效果。     

分布存储并行机上的自动数据布局优化模型

在分布式并行机上,数据布局的质量极大的影响着应用程序的执行性能,以往的研究一般将自动数据布局优化问题近似分解为数据对准优化和数据分布优化两步来解决,且对两者的结合只研究了一维的情况,在相关研究工作的基础上,在多维情况下将数据对准优化和数据分布优化结合在一个模型当中,提出了一个数据对准优化与数据分布优化统一的多维静态数据布局模型,避免了采用启发式策略,从而更加精确地描述了自动数据布局优化问题,同时给     

一种针对基音周期的3G信息隐藏方法

现今,移动通信网络已经发展到了第三代,随着3G网络的不断发展,研究3G网络隐蔽通信是十分必要的.语音编码过程中利用编码参数隐藏信息是现今的一个研究热点.基音周期是描述音源特征的一个主要参数,基于基音周期的修改较难检测的特点,在自适应码本搜索的过程中,提出一种在3G话音中利用基音周期参数隐藏信息的算法,使用该算法可以在3G通信的过程中嵌入隐秘信息.该算法可以抵抗基于浊音特性的语音压缩域隐写分析.仿真实验的结果表明该方法对合成语音质量的影响很小,具有良好的隐蔽信息传输性能.     

一种针对手写体图像的取证算法

数字图像取证是信息安全领域的研究热点.在手写体图像方面,现有的取证算法对于图像采用各种重采样技术的篡改,其检测效果并不理想.在本文中,我们根据源区域和篡改区域的特征值不变性,提出一种简单有效的盲取证算法.该算法实现了手写体图像篡改的自动检测和篡改区域的定位,并且比现有的重采样检测方法对相同的手写体图像具有更好的检测率,尤其是在图像中的字有模糊、缺损的情况下检测的优势更明显.实验结果表明,对于经过各种重采样处理的手写体图像,该算法比现有取证算法的检测率高20%,当虚警率小于1%时,本算法的检测率达96.9%以上.     

保护私有信息的范围搜索算法

合作计算的任务可能发生在彼此互不完全信任的各方之间,此时各方参与运算只是想知道最终的结果,而不希望自己的隐私信息被别人获取.安全多方计算所要解决的正是合作计算的隐私保护问题,它能够在保证各方输入的隐私数据安全性的同时获得正确的计算结果.本文考虑学术界一直悬而未决的保护私有信息的范围搜索问题,并且基于安全多方计算的理论和方法实现两类范围搜索协议,同时对它们的安全性、时间复杂性和通讯复杂性进行详细的分析讨论.在本文最后,我们将范围搜索协议应用到保护私有信息的DBSCAN算法中.     

一个自然语言水印嵌入安全性评估方案

自然语言水印是一种为自然语言文档特别设计的数字版权管理技术。虽然已经有不少精心设计的自然语言水印算法,但是对它们的嵌入质量和安全性只有简单的说明。本文中,我们提出了一个自然语言水印嵌入安全性的评估方案,定义了理想不可检测性,并提出了构造针对特定检测器的不可检测性的交互证明系统。本文也对一些实际系统按此方案作了评价。