上下文相关图文法的表达能力分析
摘要：上下文相关图文法是描述可视化语言的形式化工具，为了直观地刻画并高效地分析可视化语言，已有图文法形式框架均着重于文法形式和分析算法的研究，而忽略了对它们之间表达能力的分析．在对已有上下文相关图文法形式框架的关键特征进行分析和归纳的基础上，通过构造不同形式框架之间的转换算法，揭示并形式化证明了它们表达能力之间的关系．而且，转换算法在不同形式框架之间建立了关联，使图文法的应用不必再局限于一个框架，而是可以选择不同框架分别进行图的描述和分析，从而提高了上下文相关图文法的易用性．概率计算树逻辑的限界模型检测
摘要：为了缓解概率计算树逻辑模型检测中的状态空间爆炸问题，提出了概率计算树逻辑的限界模型检测技术．该技术首先定义概率计算树逻辑的限界语义，并证明其正确性；之后，通过实例说明在传统限界模型检测中，以路径长度作为判断检测过程终止的标准已经失效，基于数值计算中牛顿迭代法的终止准则，设计了新的终止判断标准；然后提出基于线性方程组求解的限界模型检测算法；最后，通过3个测试用例说明，概率计算树逻辑限界模型检测方法在反例较短的情况下能够快速完成检测过程，而且比概率计算树逻辑的无界模型检测算法所需求得的状态空间要少．W4H：一个面向软件部署的技术分析框架
摘要：部署是软件生命周期中的一个重要环节，是软件生产的后期活动，通过配置、安装和激活等活动来保障软件制品的后续运行．为了系统地了解软件部署的现状和最新进展，建立了一个多侧面、细粒度的分析框架--W4H，以对该领域的主要研究工作和系统工具进行概括分析．该框架从软件部署的概念和面对的问题空间出发，由5个侧面、12个维度构成，覆盖了软件部署方法中主体、客体、适用范围、方式策略和过程支持能力等多个方面．基于w4H分析框架，对当前具有代表性的软件部署方法与技术进行分析和总结．案例研究结果表明，该分析框架能够对软件部署方法与技术进行较为全面的分析，对软件系统部署方法和技术的选择及开发具有重要的指导意义．基于约束的软件失效域识别与特征分析
摘要：随机测试是实践中广泛采用的一种黑盒测试方法．近年来提出的适应性随机测试方法改进了随机测试的不足，仿真实验结果表明，改进效果取决于软件失效域的特征．提出以测试约束刻画软件失效域在输入域上的分布，探讨了基于现有的程序分析技术构造测试约束的过程，讨论了基于测试约束的软件失效域的特征分析方法．以一个实例软件验证所提出的测试约束构造过程及其软件失效域特征分析方法．测试约束揭示了软件故障的触发与传播的内在机制，基于测试约束的软件失效域的特征分析方法有助于改进测试用例的设计质量以及评价适应性随机测试方法的适用性．2012CCF中国计算机大会征文通知
摘要：第9届CCF中国计算机大会（2012 CCF China National Computer Congress，CCF CNCC2012）将于2012年10月18-20日在大连世博广场举行，承办单位为大连大学．CCFCNCC是由中国计算机学会2003年创建的系列性学术会议，已在不同的城市成功举办8届，现每年一次．基于遗传算法的工作流个人工作列表资源调度
摘要：在工作流管理系统中，个人工作列表的优化调度具有重要意义．已有的相关研究主要关注工作流实例的调度，而关于个人工作列表调度的研究还较少．首先描述了工作流实例动态执行环境下个人工作列表调度问题，并提出了一个基于遗传算法的个人工作列表资源调度算法．该算法要为每一个执行人推荐一个可行工作列表，并在保证工作项联合执行成功率的同时最小化总体延误代价．最后，通过一个仿真实验将该遗传算法与其他7种基于分配规则的典型调度算法进行了比较。结果表明，所提出的基于遗传算法的个人工作列表资源调度算法比已有的其他典型调度算法具有更好的调度效果．面向SLP的多重循环向量化
摘要：如今，越来越多的处理器集成了SIMD（single instruction multipledata）扩展，现有的编译器大多也实现了自动向量化的功能，但是一般都只针对最内层循环进行向量化，对于多重循环缺少一种通用、易行的向量化方法．为此，提出了一种面向SLP（superword level parallelism）的多重循环向量化方法，从外至内依次对各个循环层次进行分析，收集各层循环对应的一些影响向量化效果的属性值，主要包括能否对该循环进行直接循环展开和压紧、有多少数组引用相对于该循环索引连续以及该循环所包含的区域等，然后根据这些属性值决定在哪些循环层次进行直接循环展开和压紧，最后通过SLP对循环中的语句进行向量化．实验结果表明，该算法相对于内层循环向量化和简单的外层循环向量化平均加速比提升了2．13和1．41，对于一些常用的核心循环可以得到高达5.3的加速比．语义web中对象共指的消解研究
摘要：随着语义web的快速发展，语义wleb数据大幅增长．在语义Web中，单个对象很可能由多个不同的标识符（例如URI）指称．语义web中，对象共指的消解是识别语义wleb中指称相同对象的不同标识符，并消除描述这些标识符的RDF（resource description franework）数据之间不一致性的过程，它对于语义web数据的融合、搜索、浏览等具有重要作用．首先，形式化定义了语义wleb中对象共指的消解问题；然后，从对象共指识别使用的特征、数据冲突的消解方式、对象共指消解方法的适用范围、现有原型系统和基准测试集这5个方面调研了最新的研究进展；最后，讨论了尚存的挑战，并展望未来可能的研究发展方向．粗糙集的近似集
摘要：粗糙集是1982年由Pawlak教授提出的解决集合边界不确定的重要方法庀通过两个精确的上、下近似集作为边界线来刻画目标集合（概念）X的不确定性，但它没有给出如何用已知的知识基（知识粒）来精确或近似地描述边界不确定的目标集合（概念）X的方法．首先给出了集合之间的相似度概念，然后分析了分别用上近似集R-（X）和下近似集R-（X）作为目标集合（概念）X近似描述的不足，提出了在已有知识基（粒）空间下寻找目标集合（概念）X的近似集的方法，并分析了用R0.5（X）作为坝概念）的近似集的优越性．最后讨论了不同知识粒度空间下R0.5（X）与X的相似度随知识粒度的变化关系．从新的角度提出了目标集合（概念）X近似集的构造方法，促进了粗糙集模型的发展．自适应动态控制种群规模的自然计算方法
摘要：提出了一种种群规模自适应动态控制策略，实现了种群规模根据进化过程自适应的动态变化．该策略的实现不依赖于算法进化操作的具体步骤周而适用于各种基于种群优化的自然计算方法．首先给出了动态控制策略的框架；然后，在此框架下，充分利用动态种群规模反馈的有用信息，提出了基于Logistic模型的增加／删除数目自适应变化的方法，设计了自适应地兼顾有效性和多样性的增加算子和基于多样性的删除算子．将该策略应用到两种不同的自然计算方法中，采用经典测试函数和新型CEC05测试函数验证其性能．实验结果均表明，结合了所提出的种群规模自适应动态控制策略的新算法，比原算法在求解精度和收敛速度上均有明显的提升．修正免疫克隆约束多目标优化算法
摘要：针对约束多目标优化问题，提出修正免疫克隆约束多目标优化算法．该算法通过引进一个约束处理策略，用一个修正算法对个体的目标函数值进行修正，并对修正后的目标函数值采用免疫克隆算法进行优化，用一个精英种群对可行非支配解进行存储．该算法在优化过程中，既保留了非支配可行解，也充分利用了约束偏离值小的非可行解，同时引进整体克隆策略来提高解分布的多样性．通过对约束多目标问题的各项性能指标的测试以及和对比算法的比较可以看出：该算法在处理约束多目标优化测试问题时，所得解的多样性得到了一定的提高．同时，解的收敛性和均匀性也得到了一定的改进．一种视觉词软直方图的图像表示方法
摘要：基于视觉词的统计建模和判别学习，提出一种视觉词软直方图的图像表示方法．假设属于同一视觉词的图像局部特征服从高斯混合分布，利用最大．最小后验伪概率判别学习方法从样本中估计该分布，计算局部特征与视觉词的相似度漯加图像中每个视觉词与对应局部特征的相似度，在全部视觉词集合上进行结果的归一化，得到图像的视觉词软直方图．讨论了两种具体实现方法：一种是基于分类的软直方图方法，该方法根据相似度最大原则建立局部特征与视觉词的对应关系；另一种是完全软直方图方法，该方法将每个局部特征匹配到所有视觉词．在数据库Caltech-4和PASCALVOC2006上的实验结果表明，该方法是有效的．联盟规范系统及其规范能力极限
摘要：联盟规范系统（coalitional normative system，简称CNS）通过选择性地限制联盟的联合行动来对规范系统（normative system，简称NS）进行扩展．扩展了ATL的语义，提出了Coordinate-ATL（Co—ATL），用于对CNS进行形式化．为了刻画其规范能力的极限，确定了Co．ATL的两个语言片段，分别对应于两类不可改变的系统属性．对NS和CNS之间的关系进行了讨论，表明所得到的结果可以更好地界定NS的能力极限．此外，引入了对执行历史进行编码的有限状态机，进一步对CNS进行了扩展，提出了CNS．M．可以证明，关于CNS能力极限的界定在该扩展下保持稳定．一种多尺度协同变异的粒子群优化算法
摘要：为了改善粒子群算法易早熟收敛、精度低等缺点，提出一种多尺度协同变异的粒子群优化算法，并证明了该算法以概率1收敛到全局最优解．算法采用多尺度高斯变异机制实现局部解逃逸．在算法初期阶段，利用大尺度变异及均匀变异算子实现全局最优解空间的快速定位；随着适应值的提升，变异尺度随之降低；最终在算法后期阶段，利用小尺度变异算子完成局部精确解空间的搜索．将算法应用6个典型复杂函数优化问题，并同其他带变异操作的PSO算法比较，结果表明，该算法在收敛速度及稳定性上有显著提高．改进求解约束满足问题粗粒度弧相容算法
摘要：约束满足问题在人工智能领域有着广泛的应用．研究了约束满足问题的粗粒度维持弧相容求解算法，发现在求解过程中，对于指向已赋值变量的弧存在无效的修正检查，证明了这类修正检查是冗余的．提出一种方法避免这类冗余的修正检查，给出改进后的粗粒度弧相容算法的基本框架AC3_frame_ARR，该改进框架可用于改进所有粗粒度弧相容算法．实验结果表明，经过AC3_flame_ARR改进后的算法最多可以节省80％的修正检查次数和40％的求解耗时．认知无线网络信道接入协议
摘要：由于认知无线网络（cognitive radio network，简称CRN）固有“二次利用”的特性，使其日益得到重视．而作为CRN核心构成的MAC（medium access control）协议，业已成为当前各研究机构的一个热点．主要对频谱感测技术、信道接入技术等MAC层核心设计问题进行了探讨，并针对认知无线网络MAC的特性及需求进行了分析，然后对设计MAC频谱感知技术、信道接入技术、频谱共享技术等相关研究进展进行了归类总结．最后指出了当前面临的主要研究难点及挑战，并提出了一些方向性建议．基于主动路由的无线mesh网络区域移动管理方法
摘要：提出了一种无线mesh网络中基于主动路由的区域移动管理（active routing based intra-domain mobility management，简称ARMM）方法，将移动终端（mobile station，简称MS）的位置更新和mesh路由器（mesh route，简称MR）之间的动态路由相结合，让MR代替附着在它上面的MS进行位置管理，从而实现MR对MS的定位．给出了ARMM方法中的二层路由模型、路由算法及位置更新机制．性能分析结果表明，相对于现有的区域移动管理方法，ARMM方法具有较小的切换延时、位置更新开销和数据传输开销．TypeSampler：一种基于gossip的类型采样方法
摘要：在很多P2P应用中，节点可以根据其兴趣或资源划分为不同的类型，而以特定类型节点为目标的基于覆盖网的路由也就成为实现数据分发及查询的关键．非结构化覆盖网具有维护开销低、鲁棒性高的优点，却也因此难以保证路由效率．提出了一种基于gossip的类型采样方法一--TypeSampler，它以等概率采样不同类型的节点（称为类型采样），以此保证在任意节点发现特定类型邻居节点的概率下界，进而保证非结构化覆盖网中的路由效率．为了实现类型采样，TypeSampler首先通过基于gossip的节点采样及反熵聚集估计各类型节点的比例，然后，TypeSampler再根据这些比例估计值周期性地维护每个节点的类型采样表．理论分析与实验结果表明，TypeSampler能够实现精确的类型比例估计以及近似均匀随机的类型采样，并能适应动态的网络环境．而且相对于已有的方法，TypeSampler能够支持更高效的路由，且具有更好的可扩展性．