算法形式化方法在三类组合数学问题求解中的应用研究

发布时间：2018-09-14 12:19

【摘要】：算法设计是计算机科学研究的重要领域之一。目前计算机科学处理的大部分数据都是离散的数据,而组合数学是研究离散数据的科学,因此研究以组合数学为基础的算法的可靠性、正确性和生产效率就成为算法设计领域中的关键问题。对于求解组合数学相关的问题,目前存在多种算法设计方法,形式化开发方法是其中之一。形式化方法的本质是基于数学的方法来描述、开发和验证目标软件系统的一种技术,使用形式化方法开发算法程序能有效提高算法程序设计的规范化、自动化程度以及算法的可靠性和正确性。基于递推技术的算法形式化方法在部分形式化或者是完全形式化描述问题程序规约的基础上,通过对问题的程序规约进行数学变换,得到问题求解的递推关系,在此基础上得到最终的算法程序。由于求解问题的递推关系建立在严格数学变换的基础上,因而递推关系的正确性得到了保证,从而也有效确保最终的算法程序的正确性;另外,使用该方法开发算法程序,均是以寻找问题求解序列的递推关系为出发点,先得到较小的子问题的解,再在之前已获得的较小子问题解的基础上直接或间接得到较大问题的解,这样可以避免很多不必要的重复计算,从而有效提高算法程序的效率,并为算法程序的开发提供一条较为统一的途径。本文重点研究了基于递推关系的算法形式化方法在三类典型组合数学问题求解中的应用。本文分析了当前形式化开发方法的需求以及发展状况;介绍了基于递推技术的形式化开发方法的开发语言、开发步骤以及关键技术等,同时研究了它在组合数学问题开发上的有效性;接着,本文针对组合数学问题进行分类研究,使用基于递推技术的形式化方法开发了三类有代表性的组合数学问题:整除问题、排列组合问题以及NP完全问题中的0-1背包变形问题,同时在分析每一类问题形式化开发过程共性的基础上提炼得到了求解该类问题的统一策略,并将其推广到相似问题的求解;最后对基于递推关系的形式化开发方法在组合数学上的应用进行了总结。研究表明,基于递推技术的算法形式化开发方法有效保证了算法程序的正确性,提高了算法程序的执行效率。
[Abstract]:Algorithm design is one of the most important fields in computer science. At present, most of the data processed by computer science are discrete data, and combinatorial mathematics is the science of studying discrete data, so the reliability of algorithms based on combinatorial mathematics is studied. Correctness and production efficiency are the key problems in the field of algorithm design. At present, there are many algorithms for solving combinatorial mathematics problems, among which formal development method is one of them. The essence of formal method is a technique of describing, developing and verifying the target software system based on mathematical method. Using formal method to develop algorithm program can effectively improve the standardization of algorithm program design. Degree of automation and reliability and correctness of the algorithm. On the basis of partial or complete formal description of the program specification of the problem, the recursive relation of problem solving is obtained by mathematical transformation of the program specification of the problem. On this basis, the final algorithm program is obtained. Because the recursive relation of solving the problem is based on the strict mathematical transformation, the correctness of the recursive relation is guaranteed, and the correctness of the final algorithm program is effectively ensured. In addition, the algorithm program is developed by using this method. In order to find the recursion relation of the solving sequence of the problem, the solution of the smaller sub-problem is obtained first, and then the solution of the larger problem is obtained directly or indirectly on the basis of the previously obtained solution of the smaller problem. In this way, a lot of unnecessary double computation can be avoided, and the efficiency of the algorithm program can be improved effectively, and a more uniform way for the development of the algorithm program can be provided. This paper focuses on the application of recursive relation based algorithm formalization method in solving three typical combinatorial mathematics problems. This paper analyzes the requirements and development status of the current formal development method, introduces the development language, steps and key technologies of the formal development method based on recursive technology. At the same time, the validity of combinatorial mathematics problem development is studied. Then, this paper classifies the combinatorial mathematics problem and develops three representative combinatorial mathematics problems by using the formal method based on recursive technique: divisional problem. The permutation problem and the 0-1 knapsack deformation problem in the NP complete problem are analyzed. On the basis of analyzing the generality of the formalized development process of each kind of problem, the unified strategy for solving this kind of problem is obtained, and it is extended to the solution of the similar problem. Finally, the application of formal development method based on recursive relation in combinatorial mathematics is summarized. The research shows that the algorithm formalization development method based on recursive technology can effectively guarantee the correctness of the algorithm program and improve the efficiency of the algorithm program execution.
【学位授予单位】：江西师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157

【参考文献】