算法设计教学大纲课件

安徽科技学院理学院

教 学 大 纲

课程名称：算法设计

适用专业：计算机科学与技术

（本科）

计算机科学技术专业教研室制

2006.6

《算法设计》理论课教学大纲

课程名称：算法设计（Algrithm Design）

课程编号：

课程类别：选修课

学 时：36 学时（理论36学时）

学 分：2学分

考核方式：考试

适用专业：计算机科学与技术本科专业

前修课程：高等数学 离散数学 线形代数 C语言程序设计 数据结构

建设开课学期：第6学期

一、课程性质、目的任务

随着计算机的广泛应用，对计算机算法的研究变得日益重要。《算法设计》是计算机科学与技术专业的一门选修课，本课程将覆盖计算机软件实现中的大部分算法，并具有一定的深度和广度，使学生对计算机常用算法有一个全盘的了解；本课程的任务是：培养学生具有针对给定问题设计和实现高效算法的能力。

二、教学基本要求

通过本课程教学，应使学生：

1）熟悉、掌握课堂教学中所学的大部分算法设计思想；

2）具有针对所给的问题设计和实现高效算法的能力。

三、教学内容与学时分配

四、参考教材及图书资料

1.王晓东.计算机算法设计与分析.北京:电子工业出版社

2.卢开澄.计算机算法导引——设计与分析. 北京:清华大学出版社

3.顾立尧.霍义兴.算法设计分析的理论与方法.上海:上海交通大学出版社

4.霍红卫.分布式算法导论. 北京:机械工业出版社

五、教学方法与考核

1.教学方法

为充分发挥学生的积极性、主动性，启发引导、培养学生具有自我开拓和获得知识的能力，在内容的讲授上本着“少而精”的原则，突出重点，分解难点，深入浅出，举一反三，着重培养学生分析问题和解决问题能力。并就课程的各部分内容，分别采用细讲法，培养学生的基本功；采用精讲法，培养学生主动获取知识的能力；采用引导启发式，培养学生分析问题、解决问题的能力。另不同程度采取课堂讨论式、自学提问式。

2．课程考核方法

主要有：理论课考查、作业评定。

①平时占20%:理论课考查、作业评定；

②期末考试占80%：综合笔试。

六、大纲正文

第一章 算法基础

[目的要求]

1. 了解算法与程序的概念；

2. 掌握算法复杂性分析及其有关的概念；

[基本内容]

1. 算法的定义、特征,算法与程序；

2. 冒泡排序；

3. 伪代码使用约定；

4. 算法复杂度分析；

5. 算法的运行时间；

[重点难点]

1．重点：

算法的定义与特征、冒泡排序、算法复杂度分析

2. 难点：

算法复杂度分析

[课时安排]

建议：3学时。

第二章 递归与分治策略

[目的要求]

1.理解递归的概念；

2.掌握递归方程构建的思想；

3.掌握递归方程的求解方法；

4.了解分治法的基本思想；

5.掌握二叉查找算法；

6.掌握用分治法求最大值与最小值的算法；

7.掌握Strassen矩阵算法；

8.理解整数相乘算法；

9.掌握合并排序和快速排序算法；

10.了解线性时间选择算法；

11.了解最近点对问题算法

[基本内容]

1.递归的概念；

2.递归方程构建的思想；

3.递归方程的求解方法（递归树与主方法）；

4.分治法的基本思想；

5.二叉查找算法；

6.用分治法求最大值与最小值的算法；

7.Strassen矩阵算法；

8.整数相乘算法；

9.合并排序和快速排序算法；

10.线性时间选择算法；

11.最近点对问题算法

[重点难点]

1．重点：

递归方程的求解方法（递归树与主方法）、二叉查找算法、Strassen矩阵算法、合并排序和快速排序算法

2. 难点：

递归方程构建、递归方程的求解方法（递归树与主方法）、Strassen矩阵算法、合并排序和快速排序算法、线性时间选择算法、最近点对问题算法

[课时安排]

建议：10学时。

第三章 动态规划

[目的要求]

1.掌握动态规划算法的概念和步骤；
2.掌握0-1背包问题的算法设计和分析；

3.掌握矩阵链乘算法设计和分析；
4.掌握动态规划算法的基本要素；

