文档介绍：课程编号:
“算法设计与分析”课程教学大纲
Algorithm Design and Analysis Course Outline
50学时
一、本课程的性质、目的、任务
算法设计与分析是计算机科学的重要基础,介绍常用设计算法的策略:分治,贪心,规划,回溯等,通过本课程的学****使学生掌握基本算法的分析,设计技能和方法。
通过算法设计与分析的学****和研究,能掌握算法设计的主要方法,培养对算法的计算复杂性正确分析的能力,为独立设计算法和对算法进行复杂性分析奠定坚实的基础。
本课程使学生能够切实掌握算法设计与分析的基本知识,掌握常用算法的设计策略,包括:递归与分治法,动态规划,贪心算法与回溯法。掌握计算机领域中常用的非数值计算算法,并学会用这些算法解决实际问题。
二、适用专业——计算机科学与技术
三、先修课程——C++面向程序设计、数据结构
四、课程的基本要求
通过本课程的学****学生应能达到下列要求:
1理解算法的定义及特性,了解算法与程序的区别,熟悉算法复杂性的分析。
2 理解递归的概念,掌握递归方程求解方法,掌握分治算法的设计策略。
3 了解动态规划算法的基本要素,了解态规划算法的设计方法。
4理解贪心算法的基本性质,掌握贪心算法的设计原则。
5 熟悉问题的解空间、解空间树的概念,用问题的约束条件对解空间树进行修剪、递归回溯;掌握回溯算法的设计方法。
6了解分支限界法的基本思想。
五、课程的教学内容
(一)课堂讲授的教学内容:
1算法概述
算法与程序,算法复杂性的分析。
2 递归与分治策略
递归的概念,递归方程求解方法,二分搜索技术,大数的乘法,Strassen矩阵相乘,
棋盘覆盖算法
3 动态规划
矩阵连乘问题,动态规划算法的基本要素,最长公共子序列,)凸多边形的最优三角剖分,0-1背包问题。
4贪心算法
动安排问题,贪心算法的基本性质,最优装载,哈夫曼编码,单源最短路径,多机调度
5 回溯法
回溯法的算法框架,装载问题,n后问题,图的着色算法,批处理作业调度,符号三角问题,旅行商问题。
6分支限界法
分支限界法的基本思想,单源最短路径,布线问题,旅行售货问题。
(二) 课堂讨论的教学内容
下列内容可以安排讨论课:
1 贪心算法的基本应用
2 回溯算法的基本应用
(三)实验的教学内容
1 棋盘覆盖算法 2学时