《《算法设计与分析》实验大纲》由会员分享，可在线阅读，更多相关《《算法设计与分析》实验大纲（5页珍藏版）》请在金锄头文库上搜索。
1、 算法设计与分析一、 说明（一） 课程性质计算机科学是一种创造性思维活动，其教育必须面向设计。计算机算法设计与分析正是一门面向设计，且处于计算机学科核心地位的教育课程。设计一个高效的程序不仅需要编程小技巧，更需要合理的数据组织和清晰高效的算法，这正是计算机科学领域里数据结构与算法设计可研究的主要内容。（二） 教学目的通过对本课程的学习与研究，使学生掌握算法设计的主要方法，培养对算法的计算复杂性正确分析的能力，为独立设计算法和对算法复杂性分析奠定坚实的理论基础，对学生将来从事计算机系统结构、系统软件和应用软件的研究与开发提供一个广泛扎实的计算机算法知识基础。（三） 教学内容有效算法最常用的设计策
2、略递归和分治法，动态规划法的设计要点与适用性，贪心算法，回溯法和分支限界法，许多难解问题的高效算法概率算法，以及NP完全理论和NP难问题的近似解法。（四） 教学时数36学时（五）教学方式课题设计+上机实验根据一种算法设计策略的基本思想，编程解决计算机科学和应用中的实际问题，由简到繁地描述几个经典的精巧算法。同时对每个算法所需的时间和空间进行分析，使学生既能学到一些常用的精巧算法，又能通过对算法设计策略的反复应用，牢固掌握这些算法设计的基本策略，以期收到融会贯通之效。在为各种算法设计策略选择用于展示其设计思想与技巧的具体应用问题时，有意义重复选择某些经典问题，使学生能深刻地体会到一个问题可以用多
3、种设计策略求解。同时通过对解同一问题的不同算法的比较，使学生更容易体会到每一种具体算法的设计要点。随着内容的逐步展开，学生也将进一步感受到综合应用多种设计策略可以更有效地解决问题。二、 本文（一） 基本要求（1）熟练操作有关C+或JAVA编程环境（2）运用理论部分介绍的各类算法设计思想，在相关环境下设计，编写，调试和运行求解实际问题的程序（二） 实验项目总表序号 实验项目名称学时项目类别项目类型 1熟悉C+或JAVA编程的环境 2 基础 必做 2 排列问题 2 设计 必做 3 棋盘覆盖问题 2 设计 必做 4用栈模拟递归，消去算法Quick sort中的递归 2 综合 必做 5 Sarasse
4、n矩阵乘法 2 设计 选做序号 实验项目名称学时项目类别项目类型 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 装载问题 2 设计 必做 19 最大团问题 2 设计
5、 选做 20 用随机投点法计算值 2 设计 必做 21 线性时间选择（Sherwood算法） 2 设计 必做 22 n后问题（Las Vegas算法） 2 设计 必做 23 矩阵互逆问题（Monte Carlo算法） 2 设计 必做 注：必做项目数17个，选做项目数6个。（三） 实验项目内容及要求本课程实验所需设备及软件均为：微型计算机，C+/JAVA编程环境 1熟悉C+/JAVA编程环境 目的及要求：准备并熟悉后续实验项目所用的环境2排列问题 设有类型相同的N个元素组成的集合R=r1，r2，rn，试对其进行全排列目的：理解递归概念及递归算法设计方法要求： 设计、编写、调试、运行求解排列问题的
6、递归程序 写出实验报告3棋盘覆盖算法 用4种不同形态的L型骨牌覆盖一个2k2k的特殊棋盘上除特殊方格以为的所有方格，且任何2个L型骨牌不得重叠覆盖 目的：理解分治法的的基本思想及分治算法设计方法要求： 设计、编写、调试、运行求解模型底差问题的算法设计方法 写出实验报告4用栈模拟递归消去算法Quick sort中的递归 目的：理解栈与递归的关系，将递归消除要求： 使用栈设计、编写、调试、运行快速排序的非递归程序 写出实验报告 5Sarassen矩阵乘法 求两个nn 矩阵A与B的乘积，使其时间复杂度小于O（n） 目的：理解分治法的的基本思想及分治算法设计方法要求： 设计、编写、调试、运行求解模型底
7、差问题的算法设计方法 写出实验报告 6矩阵连乘问题 （动态和备忘录 给定n个矩阵A1，A2，An，其中，Ai与Ai+1是可乘的，I=1，2，n-1。我们要计算出这n个矩阵的连乘积A1A2，An。 目的：理解并掌握动态规划算法的基本思想及动态规划算法设计方法要求： 用动态规划思想设计、编写、调试、运行解此问题的程序 写出实验报告7图象压缩 要求确定像素序列p1，p2， p1的一个最优分段，使得依次分段所需的存储空间最少。 目的：理解并掌握动态规划算法的基本思想及动态规划算法设计方法要求： 用动态规划思想设计、编写、调试、运行解此问题的程序 写出实验报告8找硬币（递归算法，动态规划算法，贪心算法）
8、 设有n种不同面值的硬币，各硬币的面值存于数组T中。现要用这些面值的硬币来找钱。可以使用的各种面值的硬币个数不限。 目的：理解并掌握分治法、动态规划法、贪心算法的区别与联系要求： 分别用分治法、动态规划法、贪心算法设计、编写、调试、运行解此问题的程序 写出实验报告9活动安排问题 在所给的活动集合中选出最大的相容活动子集合目的：理解并掌握贪心算法的基本思想及贪心算法设计方法要求： 用贪心算法设计、编写、调试、运行解此问题的程序 写出实验报告10哈夫曼编码 使用一个字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式目的：理解并掌握贪心算法的基本思想及贪心算法设计方法要求： 用贪心
9、算法设计、编写、调试、运行解此问题的程序 写出实验报告11多机调度问题 要求给出一种作业调度方案，使所给的n个作业在尽可能短的时间内有m台机器加工处理完成。目的：理解并掌握贪心算法的基本思想及贪心算法设计方法要求： 用贪心算法设计、编写、调试、运行解此问题的程序 写出实验报告12多会场多活动安排问题 在足够多的会场里安排一批活动，并希望使用尽可能少的会场。目的：理解并掌握贪心算法的基本思想及贪心算法设计方法要求： 用贪心算法设计、编写、调试、运行解此问题的程序 写出实验报告13装载问题 有一批共n个集装箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且wic1+c2。要求确
10、定是否有一个合理的装载方案可将这n个集装箱装上这两艘轮船，如果有，找出一种装载方案。 目的：理解并掌握回溯法的基本思想及回溯酸法设计方法要求： 用回溯算法设计、编写、调试、运行解此问题的程序 写出实验报告14批处理作业调度问题 对于给定的n个作业，制定一个最佳作业调度方案，使其完成时间和达到最小。 目的：理解并掌握回溯法的基本思想及回溯酸法设计方法要求： 用回溯算法设计、编写、调试、运行解此问题的程序 写出实验报告15图的M着色问题 给定一个无向连通图G和m种不同的颜色。用这些颜色为图G的各顶点着色，每个顶点着一种颜色。试问是否有使得G中任何一条边的2个顶点着有不同颜色着色法。 目的：理解并掌
11、握回溯法的基本思想及回溯酸法设计方法要求： 用回溯算法设计、编写、调试、运行解此问题的程序 写出实验报告16运动员最佳配对问题 计算出男女运动员的最佳配对法，使各组男女双方竞赛优势成绩的总和达到最大。 目的：理解并掌握回溯法的基本思想及回溯酸法设计方法要求： 用回溯算法设计、编写、调试、运行解此问题的程序 写出实验报告17布线问题 将布线区域分成nm个方格阵列，电路布线问题要求确定连接某方格a的中点到另一方格b的中点的最短布线方案。 目的：理解并掌握分支界限法的基本思想及分支界限法算法设计方法要求： 用分支界限法设计、编写、调试、运行解此问题的程序 写出实验报告 18装载问题 有一批共n个集装
12、箱要装上2艘载重量分别为c1和c2的轮船，其中集装箱i的重量为wi，且wic1+c2。要求确定是否有一个合理的装载方案可将这n个集装箱装上这两艘轮船，如果有，找出一种装载方案。目的：理解并掌握分支界限法的基本思想及分支界限法算法设计方法要求： 用分支界限法设计、编写、调试、运行解此问题的程序 写出实验报告19最大团问题 给定一个无向图G（V，E）。G的最大团是指G中所含顶点数最多的团。 目的：理解并掌握分支界限法的基本思想及分支界限法算法设计方法要求： 用分支界限法设计、编写、调试、运行解此问题的程序 写出实验报告20用随机投点法计算值 设有一半径为r的圆及其外切四边形，向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点落入圆内的均匀分布概率为/4。当n足够大时，k与n之比就逼近这一概率，由此可得用随机投点发计算值的数值概率算法 目的：理解并掌握数值概率算法的思想及算法设计方法要求： 用数值概率算法设计、编写、调试、运行解此问题的程序 写出实验报告21线性时间选择（Sherwood算法） 给定线形序集中n个元素和一个整数k，1kn要求找出这n个元素中第k小的元素。 目的：理解并掌握舍伍德算法的思想及算法设计方法要求： 用舍伍德（Sherwood）算法设计、编写、调试、运行解此问题的程序 写出实验报告22n后问题（Las Vegas算法） 要求在一个nn格
