课程代码:****

课程负责人: ****

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

课程英文名称:Designand Analysis of Algorithms

课程类别:必修

课程学分数:3

课程学时数:54

授课对象:计算机科学与技术及相关专业本科

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

一、教学目的(黑体五号)

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

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

通过课堂讲授、课堂练习和讨论互动、课后作业和上机实验等教学手段，系统介绍计算机算法的有关概念和算法设计的基本技巧。使学生掌握计算机算法的基本概念和特性，了解计算机相关学科中算法分析与设计技巧的重要性，掌握算法时间复杂性的分析方法和基本的算法设计策略，结合具体问题实例，使学生重点掌握分治法、蛮力法、回溯法、分支限界法、贪心法、动态规划法、网络流、几何计算和概率算法及近似算法等常见的算法设计策略，了解计算复杂性基本理论，具备灵活运用所学解决实际应用问题的能力。

三、课程内容与学时分配(黑体五号)

1. 算法设计与分析概论。介绍算法的概念、算法分析方法和STL在算法设计中的应用。

2. 递归算法设计技术。介绍递归的概念、递归算法设计方法和相关示例、递归算法到非递归算法的转化以及递推式的计算。

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

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

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

6. 分枝限界法。介绍分枝限界法的特点和算法框架，队列式分枝限界法和优先队列式分枝限界法，讨论采用分枝限界法求解0/1背包问题、图的单源最短路径、任务分配问题和流水作业调度问题的典型算法。

7. 贪心法。介绍贪心法的策略、求解过程和贪心法求解问题应具有的性质，讨论采用贪心法求解活动安排问题、背包问题、最优装载问题、田忌赛马问题、多机调度问题、哈夫曼编码和流水作业调度问题的典型算法。

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

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

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

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

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

课程内容与学时分配表

四、考核方式(黑体五号)

课堂练习、课后作业、期末考试、上机实验。

五、推荐图书

《算法设计与分析(第2版)》

本书特色

提供20小时微课视频。PPT课件，源码，教学大纲，全部练习题、上机实验题和在线编程题的参考答案

由浅入深，循序渐进。每种算法策略从设计思想、算法框架入手，由易到难地讲解经典问题的求解过程，使读者既能学到求解问题的方法，又能通过对算法策略的反复应用，掌握其核心原理，以收到融会贯通之效。

示例丰富，重视启发。教程中列举大量的具有典型性的求解问题，深入剖析采用相关算法策略求解的思路，展示算法设计的清晰过程，并举一反三，启发学生学习算法设计的兴趣。

注重求解问题的多维性。同一个问题采用多种算法策略实现，如0/1背包问题采用回溯法、分枝限界法和动态规划求解，旅行商问题采用5种算法策略求解。通过不同算法策略的比较，使学生更容易体会到每一种算法策略的设计特点和各自的优缺点，以提高算法设计的效率。

强调实验和动手能力的培养。算法讲解不仅包含思路描述，而且以C/C++完整程序的形式呈现，同时给出了大量的上机实验题和在线编程题，大部分是近几年国内外著名IT企业面试笔题(谷歌、微软、阿里巴巴、腾讯、网易等)和ACM竞赛题。通过这些题目的训练，不仅提高编程能力，还可以直面求职市场。

《数据结构教程(第5版)最新版》

新版提供50小时微课视频。PPT课件，源码，教学大纲，习题参考答案

数据结构是一门应用实践性非常强的课程，学生在掌握各种数据结构(特别是存储结构)的基础上一定要尽可能多地上机实习，通过较多的实验把难以理解的抽象概念转化为实实在在的能够在计算机上执行的程序，这样才能将所学知识和实际应用结合起来，吸取算法的设计思想和精髓，提高运用这些知识解决实际问题的能力。因此，本教程突出上机实习内容，书中给出了大量的上机实验题(分为验证性实验、设计性实验和综合性实验)供教师和学生选用。

《(套装)直击招聘--程序员面试笔试深度解析(C语言、C++语言、数据结构、算法设计)》

其他相关教材