基于搜索与集合覆盖的最优切片集研究及应用

摘要

程序切片可以将程序分解成更小的片段，程序员通过分析这些片段来理解程序。一个程序可以被分解成若干条切片，程序员一般不需要分析所有的切片，而是只需要分析某一个具有代表性的切片子集。
　　论文将最优切片集定义为，对整个程序覆盖最全面，并且切片之间重复覆盖代码最少的切片集合。在切片结果中搜索最优切片集，属于基于搜索的软件工程中的一种优化问题。
　　本文的研究目的是，将搜索技术、集合覆盖构造算法与程序切片技术结合起来，求解程序切片中的最优切片集，用最优切片集辅助程序理解。本文所做的工作包括：
　　（1）将切片技术与基于搜索的软件工程结合，搜索最优切片集；
　　（2）提出一种有限集合覆盖的构造算法，用于求解最优切片集；
　　（3）对比集合覆盖构造算法与搜索算法的执行结果，验证用前者求解最优切片集的可行性；
　　（4）验证用程序切片来度量程序耦合的可行性；
　　（5）使用最优切片集来度量程序耦合并进行实验研究。
　　本文的创新点如下：
　　提出一种用于构造有限集合覆盖的算法，用该算法求解最优切片集。将程序代码的所有语句点看成一个有限集合，每一条切片覆盖到的语句点所组成的集合，就是原有限集合的子集。于是，寻找最优切片集就涉及到集合覆盖的概念。本文利用集合覆盖构造算法在程序的所有切片中寻找最优切片集。
　　使用搜索算法、集合覆盖构造算法求得最优切片集，来度量程序的耦合度，与工具计算出的耦合结果进行比较。对耦合度明显不同的两个程序进行实验，分析实验结果，验证最优切片集度量程序耦合的可行性。

目录

声明

第一章 绪论

1.1研究背景及意义

1.2国内外研究现状

1.3研究内容及创新点

1.4本文组织结构

第二章 基本概念

2.1程序切片概述

2.2搜索算法概述

2.3搜索技术在切片集中的应用框架

2.4本章小节

第三章 有限集合覆盖的构造算法

3.1引言

3.2算法的思想

3.3算法及相关性质

3.4算法分析

3.5集合覆盖构造算法求最优切片集

第四章 集合覆盖构造算法与搜索算法的实验对比

4.1问题描述

4.2爬山算法核心思想

4.3与集合覆盖构造算法实验结果的对比

4.4本章小结

第五章 最优切片集在程序理解中的应用

5.1最优切片集辅助程序理解

5.2用切片集来度量程序耦合的可行性研究

5.3最优切片集分析程序耦合的实验研究

5.4本章小结

第六章 总结与展望

6.1本文工作总结

6.2未来工作展望

参考文献

附录1 有限集合划分的快速生成算法

附录2 攻读硕士学位期间撰写的论文

附录3 攻读硕士学位期间申请的专利

致谢