《算法设计》课程教学大纲

1、算法设计Algorithm Design一、课程基本情况课程类别：专业任选课课程学分：2 学分课程总学时：32 学时，其中讲课： 20学时，实验（含上机）： 12 学时课程性质：选修开课学期：第4学期先修课程：数据结构 适用专业：计算机科学与技术，软件工程教 材：王晓东，计算机算法设计与分析(第四版)，电子工业出版社，2013开课单位：计算机与软件学院 软件工程系二、课程性质、教学目标和任务随着计算机的广泛应用，对计算机算法的研究变得日益重要。本课程将覆盖计算机软件实现中的大部分算法，并具有一定的深度和广度，使学生对计算机常用算法有一个全盘的了解；本课程首先介绍计算复杂性的定义和算法分析的基本

2、方法，结合计算机科学及应用领域中常见的有代表性的非数值算法，介绍了几种重要的算法设计方法：分治法、动态规划、贪心法、回溯法、分支限界法以及NP完全问题。使学生在掌握各种算法的同时，掌握算法分析的基本方法和技巧。本课程的任务是：培养学生具有针对给定问题设计和实现高效算法的能力。主要包括以下三个方面：1.通过对常用的、有代表性的算法的研究，让学生理解并掌握算法设计的基本技术；2.培养学生分析算法复杂度的初步能力，锻炼其逻辑思维能力和想象力，并使之了解算法理论的发展；3.鼓励学生运用算法知识解决各自学科的实际问题，培养他们的独立科研能力和理论联系实际的能力。三、教学内容和要求第1章 算法概述（2学时

3、）1.1算法问题求解基础（1学时）（1）了解算法与程序的概念；（2）了解为什么学习算法； （3）理解问题求解过程； （4）理解系统生命周期；重点：问题求解过程、系统生命周期；难点：系统生命周期；1.2算法复杂度（1学时）（1）了解影响程序运行时间的因素； （2）理解使用程序步分析算法； （3）理解算法的空间复杂度；（3）理解算法的空间复杂度；（3）掌握使用大O记号、W记号、Q记号表示算法复杂度的方法；重点：根据程序步推算该算法的时间渐近复杂度；难点：程序步的统计以及根据程序步如何推算该算法的时间渐近复杂度；第2章 递归与分治策略（4学时）2.1递归与分治（2学时）（1）了解递归的概念； （2）

4、理解分治法的基本思想； （3）掌握分析递归算法时间复杂度的计算方法；重点：掌握分析递归算法时间复杂度的计算方法；难点：掌握分析递归算法时间复杂度的计算方法；2.2分治策略设计技巧（2学时）（1）掌握用分治策略求最大最小元问题； （2）掌握用分治策略进行二分搜索； （3）掌握用分治策略进行合并排序和快速排序；（4）掌握用分治策略完成Strassen矩阵乘法；重点：用分治策略进行合并排序和快速排序，用分治策略完成Strassen矩阵乘法；难点：用分治策略完成Strassen矩阵乘法。第3章 动态规划（4学时）3.1动态规划基本概念（2学时）（1）了解动态规划算法的概念与步骤； （2）理解动态规划算

5、法与分治法、贪心法的异同；（3）掌握动态规划算法的基本要素最优子结构性质；重叠子问题性质；（4）掌握设计动态规划算法的步骤；重点：掌握动态规划算法的基本要素：最优子结构性质；重叠子问题性质；掌握设计动态规划算法的步骤；难点：理解并掌握动态规划算法的基本要素：最优子结构性质；重叠子问题性质。3.2动态规划算法应用（2学时）（1）掌握多段图问题、关键路径问题算法的设计与分析；（2）掌握最长公共子序列问题的算法设计与分析；（3）掌握每对结点间的最短路径问题的算法设计与分析；（4）掌握0/1背包问题的算法设计与分析；重点：掌握关键路径问题算法的设计与分析；掌握0/1背包问题的算法设计与分析；难点：掌握

6、0/1背包问题的算法设计与分析；掌握最长公共子序列问题的算法设计与分析。第4章 贪心算法（3学时）4.1贪心算法概念（1学时）（1）了解贪心算法的概念； （2）理解贪心算法的基本要素最优子结构性质；贪心选择性质； 重点：理解贪心算法的基本要素：最优子结构性质；贪心选择性质；难点：理解贪心算法的基本要素：最优子结构性质；贪心选择性质；4.2贪心算法设计范例（2学时）（3）掌握最优装载问题的算法分析；（4）掌握哈夫曼编码的算法分析；（5）掌握单源最短路径的Dijkstra算法的设计与分析；（6）掌握最小生成树的Prim和Kruskal算法的设计与分析；重点：掌握最优装载问题的算法分析；掌握单源最短

7、路径的Dijkstra算法的设计与分析；难点：掌握单源最短路径的Dijkstra算法的设计与分析；第5章 回溯法（2学时）（1）了解回溯法的思想； （2）理解回溯法的算法框架； （3）掌握装载问题、批处理作业调度问题、符号三角形问题、0-1背包问题、图的着色问题的算法设计与分析方法；（4）掌握n后问题、最大团问题的回溯法的算法设计与分析；重点：掌握批处理作业调度问题、0-1背包问题、图的着色问题的算法设计与分析方法；难点：掌握批处理作业调度问题、图的着色问题的算法设计与分析方法；第6章 分支限界法（2学时）（1）了解分支限界法的基本思想； （2）理解单源最短路问题、0-1背包问题的分支限界法分

8、析； （3）掌握旅行售货员问题的算法设计与分析；重点：掌握旅行售货员问题的算法设计与分析；难点：掌握旅行售货员问题的算法设计与分析；第7章 随机化算法（1学时）（1）了解随机化算法的特征； （2）理解随机化算法的4种分类； （3）掌握产生伪随机数的算法；重点：掌握产生伪随机数的算法；难点：理解随机化算法的4种分类；第8章 NP完全问题（2学时）（1）了解NP完全性问题的概念； （2）了解P类问题和NP类问题； （3）了解NP完全问题；（4）了解一些典型的NP完全问题；（5）典型的NP完全（或NP难度）问题的证明；重点：典型的NP完全（或NP难度）问题的证明；难点：典型的NP完全（或NP难度）问题的证明；四、课程考核（1）作业等：作业：5 次；（2）考核方式：课程论文（3）总评成绩计算方式：（平时成绩*0.3+课程论文成绩*0.7=综合成绩）五、参考书目1.陈慧南. HYPERLINK /11055510.html 算法设计与分析：C+语言描述（第2版）.电子工业出版社.2012；2.吕国英.算法分析与设计.清华大学出版社.2006；3. HYPERLINK /writer/%E7%BD%97%E4%BC%AF%E7%89%B9%60%E5%A1%9E%E5%A5%87%E5%A8%81%E5%85%8B_1.html t _blank 罗伯特.塞奇