《算法分析与设计》实验指导new.docVIP

《算法分析与设计》实验指导 专 业： 软件工程 班 级： Y121081、Y121082 执笔人： 刘在德 计算机科学与工程学院 2010年09月 课程编号: 0924002B 课程名称：英文名称：Analysis and Design of Algorithms：学　　分：一、课程目的和任务独立设计算法和对给定算法进行复杂性分析二、基本要求算法设计的主要方法、内容18个学时内完成。 序号 实验项目名称 内容提要 实验学时 每组人数 实验类型 实验类别 实验要求 1 求最大公约数 求自然数m和n的最大公约数设计出版本的求最大公约数的算法；上机实现算法并分析时间复杂性。2 1 设计型 基础实验 必修 2 字符串匹配问题 给定一段文本，在该文本中查找并定位任意给定字符串上机实现字符串匹配的KMP算法和BM算法；分析种算法的时间复杂性。1 设计型 专业实验 必修 3 最近对问题 给定平面上任意n个点，找出其中距离最近的点对1 设计型 专业实验 必修 4 Huffman编码 设需要编码的字符集为{d1,d2,…, dn}，出现的概率为{w1,w2,…,wn},应用Huffman树构造最短的变长编码方案； 设计贪心算法求解Huffman编码方案； 上机实现算法并分析时间复杂性。 4 1 设计型 专业实验 必修 5 投资问题 有n项可投资的项目1 综合设计型 专业实验 必修 四、考方式 考核实验操作、实验报告、设计报告等。、推荐教材和教学参考书 参 考 书：《The Art of Computer Programming》(3rd Edition)—Volume 1/ Fundamental Algorithms, Donald E. Knuth, Addison Wesley Longman, 1997. The Art of Computer Programming》(2ed Edition)—Volume 3/ Sorting and Searching, Donald E. Knuth Addison Wesley Longman, 1998. 实验1 1、实验目的 （1）求两个自然数m和n的GCD (Greatest Common Divisor)； （2）掌握并应用算法的数学分析和后验分析方法； （3）理解这样一个观点：不同的算法能够解决相同的问题，但这些算法的思路不同，时间复杂性也不同。（1）设计出2个版本的求最大公约数的算法； （2）采用C/C++实现算法，利用计数法记录基本语句的执行次数； （3）采用大O符号分析2种算法的时间复杂性； （4）通过分析对比，得出结论（5）根据实验结果撰写实验报告。 3、实验提示 见课本18-19页。 实验2 字符串匹配问题 1、实验目的 （1）给定一段文本，在该文本中查找并定位任意给定字符串深刻理解并掌握蛮力法的设计思想； 3）理解这样一个观点：经过适度努力，一般都可以改进用蛮力法设计的算法，从而提高计算效率 2、实验内容 （1）实现B；实现；）采用计数法记录基本语句的执行次数，并分析种算法的时间复杂性； ）通过分析对比，得出结论（5）根据实验结果撰写实验报告。设p1=(x1, y1)p2=(x2, y2)，…，pn=(xn, yn)是平面上n个点构成的集合S，设计算法找出集合S中距离最近的点对进一步掌握递归算法的设计思想以及递归程序的调试技术； 理解此观点：分治和递归经常同时应用在算法设计中。（1）用分治法求解最近对问题； （2）算法，计数法记录基本语句的执行次数时间复杂性根据实验结果撰写实验报告。设需要编码的字符集为{d1,d2,…, dn}，出现的概率为{w1,w2,…,wn},应用Huffman树构造最短的变长编码方案 （2）了解前缀编码的概念，理解数据压缩的基本方法； ）掌握贪心法的设计思想并熟练运用。（1）设计贪心算法求解Huffman编码方案； （2）采用C/C++实现算法； （3）分析算法的时间复杂性根据实验结果撰写实验报告。（1）有n项可投资的项目，每个项目需要资金si，可获利润为vi，现有可用资金总数为M，为获得最大利润，应选择那些投资项目？（）掌握实际问题的求解步骤（1）抽象出问题的模型； （2）； （3）采用C/C++实现算法； （4）分析算法的时间复杂度（5）根据实验结果撰写实验报告。