多重集全排列算法研究-開題報告

1、廈門大學(xué)軟件學(xué)院畢業(yè)設(shè)計（論文）開題報告學(xué)生姓名班級學(xué)號指導(dǎo)教師 姓名陳金柱職稱教授所在單位廈門大學(xué)軟件學(xué)院畢業(yè)設(shè)計（論文）題目多重集全排列算法研究畢業(yè)設(shè)計（論文）的目標(biāo)：一、總體目標(biāo)字符串的全排列問題是一個經(jīng)典的數(shù)學(xué)排列問題，它有著悠久的歷史，也 有著廣泛的實(shí)際應(yīng)用，比如說在密碼學(xué)領(lǐng)域?qū)斎氲囊恍?shù)字或字符產(chǎn)生其對應(yīng) 的密碼；在生物醫(yī)學(xué)領(lǐng)域dna的全排列等等。因此研究字符串的全排列問題有很 大的實(shí)際意義。此次畢業(yè)設(shè)計的冃標(biāo)是搜集當(dāng)今世界上關(guān)于字符串全排列的各種 算法，進(jìn)而與professor ray的算法進(jìn)行對比，包括內(nèi)存，運(yùn)行速度等各方面的 性能分析對比，從而證明professor ray

2、的新算法是目前世界上最高效的算法。實(shí)現(xiàn)方法：一.基本概念全排列的定義對給定的字符串進(jìn)行排列組合，得到n種準(zhǔn)確無重復(fù)無遺漏的排列結(jié)果，叫 做字符串的全排列。主要有下而兩種情況的全排列：不重復(fù)字符串的全排列給定的字符串不包含重復(fù)字母，將其進(jìn)行全排列，把其所有可能的全排列準(zhǔn) 確無重復(fù)無遺漏地列舉出來。例如：輸入abc,其全排列的結(jié)果有6種，分別為： abc, acb, bac, bca, cab, cba。重復(fù)字符串的全排列給定的字符串包含重復(fù)字母，將其進(jìn)行全排列，把其所有可能的全排列準(zhǔn)確 無重復(fù)無遺漏地列舉出來。例如：輸入mb,其全排列的結(jié)果有3種：分別為： aab, aba, baao二、具體實(shí)

3、現(xiàn)這里主要根據(jù)不同階段的具體情況，分別闡述具體的實(shí)現(xiàn)方法：2.1閱讀文獻(xiàn)、收集資料選定合適的關(guān)鍵字進(jìn)行搜索，關(guān)鍵字包括：string permutation, permutation generation method, combination, algorithmo對搜索岀的文章進(jìn)行分類篩選，找岀 當(dāng)今世界上最新的最好的全排列算法，仔細(xì)研讀，為下一階段的模擬比較作好準(zhǔn) 備。搜索的著名數(shù)據(jù)庫包括： acm （美國計算機(jī)學(xué)會）digital libraryacm （association for computing machinery,美國計算機(jī)學(xué)會）數(shù)據(jù)庫收錄 acm全文期刊29種，會議錄近1

4、70種，超過69, 000篇的全文文章、1954年至 今出版的期刊、雜志目錄以及超過23, 000篇的引用文獻(xiàn)、1985年至今出版的 990多卷會議記錄的文章目錄以及超過4& 000篇的引用文獻(xiàn)、與acm文章關(guān) 聯(lián)的大約150萬篇參考文獻(xiàn)（其中20萬篇參考文獻(xiàn)鏈接有全部書目資料，5萬 篇可以鏈接全文）、acm的“在線計算機(jī)文獻(xiàn)指南”（可以查詢和瀏覽來自計算 機(jī)領(lǐng)域重點(diǎn)出版社的巨大書目資料庫，包括圖書、期刊、會議錄和論文）。 sci （科學(xué)引文索引science citation index）sci 是美國科學(xué)情報研究所（institute for scientific informat

5、ion,簡稱 isl 網(wǎng) ill： ）出版的一部世界著名的期刊文獻(xiàn)檢索工具，其岀版形 式包括印刷版期刊和光盤版及聯(lián)機(jī)數(shù)據(jù)庫，現(xiàn)在還發(fā)行了互聯(lián)網(wǎng)上web版數(shù)據(jù) 庫（即web of science）o sci收錄全世界出版的數(shù)、理、化、農(nóng)、林、醫(yī)、生命 科學(xué)、天文、地理、環(huán)境、材料、工程技術(shù)等自然科學(xué)各學(xué)科的核心期刊約3500 種。isi通過它嚴(yán)格的選刊標(biāo)準(zhǔn)和評估程序挑選刊源，而且每年略有增減，從而 做到sci收錄的文獻(xiàn)能全面覆蓋全世界最重要和最有影響力的研究成果。 ieee/iee iel提供1988年以來，美國電氣屯子工程師學(xué)會和英國電氣工程師學(xué)會岀版的 120多種期刊、600多種會議錄、近9

