内容发布更新时间 : 2024/5/1 16:03:47星期一 下面是文章的全部内容请认真阅读。
教学大纲――算法设计与分析
《算法设计与分析》课程教学大纲
一、课程基本信息 课程名称 （中文） 课程名称 （英文） Algorithm Design 课程类型 and Analysis 4 总学时 信息与计算科学专业三年级 闭卷笔试结合实践考核，平时成绩占总成绩的百分20%、实验成绩占总成绩的20%，期末考试成绩占总成绩的60% 程序设计语言、离散数学、数据结构 64 专业选修课 算法设计与分析 学 分 适用对象 考核方式 先修课程 二、课程简介 《算法设计与分析》是信息与计算科学专业的专业选修课。算法是计算机科学的灵魂，《算法设计与分析》是一门面向设计，且处于计算机科学核心地位的课程。本课程的主要内容包括：算法概述、递归与分治策略、动态规划、贪心算法、回朔法、分枝限界法，随机化算法等。
三、课程目标
通过本课程中许多常见且有代表性算法的学习，使学生理解和掌握算法设计的主要方法，培养对算法时间复杂性进行正确分析能力，为独立的设计算法和给定算法进行复杂性分析打下良好的基础。培养学生具有针对给定问题设计和实现高效算法的能力。 四、教学内容及要求
（一）算法概述 1，教学目的与要求
（1）了解算法与程序的概念
（2）掌握算法复杂性分析及其有关的概念 （3）了解NP完全问题 2，教学内容
（1）算法与程序 （2）算法复杂性分析 （3）NP完全性理论 （二）递归与分治策略 1，教学目的与要求
（1）理解递归的概念
（2）了解分治法的基本思想 （3）掌握二分搜索技术
（4）掌握Strassen矩阵算法现 （5）了解棋盘覆盖问题的算法 （6）理解合并排序和快速排序算法
1
教学大纲――算法设计与分析
（7）了解线性时间选择算法 2，教学内容
（1）递归的概念
（2）分治法的基本思想 （3）二分搜索技术 （4）大整数的乘法 （5）Strassen矩阵乘法 （6）棋盘覆盖 （7）合并排序 （8）快速排序 （9）线性时间选择 （10）最接近点对问题 （11）循环日程表 （三）动态规划 1，教学目的与要求
（1）掌握动态规划算法的概念、步骤和基本要素 （2）掌握最长公共子序列算法设计和分析 （3）掌握矩阵的连乘算法设计和分析 （4）了解凸多边形最优三角剖分算法 （5）了解多边形游戏问题的算法分析 （6）了解图像压缩算法分析
（7）掌握电路布线问题的算法分析 （8）掌握流水作业调度
（9）了解背包问题的算法分析
（10）了解最优二叉搜索树的算法分析 2，教学内容
（1）矩阵的连乘问题
（2）动态规划算法的基本要素 （3）最长公共子序列 （4）最大子段和
（5）凸多边形最优三角剖分 （6）多边形游戏 （7）图像压缩 （8）电路布线 （9）流水作业调度 （10）0－1背包问题 （11）最优二叉搜索树 （四）贪心算法 1，教学目的与要求
（1）掌握贪心算法的概念和基本要素 （2）了解贪心算法的理论基础 （3）了解最优装载问题的算法分析 （4）了解哈夫曼编码的算法分析
（5）了解单源最短路径的Dijkstra算法的设计与分析
2
教学大纲――算法设计与分析
（6）了解最小生成树的Prim和Kruskal算法的设计与分析 2，教学内容
（1）活动安排问题
（2）贪心算法的基本要素 （3）最优装载 （4）哈夫曼编码 （5）单源最短路径 （6）最小生成树 （7）多机调度问题 （五）回溯法 1，教学目的与要求
（1）掌握回溯法的算法框架
（2）掌握批处理作业调度问题的算法设计与分析 （3）掌握n 后问题的算法设计与分析
（4）了解符号三角形问题的算法设计与分析 （5）了解背包问题的回溯法的算法分析 （6）了解最大团问题的算法设计与分析
（7）了解电路板排列问题的算法设计与分析构。 （8）了解回溯法的效率分析 2，教学内容
（1）回溯法的算法框架 （2）装载问题
（3）批处理作业调度 （4）符号三角形问题 （5）n后问题
（6）0－1背包问题 （7）最大团问题 （8）图的m着色问题 （9）旅行售货问题 （10）圆排列问题 （11）电路板排列问题 （12）连续邮资问题 （13）回溯法的效率分析 （六）分支限界法 1，教学目的与要求
（1）掌握分支限界法的基本思想
（2）掌握单源最短路问题的分支限界法分析 （3）掌握背包问题的分支限界法分析
（4）了解旅行售货员问题的算法设计与分析 2，教学内容
（1）分支限界法的基本思想 （2）单源最短路问题 （3）装载问题 （4）布线问题
3