《算法分析与设计》教学大纲
大纲说明
课程代码：3235058 总学时：32学时（讲课32学时） 总学分：2
课程类别：限制性选修课
适用专业：本大纲适用于计算机科学与技术专业使用 预修要求：高等数学、C语言程序设计、数据结构
课程的性质、目的、任务：
本课程是计算机科学与技术专业选修课。通过本课程的学习，使学生理解和掌握算法设计的主要方法，培养学生对算法复杂性进行正确分析的基本能力，为独立地设计求解问题的最优算法和对给定算法进行复杂性分析奠定坚实的基础。 课程教学的基本要求：
算法分析与设计是一门理论性较强的课程，是计算机科学与计算机应用的核
心。本课程主要介绍算法设计的基本方法，其先修课为高等数学、程序设计、数据结构。通过本课程的学习，能够在掌握算法设计基本方法的基础上，加深对计算机领域中常用的非数值算法的理解和应用。
该课程采用教师授课和学生自学相结合的教学方法，以教师授课为主，结合理论知识，通过具体算法来论证，加深理解。在授课过程中采用多媒体课件进行操作演示，帮助学生进一步理解和掌握。 大纲的使用说明：
本教学大纲供计算机科学与技术专业使用，若学时小于32或大于32则可以根据教学实际酌情取舍有关的内容。
第一章：导引与基本数据结构 学时：4学时
通过本章的学习，使学生理解算法的概念及其特性，学会分析算法的一般方法，掌握计
大纲正文
算机科学中常用的数据结构，了解本教材描述算法所用的语言。另外，若学过数据结构的可跳过1.4节。
本章讲授要点：算法、分析算法、用SPARKS语言写算法、基本数据结构和递归和消去递归
重点：算法及分析算法 难点：递归和消去递归 第一节：算法 第二节：分析算法
第三节：用SPARKS语言写算法 第四节：基本数据结构 第五节：递归和消去递归 习题：书后习题一
第二章：分治法 学时：4学时
通过本章的学习，使学生理解分治法的内涵，然后从解决计算机科学和应用中出现的几个实际问题入手，用二分法的基本思想描述了几个经典的精巧的算法，包括二分检索算法、分类算法、选择算法等，同时对每个算法给出了数量级的分析，以使学生理解本章介绍的算法，并能用于解决实际问题。
本章讲授要点：一般方法、分治检索、找最大和最小元素、归并分类、快速分类、选择问题和斯特拉森矩阵乘法
重点：分治法的一般方法、归并分类和快速分类算法 难点：快速分类算法、选择问题算法 第一节：一般方法 第二节：分治检索 第三节：找最大和最小元素 第四节：归并分类 第五节：快速分类 第六节：选择问题 第七节：斯特拉森矩阵乘法 习题：书后习题二
第三章：贪心方法 学时：4学时
通过本章的学习，使学生理解并掌握贪心方法,然后用贪心设计策略解决背包问题、作业排序问题、归并问题、最小生成树问题、最短路径问题，并给出了相应的算法，要求学生理解这些算法。
本章讲授要点：一般方法、背包问题、带有限期的作业排序、最优归并模式、最小生成 树和单源点最短路径
重点：贪心设计策略的一般方法，归并算法、最小生成树算法 难点：最小生成树算法、最短路径算法 第一节：一般方法 第二节：背包问题
第三节：带有限期的作业排序 第四节：最优归并模式 第五节：最小生成树 第六节：单源点最短路径 习题：书后习题三
第四章：动态规划 学时：8学时
通过本章的学习，使学生理解并掌握动态规划的一般方法，理解用动态规划解决多段图、每对结点之间的最短路径、最优二分检索树等问题的算法。
本章讲授要点：一般方法、多段图、每对结点之间的最短路径、最优二分检索树、0/1 背包问题、可靠性设计、货郎担问题和流水线调度问题
重点：动态规划的一般方法、最优二分检索树、0/1背包问题、可靠性设计 难点：多段图、最优二分检索树、流水线调度问题 第一节：一般方法 第二节：多段图
第三节：每对结点之间的最短路径 第四节：最优二分检索树 第五节：0/1背包问题 第六节：可靠性设计 第七节：货郎担问题 第八节：流水线调度问题 习题：书后习题四
第五章：基本检索与周游方法 学时：6学时
通过本章的学习，使学生理解并掌握基本检索与周游的一般方法，理解代码最优化的概念与方法，理解双连通分图、深度优先检索、与/或图和对策树的有关概念并掌握相应的算法。
本章讲授要点：一般方法、代码最优化、双连通分图和深度优先检索、与/或图和对策树
重点：基本检索与周游的一般方法、代码最优化 难点：基本检索与周游的一般方法、代码最优化、对策树 第一节：一般方法 第二节：代码最优化
第三节：双连通分图和深度优先检索 第四节：与/或图 第五节：对策树 习题：书后习题五
第六章：回溯法 学时：6学时
通过本章的学习，使学生理解并掌握回溯的一般方法，掌握用回溯法解决8-皇后问题、
子集和数的问题、图着色问题、哈密顿环问题、背包问题的方法，并理解相应的算法，了解相应算法的效率。
本章讲授要点：一般方法、8-皇后问题、子集和树的问题、图的着色、哈密顿环和背包问题
重点：回溯的一般方法、8-皇后问题、图的着色 难点：8-皇后问题、图的着色 第一节：一般方法 第二节：8-皇后问题 第三节：子集和树的问题 第四节：图的着色 第五节：哈密顿环 第六节：背包问题 习题：书后习题六
本课程对学生自学的要求：
学生在自学本课程时应根据算法分析发展的最新情况，随时了解最新的算法。在学习中遇到困难能充分利用网络或书籍查阅相关信息，解决实际问题。
课时数分配表： 章节 第一章 第二章 第三章 第四章 第五章 第六章
考核方式与要求：
采用开卷的方式与平时成绩相结合。期末考试占总成绩的70％，平时成绩占30％，可根据考勤和作业进行记分。
推荐教材与参考书目：
教材：余祥宣等编著，《计算机算法基础》（第二版），华中理工大学出版社。 参考书目：
1、算法与数据结构.傅清祥、王晓东.电子工业出版社.2001 2、徐士良编，C 常用算法程序集，清华大学出版社，1998。 3、并行算法引论.陈景良.石油工业出版社.1992
章名 导引与基本数据结构 分治法 贪心方法 动态规划 基本检索与周游方法 回溯法 合计：32 教学时数 4 4 4 8 6 6 32