| 摘要: |
| 排序是计算机学科中的一类特殊问题,其算法设计策略的灵活性使得求解算法更具多样性.基于形式化方法PAR(partition-and-recur),研究了排序算法的自动生成问题.刻画了排序问题的代数性质,形式化构建了排序算法领域的泛型类型构件和算法构件,建立了排序领域特定语言和算法生成形式化模型,以参数替换的方式自动生成了一组排序算法,包括快速排序、堆排序、Shell 排序等典型的已知算法以及增量选择排序等若干未见于现有文献的算法,并在程序生成系统中予以了实现.通过上层框架研究和底层构件支持,显著提高了特定领域算法的开发效率和可靠性. |
| 关键词: 排序算法 自动生成 领域特定语言 形式化模型 PAR 方法 |
| DOI：10.3724/SP.J.1001.2012.04164 |
| 分类号: |
| 基金项目:国家自然科学基金(61020106009); 科技部国际科技合作项目(2008DFA11940); 江西省自然科学基金(2010GQS0100); 江西省教育厅科技项目(GJJ12199) |
|
| Research on Automated Sorting Algorithms Generation Based on PAR |
|
SHI Hai-He1,2,3, XUE Jin-Yun1,2
|
|
1.Provincial Key Laboratory of High Performance Computing Jiangxi Normal University, Nanchang 330022, China;2.National Key Laboratory of Computer Science, Institute of Software, The Chinese Academy of Sciences, Beijing 100190, China;3.Graduate University, The Chinese Academy of Sciences, Beijing 100049, China
|
| Abstract: |
| 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. |
| Key words: sorting algorithm automated generation domain specific language formal model PAR method |
