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

软件学报 2008年第03期杂志 文档列表

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

开放式频谱系统中启发式动态频谱分配算法479-491

摘要：在回顾了现有的开放式频谱系统中的动态频谱分配算法后，基于快速收敛和公平性两方面的性能因素并兼顾系统总带宽性能，提出了两种易于实现且具有良好收敛性能的启发式频谱动态分配算法——兼顾最大化系统总带宽的快速收敛算法（fast convergency algorithm with maximum bandwidth，简称FCMB）和兼顾最大化系统总带宽的启发式公平性分配算法（heuristic fairness algorithm with maximum bandwidth，简称HFWB）．通过大量的仿真实验，就系统总带宽、公平性以及收敛性能3个方面，与现有的协调式最大化系统总带宽（collaboration max-sum-bandwidth，简称CMSB）算法、随机分布式算法（randomized distributed algorithm,简称RAND）以及以最大化系统总带宽为目标的理论最优（theoretical max-bandwidth optimal，简称OPTL）算法进行了比较，并针对主、次用户数目变化、系统中信道数目以及次用户干扰区域半径大小变化等不同系统参数情况下各种算法的性能进行了对比分析．仿真结果表明，在综合考虑系统总带宽的基础上，FCMB算法和HFWB算法在快速收敛和兼顾系统带宽的公平性能上分别表现突出，尤其是FCMB算法，其在收敛速度上远远优于其他算法（和与其在系统吞吐性能上表现相近的CMSB算法相比，在收敛性能上至少有300％的提高）．

最大简单共享问题的快速近似算法492-499

摘要：介绍了一种基于复制结点的消除线路交叉的模型．该模型提出了一个优化问题，就是最小化结点复制的数量．同时提出一个自定义问题——“最大简单共享问题”，并证明最小化结点复制的数量与最大共享问题是等价的．证明了最大简单共享问题是NP-hard的，给出了一种简单的贪心算法，并证明该贪心算法的近似度为3．引入一个“最大互斥简单共享问题”，该问题是最大简单共享问题的2-近似．将其转化为在一系列图上的完美匹配问题，使该问题可以在多项式时间内得到完美解决．最后，在最大互斥简单共享的基础上，用局部搜索的方法将近似度提高到12/7．

两元指纹向量聚类问题的复杂性与改进启发式算法500-510

摘要：证明丢失值位数不超过2的指纹向量聚类问题为NP-Hard，并给出Figueroa等人指纹向量聚类启发式算法的改进算法．主要改进了算法的实现方法．以链表存储相容顶点集合，并以逐位扫描指纹向量的方法产生相容点集链表，可将产生相容点集的时间复杂性由O（m·n·2^p）减小为O（m·（n-p＋1）·2^p），可使划分一个唯一极大团或最大团的时间复杂性由O（m·p·2^p）减小为O（m·2^p）．实际测试显示，改进算法的空间复杂性平均减少为原算法的49％以下，平均可用原算法20％的时间求解与原算法相同的实例．当丢失值位数超过6时，改进算法几乎总可用不超过原算法11％的时间计算与原算法相同的实例．

k-LSAT（k≥3）是NP-完全的511-521

摘要：合取范式（conjunctive normal form，简称CNF）公式F是线性公式，如果F中任意两个不同子句至多有一个公共变元．如果F中的任意两个不同子句恰好含有一个公共变元，则称F是严格线性的．所有的严格线性公式均是可满足的，而对于线性公式类LCNF,对应的判定问题LSAT仍然是NP-完全的．LCNF≥k是子句长度大于或等于后的CNF公式子类，判定问题LSAT≥k的NP-完全性与LCNF≥k中是否含有不可满足公式密切相关．即LSAT≥k的NP-完全性取决于LCNF≥k是否含有不可满足公式．S．Porschen等人用超图和拉丁方的方法构造了LCNF≥3和LCNF≥4中的不可满足公式，并提出公开问题：对于k≥5，LCNF≥k是否含有不可满足公式？将极小不可满足公式应用于公式的归约，引入了一个简单的一般构造方法．证明了对于k≥3，k-LCNF含有不可满足公式，从而证明了一个更强的结果：对于k≥3，k-LSAT是NP-完全的．

2008全国开放式分布与并行计算学术年会征文通知521-521

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

在开放世界中实现逃逸分析522-532

