算法形式化方法在三類組合數(shù)學(xué)問題求解中的應(yīng)用研究.pdf

1、算法設(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)鍵問題。對(duì)于求解組合數(shù)學(xué)相關(guān)的問題，目前存在多種算法設(shè)計(jì)方法，形式化開發(fā)方法是其中之一。形式化方法的本質(zhì)是基于數(shù)學(xué)的方法來描述、開發(fā)和驗(yàn)證目標(biāo)軟件系統(tǒng)的一種技術(shù)，使用形式化方法開發(fā)算法程序能有效提高算法程序設(shè)計(jì)的規(guī)范化、自動(dòng)化程度以及算法的可

2、靠性和正確性。
　　基于遞推技術(shù)的算法形式化方法在部分形式化或者是完全形式化描述問題程序規(guī)約的基礎(chǔ)上，通過對(duì)問題的程序規(guī)約進(jìn)行數(shù)學(xué)變換，得到問題求解的遞推關(guān)系，在此基礎(chǔ)上得到最終的算法程序。由于求解問題的遞推關(guān)系建立在嚴(yán)格數(shù)學(xué)變換的基礎(chǔ)上，因而遞推關(guān)系的正確性得到了保證，從而也有效確保最終的算法程序的正確性；另外，使用該方法開發(fā)算法程序，均是以尋找問題求解序列的遞推關(guān)系為出發(fā)點(diǎn)，先得到較小的子問題的解，再在之前已獲得的較小子問題解

3、的基礎(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ā)上的有效性；接著，本文針對(duì)組合數(shù)學(xué)問題進(jìn)行分類研究，使用基于遞