科目编号：****
课程负责人：****
课程中文名称：算法设计与分析
课程英文名称：Design and Analysis of Algorithms
课程类别：必修
课程学分数：3
课程学时：54
教学对象：计算机科学与技术及相关专业本科生
本课程的先决条件：高等数学、离散数学、数据结构
一、教学目的（加粗五字）
本课程是计算机科学与技术专业的必修课。 本课程的目的是培养学生分析问题和解决问题的能力计算机算法设计与分析，使学生掌握算法设计的基本技能和方法，熟悉算法分析的基本技巧，并能熟练运用某些算法。常用的算法来解决一些比较综合的问题。 为学生进一步学习后续课程打下良好的基础。
2. 教学要求（粗体5）
通过课堂讲授、课堂练习与讨论互动、课后作业、计算机实验等教学方式，系统介绍计算机算法相关概念和算法设计的基本技能。 使学生掌握计算机算法的基本概念和特点，理解算法分析和设计技能在计算机相关学科中的重要性，掌握算法时间复杂度的分析方法和基本的算法设计策略，结合具体问题实例，使学生重点掌握治理法、蛮力法、回溯法、分支定界法、贪心法、动态规划法、网络流、几何计算、概率算法、近似算法等常用算法设计策略，了解计算基础理论复杂性，并有能力灵活运用所有 学习解决实际应用问题的能力。
三、课程内容及课时分配（粗体5）
1. 算法设计与分析简介。 介绍了算法的概念、算法分析方法以及STL在算法设计中的应用。
2.递归算法设计技术。 介绍了递归的概念、递归算法的设计方法及相关实例、递归算法向非递归算法的转换、递归计算。
3.分而治之。 介绍了分治的策略和求解过程，讨论了排序问题、搜索问题、最大连续子序列求和问题、大整数乘法问题和矩阵乘法问题的典型算法，并简要介绍了并行计算的概念。
4、暴力破解法。 介绍了暴力法的特点、暴力法的基本应用实例、递归在暴力法中的应用实例、图的深度优先和广度优先遍历算法。
5.回溯法。 介绍解空间的概念和回溯法的算法框架，讨论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.概率算法和近似算法。 介绍了这两类算法的特点和基本的算法设计方法。
课程内容及课时分配表
内容
小时
一、算法设计与分析简介
4个
2.递归算法设计技术
4个
3.分而治之
4个
4.蛮力
4个
5.回溯法
6个
6. 分支定界法
4个
7.贪心法
4个
8.动态规划
6个
9.图算法设计
8个
10.几何计算
4个
11. 计算复杂性理论简介
3个
12.概率算法和逼近算法
3个
4.评估方法（粗体5号）
课堂练习、作业、期末考试、电脑实验。
5. 推荐书籍
《算法设计与分析（第2版）》
本书特色
提供20小时的微课视频。 PPT课件、源代码、教学大纲、所有练习题参考答案、计算机实验题和在线编程题
《数据结构教程（第5版）最新版》
新版提供50小时微课视频。 PPT课件、源代码、教学大纲、练习参考答案
数据结构是一门应用性和实践性很强的课程。 学生在掌握了各种数据结构（尤其是存储结构）后，要尽可能多地在计算机上进行练习计算机算法设计与分析，通过更多的实验将难以理解的抽象概念进行转化。 它是可以在计算机上执行的真实程序，从而将所学知识与实际应用相结合，吸取算法的设计思想和精髓，提高运用这些知识解决实际问题的能力。 因此，本教程突出计算机实践内容，书中给出了大量计算机实验题（分为验证实验、设计实验、综合实验）供师生选择。
《（西装）命中招聘——深度剖析程序员面试笔试（C语言、C++语言、数据结构、算法设计）》
其他相关教材