6、00種標(biāo)準(zhǔn)的全文信息。2. 2模擬階段代碼實(shí)現(xiàn)搜索到的具有代表性的全排列算法，通過對比比較，采用最合適的編程語言，遵循世界上通用的標(biāo)準(zhǔn)，并采用最通用的編譯器，在相同的軟硬件環(huán) 境下進(jìn)行模擬測試，得到相關(guān)一系列精確的比較數(shù)據(jù)。編程語言：符合ansic標(biāo)準(zhǔn)的c語言編碼開發(fā)環(huán)境包括： 軟件環(huán)境：windows 下 microsoft visual c+ 6.0> microsoft visual studio .net2003、microsoft visual studio 2005 linux gcc 硬件環(huán)境：intel® pentium® 4 cpu 2.93ghz,

7、 1gb memory 便件環(huán)境 23比較，得出結(jié)論階段結(jié)合理論和實(shí)際模擬數(shù)據(jù)兩方面，通過數(shù)學(xué)公式和圖表形式，直觀準(zhǔn)確地給 出各種算法的比較結(jié)果。根據(jù)比較階段的比較結(jié)果，得出最終結(jié)論，找到當(dāng)今世 界上最高效的字符串全排列算法，肯定其在世界上的領(lǐng)先地位，分析其主要應(yīng)用 和實(shí)用性。校外指導(dǎo)教師簽名: 校內(nèi)指導(dǎo)教師簽名:2007年 月 日2007年刀 日時間進(jìn)度安排：2007. 1.29-2007.2.25理解課題任務(wù)，理解professor ray最新全排列算法。2007. 2. 26-2007. 3.31搜索閱讀文獻(xiàn)資料，完成開題報告2007. 4. 01-2007. 4. 30模擬比較各種算法

8、的性能，并進(jìn)行分析2007. 5.01-2007. 5.25指導(dǎo)教師審核意見：總結(jié)前面幾個階段的各項(xiàng)成果，完成論文。畢業(yè)論文任務(wù)書（以下由學(xué)生填寫）題 目：多重集全排列算法研究目標(biāo)要求：字符串的全排列問題是一個經(jīng)典的數(shù)學(xué)排列問題，它有著悠久的歷史，也有 著廣泛的實(shí)際應(yīng)用，比如說在密碼學(xué)領(lǐng)域?qū)斎氲囊恍?shù)字或字符產(chǎn)生其對應(yīng)的 密碼；在生物醫(yī)學(xué)領(lǐng)域dna的全排列等等。因此研究字符串的全排列問題有很大 的實(shí)際意義。對于n個數(shù)來說，其全排列的個數(shù)有2/個，近二十年來岀現(xiàn)了許多關(guān)于全排 列的算法,它們的思想各不相同，因此執(zhí)行效率和所用的時間也各不相同。將這些 不同的算法集中起來加以比較，分析它們的思想并

9、將其轉(zhuǎn)換成可運(yùn)行的c代碼， 輸入不同的字符串并比較其運(yùn)行時間和所占用的內(nèi)存，從而確定每個算法的優(yōu) 劣。通過上網(wǎng)搜索有關(guān)全排列的經(jīng)典算法的英文論文（包括其發(fā)表日期、作者、 岀處），并將其用c語言加以實(shí)現(xiàn)，然后模擬其運(yùn)行過程，測試其所用的內(nèi)存以 及時間，然后和老師的關(guān)于全排列的算法加以比較，確定哪種算法最優(yōu)，以及輸 出全排列所用的時間最少，占用內(nèi)存最少。通過此次畢業(yè)設(shè)計，旨在提高我們閱讀英語科技論文的能力，研究各種算法 的能力，利用網(wǎng)絡(luò)搜索引擎解決實(shí)際問題的能力，以及利用vc6.0開發(fā)環(huán)境以及 c語言開發(fā)應(yīng)用程序的實(shí)際動手能力。支持條件：支持硬件：奔騰4, cpu主頻為2.93ghz,內(nèi)存為1gb的電腦；操作系統(tǒng)：windows xp開發(fā)環(huán)境：visual c+6.0指導(dǎo)教師（簽名）職稱學(xué)生（簽名）分階段進(jìn)度安排階段起訖時間計劃完成內(nèi)容12007年1月29日3月10日查找、閱讀相關(guān)的文獻(xiàn)資料22007年3月11 h3月20 h仔細(xì)挑選權(quán)威論文，實(shí)現(xiàn)經(jīng)典高效算法32007年3月21日4月30日算法的模擬與比較42007年5月1日5月10 口匯總模擬日志，整理、校對實(shí)驗(yàn)數(shù)據(jù)，繪 制比較圖表52007年5月11日6月1