算法设计与分析课程教学大纲.pdfVIP

算法设计与分析课程教学大纲

课程英文名称：AlgorithmicDesignAnalysis

课程编号：0800360学分：3.0学时：

32+16（实验）

一、课程教学对象

数学与计算科学学院信息与计算科学专业本科学生。

二、课程性质及教学目的

课程性质:本课程是信息与计算科学专业专业选修课。该课程

包括理论教学(32学时)和课内实验(16学时)两个环节。

目的和任务:通过本课程的学习，可以开阔编程思路，编写出

优质程序；通过许多常见且有代表性算法的学习，使学生理解和

掌握算法设计的基本方法，熟悉算法分析的基本技术，同时掌握

算法分析的基本方法和技巧，培养对算法时间、空间复杂性进行

正确分析能力，锻炼其逻辑思维能力和想象力，使学生具有问题

抽象和建模的初步能力，并使之了解算法理论的发展；同时鼓励

学生运用算法知识解决本学科的实际问题，培养学生独立科研的

能力和理论联系实践的能力，为独立的设计算法和给定算法进行

复杂性分析打下良好的基础，并能熟练运用一些常用算法，为学

生进一步学习后续课程奠定良好的基础。

三、对先修知识的要求

离散数学，C++程序设计，数据结构

四、课程的主要内容、基本要求和学时分配建议（总学时数:理

论课32学时）

知识模块知识点要求学时学习方式课外学习要求

1、绪论1.1算法的基本概念C1课堂讲授

1.2算法分析A1课堂讲授

2、NP完全理论2.1P类问题和NP类问题B1课堂讲授

2.2NP完全问题C1课堂讲授

3、蛮力法3.1蛮力法的设计思想A1课堂讲授

3.2查找问题中的蛮力法B1课堂讲授

3.3排序问题中的蛮力法B1课堂讲授

3.4组合问题中的蛮力法B1课堂讲授

4、分治法4.1分治法的设计思想A1课堂讲授

4.2排序问题中的分治法B1课堂讲授

4.3组合问题中的分治法C1课堂讲授

4.4几何问题中的分治法B1课堂讲授

5、减治法5.1减治法的设计思想A1课堂讲授

5.2查找问题中的减治法B1课堂讲授

5.3排序问题中的减治法B1课堂讲授

5.4组合问题中的减治法C1课堂讲授

6、动态规划法6.1动态规划法的设计思想A1课堂讲授

6.2图问题中的动态规划法A1课堂讲授

6.3组合问题中的动态规划法C1课堂讲授

6.4查找问题中的动态规划法B1课堂讲授

7、贪心