0923D06030-算法设计与分析实验.docxVIP

PAGE6

ADDINCNKISM.UserStyle《算法设计与分析实验》课程教学大纲

（实验课程）

一、课程基本信息

课程号

0923D06030

开课单位

数学与信息科学学院

课程名称

（中文）算法设计与分析实验

（英文）ExperimentalCourseofAlgorithmDesignandAnalysis

课程性质

选修

考核类型

考查

课程学分

1

课程学时

34

课程类别

专业拓展课

适用专业（类）

数据科学与大数据技术、软件工程

二、课程描述及目标

（一）课程简介

《算法设计与分析实验》课程是数据科学与大数据技术专业教学计划中《算法分析与设计》课程相配套的数学实验课程。旨在培养学生算法分析以及综合利用简单算法设计新算法的能力，还培养学生学会分析算法、估计算法的复杂性，以便理解并科学评估有一个算法的好坏。它是进行软件设计的核心内容，是一门实践性很强的课程。本课程主要基于计算机领域及其它有关领域中的主要算法设计方法及一些常用算法，要求学生掌握算法设计的常用方法，以便运用这些方法来设计解决一些常用的或较为复杂的实际问题的算法，并力争做到快捷、有效，从而提高程序设计的质量。本课程主要包括分治策略、动态规划、贪心算法、回溯法、分支限界法等实验项目。

（二）教学目标

通过本课程，使学生掌握算法分析的基础，学会如何分析一个算法的复杂度，评估一个算法的好坏，掌握递归算法、分治算法、贪心算法、动态规划算法、回溯算法和分支定界算法，并能灵活运用这些算法解决实际问题。通过实验使学生加深对基本算法设计方法的理解，增强学生对解决问题的不同算法运行时间不同的感性认识，使学生在算法设计方法和编程技能等方面得到系统的训练，使学生养成设计良好算法的习惯，为今后从事软件开发和软件理论研究打下良好的实验基础。

课程目标1：掌握算法复杂度分析的基本理论以及算法的计算复杂性分析方法，以及算法分析相关的数学基础，能够对所现有的或者设计出的算法从理论上进行复杂度分析；

课程目标2：理解、掌握常见的算法设计方法，能够综合利用多种算法设计技术更有效地解决实际问题；

课程目标3：培养学生算法分析的时空意识、离散的计算思维、以及在有限的计算资源上为实际问题选择或设计合适算法的能力。

三、课程目标对毕业要求的支撑关系

毕业要求指标点

课程目标

权重

1-2：掌握计算机科学与软件开发的基本理论和基础专业知识，具备常用软件及数据分析软件使用的相关知识，掌握常用软件开发语言，具备大数据环境下数据分析算法与软件系统的设计、开发与分析等相关知识。

课程目标1

0.4

2-2：具有较强的创新意识和批判意识，善于发现、提出问题，有意识涉猎相关学科的基本知识，并尝试将数据科学与大数据技术的理论和方法应用到具体问题分析、建模及求解中。

课程目标2

0.3

3-4：具有科学情怀，具备数学思维和数据思维素养，能胜任数据建模、数据分析与挖掘算法等问题的研究和大数据系统的开发工作，即可在科研机构或高校继续深造，从事数据科学相关的科研工作，也可在经济、管理、生物、交通、医疗等领域或业界从事大数据的采集、管理、分析与处理方面的工作。

课程目标3

0.3

四、教学方式与方法

以实际操作能力为主，参考小组讨论和教师演示与提问。

五、教学重点与难点

（一）教学重点

掌握分治策略的基本思想以及用分治法解决问题的一般技巧；掌握动态规划解决问题的一般过程，学会使用动态规划解决实际问题；掌握贪心法解决问题的一般步骤，学会使用贪心法解决实际；掌握回溯法解决问题的一般步骤，学会使用回溯法解决实际问题；掌握分支限界法解决问题的基本思想，学会使用分支限界法解决实际问题；掌握动态规划算法、贪心算法、回溯与分支限界算法的主要区别与联系。理解并综合各种算法的优缺点以设计心得算法解决新问题。

（二）教学难点

递归概念的理解，用分治法解决问题的一般技巧；掌握动态规划解决问题的一般过程，学会使用动态规划解决最长公共子序列，最大子段和，凸多边形最优三角剖分，多边形游戏，图像压缩，电路布线，流水作业调度等问题。

六、实验内容、基本要求与学时分配

序号

实验项目名称

实验内容与要求

学时

类型

对应课程目标

1

分治策略

掌握分治策略的基本思想以及用分治法解决问题的一般技巧。完成下列程序中的一个：递归概念，分治法基本思想，二分有哪些信誉好的足球投注网站技术，大整数乘法，矩阵乘法，棋盘覆盖，合并排序，快速排序，线性时间选择，最接近点对问题，循环赛日程表。此部分为必修。

4

设计性

课程目标1

课程目标2

2

动态规划

掌握动态规划解决问题的一般过程，学会使用动态规划解决实际问题。用动态规划算法实现下列程序中的一个：矩阵连乘，最长公共子序列，最大子段和，凸多边形最优三角剖分，多边形游戏，图像压缩，电路布线，流水作业调度