【摘要】：算法設(shè)計(jì)是計(jì)算機(jī)科學(xué)研究的重要領(lǐng)域之一。目前計(jì)算機(jī)科學(xué)處理的大部分?jǐn)?shù)據(jù)都是離散的數(shù)據(jù),而組合數(shù)學(xué)是研究離散數(shù)據(jù)的科學(xué),因此研究以組合數(shù)學(xué)為基礎(chǔ)的算法的可靠性、正確性和生產(chǎn)效率就成為算法設(shè)計(jì)領(lǐng)域中的關(guān)鍵問題。對于求解組合數(shù)學(xué)相關(guān)的問題,目前存在多種算法設(shè)計(jì)方法,形式化開發(fā)方法是其中之一。形式化方法的本質(zhì)是基于數(shù)學(xué)的方法來描述、開發(fā)和驗(yàn)證目標(biāo)軟件系統(tǒng)的一種技術(shù),使用形式化方法開發(fā)算法程序能有效提高算法程序設(shè)計(jì)的規(guī)范化、自動化程度以及算法的可靠性和正確性。基于遞推技術(shù)的算法形式化方法在部分形式化或者是完全形式化描述問題程序規(guī)約的基礎(chǔ)上,通過對問題的程序規(guī)約進(jìn)行數(shù)學(xué)變換,得到問題求解的遞推關(guān)系,在此基礎(chǔ)上得到最終的算法程序。由于求解問題的遞推關(guān)系建立在嚴(yán)格數(shù)學(xué)變換的基礎(chǔ)上,因而遞推關(guān)系的正確性得到了保證,從而也有效確保最終的算法程序的正確性;另外,使用該方法開發(fā)算法程序,均是以尋找問題求解序列的遞推關(guān)系為出發(fā)點(diǎn),先得到較小的子問題的解,再在之前已獲得的較小子問題解的基礎(chǔ)上直接或間接得到較大問題的解,這樣可以避免很多不必要的重復(fù)計(jì)算,從而有效提高算法程序的效率,并為算法程序的開發(fā)提供一條較為統(tǒng)一的途徑。本文重點(diǎn)研究了基于遞推關(guān)系的算法形式化方法在三類典型組合數(shù)學(xué)問題求解中的應(yīng)用。本文分析了當(dāng)前形式化開發(fā)方法的需求以及發(fā)展?fàn)顩r;介紹了基于遞推技術(shù)的形式化開發(fā)方法的開發(fā)語言、開發(fā)步驟以及關(guān)鍵技術(shù)等,同時(shí)研究了它在組合數(shù)學(xué)問題開發(fā)上的有效性;接著,本文針對組合數(shù)學(xué)問題進(jìn)行分類研究,使用基于遞推技術(shù)的形式化方法開發(fā)了三類有代表性的組合數(shù)學(xué)問題:整除問題、排列組合問題以及NP完全問題中的0-1背包變形問題,同時(shí)在分析每一類問題形式化開發(fā)過程共性的基礎(chǔ)上提煉得到了求解該類問題的統(tǒng)一策略,并將其推廣到相似問題的求解;最后對基于遞推關(guān)系的形式化開發(fā)方法在組合數(shù)學(xué)上的應(yīng)用進(jìn)行了總結(jié)。研究表明,基于遞推技術(shù)的算法形式化開發(fā)方法有效保證了算法程序的正確性,提高了算法程序的執(zhí)行效率。
[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.
【學(xué)位授予單位】：江西師范大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2017
【分類號】：O157

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 陳鋼;于林宇;裘宗燕;王穎;;基于邏輯的形式化驗(yàn)證方法:進(jìn)展及應(yīng)用[J];北京大學(xué)學(xué)報(bào)(自然科學(xué)版);2016年02期

2 詹乃軍;王戟;李宣東;;軟件形式化方法與應(yīng)用專題前言[J];軟件學(xué)報(bào);2016年03期

3 于水青;;排列組合問題的求解方法與技巧[J];山西師范大學(xué)學(xué)報(bào)(自然科學(xué)版);2014年S2期

4 李愷;;組合數(shù)學(xué)在軟件工程領(lǐng)域的應(yīng)用[J];軟件導(dǎo)刊;2013年02期

5 石海鶴;薛錦云;;基于PAR的排序算法自動生成研究[J];軟件學(xué)報(bào);2012年09期

6 張園;楊慶紅;胡昊;;基于遞推技術(shù)的算法設(shè)計(jì)方法的應(yīng)用研究[J];計(jì)算機(jī)與現(xiàn)代化;2012年06期

7 程躍;;多背包問題的一種求解方法[J];產(chǎn)業(yè)與科技論壇;2011年20期

8 胡勤;;組合數(shù)學(xué)淺析[J];電腦知識與技術(shù);2010年11期

9 田烽楠;王于;;求解0-1背包問題算法綜述[J];軟件導(dǎo)刊;2009年01期

10 孫凌宇;冷明;彭宣戈;;一種用戶身份認(rèn)證系統(tǒng)的形式化描述[J];計(jì)算機(jī)應(yīng)用與軟件;2009年01期

相關(guān)碩士學(xué)位論文 前8條

1 張園;遞推技術(shù)在算法設(shè)計(jì)中的應(yīng)用研究[D];江西師范大學(xué);2012年

2 單學(xué)廣;基于遞推技術(shù)的算法程序設(shè)計(jì)方法的研究與應(yīng)用[D];江西師范大學(xué);2011年

3 李英龍;PAR方法中關(guān)系數(shù)據(jù)庫機(jī)制的描述與實(shí)現(xiàn)[D];江西師范大學(xué);2006年

4 夏蕓;Apla-VB.NET自動程序轉(zhuǎn)換系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D];江西師范大學(xué);2006年

5 孫凌宇;PAR方法在組合數(shù)學(xué)問題中的應(yīng)用研究[D];江西師范大學(xué);2005年

6 冉小曉;Radl->Apla自動程序轉(zhuǎn)換系統(tǒng)研究與實(shí)現(xiàn)[D];江西師范大學(xué);2005年

7 左正康;Apla→C#自動程序轉(zhuǎn)換系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[D];江西師范大學(xué);2004年

8 王森;基于PAR方法開發(fā)算法程序的研究[D];江西師范大學(xué);2004年

，

本文編號：2242693