多重集全排列算法研究-开题报告

1、厦门大学软件学院毕业设计（论文）开题报告学生姓名班级学号指导教师 姓名陈金柱职称教授所在单位厦门大学软件学院毕业设计（论文）题目多重集全排列算法研究毕业设计（论文）的目标：一、总体目标字符串的全排列问题是一个经典的数学排列问题，它有着悠久的历史，也 有着广泛的实际应用，比如说在密码学领域对输入的一些数字或字符产生其对应 的密码；在生物医学领域dna的全排列等等。因此研究字符串的全排列问题有很 大的实际意义。此次毕业设计的冃标是搜集当今世界上关于字符串全排列的各种 算法，进而与professor ray的算法进行对比，包括内存，运行速度等各方面的 性能分析对比，从而证明professor ray

2、的新算法是目前世界上最高效的算法。实现方法：一.基本概念全排列的定义对给定的字符串进行排列组合，得到n种准确无重复无遗漏的排列结果，叫 做字符串的全排列。主要有下而两种情况的全排列：不重复字符串的全排列给定的字符串不包含重复字母，将其进行全排列，把其所有可能的全排列准 确无重复无遗漏地列举出来。例如：输入abc,其全排列的结果有6种，分别为： abc, acb, bac, bca, cab, cba。重复字符串的全排列给定的字符串包含重复字母，将其进行全排列，把其所有可能的全排列准确 无重复无遗漏地列举出来。例如：输入mb,其全排列的结果有3种：分别为： aab, aba, baao二、具体实

3、现这里主要根据不同阶段的具体情况，分别阐述具体的实现方法：2.1阅读文献、收集资料选定合适的关键字进行搜索，关键字包括：string permutation, permutation generation method, combination, algorithmo对搜索岀的文章进行分类筛选，找岀 当今世界上最新的最好的全排列算法，仔细研读，为下一阶段的模拟比较作好准 备。搜索的著名数据库包括： acm （美国计算机学会）digital libraryacm （association for computing machinery,美国计算机学会）数据库收录 acm全文期刊29种，会议录近1

4、70种，超过69, 000篇的全文文章、1954年至 今出版的期刊、杂志目录以及超过23, 000篇的引用文献、1985年至今出版的 990多卷会议记录的文章目录以及超过4& 000篇的引用文献、与acm文章关 联的大约150万篇参考文献（其中20万篇参考文献链接有全部书目资料，5万 篇可以链接全文）、acm的“在线计算机文献指南”（可以查询和浏览来自计算 机领域重点出版社的巨大书目资料库，包括图书、期刊、会议录和论文）。 sci （科学引文索引science citation index）sci 是美国科学情报研究所（institute for scientific informat

5、ion,简称 isl 网 ill： ）出版的一部世界著名的期刊文献检索工具，其岀版形 式包括印刷版期刊和光盘版及联机数据库，现在还发行了互联网上web版数据 库（即web of science）o sci收录全世界出版的数、理、化、农、林、医、生命 科学、天文、地理、环境、材料、工程技术等自然科学各学科的核心期刊约3500 种。isi通过它严格的选刊标准和评估程序挑选刊源，而且每年略有增减，从而 做到sci收录的文献能全面覆盖全世界最重要和最有影响力的研究成果。 ieee/iee iel提供1988年以來，美国电气屯子工程师学会和英国电气工程师学会岀版的 120多种期刊、600多种会议录、近9

6、00种标准的全文信息。2. 2模拟阶段代码实现搜索到的具有代表性的全排列算法，通过对比比较，采用最合适的编程语言，遵循世界上通用的标准，并采用最通用的编译器，在相同的软硬件环 境下进行模拟测试，得到相关一系列精确的比较数据。编程语言：符合ansic标准的c语言编码开发环境包括： 软件环境：windows 下 microsoft visual c+ 6.0> microsoft visual studio .net2003、microsoft visual studio 2005 linux gcc 硬件环境：intel® pentium® 4 cpu 2.93ghz,

7、 1gb memory 便件环境 23比较，得出结论阶段结合理论和实际模拟数据两方面，通过数学公式和图表形式，直观准确地给 出各种算法的比较结果。根据比较阶段的比较结果，得出最终结论，找到当今世 界上最高效的字符串全排列算法，肯定其在世界上的领先地位，分析其主要应用 和实用性。校外指导教师签名: 校内指导教师签名:2007年 月 日2007年刀 日时间进度安排：2007. 1.29-2007.2.25理解课题任务，理解professor ray最新全排列算法。2007. 2. 26-2007. 3.31搜索阅读文献资料，完成开题报告2007. 4. 01-2007. 4. 30模拟比较各种算法

8、的性能，并进行分析2007. 5.01-2007. 5.25指导教师审核意见：总结前面几个阶段的各项成果，完成论文。毕业论文任务书（以下由学生填写）题 目：多重集全排列算法研究目标要求：字符串的全排列问题是一个经典的数学排列问题，它有着悠久的历史，也有 着广泛的实际应用，比如说在密码学领域对输入的一些数字或字符产生其对应的 密码；在生物医学领域dna的全排列等等。因此研究字符串的全排列问题有很大 的实际意义。对于n个数来说，其全排列的个数有2/个，近二十年来岀现了许多关于全排 列的算法,它们的思想各不相同，因此执行效率和所用的时间也各不相同。将这些 不同的算法集中起来加以比较，分析它们的思想并

9、将其转换成可运行的c代码， 输入不同的字符串并比较其运行时间和所占用的内存，从而确定每个算法的优 劣。通过上网搜索有关全排列的经典算法的英文论文（包括其发表日期、作者、 岀处），并将其用c语言加以实现，然后模拟其运行过程，测试其所用的内存以 及时间，然后和老师的关于全排列的算法加以比较，确定哪种算法最优，以及输 出全排列所用的时间最少，占用内存最少。通过此次毕业设计，旨在提高我们阅读英语科技论文的能力，研究各种算法 的能力，利用网络搜索引擎解决实际问题的能力，以及利用vc6.0开发环境以及 c语言开发应用程序的实际动手能力。支持条件：支持硬件：奔腾4, cpu主频为2.93ghz,内存为1gb的电脑；操作系统：windows xp开发环境：visual c+6.0指导教师（签名）职称学生（签名）分阶段进度安排阶段起讫时间计划完成内容12007年1月29日3月10日查找、阅读相关的文献资料22007年3月11 h3月20 h仔细挑选权威论文，实现经典高效算法32007年3月21日4月30日算法的模拟与比较42007年5月1日5月10 口汇总模拟日志，整理、校对实验数据，绘 制比较图表52007年5月11日6月1