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

作     者：石海鹤 薛锦云 SHI Hai-He;XUE Jin-Yun

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

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

出 版 物：《软件学报》 (Journal of Software)

年 卷 期：2012年第23卷第9期

页      码：2248-2260页

摘      要：排序是计算机学科中的一类特殊问题,其算法设计策略的灵活性使得求解算法更具多样性.基于形式化方法 PAR(partition-and-recur),研究了排序算法的自动生成问题.刻画了排序问题的代数性质,形式化构建了排序算法领域的泛型类型构件和算法构件,建立了排序领域特定语言和算法生成形式化模型,以参数替换的方式自动生成了一组排序算法,包括快速排序、堆排序、Shell排序等典型的已知算法以及增量选择排序等若干未见于现有文献的算法,并在程序生成系统中予以了实现.通过上层框架研究和底层构件支持,显著提高了特定领域算法的开发效率和可靠性.

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

学科分类：08[工学] 0835[0835] 0811[工学-水利类] 0812[工学-测绘类] 081202[081202] 

核心收录：

D　O　I：10.3724/SP.J.1001.2012.04164

馆 藏 号：203233913...