算法设计与分析实验大纲

算法设计与分析实验大纲

课程名称：算法设计与分析（实验）

英文名称：Algorithm Design and Analysis

课程编号：1204017270

课程性质：专业必修课

先修要求：C语言程序设计或Java语言程序设计、数据结构

适用专业：信息与计算科学及相近专业

任课老师：郭娟、方欢

一、教学目标

通过本课程的理论教学和实验训练，使学生具备以下知识和能力：

目标1：理解算法基本概念，掌握算法时间和空间复杂度分析的基本方法；通过算法的时间复杂度和空间复杂度的分析，衡量算法的优劣；

目标2：掌握集合、线性表、树、二元树、图等基本数据结构，能应用某程序设计语言实现基本数据结构，应用基本数据结构求解特定问题；

目标3：理解递归程序原理，掌握递归编程思想，掌握递归程序的设计和分析方法，掌握简单递归方程求解会求解K阶线性（非）齐次递归方程求解

目标4：了解常见经典算法基本原理，掌握分治法、贪心法、动态规划、周游及检索算法、回溯法和分支限界法求解特点和关键；根据实际问题建立数学模型，并选择适当的方法求解。

二、课程教学目标与毕业要求的对应关系

教学目标	毕业要求	支撑强度
目标1	具有利用数学、计算机等自然科学和工程科学的基本原理及软件工程专业知识，能将数理科学、软件工程基础和专业知识运用到信息与计算复杂工程问题的恰当表述之中。能够利用数理科学、计算机科学相关的基础理论和知识以及文献资料对数据进行数值计算，或者对案例进行软件建模，能对软件设计技术进行经济评价，并能对解决方案的合理性进行验证。（毕业要求1，2）	H
目标2	具有利用数学、计算机等自然科学和工程科学的基本原理及软件工程专业知识，能将数理科学、软件工程基础和专业知识运用到信息与计算复杂工程问题的恰当表述之中。（毕业要求1）	H
目标3	能够利用数理科学、计算机科学相关的基础理论和知识以及文献资料对数据进行数值计算，或者对案例进行软件建模，能对软件设计技术进行经济评价，并能对解决方案的合理性进行验证。（毕业要求2）	H
目标4	能通过建模、软件开发等手段进行数值计算和系统软件实现，对相关设计方案进行优化设计，体现创新意识，能够应用数值分析与计算、软件工程的基本原理和方法开发、设计数值计算、软件系统的合理方案，并能够使用图纸、报告或者实物等形式，呈现设计结果。能够基于信息与计算专业理论，根据对象特征，选择合适的研究路线、设计可行的试验方案（毕业要求3，4）	H

备注：H-高度支撑；M-中度支撑；L-一般支撑。

三、实验教学主要内容(支撑教学目标2、3、4)（查看2016培养方案计划表中实验课时）

实验一基本数据结构的应用

1.理解不相交集合的树结构表示思想；

2.集合的树结构表示和贪心方法解决作业调度问题。

3.理解递归程序原理，用递归实现指定程序的设计和时间测定。

实验二分类算法

1.理解直接插入、归并分类、快速分类算法思想；

2. 能够实现归并分类和快速分类算法，并通过程序测试和比较执行速度差异。

实验三贪心算法

1.理解贪心算法关键思想，会应用解决实际问题；

2.能实现贪心法求解背包问题，并输出最优解；

3. 理解堆排序思想，能实现贪心法求解最小生成树的程序；

4. 能实现贪心法求解单源点最短路并输出最短路径。

实验四检索和周游算法

1.理解深度优先遍历和广度优先遍历算法思想；

2.会利用周游算法对无向图生成双连通分图；

3.检索树中给定特征的结点。

实验课具体由数据分析与处理课程同时执行。

四、建议教学进度

实验一基本数据结构的应用学时数2

实验二分类算法学时数2

实验三贪心算法学时数2

实验四检索和周游算法学时数2

五、教学方法

1.以上机实际操作的方式实现；

2.强化基本数据结构的应用及典型算法的应用和程序调试能力的培养。

六、考核方式

和算法设计与分析课程一起考核，实验成绩占平时成绩的15%。

七、成绩评定方法

笔试成绩70%，平时成绩30%（含课程作业，包含实验成绩）

八、主要参考书籍

1.余祥宣，计算机算法基础，华中科技大学出版社，

2.王晓东，算法设计与分析，电子工业出版社，