摘要:电路划分是VLSI 物理设计过程中的一个关键阶段.该问题本质上是一个NP 困难的组合优化问题.针对该问题,提出了一种带FM 策略的混合粒子群优化算法.引入遗传算法的两点交叉算子和随机两点交换变异算子,保证了粒子在位置更新后依然可行;为了提高算法的局部搜索能力,将具有较强局部搜索能力的FM 策略融入算法的位置更新;设计了种群多样性变异策略,提高了种群多样性,避免了易陷入局部最优的缺陷.对ISCAS89 标准测试电路的仿真实验结果表明,所构造的算法是有效的.

摘要:在穴度方法的基础上结合捆绑策略,为三维欧氏空间中长方体Packing 问题的求解提供了一种高效的启发式算法.试算了由Loh 和Nee 于1992 年提出的15 个经典算例,对其中的困难算例LN2,取得了98.2%的空间利用率,比目前的最好纪录高1.6 个百分点;对另一个困难算例LN6,取得了96.2%的空间利用率,与目前的最好纪录持平;对其他13 个较为容易的算例均取得了最优的布局,与目前的最好纪录持平.总体而言,15 个算例的平均空间利用率为70.96%,在整体空间利用率上达到了较好的效果.

摘要:针对现有服务选择中服务推荐技术的不足,提出一种基于偏好推荐的服务选择(trustworthy services selection based on preference recommendation,简称TSSPR)方法.首先搜索一组偏好相似的推荐用户,并通过皮尔逊相关系数计算用户的评价相似度,然后基于用户的推荐等级、领域相关度和评价相似度等对用户的推荐信息进行过滤,从而使推荐信息更为可信.模拟实验结果表明,通过正确的参数设置,该方法能够有效地解决推荐算法中冷启动、推荐信息不准确等问题.

摘要:提出了一个开放环境特性描述框架.该框架支持便捷地、形式化地描述异步环境的各种特性,包括那些既有技术不能处理的时序特性.该框架还引入了谓词检测技术,支持高效的环境特性感知机制的实现.开发了一个开放环境特性感知中间件平台,并通过详细的案例分析展示了如何基于所提出的环境特性描述框架与中间件平台,高效地感知环境特性,支持可信软件系统的构建.

摘要:简述了量子程序设计语言NDQJava-2.该语言是在NDQJava 的基础上增添了量子条件语句、量子循环语句、量子子程序、量子模块以及量子异常处理机制等量子成分,使其成为一种结构化的量子程序设计语言.书写量子程序的实践表明,相对于NDQJava 而言,NDQJava-2 是一种更为实用、易读,其成分设定更为合适的量子程序设计语言.

摘要:不同于已有的基于手工模板和规则的方法,提出了一种基于句法路径的情感评价单元自动识别方法.该方法自动获取句法路径来描述评价对象及其评价词语之间的修饰关系,并通过计算句法路径编辑距离来改进情感评价单元抽取的系统性能.实验语料来自数码相机和MP3 播放器两个典型的电子产品领域.实验结果表明:(1) 句法路径能够有效描述评价对象及其评价词语之间的关系,对情感评价单元的识别有很大帮助;(2) 基于编辑距离的句法路径改进策略能够进一步提高情感评价单元识别的系统性能.

摘要:在基因表达式编程(gene expression programming,简称GEP)中,由于不同问题得到的适应度-距离相关系数(fitness-distance correlation,简称FDC)值很相近,所以难以用FDC 预测GEP 求解不同问题的进化难度.为了解决该问题,提出了态势模型及其区间密度指标来预测GEP的进化难度.主要工作包括:(1) 提出了GEP染色体之间的距离和态势模型的新概念;(2) 提出了态势模型中的区间密度指标;(3) 从动力学角度证明了态势模型是对GEP 原搜索空间的一种映射

摘要:提出了一种称为可纳子目标排序(admissible subgoal ordering,简称ASO)的排序关系,给出了可纳排序的形式化定义并讨论其对增量式规划的重要性.随后介绍了原子依赖关系理论和原子依赖图技术,能够在多项式时间内近似求解可纳子目标排序关系.最后给出了一种计算可纳子目标序列的算法.其所有思想已经在规划系统ASOP 中实现.通过在国际规划大赛标准测试领域问题上的实验,其结果表明,该方法能够有效地求解大规模的规划问题,并能极大地改善规划性能.

