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

《多重集全排列算法研究-開題報告.doc》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在學術論文-天天文庫。

1、廈門大學軟件學院本科畢業(yè)論文廈門大學軟件學院《畢業(yè)設計（論文）》開題報告學生姓名班級學號指導教師姓名陳金柱職稱教授所在單位廈門大學軟件學院畢業(yè)設計（論文）題目多重集全排列算法研究畢業(yè)設計（論文）的目標：一、總體目標字符串的全排列問題是一個經(jīng)典的數(shù)學排列問題，它有著悠久的歷史，也有著廣泛的實際應用，比如說在密碼學領域?qū)斎氲囊恍?shù)字或字符產(chǎn)生其對應的密碼；在生物醫(yī)學領域DNA的全排列等等。因此研究字符串的全排列問題有很大的實際意義。此次畢業(yè)設計的目標是搜集當今世界上關于字符串全排列的各種算法，進而與ProfessorRay的算法進

2、行對比，包括內(nèi)存，運行速度等各方面的性能分析對比，從而證明ProfessorRay的新算法是目前世界上最高效的算法。實現(xiàn)方法：一、基本概念全排列的定義對給定的字符串進行排列組合，得到N種準確無重復無遺漏的排列結(jié)果，叫做字符串的全排列。主要有下面兩種情況的全排列：n不重復字符串的全排列給定的字符串不包含重復字母，將其進行全排列，把其所有可能的全排列準確無重復無遺漏地列舉出來。例如：輸入ABC，其全排列的結(jié)果有6種,分別為：ABC,ACB,BAC,BCA,CAB,CBA。n重復字符串的全排列給定的字符串包含重復字母，將其進行全排列，

3、把其所有可能的全排列準確無重復無遺漏地列舉出來。例如：輸入AAB，其全排列的結(jié)果有3種：分別為：AAB,ABA,BAA。廈門大學軟件學院本科畢業(yè)論文二、具體實現(xiàn)這里主要根據(jù)不同階段的具體情況，分別闡述具體的實現(xiàn)方法：2.1閱讀文獻、收集資料選定合適的關鍵字進行搜索，關鍵字包括：stringpermutation,permutationgenerationmethod,combination,algorithm。對搜索出的文章進行分類篩選，找出當今世界上最新的最好的全排列算法，仔細研讀，為下一階段的模擬比較作好準備。搜索的著名數(shù)據(jù)

4、庫包括：uACM（美國計算機學會）DigitalLibraryACM（AssociationforComputingMachinery，美國計算機學會）數(shù)據(jù)庫收錄ACM全文期刊29種，會議錄近170種，超過69,000篇的全文文章、1954年至今出版的期刊、雜志目錄以及超過23,000篇的引用文獻、1985年至今出版的990多卷會議記錄的文章目錄以及超過48,000篇的引用文獻、與ACM文章關聯(lián)的大約150萬篇參考文獻（其中20萬篇參考文獻鏈接有全部書目資料，5萬篇可以鏈接全文）、ACM的“在線計算機文獻指南”（可以查詢和瀏覽來

5、自計算機領域重點出版社的巨大書目資料庫，包括圖書、期刊、會議錄和論文）。uSCI(《科學引文索引》ScienceCitationIndex）SCI是美國科學情報研究所（InstituteforScientificInformation，簡稱ISI，網(wǎng)址：http://www.isinet.com）出版的一部世界著名的期刊文獻檢索工具，其出版形式包括印刷版期刊和光盤版及聯(lián)機數(shù)據(jù)庫，現(xiàn)在還發(fā)行了互聯(lián)網(wǎng)上Web版數(shù)據(jù)庫（即WebofScience）。SCI收錄全世界出版的數(shù)、理、化、農(nóng)、林、醫(yī)、生命科學、天文、地理、環(huán)境、材料、工程技

6、術等自然科學各學科的核心期刊約3500種。ISI通過它嚴格的選刊標準和評估程序挑選刊源，而且每年略有增減，從而做到SCI收錄的文獻能全面覆蓋全世界最重要和最有影響力的研究成果。uIEEE/IEEIEL提供1988年以來，美國電氣電子工程師學會和英國電氣工程師學會出版的120多種期刊、600多種會議錄、近900種標準的全文信息。2.2模擬階段廈門大學軟件學院本科畢業(yè)論文代碼實現(xiàn)搜索到的具有代表性的全排列算法，通過對比比較，采用最合適的編程語言，遵循世界上通用的標準，并采用最通用的編譯器，在相同的軟硬件環(huán)境下進行模擬測試，得到相關一

7、系列精確的比較數(shù)據(jù)。編程語言：符合ANSIC標準的C語言編碼開發(fā)環(huán)境包括：n軟件環(huán)境：Windows下MicrosoftVisualC++6.0、MicrosoftVisualStudio.NET2003、MicrosoftVisualStudio2005、LinuxGCCn硬件環(huán)境：Intel?Pentium?4CPU2.93GHz,1GBMemory硬件環(huán)境2.3比較，得出結(jié)論階段結(jié)合理論和實際模擬數(shù)據(jù)兩方面，通過數(shù)學公式和圖表形式，直觀準確地給出各種算法的比較結(jié)果。根據(jù)比較階段的比較結(jié)果，得出最終結(jié)論，找到當今世界上最高效

8、的字符串全排列算法，肯定其在世界上的領先地位，分析其主要應用和實用性。時間進度安排：2007.1.29-2007.2.25理解課題任務，理解ProfessorRay最新全排列算法。2007.2.26-2007.3.31搜索閱讀文獻資料，完成開題報告2007.4.