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

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

Research on Automated Sorting Algorithms Generation Based on PAR

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.