论文部分内容阅读
可信软件的不断发展,进一步推动了形式化方法的深入研究。形式化方法具有严格的数学语言和精确的逻辑语义,从而保证软件在开发过程中的正确性。形式化方法主要包括形式化推导和形式化验证两个部分。形式化推导是通过对问题程序规约进行精确变换,最终得到算法程序。形式化验证是在对软件进行规约的基础上,验证软件是否具有所期望的性质。形式化方法对保证软件正确性和可靠性具有十分重要的意义。本文从形式化推导和自动化验证两方面研究提高算法程序正确性的有效途径。在形式化推导方面,采用基于递推技术的算法形式化方法开发算法程序,通过程序规约变换技术对形式化程序规约进行等价变换,得到问题求解的递推关系和循环不变式,以此为基础得到算法程序。该方法不仅清晰地展示了算法的设计思路与过程,而且有效保证了算法程序的正确性。在自动化验证方面,选择Isabelle定理证明器为工具。Isabelle传统应用领域为数学定理证明,本文结合验证需要在对其内置类型库和规则库进行扩充的基础上,探索将它应用于算法程序自动化验证以及问题求解序列递推关系自动化验证的有效方法。论文从三个层面深入剖析了Isabelle定理证明器,从三个部分展示了Isabelle的理论证明过程。结合本文两方面验证工作的需要,对Isabelle的类型库和规则库进行了扩充,完成了新添加规则的内部形式转换和正确性验证,以及新类型的嵌入;然后以此扩充的Isabelle类型库和规则库为基础,采用后推证明方式,结合Dijkstra最弱前置谓词方法,给出了算法程序自动化验证的基本流程,并对若干问题的算法程序进行了自动化验证;同时,为了避免手工推导递推关系带来的人为性错误,基于以上扩充的Isabelle规则库,对本文实例中推导得到的递推关系实现了进一步自动化验证。研究表明,上述工作有效提高了算法程序正确性证明和问题求解序列递推关系正确性验证的效率。