|
一、 课程名称：算法设计与分析
二、 学分：4
三、 先修课程：《高等数学》、《计算机文化基础》、《程序设计语言》、《离散数学》、《数据结构》。
四、 课程的性质、目的和任务：
《算法设计与分析》课程是网络教育学院计算机专业本科的专业必修课。这是一门面向设计的课程，要求学生。设立本课程的目的是适应21世纪我国计算机科学技术及软件工程人才培养的需要，培养学生设计和分析算法的能力。通过学习本课程，学生应该掌握计算机软件常用的几种算法，并可以对算法的复杂性进行分析，从而能够在实际工作中根据具体问题设计和优化算法。
五、 课程的教学基本要求及主要内容：
第一章 计算机算法概论
一、学习要求
通过本章的学习，要求学生了解该课程的基本框架，理解算法的概念，如何来表达算法，同时还简要介绍如何使用计算机程序设计语言来描述算法。
本章要了解算法与程序的区别，算法在计算机及软件领域的作用和地位，理解使用抽象数据来表达算法，重点掌握如何使用计算机程序设计语言来描述算法。
二、课程内容
1．算法的基本概念
2．表达算法的抽象机制
3．使用语言来描述算法
4．算法的复杂性分析
三、实践（上机）环节内容和基本要求
本章节没有安排实践和上机环节。
Ⅴ 自学安排：
第二章的内容
第二章 递归与分治策略
一、学习要求
通过本章的学习，要求学生了解递归与分治的概念及相互关系，理解递归与分治算法策略的基本思想，掌握使用递归与分治策略解决经典的问题，并对算法进行复杂性分析。
二、课程内容
1．递归的概念
（1） 递归的含义
（2） 使用递归的方法解决实际的问题
阶乘函数的递归表达式
Fabonacci数列的递归表达式
使用递归方法解决Hanoi塔问题
2．分治法的基本思想
（1） 分治的含义
（2） 分治算法的设计模式
（3） 分治法的效率分析
3．分治策略应用实例
二分搜索算法
大整数的乘法
Stassen矩阵乘法
棋盘覆盖游戏
合并排序算法
快速排序算法
三、实践（上机）环节内容和基本要求
本章节的学习安排两个课时的上机实践。
主要内容为：
1． 编制程序，使用递归的方法解决Hanoi塔问题
2． 编制程序，使用二分搜索法查找字符
3． 编制程序，使用合并排序法对一个数组中的元素进行排序
Ⅴ 自学安排：
第三章的内容
第三章 动态规划
一、学习要求
通过本章的学习，要求学生了解动态规划的基本思想，掌握设计动态规划算法的步骤，并学会使用动态规划方法分析和解决实际的问题，并对算法进行复杂性分析。
二、课程内容
1．动态规划算法介绍
（1） 动态规划算法的基本思想
（2） 动态规划算法与分治算法的区别
（3） 动态规划算法的设计步骤
（4） 动态规划算法的基本要素
2．使用动态规划算法解决实际问题
矩阵连乘问题
最长公共子序列问题
凸多边形最优三角剖分
多边形游戏
图像压缩
0-1背包问题
三、实践（上机）环节内容和基本要求
本章节的学习安排两个课时的上机实践。
主要内容为：
1． 编制程序，解决0-1背包问题
2． 编制程序，解决多边形游戏问题
Ⅴ 自学安排：
第四章的内容
第四章 贪婪算法
一、学习要求
通过本章的学习，要求学生了解贪婪法的基本思想，掌握贪婪算法的设计步骤，并学会使用贪婪算法分析和解决实际的问题，并对算法进行复杂性分析。
二、课程内容
1．贪婪算法
2．使用贪婪算法分析和解决具体问题
（1） 活动安排问题
（2） 最优装载问题
（3） 哈夫曼编码
（4） 单源最短路径
（5） 最小生成树
（6） 多机调度问题
3．贪婪算法的理论基础
三、实践（上机）环节内容和基本要求
本章节的学习安排两个课时的上机实践。
主要内容为：
1． 编制程序，解决最优装载问题
2． 编制程序，解决多机调度问题
Ⅴ 自学安排：
第五章的内容
第五章 回溯法
一、学习要求
通过本章的学习，要求学生了解回溯法的基本思想，掌握回溯算法的设计步骤，并学会使用回溯算法分析和解决实际的问题，并对算法进行复杂性分析。
二、课程内容
1．回溯算法的基本框架和基本要素
2．使用回溯算法分析和解决具体问题
（1） 最优装载问题
（2） 批处理作业调度
（3） N皇后问题
（4） 0-1背包问题
（5） 图的M着色问题
（6） 旅行售货员问题
3．回溯算法的效率分析
三、实践（上机）环节内容和基本要求
本章节的学习安排两个课时的上机实践。
主要内容为：
1． 编制程序，解决N皇后问题
2． 编制程序，解决0-1背包问题
Ⅴ 自学安排：
第六章的内容
第六章 分支限界法
一、学习要求
通过本章的学习，要求学生了解分支限界算法的基本思想，掌握分支限界算法的设计步骤，并学会使用分支限界算法分析和解决实际的问题，并对算法进行复杂性分析。
二、课程内容
1．分支限界算法的基本思想
2．使用分支限界算法分析和解决具体问题
（1） 最优装载问题
（2） 单源最短路径问题
（3） 布线问题
（4） 0-1背包问题
（5） 旅行售货员问题
（6） 批处理作业调度问题
三、实践（上机）环节内容和基本要求
本章节的学习安排两个课时的上机实践。
主要内容为：
1． 编制程序，使用分支限界算法解决装载问题
2． 编制程序，使用分支限界算法解决0-1背包问题
Ⅴ 自学安排：
第七章的内容
第七章 概率算法
一、学习要求
通过本章的学习，要求学生了解概率算法的基本思想，掌握概率算法的设计步骤，并学会使用概率算法分析和解决实际的问题，并对算法进行复杂性分析。
二、课程内容
1．概率算法的概念
2．随机数
3．数值概率算法
六、 考试方式：闭卷笔试
七、 使用教材：《算法设计与分析》；王晓东编；清华大学出版社出版。
|
