一种非功能需求满足性问题模型的难解性及其近似算法

来源 :北京大学 | 被引量 : 0次 | 上传用户:meng010
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
非功能需求建模在软件工程领域越来越受到重视,存在着多种分析和建模方法,其中NFR Framework是一种发展迅速和应用广泛的框架。该框架的思想是用软目标来表示非功能需求,将顶层的非功能需求进行自上而下的分解,得到粒度更小的非功能需求和实现方法,并记录在SIG(软目标依赖关系图)中。评估过程是该框架中进行推理的主要方法,也是本文关注的重点。  目前已经有研究结果给出了针对NFR Framework的定性和定量推理规则,定性上也给出了后向推理方法,即如何选择实现方案,使得顶层的非功能需求得到最大的满足,本文主要关注在定量上的后向推理方法。  我们首先给出了一个定量模型,说明了该模型规则的定义是充分有理的,并将其用在NFR Framework上,可以看到该模型推理规则的定义是框架评估过程的一个很自然的推广。接着将定量的后向推理问题表述成一个最优化问题NFRFOPTF,将实现方案与优化问题中的赋值对应起来。之后通过证明其判定形式的NP难得到了优化问题是NP难的。  在给出NFRFOPT的困难性后,我们考虑了近似算法的设计。主要的设计思想是基于整数规划的舍入算法,因此首先通过一些技巧将NFRFOPT问题表述成了混合整数规划形式。接着给出了该优化问题的4个子问题,并将它们归结成3个子问题,之后对这些子问题分别设计了近似算法。  本文证明了后向推理问题的困难性,并给出了某些情况下的近似算法,可以在运用NFR Framework时对实现方案的选择进行分析和提供帮助。
其他文献
随着XML数据被广泛应用于互联网服务、信息集成等各个领域,针对XML数据的结构化查询,尤其是作为其核心操作的多分支查询,已经在研究领域成为一个热点话题。虽然在最近几年,为
计算机辅助设计(CAD、Computer Aided Design)在工业界已经得到广泛应用,极大促进了汽车、航空、航天、造船、建筑等行业的发展。离散曲面形变是CAD领域的研究热点之一,但是
任务群计算(Many-Task Computing,MTC)是广泛应用于科学计算领域的一种大规模松耦合任务并行计算模式,目的是在较短的时间内完成大量资源需求相同的可独立调度任务。这种模式下
经过多年的研究与应用实践,基于relation数据库引擎扩展XML管理功能已成为共识。目前,各大商用数据管理系统DB2,ORACLE,SQL SERVER以及开源数据管理系统(MonetDB,GALAXY,xlnd
工尺谱作为一种中国古代乐谱,常用于昆剧等中国传统音乐。工尺谱拥有完整的音调、音高标记,但是节奏标记不完备,一个节拍内音符的时值划分不明确。因此,工尺谱一般都以“口传心授
观点检索任务需要为每个用户查询返回一个文档列表,要求列表中的每篇文档表达了对当前查询主题的某种观点,并依据它们对查询主题的情感程度进行排序。目前,在微博数据(比如推
学位
随着人口信息系统应用范围的不断扩大,数据将急剧增长,简单的设施的扩容虽然能在一定时期满足人口信息系统的需求但不是长久之计。云计算的便利、经济、高可扩展性等优势吸引
Sybil账号是由恶意攻击者创建的,用来不公平的获取大量互联网资源与能力的虚假账号。长久以来,人们注意到sybil账号出现在各种互联网社区中,例如文件共享系统。但由于缺乏进
网页作为人类知识的一个重要载体,像照片一样记录了人类的历史,是人类的一份珍贵史料。同时,网页如同书籍、报纸一样,其生存周期是有限的。因此,就有许多有机构致力于有效的