两类组合数学问题循环不变式开发策略的研究与应用

发布时间：2020-12-04 03:11

　　随着计算机应用的日益普及,计算机软件的正确性和可靠性在各个领域中都受到高度重视,尤其在一些关键领域如市场经济、交通安全、航空航天等领域中更是至关重要。算法是软件的核心,它在软件开发中占有不容忽视的地位。形式化方法是保证算法正确性和可靠性的有效途径之一。而循环不变式在算法形式化方法中具有至关重要的作用,它是理解、开发和证明一个算法程序的关键。循环不变式的开发一直是形式化领域中最具挑战性、最富创造性的问题之一,寻找循环不变式开发策略一直存在较多难点。组合数学是计算机出现以后迅速发展起来的一个数学分支,它在理论方面的推进也促进了计算机科学的迅速发展,在计算机科学领域中许多问题的算法求解以组合数学为基础,因而组合数学问题的算法研究已成为计算机科学中重要的研究领域。在组合数学问题中,数列问题和排列组合问题是最经典和最具有代表性的两类问题,因此本文重点研究了数列问题和排列问题算法程序的循环不变式开发技术。本文首先进一步探究了循环不变式在算法形式化方法中的作用,并对现有的循环不变式开发技术和策略进行了分析和比较。其次,通过对组合数学问题中卡特兰数列和斐波那契数列问题进行深入研究,根据这两类数列问题的... 

【文章来源】：江西师范大学江西省

【文章页数】：63 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
第1章 引言
    1.1 研究背景和意义
    1.2 循环不变式研究现状
        1.2.1 循环不变式的定义
        1.2.2 循环不变式的开发技术
    1.3 主要研究工作
    1.4 预备知识
        1.4.1 常用量词及其性质
        1.4.2 问题的算法程序
        1.4.3 算法形式化推导方法概述
        1.4.4 组合数学加法原理和乘法原理
    1.5 本文的组织结构
第2章 循环不变式在算法形式化方法中的作用
    2.1 利用循环不变式理解算法程序
    2.2 利用循环不变式证明算法程序
    2.3 基于循环不变式形式化推导算法程序
    2.4 总结
第3章 两类数列问题循环不变式开发策略研究与应用
    3.1 两类数列问题的概述
    3.2 两类数列问题循环不变式开发策略
    3.3 卡特兰数列问题开发实例
        3.3.1 进栈出栈问题
        3.3.2 二叉树的形态数问题
    3.4 斐波那契数列问题开发实例
        3.4.1 铺砖问题
        3.4.2 走阶梯问题
    3.5 总结
第4章 排列问题循环不变式开发策略研究与应用
    4.1 排列问题概述
    4.2 排列问题循环不变式开发策略之一
    4.3 排列问题循环不变式开发策略一开发实例
        4.3.1 奇偶排列问题
        4.3.2 color排列问题
        4.3.3 数组逆转问题
    4.4 排列问题循环不变式开发策略之二
    4.5 排列问题循环不变式开发策略二开发实例
        4.5.1 二元选择排序问题
        4.5.2 中点优先数组遍历问题
        4.5.3 二叉树的中序遍历
    4.6 总结
第5章 总结与展望
参考文献
致谢
在读期间公开发表论文（著）及科研情况



本文编号：2896925