摘要：逃逸分析（escape analysis）是一种可以有效减少Java程序中同步负载和内存堆分配压力的跨函数全局数据流分析算法．此前绝大多数逃逸分析的实现都基于一个所谓“封闭世界（closed world）”的前提：所有可能被执行的方法在做逃逸分析前都已经得知，并且，程序的实际运行不会改变它们之间的调用关系．但当真实的Java程序运行时，这样的假设并不成立．Java程序拥有的许多特性，例如动态类加载、调用本地函数以及反射程序调用等等，都将打破所谓“封闭世界”的约定．这样的真实运行环境被称为“开放世界”．在开放世界中，实现逃逸分析将面临许多重要的问题，例如，能否正确、全面地捕捉动态载入的类和方法，并分析它们与原有程序的关系；逃逸分析算法的复杂性是否能够得以控制，以保证即时编译器的重新分析时间不会过长，等等．提出一个新的逃选分析架构，它可以有效地处理上述开放世界所面临的问题．该分析架构将增量分析Java程序，动态捕获新载入和调用的类及方法，同时，在复杂性和精度之间进行权衡，正确、有效地降低程序的运行负载．该分析架构已经在Intel的开放式Java虚拟机系统ORP中实现，经过实际测试，可以有效地消除一些主要基准测试程序，如SPECjbb2000和SPEcjvm98的db中70％-94％的同步操作，大幅度地提高15％-31％的程序的运行速度．

一种基于组织实体能力的软件过程建模方法533-544

摘要：提出了一种基于组织实体能力的软件过程建模方法（organiztional entity capabilities based software process modeling method，简称OEC-SPM），针对软件过程的特殊性，将具有确定能力的组织实体定义为建模过程中的核心要素和基本单元——过程Agent（过程主体）．过程Agent根据其自身的目标、知识、经验和能力，在确定的项目目标和约束环境下，通过主动和自治的行为推理，生成具体的软件开发过程和生产过程，为软件项目开发提供正确的决策和有效的支持、该方法由于在建立软件过程时充分考虑过程执行者完成目标的能力，使建立的过程具有良好的可预见性，具备过程稳定执行的前提罔此从根本上解决了软件过程不稳定、难以控制等问题．

基于服务关系本体的服务生成545-556

摘要：针对服务组合过程中生成复杂业务所涉及的用户个性化、动态生成等问题，提出了一种基于服务关系本体的交互式服务生成方法．该方法从3个视点对服务的关系进行分析，构建了服务关系本体，进而在服务生成中，通过挖掘服务的动态语义，获取用户意图，结合服务关系本体以引导后继服务的匹配．该方法可以灵活地适应用户及业务提供者的需求变化，获得较优的服务匹配结果，同时还提高了服务组合的效率．最后，实现并给出了支持该方法的原型系统以及实验结果，表明了该方法的可行性与有效性．

一种基于判别式重排序的拼写校正方法557-564

摘要：提出一种基于判别模型的拼写校正方法坨针对已有拼写校正系统Aspell的输出进行重排序，使用判别模型Ranking SVM来改进其性能．将现今较为成熟的拼写校正技术（包括编辑距离、基于字母的n元语法、发音相似度和噪音信道模型）以特征的形式整合到该模型中来，显著地提高了基准系统Aspell的初始排序质量，同时性能也超过了一些商用系统（如Microsoft Word 2003）的拼写校正模块．此外，还提出了一种在搜索引擎查询日志链中自动抽取拼写校正训练对的方法、基于这种方法训练的模型获得了基于人工标注数据所得结果相近的性能，它们分别将基准系统的错误率降低了32．2％和32．6％.

软件学报杂志模式识别与人工智能

粒度粗糙理论研究565-583

摘要：从动机、理论和实现三方面系统地阐述了粒度粗糙理论体系．分析了构建粒度粗糙理论的3点动机：1）通过显式编码语义上下文的信息表示模型，强调粗糙性的表示语义；2）通过半结构化思想设计表示模型，扩展粗糙性方法适用的信息源；3）通过构建纯粹总分学关系上的粗糙性，描述丰富的信息结构应用语境，扩展粗糙性方法到总分学推动的领域，并展示结合总分学和计算机科学创建新型跨学科方法学的潜力．理论上定义了粒度表示演算，使其兼具一般信息源和粗糙性方法底层表示系统的双重功能，在此基础上构造内核、外壳及主体信息颗粒，分别对应粗糙性的下界近似、边界区域及上界近似概念、实现上，提出了通过“实体-属性-值”模型开源系统进行粒度粗糙理论快速原型化的思路，从而提供实验平台验证理论的正确性，同时，更自然地对临床数据进行粗糙性分析．作为总结，阐述了粒度粗糙理论的意义、未解决问题及未来的研究方向．

基于模型诊断的分步求解584-593