摘要:基于约束的配置模型中会有一些变量之间不存在任何直接或间接的约束关系,这样的变量之间进行约束传播不会互相影响取值.基于配置问题的这一特点,提出了一种等价类划分的思想,用于构造产品模型时的预处理技术,可以有效地将原问题划分为若干子问题,证明了这些子问题可以分别处理.分别采用两种回溯策略对求解效率进行了测试,结果表明能够有效地提高求解效率.最后,等价类划分方法与计算解释的QUICKXPLAIN 算法集成计算冲突解释,测试结果表明,经过等价类划分后,同样可以有效地提高计算解释的效率.

摘要:首先,在有限整数集上建立有效拆分关系,在联盟集上建立有效二部分解关系,并设计了一种EOCS (effective optimal coalition structure)算法.该算法采用自底向上方式,只对具有有效二部分解关系的联盟进行二部分解来求联盟的优值,从而降低了二部分解的数量.随后,利用函数的克林闭包特性证明了EOCS算法的正确性,利用积分极限定理证明了EOCS 算法时间复杂度的下界是Ω(2.818ⁿ),用时间序列分析方法求出了EOCS 算法的上界是

摘要:提出一种称为TRAVEL 的网络聚类算法.它能够产生包含所有可能密度聚类的网络链接遍历序列,并从中自动发现网络的全局优化聚类.然后,遍历序列被转换为连续子区间堆结构.在此基础上,提出一种聚类算法HCLU,可以无须用户干预地从连续子区间堆中自动发现网络的层次聚类边界.在真实网络以及计算机生成的仿真网络数据集上的实验结果表明,所提出的算法比目前的基准方法具有更高的聚类精度.此外,算法能够从各种带有噪声的网络中发现无冗余且鲁棒的层次社团结构.

摘要:提出了“内涵亏值”与“紧致依赖”的概念,证明了由“紧致依赖”组成的依赖基对于“左部加属性、右部减属性”这一规则的公理系统是无冗余而完整的.由此发现了除Guigues-Duquenne 基以外还有其他无冗余完整依赖基,改变了只有唯一的一个无冗余完整依赖基的传统观念,揭开了寻找多种无冗余完整依赖基以满足多样化需求的序幕.

摘要:提出了在多源组播路由过程中解决交互同步问题而无须使用同步控制器的思想,在这种思想的基础上进一步实现低延迟组播.主要贡献包括:(1) 建立面向多点交互过程的同步模型及证明支持多点交互同步的组播路由定理;(2) 提出一种有效的、低延迟的、支持多点交互同步的应用层组播路由算法;(3) 采用数学方法对新算法和现有相关算法进行性能分析和对比.最后,通过仿真实验和实际应用表明,新算法是正确和有效的.

摘要:通过结合体系结构和算法进行研究发现,基于锁的同步机制是细粒度并行介度中心(betweenness centrality,简称BC)算法在现有多核平台上高效执行的主要瓶颈.提出了一种消除锁同步的数据驱动(data-centric)并行算法,在AMD 32 核SMP 和Intel 8 核SMP 两个平台上获得了2 倍左右的加速比.

摘要:为了能够自动分析入侵证据,提出了一种层次化入侵场景重构方法.其原理是:首先,基于报警关联技术重构出入侵者的抽象攻击步骤及步骤间关系;然后,基于攻击特征和依赖追踪技术重构出各步骤的行为细节;最后,通过两层重构结果的彼此映射,调整获得完整的入侵行为图.基于DARPA 2000 的实验结果表明,该方法的重构结果准确性和完备性均比较高,而且抽象与细节相结合的表示方法更易理解,也更适合作为法律证据.而与现有方法相比,该方法在重构场景的完整性、适用行为的复杂性以及方法安全性等方面也有一定的改善.

摘要:分析了移动自组网(mobile ad hoc network,简称MANET)暴露拓扑带来的安全问题,提出了一种拓扑隐藏的安全多路径路由协议.在路由发现过程中,不在路由包中携带任何路径信息,从而有效隐藏网络拓扑.通过按需的邻居发现进行身份认证并建立路由表项,最终采用排除节点的方法实现多路径的选取;在路由维护过程中,设计了专门的错误发现机制以检验所选路径的有效性和安全性.该协议综合考虑时间因素和路径长度因素,实现了安全的最短路径确定.安全分析表明,该方案可以抵御黑洞攻击、虫洞攻击、rushing 攻击和sy

