课程编号：04020068 课程名称：算法设计与分析
总学时：54 总学分：3 实验学时：18 实验学分：1
适应专业：计算机科学与技术、软件工程、网络工程等计算机类本科专业
实验指导书：待定.
一、本实验课的任务、性质与目的
算法设计与分析 实验是 算法设计与分析课的 一个实践性教学环节。通过实验使学生加深对基本算法设计方法的理解，增强学生对解决问题的不同算法运行时间不同的感性认识，使学生在算法设计方法和编程技能等方面得到系统的训练，使学生养成设计良好算法的习惯， 为今后从事软件开发和软件理论研究打下良好的实验基础 。
二、实验方式与基本要求
实验方式：上机实验。
基本要求：通过实验,使学生熟悉常用的计算机算法，能够运用所学的基本方法求解一些实际应用问题。上机实验根据实验题目选择合适的数据结构,设计相应的算法并实现，要求所编程序能正确运行并提交实验报告，实验报告的主要内容有：程序的功能；输入的形式和输入值的范围；输出的形式；程序流程图或带注释的源程序；调试过程中所遇到的问题及解决方法；经验与体会。
⑴需求分析：陈述设计的任务,强调程序要做什么,明确规定：①输入的形式和输入值的范围；②输出的形式；③程序所实现的功能；④测试数据：包括正确的输入输出和错误的输入及其输出。
⑵概要设计：说明采用的数据结构、主程序的流程及各程序模块之间的调用关系。
⑶详细设计：提交带注释的源程序或者用伪代码写出每个操作的算法。
⑷调试分析：①调试过程中所遇到的问题及解决方法；②算法的时空分析；③经验与体会。
⑸用户使用说明：说明如何使用程序,详细列出每一步操作步骤。
⑹测试结果：列出对于给定的输入所产生的输出结果。若可能,测试随输入规模的增长所用算法的实际运行时间的变化。
三、实验项目与内容提要
本课程的实验教学环节包括上机实验部分。
上机实验项目：
序 号 |
项目名称 |
内容提要 |
实验 时数 |
实验 类型 |
实验 要求 |
1 |
递归法 |
递归法的框架；递归法求解汉诺塔问题 |
2 |
设计性 |
必做 |
2 |
分治法 |
分治法的框架；分治法求解二分查找问题 |
2 |
设计性 |
必做 |
3 |
动态规划法 |
动态规划法的框架；动态规划法法求解矩阵连乘问题 |
4 |
设计性 |
必做 |
4 |
贪心法 |
贪心法的框架；贪心法求解取款机取款问题 |
2 |
设计性 |
必做 |
5 |
回溯法 |
回溯法的框架；回溯法求解装载问题 |
2 |
设计性 |
必做 |
6 |
分支限界法 |
分支限界法的框架；分支限界法法求解单源最短路径问题 |
4 |
设计性 |
必做 |
7 |
随机化算法 |
搜索有序表 |
2 |
设计性 |
必做 |
实验类型是指：验证性/设计性/综合性实验；实验要求是指：必做性/选做性实验；
四、考核与评分
考核方式：开卷、机试，与实验同步进行，时间90分钟，成绩评定采用计分制(满分100分),上机实验成绩折算为课程总成绩的20%。