摘要：对诊断问题的分解进行研究，给出了候选诊断的分解与组合定理．在此基础上，提出了利用分步求解方法实现诊断分解的算法，并对算法的正确性、完备性和复杂性进行了证明．实验结果表明，分步求解方法明显提高了包含多个输出的系统的诊断效率．与利用变量假定例化值分解诊断问题的方法相比，该算法能提高了效率并且扩大了适用范围．

中国科学院软件研究所筹建国内首家软件博物馆593-593

摘要：近日，中国科学院软件研究所发起建设我国首家以计算机软件为主题的软件博物馆。 软件博物馆旨在记录软件发展历程，展示软件发展成就，传播软件科技知识，宣传软件科学文化。软件博物馆将以丰富而翔实的史料及珍贵的实物，

一般术语公理下的模糊描述逻辑FALCN推理594-604

摘要：分析了一般术语公理下推理的主要难点：在模糊解释中的隶属度不是离散值，而是区间[0，1]上的连续值．为解决该难点，提出了模糊描述逻辑FALCN下的模糊解释离散化方法，从而使解释中的隶属度都属于一个特殊的有限离散集合．基于该离散化方法，给出一般术语公理下FALCN推理问题的离散Tableau推理技术，包括离散Tableau的定义以及离散Tableau的构造算法，并证明了算法的正确性、完备性和复杂度．

一种支持自治计算的基于可废止逻辑的柔性Agent605-620

摘要：以自治计算的研究为背景，利用可废止逻辑理论的非单调知识表征和推理机制，提出一种能够动态接受规则变更、灵活处理实时发生的规则冲突，并进行高效的非单调推理的柔性Agent模型．这种Agent既是自主的，又是可控的，而且可以在开放、动态的环境中通过合同与其他Agent进行协同工作．

基于最大-最小相似度学习方法的文本提取621-629

摘要：应用最大-最小相似度（maximum-minimum similarity,简称MMS）学习方法，对基于高斯混合模型的文本区域提取方法中的有关参数进行优化．该学习方法通过最大化正样本相似度和最小，化反样本相似度获得最佳分类能力．根据这种判别学习思想，建立了相应的目标函数，并利用最速梯度下降法寻找目标函数最小值，以得到文本区域提取方法的最优参数集合．文本区域提取实验结果表明：在用期望最大化（expectation maximization，简称EM）算法获得参数的极大似然估计值后，使用最大．最小相似度学习方法，使文本提取综合性能明显提高，开放实验的召回率和准确率分别达到98．55％和93．56％．在实验中，最大．最小相似度学习方法的表现还优于常用的判别学习方法——最小分类错误（minimum classification error,简称MCE）学习方法．

面向文本分类的混淆类判别技术630-639

摘要：分析了文本分类过程中存在的混淆类现象，主要研究混淆类的判别技术，进而改善文本分类的性能．首先，提出了一种基于分类错误分布的混淆类识别技术，识别预定义类别中的混淆类集合．为了有效判别混淆类，提出了一种基于判别能力的特征选取技术，通过评价某一特征对类别之间的判别能力实现特征选取．最后，通过基于两阶段的分类器设计框架，将初始分类器和混淆类分类器进行集成，组合了两个阶段的分类结果作为最后输出．混淆类分类器的激活条件是：当测试文本被初始分类器标注为混淆类类别时，即采用混淆类分类器进行重新判别在比较实验中采用了Newsgroup和863中文评测语料，针对单标签、多类分类器．实验结果显示，该技术有效地改善了分类性能．

基于邻域粒化和粗糙逼近的数值属性约简640-649

摘要：对于空间中的任一子集，通过基本邻域信息粒子进行逼近，由此提出了邻域信息系统和邻域决策表模型．分析了该模型的性质，并且基于此模型构造了数值型属性的选择算法、利用UCI标准数据集与现有算法进行了比较分析，实验结果表明，该模型可以选择较少的特征而保持或改善分类能力．

基于MHC调控的免疫公式发现算法650-662

摘要：在分析了基于遗传原理的公式发现方法的优势与不足的基础上，根据免疫原理和MHC（major histocompatibility complex）在免疫系统中的调控作用，提出了一种应用于公式发现领域的算法IFDA（immune formula discovering algorithm）来解决公式进化中优良结构不易保护的问题．该算法将公式翻译成树状图，并按深度优先的编码方法形成抗体的恒定区和可变区代码，把公式片段编码成为MHC代码，借鉴MHC调控原理指导抗体进化，寻找出数据集合中蕴涵的规律，并用公式的形式表示．通过对多组基准数据的实验说明，此方法在公式复杂度和收敛速度方面比基因表达式算法有更好的性能．