摘要:提出了一种自底向上的方法来实现系统迁移过程中自动和科学的访问控制策略转换.首先对多级安全中敏感标记最优化挖掘问题作了形式化描述,证明了该问题是NP 完全问题,不存在多项式时间算法.然后,在此基础上提出了基于层次聚类和遗传算法的近似最优化挖掘算法,将该问题分解为范畴划分和密级分配两个阶段.最后,实验结果表明,算法能够有效地挖掘出最优的敏感标记.该方法可以应用于等级保护工作中的系统迁移工程.

摘要:在Waters 的基于身份加密方案的基础上提出了一种高效的基于身份认证密钥协商协议,并在标准模型下证明了该协议的安全性.与目前已有的同类协议相比,该协议具有更高的效率和更弱的安全假设,并具有已知密钥安全和前向安全性等安全性质,同时能够抵抗未知密钥共享和密钥泄露伪装攻击.在该协议基础上,构造了防止用户密钥生成中心获取会话密钥的协议,以满足需要防止密钥托管的应用需求,并采用安全的消息认证码算法为该协议增加了密钥确认过程.

摘要:在MANET 中,通信节点的移动会造成端到端通信路由的时常中断.传统TCP 协议只有拥塞控制机制,对由于节点移动造成的数据包传输丢失和超时也作为拥塞处理,使得端到端传输性能低下.为解决这一问题,采用跨层设计思想,将传输控制与链路稳定性路由结合,提出了一种基于链路生存时间概率的传输控制协议(transmission control protocol based on probability of link residual lifetime,简称TCP-PLRT).该协议通过在路由稳定时跨层收集路由层链路生

摘要:Ad hoc 网络和无线传感器网络具有广泛的应用,但对于这样自组性的网络须采用分层结构的聚簇来有效管理.通过选择具有支配属性的节点构成虚拟主干以支持路由、广播及覆盖等应用.大部分的研究都集中在高效选择较小的连通支配集.全面阐述了连通支配集构造的研究进展,并依据不同的网络假设、设计目标和性能对超过20 种连通支配集的构造算法进行分类和总结.指出这一领域的研究方向.

摘要:分析了视觉手势的交互特征,提出了非接触型设备交互模型,基于数据流图方法建立了支持连续信息输入的数据流模型来描述视觉手势信息的处理流程,基于“paint-view-correct”隐喻构建了手势界面开发工具IEToolkit.系统的主要特点包括:使用插件设计思想提供了可扩展的接口,方便开发人员对系统进行扩展;实现了对平台内部多个分类器的统一管理,方便用户对这些分类器进行动态配置;提供了可视化的用户界面,用户能够根据不同的应用灵活地定义高层的手势交互语义;屏蔽了图像处理、机器学习等底层的技术细节,降低了界面开

摘要:提出了一种面向个人信息管理(personal information management,简称PIM)的Post-WIMP 界面模型(Post-WIMP PIM interface model,简称PWPIM).首先给出了PWPIM 的形式化描述,从5 个方面对个人信息管理进行建模,分别描述了用户特征、领域对象和交互过程等;在此基础上给出了PWPIM 的建模方法;最后,将PWPIM 应用于一个基于实物界面的PIM 系统.应用实例表明,PWPIM 能够有效地描述PIM 的Post-WIMP 界面,能够满足

摘要:根据变分网格逼近表示所定义的全局误差能量,提出一种局部贪心优化算法.该算法通过控制目标网格分片数来简化网格,通过种子的自适应选取来达到理想的简化效果,具有直观的几何意义.该方法计算量较小,效率较高,能够有效地应用于几何造型系统中.

摘要:针对过约束、完整约束和欠约束三维几何约束系统的求解问题,提出了等价性分析方法.该方法基于三维几何约束系统的内在等价性,充分挖掘几何领域知识,依据拆解约束闭环、缩减约束闭环和析出约束闭环等原则,采用等价约束替换来处理几何约束闭环问题,优化几何约束图的结构,实现几何约束系统的优化分解.最后用多个实例验证了该方法的正确性和有效性.