算法分析与设计 算法设计与分析的教与学（教学大纲）

课程代码:* * * *

课程负责人:* * * *

课程中文名称:算法设计与分析

课程的英文名称:算法设计与分析

课程类别:必选

课程分数:3

课时:54

教学目标:计算机科学与技术及相关专业本科

本课程的主导课程:高等数学、离散数学、数据结构

一、教学目的(Bold号)

本课程是计算机科学与技术专业的必修课。本课程的目的是培养学生分析问题和解决问题的能力，使学生掌握算法设计的基本技能和方法，熟悉算法分析的基本技术，熟练运用一些常用算法，解决一些综合性问题，为学生进一步学习后续课程打下良好的基础。

二、教学要求(黑体5号)

通过课堂教学、课堂实践与讨论互动、课后作业和计算机实验，系统介绍了计算机算法的概念和算法设计的基本技巧。使学生掌握计算机算法的基本概念和特点，了解算法分析和设计技巧在计算机相关学科中的重要性，掌握算法时间复杂度的分析方法和基本算法设计策略，并结合具体实例使学生重点关注分而治之法、蛮力法、回溯法、分支定界法、贪心法、动态规划法、网络流、几何计算、概率算法、近似算法等常见算法设计策略，了解计算复杂度的基本理论，并有灵活运用所学知识的能力。

三.课程内容和时间分配(粗体5号)

1.算法设计与分析导论。本文介绍了算法的概念、算法分析方法以及STL在算法设计中的应用。

2.递归算法设计技术。介绍了递归的概念、递归算法的设计方法及相关实例、递归算法到非递归算法的转换以及递归公式的计算。

3.分而治之。介绍了分治法的策略和求解过程，讨论了分治法求解排序问题、搜索问题、最大连续子序列和问题、大整数乘法问题和矩阵乘法问题的典型算法，并简要介绍了并行计算的概念。

4.暴力方法。介绍了蛮力方法的特点、蛮力方法的基本应用实例、递归在蛮力方法中的应用实例以及图的深度优先和广度优先遍历算法。

5.追溯法。介绍了solution 空的概念和回溯法的算法框架，讨论了用回溯法求解0/1背包问题、装载问题、子集与问题、N皇后问题、图的M着色问题、任务分配问题、活动安排问题和流水车间调度问题的典型算法。

6.分支定界法。介绍了分支定界法、队列型分支定界法和优先级队列型分支定界法的特点和算法框架，讨论了求解0/1背包问题、图的单源最短路径、任务分配问题和流水车间调度问题的典型算法。

7.贪婪法。介绍了贪心法求解问题的策略、求解过程和性质，讨论了用贪心法求解活动调度问题、背包问题、最优装载问题、田忌赛马问题、多机调度问题、霍夫曼编码和流水车间调度问题的典型算法。

8.动态规划。介绍了动态规划的原理和求解步骤，讨论了求解整数分裂问题、最大连续子序列和问题、三角形最小路径问题、最长公共子序列问题、最长递增子序列问题、编辑距离问题、0/1背包问题、完全背包问题、资源分配问题、会议安排问题和滚动数组问题的典型算法。

9.图形算法设计。讨论了构造图的最小生成树的两种算法(Prim和Kruskal算法，以及搜索集的应用)和寻找图的最短路径的四种算法(Dijkstra、Bellman-Ford、SPFA和Floyd)，并采用五种算法求解旅行商问题(TSP问题)。最后，介绍了网络流的相关概念以及求最大流和最小费用最大流的算法。

10.几何计算。介绍了几何计算中常用的向量运算，以及求解凸包问题、最近点对问题和最远点对问题的典型算法。

11.计算复杂性理论介绍。介绍了图灵机计算模型、P类和NP类问题以及NPC问题。

12.概率算法和近似算法。介绍了这两种算法的特点和基本算法设计方法。

课程内容和课时分配表

内在内容

学习时间

1.算法设计与分析导论

四

2.递归算法设计技术

四

3.分而治之

四

4.强力法

四

5.追溯方法

六

6.分支定界法

四

7.贪婪方法

四

8.动态规划

六

9.图形算法设计

八

10.几何计算

四

11.计算复杂性理论导论

三

12、概率算法和近似算法

三

四、考核方法(加粗五项)

课堂练习，课后作业，期末考试，计算机实验。

动词 （verb的缩写）推荐书籍

算法设计与分析(第二版)

其他相关教材