《算法分析与设计》教学大纲
(2013版)
课程编码:0611102103
课程名称:算法分析与设计
学时/学分:48/3
先修课程:《程序设计基础》、《数据结构》
适用专业:计算机科学与技术
开课教研室:软件工程教研室
执笔:
审定:
一、课程性质与任务
1.课程性质:
算法设计与分析是一门理论性与实践性兼顾的课程,是与计算科学专业的重要课程之一;为专业选修课。
2.课程任务
通过本课程的学习,应使学生掌握算法分析方法,掌握蛮力法、分治法、减治法、动态规划法、贪心法、回溯法分支限界法等算法设计技术,通过不同的算法设计技术在同一问题中的应用进行比较,牢固掌握算法设计技术的基本策略,深刻体会算法设计技术的思想方法,综合利用多种算法设计技术更有效地解决问题。
二、课程教学基本要求
学生通过学习该课程后,让学生掌握算法分析与设计的基本理论;理解并掌握算法设计的基本技术。培养学生分析算法复杂度的初步能力,锻炼其逻辑思维能力和想象力,并使之了解算法理论的发展。鼓励学生运用算法知识解决各自学科的实际问题,培养学生的独立科研的能力和理论联系实践的能力。
本课程共计学时:48,理论学时32,实践学时16。
成绩考核形式:末考成绩(闭卷机试考查)(70%)+平时成绩(平时测验、作业、实验、课堂讨论等)(30%)。成绩评定采用百分制,60分为及格。
三、课程教学内容
第一章 算法设计基础
1.教学基本要求
使学生初步认识课程的性质与作用,激发课程学习热情。
2.要求学生掌握的基本概念、理论、技能
通过本章教学使学生了解算法的概念,描述方法;了解常见的重要问题类型。
3.教学重点和难点
教学重点和难点是算法设计的一般过程。
4.教学内容
(1)算法的基本概念
主要知识点:算法及其重要特性;算法的描述方法;算法设计的一般过程。
(2)为什么要学习和研究算法
主要知识点:算法在问题求解中的地位;算法训练能够提高计算思维能力;算法研究是推动计算机技术发展的关键。
(3)重要的问题类型
主要知识点:查找问题;排序问题;图问题;组合问题。
第二章 算法分析基础
1.教学基本要求
掌握算法复杂度的分析方法。
2.要求学生掌握的基本概念、理论、技能
通过本章教学使学生掌握算法的时间和空间复杂度。
3.教学重点和难点
教学重点是时间复杂度分析。教学难点是递归和非递归算法的时间复杂度分析。
4.教学内容
(1)算法的时间复杂性分析
主要知识点:输入规模与基本语句;算法的渐进分析;最好、最坏和平均情况;非递归算法的时间复杂性分析;递归算法的时间复杂性分析。
(2)算法的空间复杂性分析
主要知识点:算法的空间复杂性分析。
(3)最优算法
主要知识点:问题的计算复杂性下界;平凡下界;判定树模型。
第三章 蛮力法
1.教学基本要求
掌握利用蛮力法解决问题的基本思想,会用某高级语言对算法进行描述,并对算法复杂度(时间和空间)进行分析。
2.要求学生掌握的基本概念、理论、技能
通过本章教学使学生掌握蛮力法的设计思想、时间性能以及查找、排序、图问题和组合问题中的蛮力法。
3.教学重点和难点
教学重点是蛮力法的几种情况和解题步骤。教学难点是组合问题中的蛮力法。
4.教学内容
(1)概述
主要知识点:蛮力法的设计思想;一个简单的例子-百元买百鸡问题。
(2)查找问题中的蛮力法
主要知识点:顺序查找;串匹配。
(3)排序问题中的蛮力法
主要知识点:选择排序;起泡排序。
(4)组合问题中的蛮力法
主要知识点:0/1背包问题;任务分配问题。
(5)图问题中的蛮力法
主要知识点:TSP问题;任务分配问题。
第四章 分治法
1.教学基本要求
掌握利用分治法解决问题的基本思想,会用某高级语言对算法进行描述,并对算法复杂度(时间和空间)进行分析。
2.要求学生掌握的基本概念、理论、技能
通过本章教学使学生掌握分治法的设计思想、求解步骤、时间性能、适用条件以及排序、组合问题中的分治法。
3.教学重点和难点
教学重点是分治法的设计思想、求题步骤、适用条件。教学难点是组合问题中的分治法。
4.教学内容
(1)概述
主要知识点:分治法的设计思想;一个简单的例子-数字旋转方阵。
(2)排序问题中的分治法
主要知识点:归并排序。
(3)组合问题中的分治法
主要知识点:最大子段和问题;棋盘覆盖问题。
第五章 减治法
1.教学基本要求
掌握利用减治法解决问题的基本思想,会用某高级语言对算法进行描述,并对算法复杂度(时间和空间)进行分析。
2.要求学生掌握的基本概念、理论、技能
通过本章教学使学生掌握减治法的设计思想、时间性能,与分治法的区别,以及查找、排序、组合问题中的减治法。
3.教学重点和难点
教学重点是减治法的设计思想,与分治法的区别。教学难点是组合问题中的减治法。
4.教学内容
(1)概述
主要知识点:减治法的设计思想;一个简单的例子--两个序列的中位数。
(2)查找问题中的减治法
主要知识点:折半查找;二叉查找树;选择问题。
(3)排序问题中的减治法
主要知识点:插入排序;堆排序。
(4)组合问题中的减治法
主要知识点:淘汰赛冠军问题;假币问题。
第六章 动态规划法
1.教学基本要求
掌握利用动态规划方法解决问题的基本思想;学会如何将问题化为多阶段图的方法;能对具体问题写出正确的递推公式。
2.要求学生掌握的基本概念、理论、技能
通过本章教学使学生掌握多阶段决策过程、最优性原理,掌握动态规划法的设计思想、求解步骤、时间性能、以及图、组合和查找问题中的动态规划法。
3.教学重点和难点
教学重点是把握动态规划法的设计思想、求解步骤、组合问题中的动态规划法。教学难点是最长递增子序列问题。
4.教学内容
(1)概述
主要知识点:多阶段决策过程;动态规划法的设计思想;一个简单的例子--数塔问题。
(2)图问题中的动态规划法
主要知识点:多段图的最短路径问题;多源点最短路径问题;TSP问题。
(3)组合问题中的动态规划法
主要知识点:最长递增子序列问题;最长公共子序列问题;0/1背包问题。
(4) 查找问题中的动态规划法
主要知识点: 最优二叉查找树;近似串匹配问题。
第七章 贪心法
1.教学基本要求
掌握利用贪心算法解决问题的基本思想;会用某高级语言编写用贪心算法解决问题的程序,并能对算法的复杂度,可靠性进行分析。
2.要求学生掌握的基本概念、理论、技能
通过本章教学使学生掌握贪心算法的设计思想、时间性能,能够用贪心法解决背包问题、多机调动、TSP等实际应用问题。
3.教学重点和难点
教学重点是贪心法的设计思想、组合问题中的贪心法。教学难点是组合问题中的贪心法。
4.教学内容
(1)概述
主要知识点:贪心法的设计思想;一个简单的例子--埃及分数。
(2) 图问题中的贪心法
主要知识点:TSP问题;图着色问题;最小生成树问题。
(3) 组合问题中的贪心法
主要知识点:背包问题;活动安排问题;多机调度问题。
第八章 基于搜索的算法设计技术
1.教学基本要求
掌握利用回溯法解决问题的基本思想,并能用此方法解法实际的应用问题。
2.要求学生掌握的基本概念、理论、技能
通过本章教学使学生了回溯算法的设计思想、时间性能,能够用回溯法解决:n个皇后问题,图的m着色问题,批处理作业调度问题等,并能准确地分析回溯法的效率及稳定性。
3.教学重点和难点
教学重点是回溯法的设计思想、图的m着色问题,批处理作业调度问题。教学难点是图着色问题、哈密顿回路问题。
4.教学内容
(1)概述
主要知识点:问题的解空间树;回溯法的设计思想;回溯法的时间性能;一个简单的例子——素数环问题。
(2)图问题中的回溯法
主要知识点:图着色问题;哈密顿回路问题。
(3)组合问题中的回溯法
主要知识点:八皇后问题;批处理作业调度问题。
第九章 分支限界法
1.教学基本要求
掌握利用分支限界法解决问题的基本思想,并能用此方法解法实际的应用问题。
2.要求学生掌握的基本概念、理论、技能
通过本章教学使学生掌握分支限界法的设计思想、时间性能,与回溯法的区别以及图问题和组合问题中的分支限界法。
3.教学重点和难点
教学重点是分支限界法的设计思想,与回溯法的区别,0/1背包问题,批处理作业调度。教学难点是图的TSP问题,0/1背包问题。
4.教学内容
(1)概述
主要知识点:分支限界法的设计思想;分支限界法的时间性能;简单的例子—圆排列问题。
(2) 图问题中的分支限界法
主要知识点:TSP问题;多段图的最短路径问题。
(3)组合问题中的分支限界法
主要知识点:0/1背包问题;任务分配问题;批处理作业调度问题。
四、学时分配表
理论部分:
章序 |
内容 |
课时 |
备注 |
一 |
算法设计基础 |
1 |
|
二 |
算法分析基础 |
1 |
|
三 |
蛮力法 |
2 |
|
四 |
分治法 |
6 |
|
五 |
减治法 |
2 |
|
六 |
动态规划法 |
6 |
|
七 |
贪心法 |
4 |
|
八 |
回溯法 |
5 |
|
九 |
分支限界法 |
5 |
|
合计 |
32 |
|
实践部分:
序号 |
项目 名称 |
内容提要 |
学时 |
必/选开 |
1 |
递归算法 |
任意输入一串整数或字符,输出结果能够用递归方法实现整数或字符的全排列。 |
2 |
必开 |
2 |
分治法算法 |
循环为n个运动员进行单循环赛编写比赛日程 |
2 |
必开 |
3 |
动态规划算法 |
三角形问题:给定一个由n行数字组成的数字三角形,设计一个算法,计算出从三角形的顶至底的一条路径,是该路径经过的数字 |
2 |
必开 |
4 |
动态规划算法 |
0-1背包问题 |
2 |
必开 |
5 |
贪心算法 |
键盘输入一个正整数n,去掉任意s个数字后剩下的数字按原左右次序将组成一个新的正整数。编程对给定的n和s,寻找一种方案,使得剩下的数最小。 |
2 |
必开 |
6 |
回溯算法 |
工作分配问题:设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij。试设计一个算法为每一个人都分配1件不同的工作,并使总费用达到最小。 |
2 |
必开 |
7 |
回溯算法 |
0-1背包问题 |
2 |
必开 |
8 |
分支限界算法 |
0-1背包问题 |
2 |
必开 |
合计 |
16 |
|
五、主用教材及参考书
(一)主用教材:
《算法设计与分析》主编:王红梅、胡明 出版社:清华大学出版社 出版时间:2013年。
(二)参考书:
1. 《计算机算法设计与分析》主编:王晓东 出版社:电子工业出版社 出版时间:2012年。
2.《算法设计与分析》主编:屈婉玲、刘田、张立昂 出版社:清华大学出版社 出版时间:2011年。
3.《算法设计与分析》 主编:吕国英 出版社:清华大学出版社 出版时间:2008年。
4.《算法设计与分析》 主编:郑宗汉、郑晓明 出版社:清华大学出版社 出版时间:2011
年。