《算法设计与分析》实验大纲

《《算法设计与分析》实验大纲》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法设计与分析一、说明（一）课程性质计算机科学是一种创造性思维活动，其教育必须面向设计。计算机算法设计与分析正是一门面向设计，且处于计算机学科核心地位的教育课程。设计一个高效的程序不仅需要编程小技巧，更需要合理的数据组织和清晰高效的算法，这正是计算机科学领域里数据结构与算法设计可研究的主要内容。（二）教学目的通过对本课程的学习与研究，使学生掌握算法设计的主要方法，培养对算法的计算复杂性正确分析的能力，为独立设计算法和对算法复杂性分析奠定坚实的理论基础，对学生将来从事计算机系统结构、系统软件和应用软件的研究与开发提供一个广泛扎实的计算机算法

2、知识基础。（三）教学内容有效算法最常用的设计策略——递归和分治法，动态规划法的设计要点与适用性，贪心算法，回溯法和分支限界法，许多难解问题的高效算法——概率算法，以及NP完全理论和NP难问题的近似解法。（四）教学时数36学时（五）教学方式课题设计+上机实验根据一种算法设计策略的基本思想，编程解决计算机科学和应用中的实际问题，由简到繁地描述几个经典的精巧算法。同时对每个算法所需的时间和空间进行分析，使学生既能学到一些常用的精巧算法，又能通过对算法设计策略的反复应用，牢固掌握这些算法设计的基本策略，以期收到融会贯通之效。在为各种算法设计策略选

3、择用于展示其设计思想与技巧的具体应用问题时，有意义重复选择某些经典问题，使学生能深刻地体会到一个问题可以用多种设计策略求解。同时通过对解同一问题的不同算法的比较，使学生更容易体会到每一种具体算法的设计要点。随着内容的逐步展开，学生也将进一步感受到综合应用多种设计策略可以更有效地解决问题。二、本文（一）基本要求（1）熟练操作有关C++或JAVA编程环境（2）运用理论部分介绍的各类算法设计思想，在相关环境下设计，编写，调试和运行求解实际问题的程序（二）实验项目总表序号实验项目名称学时项目类别项目类型1熟悉C++或JAVA编程的环境2基础必做2

4、排列问题2设计必做3棋盘覆盖问题2设计必做4用栈模拟递归，消去算法Quicksort中的递归2综合必做5Sarassen矩阵乘法2设计选做5序号实验项目名称学时项目类别项目类型6矩阵连乘问题（动态和备忘录）2设计必做7图象压缩2设计必做8找硬币（递归算法，动态规划算法，贪心算法）2综合必做9活动安排问题2设计必做10哈夫曼编码2设计必做11多机调度问题2设计选做12多会场多活动安排问题2综合选做13装载问题2设计必做14批处理作业调度问题2设计选做15图的M着色问题2设计必做16运动员最佳配对问题2设计选做17布线问题2设计必做18装载问

5、题2设计必做19最大团问题2设计选做20用随机投点法计算∏值2设计必做21线性时间选择（Sherwood算法）2设计必做22n后问题（LasVegas算法）2设计必做23矩阵互逆问题（MonteCarlo算法）2设计必做注：必做项目数17个，选做项目数6个。（一）实验项目内容及要求本课程实验所需设备及软件均为：微型计算机，C++/JAVA编程环境1．熟悉C++/JAVA编程环境目的及要求：准备并熟悉后续实验项目所用的环境2．排列问题设有类型相同的N个元素组成的集合R={r1，r2，……，rn}，试对其进行全排列目的：理解递归概念及递归算法

6、设计方法要求：①设计、编写、调试、运行求解排列问题的递归程序②写出实验报告3．棋盘覆盖算法用4种不同形态的L型骨牌覆盖一个2k×2k的特殊棋盘上除特殊方格以为的所有方格，且任何2个L型骨牌不得重叠覆盖目的：理解分治法的的基本思想及分治算法设计方法要求：①设计、编写、调试、运行求解模型底差问题的算法设计方法②写出实验报告4．用栈模拟递归消去算法Quicksort中的递归目的：理解栈与递归的关系，将递归消除要求：①使用栈设计、编写、调试、运行快速排序的非递归程序②写出实验报告5．Sarassen矩阵乘法5求两个n×n矩阵A与B的乘积，使其时间

7、复杂度小于O（n³）目的：理解分治法的的基本思想及分治算法设计方法要求：①设计、编写、调试、运行求解模型底差问题的算法设计方法②写出实验报告6．矩阵连乘问题（动态和备忘录给定n个矩阵{A1，A2，…，An}，其中，Ai与Ai+1是可乘的，I=1，2，…，n-1。我们要计算出这n个矩阵的连乘积A1A2，…，An。目的：理解并掌握动态规划算法的基本思想及动态规划算法设计方法要求：①用动态规划思想设计、编写、调试、运行解此问题的程序②写出实验报告7．图象压缩要求确定像素序列{p1，p2，…，p1}的一个最优分段，使得依次分段所需的存储空间最少。

8、目的：理解并掌握动态规划算法的基本思想及动态规划算法设计方法要求：①用动态规划思想设计、编写、调试、运行解此问题的程序②写出实验报告8．找硬币（递归算法，动态规划算法，贪心算法）设有n种不同面