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

厦门大学软件学院本科毕业论文厦门大学软件学院毕业设计（论文）开题报告学生姓名 班级 学号 指导教师姓 名陈金柱职称教授所在单位厦门大学软件学院毕业设计（论文）题 目多重集全排列算法研究毕业设计（论文）的目标：一、总体目标字符串的全排列问题是一个经典的数学排列问题，它有着悠久的历史，也有着广泛的实际应用，比如说在密码学领域对输入的一些数字或字符产生其对应的密码；在生物医学领域DNA的全排列等等。因此研究字符串的全排列问题有很大的实际意义。此次毕业设计的目标是搜集当今世界上关于字符串全排列的各种算法，进而与Professor Ray的算法进行对比，包括内存，运行速度等各方面的性能分析对比，从而证明Professor Ray的新算法是目前世界上最高效的算法。实现方法：一、基本概念全排列的定义对给定的字符串进行排列组合，得到N种准确无重复无遗漏的排列结果，叫做字符串的全排列。主要有下面两种情况的全排列：n 不重复字符串的全排列给定的字符串不包含重复字母，将其进行全排列，把其所有可能的全排列准确无重复无遗漏地列举出来。例如：输入ABC，其全排列的结果有6种,分别为：ABC,ACB,BAC,BCA,CAB,CBA。n 重复字符串的全排列给定的字符串包含重复字母，将其进行全排列，把其所有可能的全排列准确无重复无遗漏地列举出来。例如：输入AAB，其全排列的结果有3种：分别为：AAB,ABA,BAA。二、具体实现这里主要根据不同阶段的具体情况，分别阐述具体的实现方法：2.1阅读文献、收集资料选定合适的关键字进行搜索，关键字包括：string permutation, permutation generation method, combination, algorithm。对搜索出的文章进行分类筛选，找出当今世界上最新的最好的全排列算法，仔细研读，为下一阶段的模拟比较作好准备。搜索的著名数据库包括：u ACM（美国计算机学会） Digital Library ACM（Association for Computing Machinery，美国计算机学会）数据库收录ACM全文期刊29种，会议录近170种，超过69,000篇的全文文章、1954年至今出版的期刊、杂志目录以及超过23,000 篇的引用文献、1985年至今出版的990多卷会议记录的文章目录以及超过48,000 篇的引用文献、与ACM文章关联的大约150万篇参考文献（其中20万篇参考文献链接有全部书目资料，5万篇可以链接全文）、ACM的“在线计算机文献指南”（可以查询和浏览来自计算机领域重点出版社的巨大书目资料库，包括图书、期刊、会议录和论文）。u SCI (科学引文索引Science Citation Index）SCI是美国科学情报研究所（Institute for Scientific Information，简称ISI，网址：）出版的一部世界著名的期刊文献检索工具，其出版形式包括印刷版期刊和光盘版及联机数据库，现在还发行了互联网上Web版数据库（即Web of Science）。SCI收录全世界出版的数、理、化、农、林、医、生命科学、天文、地理、环境、材料、工程技术等自然科学各学科的核心期刊约3500种。ISI通过它严格的选刊标准和评估程序挑选刊源，而且每年略有增减，从而做到SCI收录的文献能全面覆盖全世界最重要和最有影响力的研究成果。 u IEEE/IEE IEL提供1988年以来，美国电气电子工程师学会和英国电气工程师学会出版的120多种期刊、600多种会议录、近900种标准的全文信息。2.2模拟阶段代码实现搜索到的具有代表性的全排列算法，通过对比比较，采用最合适的编程语言，遵循世界上通用的标准，并采用最通用的编译器，在相同的软硬件环境下进行模拟测试，得到相关一系列精确的比较数据。编程语言：符合ANSI C标准的C语言编码开发环境包括：n 软件环境：Windows下Microsoft Visual C+ 6.0、Microsoft Visual Studio .NET 2003、Microsoft Visual Studio 2005、Linux GCCn 硬件环境：Intel Pentium 4 CPU 2.93GHz, 1GB Memory 硬件环境2.3比较，得出结论阶段结合理论和实际模拟数据两方面，通过数学公式和图表形式，直观准确地给出各种算法的比较结果。根据比较阶段的比较结果，得出最终结论，找到当今世界上最高效的字符串全排列算法，肯定其在世界上的领先地位，分析其主要应用和实用性。时间进度安排：2007.1.29-2007.2.25 理解课题任务，理解Professor Ray最新全排列算法。2007.2.26-2007.3.31 搜索阅读文献资料，完成开题报告2007.4.01-2007.4.30 模拟比较各种算法的性能，并进行分析2007.5.01-2007.5.25 总结前面几个阶段的各项成果，完成论文。指导教师审核意见： 校外指导教师签名： 2007年 月 日 校内指导教师签名： 2007年 月 日毕业论文任务书（以下由学生填写）题 目：多重集全排列算法研究目标要求：字符串的全排列问题是一个经典的数学排列问题，它有着悠久的历史，也有着广泛的实际应用，比如说在密码学领域对输入的一些数字或字符产生其对应的密码；在生物医学领域DNA的全排列等等。因此研究字符串的全排列问题有很大的实际意义。对于N个数来说，其全排列的个数有N!个,近二十年来出现了许多关于全排列的算法,它们的思想各不相同,因此执行效率和所用的时间也各不相同。将这些不同的算法集中起来加以比较，分析它们的思想并将其转换成可运行的C代码，输入不同的字符串并比较其运行时间和所占用的内存，从而确定每个算法的优劣。通过上网搜索有关全排列的经典算法的英文论文（包括其发表日期、作者、出处），并将其用C 语言加以实现，然后模拟其运行过程，测试其所用的内存以及时间，然后和老师的关于全排列的算法加以比较，确定哪种算法最优，以及输出全排列所用的时间最少，占用内存最少。通过此次毕业设计，旨在提高我们阅读英语科技论文的能力，研究各种算法的能力，利用网络搜索引擎解决实际问题的能力，以及利用VC6.0开发环境以及C语言开发应用程序的实际动手能力。支持条件：支持硬件：奔腾4，CPU主频为2.93GHz，内存为1GB的电脑；操作系统：Windows XP开发环境：Visual C+6.0指导教师（签名） 职称 学生（签名） 分阶段进度安排阶段起讫时间计划完成内容12007年1月29日-3月10日查找、阅读相关的文献资料 22007年3月11日- 3月20日仔细挑选权威论文，实现经典高效算法32007年3月21日-4月30日算法的模拟与比较42007年5月1日-5月10日汇总模拟日志，整理、校对实验数据，绘制比较图表 52007年5月11日- 6月11日完成毕业论文的初稿，并进行修