二叉树排序非递归算法推导及形式化证明

作者：左正康; 方越; 黄箐; 廖云燕; 王渊; 王昌晶^*

来源：江西师范大学学报(自然科学版), 2020, 44(06): 625-632.

DOI：10.16357/j.cnki.issn1000-5862.2020.06.14

• 二叉树类非递归算法
• 循环不变式
• PAR平台
• Dijkstra-Gries标准程序证明法
• 非线性数据结构

非线性数据结构递归问题非递归算法的循环不变式的开发一直是形式化开发的难点.研究二叉树类非递归算法的推导及形式化证明方法,对二叉树排序算法进行推导,得出非递归Apla(Abstract Programming Language)算法及其精确而简单的循环不变式,然后用Dijkstra-Gries标准程序证明法证明算法的正确性,最后使用PAR平台C++程序自动生成系统自动生成C++代码.实例的实验结果简化了算法程序的推导和证明过程,对递归问题非递归算法的循环不变式的探测具有一定的借鉴意义,而且对非线性数据结构算法程序的推导及形式化证明具有指导意义.

• 单位
  江西师范大学