基于CPN的程序测试用例生成方法的研究

采用成熟的建模仿真工具CPN tools不仅仅对程序设计语言的三种基本结构进行了建模,而且对并行程序中的并行结构也进行了建模和仿真。在不针对某些具体语言比如C语言的情况下,提出了生成测试用例的新方法,该方法对具备三种基本结构特性的所有程序都具有普遍适用性。对具有并行结构的程序通过化简寻找测试路径。最后在生成测试用例之后,又利用CPN tools对所获得的测试用例进行选择和评价,最终确定合适的测试用例,不仅能够保证获取的测试路径是完整的而且是最优的。

有向图的所有强连通分量

现在有一些文献对有向图的强连通分量做了一些讨论,一般采用了递归的方法。本文利用邻接 矩阵存放有向图,用非递归的方法来求有向图的所有强迫通分量。

基于强连通分量的^13C MFA计算模型稳定性判断

基于碳同位素标记实验的代谢通量分析，是代谢工程中一种强大的定量分析工具。^13C MFA在进行定量分析时，需要给定代谢网络及其对应的碳原子转移网络，同时为了保证计算的正确性和可靠性，要求所给定的碳原子转移网络中不能含有陷阱（trap）。本文基于有向图中强连通分量的概念，给出了trap的一种形式化定义，并利用一种基于深度优先搜索的图论算法，实现了对trap的自动检测。实验结果表明，该算法能够得到正确可靠的结果。

求强分图图的算法

由于如文献［１］和［２］等的实际需要，对基于ＤＦＳ技术的求强分图算法进行扩充、改进，使之更完整。

A Practical Parallel Algorithm for Propositional Knowledge Base Revision

Different methods for revising propositional knowledge base have been proposed recently by several researchers, but all methods are intractable in the general case. For practical application, this paper presents a revision method in special case, and gives a corresponding polynomial algorithm as well as its parallel version on CREW PRAM.

基于图和并行计算的云计算攻击图

不同于传统的计算模型,云计算本身特有的虚拟化特性和动态扩展性,给云计算的安全研究带来挑战。为此提出基于图的技术框架,采用软件定义网络(SDN)来获取网络配置和主机访问控制列表等信息,根据这些信息构建网络系统的可达性图;然后,对可达性图进行分解以获取强连通分量(SCC),在此基础上执行并行的安全性分析;最后,根据分析结果构建攻击图并通过搭建一个真实的网络系统进行验证。实验结果表明:与传统的分析方法相比,攻击图生成时间有明显的改进。

基于顶点粒的强连通分量挖掘算法

强连通分量问题的实质是将有向图分解为一组互不相交的极大强连通子图.每个子图中的任一顶点到其它顶点都是可达的,既是其它顶点的祖先,又是后代.利用宽度优先搜索(BFS)可得到目标有向图中任一顶点的祖先顶点集与后代顶点集,两个集合的交集即为包含当前顶点的强连通分量.首先,基于BFS的强连通分量挖掘方法(BSCC)的效率取决于BFS被调用次数,因此,引入了3种启发式信息来减少BFS调用次数.对强连通分量进行深入分析,发现了顶点间的两种相关性.满足任一相关性的两个顶点不会分属两个有价值强连通分量.根据这两种相关性提出了一种顶点粒化策略,可构建每个顶点所对应的顶点粒,继而提出了基于顶点粒的强连通分量挖掘算法(GSCC),优化了BSCC算法中顶点调用BFS的方式,提高了强连通分量挖掘效率.实验结果表明,相比BSCC算法和线性复杂度的Tarjan算法,GSCC算法具有更好的性能.