基于PAR的排序算法自动生成研究  

Research on Automated Sorting Algorithms Generation Based on PAR

作　　者：石海鹤[1,2,3] 薛锦云[1,2] 

机构地区：[1]江西省高性能计算重点实验室(江西师范大学),江西南昌330022 [2]中国科学院软件研究所计算机科学国家重点实验室,北京100190 [3]中国科学院研究生院,北京100049

出　　处：《软件学报》2012年第9期2248-2260,共13页Journal of Software

基　　金：国家自然科学基金(61020106009);科技部国际科技合作项目(2008DFA11940);江西省自然科学基金(2010GQS0100);江西省教育厅科技项目(GJJ12199)

摘　　要：排序是计算机学科中的一类特殊问题,其算法设计策略的灵活性使得求解算法更具多样性.基于形式化方法 PAR(partition-and-recur),研究了排序算法的自动生成问题.刻画了排序问题的代数性质,形式化构建了排序算法领域的泛型类型构件和算法构件,建立了排序领域特定语言和算法生成形式化模型,以参数替换的方式自动生成了一组排序算法,包括快速排序、堆排序、Shell排序等典型的已知算法以及增量选择排序等若干未见于现有文献的算法,并在程序生成系统中予以了实现.通过上层框架研究和底层构件支持,显著提高了特定领域算法的开发效率和可靠性.Sorting is a kind of special problem in computer science. The flexibility of whose algorithm design tactics leads to the diversity of sorting algorithms. Based on the formal method PAR （partition-and-recur）, an automated sorting algorithm generation is studied. The algebraic property of sorting problem is described, generic type components and algorithm components are formally developed, and domain specific language and a formal algorithm generative model are designed. Through replacing the generic identifiers with a few concrete operations a series of known and unknown sorting algorithms, such as quick sort, heap sort, shell sort, and increment select sort, etc., are automatically generated, which is supported by the enhanced program generation system. Through the super framework and underlying components, the reliability and productivity of domain specific algorithm have dramatically improved.

关 键 词：排序算法 自动生成 领域特定语言 形式化模型 PAR.方法 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]