5.理解备忘录方法；
6.了解装配线调度问题算法设计和分析；
7.理解最长公共子序列问题算法设计和分析；
8.掌握最优二分检索树算法设计和分析。
9.了解凸多边形最优三角剖分算法；

[基本内容]

1.动态规划算法的概念和步骤；
2.0-1背包问题；

3.矩阵链乘；
4.动态规划算法的基本要素；

5.备忘录方法；
6.装配线调度问题；
7.最长公共子序列问题；
8.最优二分检索树。
9.凸多边形最优三角剖分；

[重点难点]

1．重点：

动态规划算法的概念和步骤、0-1背包问题、矩阵链乘、动态规划算法的基本要素、最优二分检索树

2. 难点：

0-1背包问题、矩阵链乘

[课时安排]

建议：8学时。

第四章 贪心法

[目的要求]

1.掌握贪心算法的概念、思想；

2.掌握贪心算法的基本要素；
3.掌握背包问题的算法设计和分析；

4.理解活动选择问题算法设计和分析；
5.理解哈夫曼编码的算法分析；

6.掌握最小生成树的Prim和Kruskal算法的设计与分析；

7.了解最小生成树的Boruvka算法的设计与分析；
8.掌握单源最短路径的Dijkstra算法的设计与分析；
9.理解贪心算法的理论基础；

[基本内容]

1.贪心算法的概念、思想；

2.贪心算法的基本要素；
3.背包问题的算法设计和分析；

4.活动选择问题算法设计和分析；
5.哈夫曼编码的算法分析；

6.最小生成树的Prim、Kruskal算法和Boruvka算法；
7.单源最短路径的Dijkstra算法；
8.贪心算法的理论基础；

[重点难点]

1．重点：

贪心算法的概念、思想、贪心算法的基本要素、背包问题、最小生成树的Prim和Kruskal算法、单源最短路径的Dijkstra算法、贪心算法的理论基础

2. 难点：

贪心算法的思想、背包问题、单源最短路径的Dijkstra算法、贪心算法的理论基础

[课时安排]

建议：7学时。

第五章 回溯法

[目的要求]

1.掌握回溯法的概念、思想；

2.掌握子集树、排列树、搜索树的构造；
3.理解N皇后问题的算法设计和分析；

4.理解子集和数问题算法设计和分析；
5.理解0-1背包问题算法设计和分析；

6.了解着色问题算法的设计与分析；

[基本内容]

1.回溯法的概念、思想；

2.子集树、排列树、搜索树的构造；
3.N皇后问题；

4.子集和数问题；
5.0-1背包问题；

6.着色问题；

[重点难点]

1．重点：

回溯法的思想、子集树的构造、排列树的构造、搜索树的构造、N皇后问题、子集和数问题、背包问题

2. 难点：

回溯法的思想、N皇后问题、子集和数问题、背包问题

[课时安排]

建议：4学时。

第六章 分枝限界法

[目的要求]

1.掌握分枝限界法的概念、思想；

2.理解0-1背包问题算法设计和分析；
3.理解作业调度问题的算法设计和分析；

[基本内容]

1.分枝限界法的概念、思想(先进先出状态空间树、优先队列状态空间树)；

2.0-1背包问题算法设计和分析；
3.作业调度问题的算法设计和分析；

[重点难点]

1．重点：

分枝限界法的思想、0-1背包问题算法设计和分析

2. 难点：

分枝限界法的思想、0-1背包问题算法设计和分析

[课时安排]

建议：4学时。

第七章 NP完全性问题

[目的要求]

1.了解NP完全性问题的概念；

2.了解P类问题和NP类问题；

3.了解NP完全问题；

4.了解一些典型的NP完全问题；

[基本内容]

1.NP完全性问题的概念；

2.P类问题和NP类问题；

3.NP完全问题；

4.一些典型的NP完全问题；

[重点难点]

1．重点：

P类问题和NP类问题、NP完全问题

2. 难点：

P类问题和NP类问题、NP完全问题

[课时安排]

建议：自学。

课程负责人：

大纲主撰人：刘斌

大纲审核人：

计算机科学技术教研室

2006．5

本文来源：https://www.2haoxitong.net/k/doc/b34fd771f02d2af90242a8956bec0975f565a460.html