三类组合数学问题算法形式化推导策略的研究

论文摘要

组合数学是研究离散对象的科学,而计算机处理的对象主要是离散数据,因此,关于组合数学问题算法的研究一直以来都是计算机科学的重要研究领域之一。然而在许多相关文献中,对于组合数学问题的求解,其相关算法大多都是利用传统算法设计方法经过简单分析得到,并未给出算法程序的详细设计过程,导致读者无法理解算法本质,更重要的是算法程序的正确性无法得到保证。本文通过对若干算法设计方法进行分析对比,选择使用基于递推技术的算法形式化方法对组合数学中若干问题的算法进行深入研究和形式化开发。基于递推技术的算法形式化方法首先要求对所求解问题的功能规约进行形式化描述,再利用严格的程序规约变换技术对规约进行一系列等价变换,从而获取问题的递推关系式,然后以所获得的递推关系式为基础利用循环结构给出问题最终的算法程序。本文首先对组合数学问题中的若干问题进行了深入的研究,通过对部分组合数学问题的特征和共性进行分析和比较,将这些组合数学问题划分成了三大类问题:连续子序列求解问题、“相同元素”的划分问题和“不同元素”的分类问题;然后,针对这三大类组合数学问题,本文分别选择了若干实例使用基于递推技术的算法形式化方法详细展示了其算法程序的形式化推导过程;最后,根据这三大类问题中每类问题的共性特征,定义不同含义的一元向量表达每类问题的程序规约,同时分别提炼出了这三大类组合数学问题算法形式化推导的统一求解策略,并将这些统一求解策略进一步应用于具体组合数学问题的算法开发。本文研究工作的意义在于:1)使用基于递推技术的算法形式化方法开发组合数学问题的算法程序,从问题的形式化程序规约出发,使用规约变换规则对程序规约进行一系列等价变换,获得问题求解序列的递推式,以此为基础得到问题求解的算法程序,清晰地展示了从问题的需求到算法程序的详细推导过程,有效解决了这些组合数学问题的算法“从何而来”的问题,有利于帮助读者理解这些算法的本质;2)推导过程中,问题最终的算法程序是建立在递推关系式的基础上的。由于问题的递推关系式都是经过严格数学变换获取的,因而我们通过保证问题求解递推关系式的正确性保证了最终算法程序的正确性;3)利用递推关系式求解问题的算法程序,先获取子问题的解,然后再通过子问题解进一步获取更大问题的解,最终获取原问题的解,这种方式可以避免许多重复计算,有效提高算法程序的执行效率;4)提出了三类组合数学问题的程序规约表达方法和算法推导统一策略,为开发可靠的组合数学问题的算法程序提供了有效的参考途径。

论文目录

摘要

Abstract

一、引言

1.1 研究背景

1.2 研究现状

1.2.1 组合数学算法的研究现状

1.2.2 形式化方法的研究现状

1.3 研究意义及主要研究内容

1.4 本文的组织结构

二、基于递推技术的算法形式化方法

2.1 基于递推技术的算法形式化方法的概述

2.2 预备知识

2.3 问题的算法结构及算法程序

2.4 组合数学的加法原理和乘法原理

三、连续子序列问题的算法形式化推导

3.1 连续子序列问题的概述

3.2 连续子序列问题的推导实例

3.2.1 连续子序列最大乘积问题

3.2.2 连续递增子序列的最大和问题

3.3 连续子序列问题的统一求解策略

3.4 统一求解策略在最小m段和问题的应用

四、“相同元素”的划分问题算法形式化推导

4.1 “相同元素”的划分问题的概述

4.2 “相同元素”的划分问题的推导实例

4.2.1 m份的整数划分问题

4.2.2 不大于m的整数划分问题

4.2.3 互不相同的整数划分问题

4.3 “相同元素”的划分问题的统一求解策略

4.4 统一求解策略的应用

五、“不同元素”的分类问题

5.1 “不同元素”的分类问题的概述

5.2 “不同元素”的分类问题的推导实例

5.2.1 第二类司特林数问题

5.2.2 第二类司特林数变形问题

5.3 “不同元素”的分类问题的统一求解策略

5.4 统一求解策略在第一类司特林数问题的应用

六、总结与展望

参考文献

致谢

在读期间公开发表论文（著）及科研情况

文章来源

类型: 硕士论文

作者: 熊小超

导师: 杨庆红

关键词: 形式化方法,组合数学问题,递推技术,程序规约

来源: 江西师范大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 江西师范大学

分类号: O157

DOI: 10.27178/d.cnki.gjxsu.2019.000258

总页数: 66

文件大小: 2091K

下载量: 29

三类组合数学问题算法形式化推导策略的研究

论文摘要

论文目录

文章来源

相关论文文献

猜你喜欢