算法设计与分析 实验讲义(2012_09_17)

《算法设计与分析 实验讲义(2012_09_17)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、云南大学信息学院计算机科学与技术专业本科《算法设计与分析》实验讲义任课教师：岳昆2012年9月26前言计算思维、算法设计能力，程序实现、系统开发能力，分别是计算机科学与技术专业研究型（科学与分析）和应用型（工程与综合）人才培养的目标，这些目标由一系列专业课程支撑，《算法设计与分析》又是这一系列课程中的核心课程。《算法设计与分析》针对现实问题抽象、建模和求解，以程序设计、数据结构等课程内容为基础，具有较高的理论性和综合性，也具有较强的针对性和实用性，是提升学生解决问题和技术研发能力的重要课程。教育部高等学校计算机科学与技术教学指导委员会编制的《高

2、等学校计算机科学与技术专业发展战略报告暨专业规范》中，“算法与复杂度（CS-AL和CE-ALG）”对计算机科学与技术专业的计算机科学方向、计算机工程方向、软件工程方向和信息技术方向的培养目标和规格、教育内容和知识体系、以及主要参考指标进行了全面阐述，《算法设计与分析》理论课程以《规范》中的培养目标和规格、教育内容和知识体系、以及主要参考指标为蓝本。开设与理论课相对应、具有统一课程体系的实验课程，是学生对理论课程讲授内容及知识点深入理解、能应用理论知识解决问题的必要环节，是提高实践能力和系统研发能力的必要手段。算法设计与复杂度分析是《算法设计与分

3、析》课程的核心和主线，通过搜索算法、排序算法、数值算法、串匹配算法、图算法等，讲授分治、贪心、动态规划、回溯等算法思想。本实验讲义围绕这些内容，包括时间复杂度分析相关概念的例子及理解，经典算法的实现与性能测试，给定问题的算法设计、实现与性能测试。旨在通过实验教学，使学生对所学基本概念、经典算法思想和性能有更直观和深刻的理解，训练学生针对实际问题设计与分析算法的能力。根据云南大学信息学院计算机科学与技术专业教学计划和实际情况，《算法设计与分析》实验一共30学时，共安排7个实验、16个学时，包括基于实验测试理解算法分析的基本概念、搜索算法、递归与分

4、治算法、动态规划算法、贪心算法、回溯算法的实现与测试。每个实验从实验目的、原理解析、实验内容、实验步骤和要求几方面讲解。此外，安排4个学时进行综合练习讲解、实验展示和检查等。26目录第1章算法分析基本概念4实验1.1算法计算时间复杂度和增长率（4学时）41.实验目的42.原理解析43.实验内容64.实验步骤和要求6第2章搜索算法8实验2.1搜索算法的实现，时间复杂度分析与测试（4学时）81.实验目的82.原理解析83.实验内容94.实验步骤和要求9第3章递归与分治算法11实验3.1分治算法的递归程序实现与时间复杂度测试（4学时）111.实验目的

5、112.原理解析113.实验内容134.实验步骤和要求13第4章动态规划算法15实验4.1动态规划算法的实现与时间复杂度测试（3学时）151.实验目的152.原理解析153.实验内容164.实验步骤和要求16实验4.2动态规划算法的适应性测试（3学时）171.实验目的172.原理解析173.实验内容184.实验步骤和要求18第5章贪心算法19实验5.1贪心算法的实现与时间复杂度测试（4学时）191.实验目的192.原理解析193.实验内容20264.实验步骤和要求20第6章回溯算法22实验6.1回溯算法的实现和时间复杂度测试（4学时）221.实

6、验目的222.原理解析223.实验内容234.实验步骤和要求23第7章算法设计与性能测试综合练习24实验7.1哈夫曼编码与数据压缩24实验7.2最优选课24附录：实验报告撰写规范2626第1章算法分析基本概念实验1.1算法计算时间复杂度和增长率（4学时）1.实验目的通过算法的程序实现和执行时间测试、并与理论上的结论进行对比分析，深入理解算法时间复杂度分析中对于输入数据考虑其等价类的意义，理解算法时间复杂度渐进性态和和增长率的概念，为后续学习和实验奠定基础，同时也学习程序效率测试的基本思路。2.原理解析n算法时间复杂度分析的相关概念(1)算法的计

7、算时间取决于算法中某些操作的执行次数，这些操作是算法时间复杂度分析的依据。(2)增长率反映了算法的计算时间复杂度，即随着算法输入规模的增加、算法计算时间增加的趋势。(3)算法的计算时间复杂度针对输入数据的等价类来分析或测试。n随机数生成算法通过程序生成（伪）随机数，作为实验用测试数据。可使用编程语言自带的random函数生成，也可以采用一些有效的随机数生成算法生成，例如“线性同余法”，基于该算法，只要参数选择合适，所产生的伪随机数就能满足均匀性和独立性，与真正的随机数具有相近的性质。该算法的基本思想如下：通过设置Xi+1=(aXi+c)modm

8、,n³0，其中的4个整数参数：m——模数,m>0；a——乘数,0£a