模型驱动的高可靠图算法构件自动生成研究

The reliability and productivity of algorithms contribute greatly to the trustworthiness and application of software. Algorithm automation has been viewed as an important way to improve the reliability and productivity of algorithms. Graph algorithms are widely used in real life, production and scientific research. The flexibility of graph algorithm design tactics leads to the diversity of graph algorithms, thus the productivity and reliability of graph algorithms are difficult to guarantee. Most of the existing research work take the graph algorithms as a case study for a method or theory, but rarely study the laws of algorithm design, or build a knowledge database for problem solving tactics and users are asked to select tactics from database when solving a problem. The automatic level and effect of algorithm generation are not ideal. Inspiring by model-driven development method in software engineering, based on the PAR method, the project combines abstract data type mechanism, deductive inference, and generative programming techniques to describe algebraic properties of graph problems, formally develop several models with different levels of abstraction including domain-specific language of graph algorithms, abstract graph algorithm frame, graph algorithm components generation, drive the algorithm generation process via model transformation supported by the enhanced PAR platform, thus improve productivity and reliability of the graph algorithm components significantly. Meanwhile the flexibility and configurability of algorithm evolution also provide an effective means to discover and generate new algorithms. This project is expected to provide new ideas and methods for highly-reliable domain algorithm components.

算法的可靠性和开发效率对于软件可信性及应用发展具有重要意义。算法自动化是提高算法开发效率、保证算法可靠性的一种重要途径。图算法广泛应用于生活、生产和科学研究中，其算法设计策略的灵活性使图算法更具复杂性和多样性，算法的开发效率和可靠性难以得到保证。现有工作多将图算法作为某方法和理论的案例研究，甚少涉及算法开发规律的研究，或构建问题求解策略知识库并由用户手工选取，算法生成的自动化程度和效果不理想。本项目受模型驱动软件开发思想启发，以形式化方法PAR为基础，综合运用抽象数据类型、演绎推理、生成式程序设计等相关方法和机制，刻划图问题的抽象代数性质，形式化构建图领域专用语言、抽象图算法框架、算法构件生成等模型，并拓展PAR平台支持模型转换以驱动算法生成的过程，提高图算法构件的开发效率和可靠性，算法演化的灵活性与可配置性也为发现和生成新算法提供有效手段。本研究可望为领域高可靠算法构件的开发提供新思路。

图算法广泛应用于生活、生产和科学研究中，其算法设计策略的灵活性使图算法更具复杂性和多样性。本项目结合申请人所在学术团队已取得的形式化方法PAR及其平台，将模型驱动的软件开发思想引入到算法开发中来，研究图领域高可靠算法构件自动生成问题。主要研究工作包括：（1）算法生成方法学研究。通过剖析典型模型驱动开发工具的工作机理并应用其开发若干实际应用系统，进一步分析模型驱动软件开发方法“以模型为核心”的思想，进而探索和实践将该方法应用于逻辑关系相对复杂的算法构件自动生成。（2）图算法规约方法研究。分析图领域算法的特征，形成一种有利于高可靠图算法构件自动生成的算法规约方法，从而描述独立于实现细节的顶层抽象模型。（3）图算法构件生成模型研究。刻画和提炼图问题的共性特征，形式化构建泛型抽象图算法框架，得到与形式化算法规约对应的上层模型精化结果；设计图领域算子构件，使用PAR方法及其高可靠平台形式化开发算子构件，通过算子和抽象算法框架的组合来进一步引入实现细节，精化抽象模型；开展泛型约束机制研究，并实现新型抽象泛型机制，从而保证泛型程序的可靠性、安全性和高效性；建立约束条件下经抽象图算法框架和算子构件作用、由算法规约逐步精化至特定图算法构件的模型。（4）构建相关模型自动转换原型系统，保证精化的可靠性和安全性。. 本项目共发表学术论文9篇，其中EI检索3篇，ISTP检索2篇，中文核心4篇；出版学术专著2部，获软件著作权7项。培养硕士研究生20名（毕业硕士17名、在读3名），协助培养博士研究生2名（毕业博士1名、在读1名）。