南昌大学本科课程教学大纲doc.docx
《南昌大学本科课程教学大纲doc.docx》由会员分享，可在线阅读，更多相关《南昌大学本科课程教学大纲doc.docx（12页珍藏版）》请在冰点文库上搜索。
南昌大学本科课程教学大纲doc
南昌大学本科课程教学大纲
课程名称
算法设计与分析
课程英文名称
AlgorithmstoDesignondAnolysis
课程编码
Z6110X0031
课程性质
（用■表示）
□1类通识教育课程口II类通识教育课程
□学科基础课程口专业主干课程
■专业选修课程口创新创业类课程
学分
总学时
理论
实验学时
实践（学时/周数）
课内学时
课外学时
48
32
16
开课院系
信息工程学院计算机科学与技术系
面向专业
计算机系各专业
先修课程
高级语言程序设计、高等数学（数学分析）、数据结构
课程关键词
算法、算法复杂性、递归与分治法、排序问题、贪婪法、动态规划法、回溯法
授课教师基本信息
课程负责人
姓名
教师工号
性别
出生年月
职称
学历/学位
邱桃荣
021029
男
1964-12
教授
研究生/博士
其他主讲教师
薛之昕
004488
男
1966-12
副教授
研究生/硕士
江顺亮
004529
男
1965-11
教授
研究生/博士
教材及参考资料
1、算法设计与分析，郑宗汉、郑晓明编著，清华大学岀版社，
2011,978-7-302-25198-9
2、算法设计与分析，张德富编著，国防工业岀版社，2009,,978-7-118-06308-0
课程简介
（中文）
《算法设计与分析》是计算机科学与技术专业的专业选修课。
在计算科学及计算实践中，算法都在其中扮演着重要角色，软件的效率和稳定性取决于软件中所采用的算法。
本课程的教学目的是讲授在计算机应用中常遇到的实际问题的解决方法，讲授设计和分析各种算法的基本原理、方法和技术。
通过本课程的学习，培养学生对算法复杂性进行正确分析的能力，开阔编程思路，编写岀优质程序。
知识贡献：
专业知识
能力贡献：
发现问题、分析问题、解决问题能力、逻辑思维能力、实践能力
素质贡献：
国际视野、团队合作
课程简介（英文）
DesignandAnalysisofAlgorithmsisanelectivecourseforundergraduateswhomajorincomputerscienceandtechnology.Algorithmplaysanimportantroleininthescienceandcomputingpractice.Theefficiencyandstabilityofthesoftwaredependsonthealgorithmadoptedinthesoftware.Theteachingpurposeofthiscourseistoteachthesolutionofpracticalproblemsoccurringincomputerapplicationandthedesignandanalysisofbasicprinciples,methodsandtechniquesofthealgorithm・Throughlearningthiscourse,theabilityofstudentstoanalyzethecomplexityofalgorithmscorrectlyisabletobecultivated.Fuilhermore,theprogrammingideascanbebroadenedsoastowritehighqualityprograms.
教学目的
通过对常用的、有代表性的算法的研究，让学生理解并掌握算法设计的基本技术，培养学生分析算法复杂性的初步能力，锻炼学生逻辑思维能力和想象力，并使之了解算法理论的发展。
鼓励学生运用算法设计与分析的知识和能力解决学科中的实际问题，培养学生的独立科研的能力和理论联系实践的能力。
课程内容
第1章算法的基本概念
教学内容：
1.1引言
1」」算法的定义和特征
算法设计的例子，穷举法
1」.3算法复杂性分析
1.2算法的时间复杂性
121算法的输入规模和运行时间的阶
1.2.2运行时间的上界，0记号
1.2.3运行时间的下界，。
记号
1.2.4运行时间的准确界，G）记号
教学重点：
算法、算法设计和分析的基本概念，算法复杂性概念及度量。
教学难点：
算法复杂性度量。
课后作业：
（1）阅读教材对应部分内容；
（2）练习教材P17的习题1、3、5、7、8o
第2章算法的时间复杂性分析
教学内容：
2.1常用函数和公式
2.1.1整数函数
2.1.2
对数函数
2.1.3
排列、组合和二项式多项式
2.1.4
级数求和
2.2算法的时间复杂性分析
2.2.1
循环次数的统计
2.2.2
基本操作频率的统计
2.2.3
计算步的统计
2.3最好、最坏和平均情况分析
2.3.1最好情况、最坏情况和平均情况
2.3.2最好情况和最坏情况分析
2.3.3平均情况分析
教学重点：
算法的时间复杂性分析、算法最好最坏和平均情况分析。
教学难点：
算法时间复杂性分析的方法：
循环次数统计、基本操作频率的统计、计算步的统计。
课后作业：
（1）阅读教材对应部分内容；
（2）练习教材P55的习题1、2。
第3章排序问题和离散集合问题的操作
教学内容：
3.1合并排序
3.1.1合并排序算法的实现
3」.2合并排序算法的分析
3.2基于堆的排序
3.2.1
堆
3.2.2
堆的操作
3.2.3
堆的建立
3.2.4
堆的排序
3.3基数排序
3.3.1基数排序算法的思想方法
3.3.2基数排序算法的实现
3.3.3基数排序算法的分析
3.4离散集合的Union_Find操作
3.4.1用于Union_Find操作的数据结构
3.4.2union、find操作及路径压缩
教学重点：
理解如何对合并排序算法、堆排序算法和基数排序算法的算法设计与时间复杂性分析。
教学难点：
三种排序算法的时间复杂性分析。
课后作业：
（1）阅读教材对应部分内容；
（2）练习教材P80的习题1、4、7、9o
第4章递归和分治
教学内容：
4.1基于归纳的递归算法
4.1.1基于归纳的递归算法的思想方法
4.1.2递归算法的例子
4.1.3排列问题的递归算法
4.1.4求数组主元素的递归算法
4.1.5整数划分问题的递归算法
4.2分治法
4.2.1分治法的例子
4.2.2分治法的设计原理
4.2.3快速排序
4.2.4多项式乘积和达整数乘法
教学重点：
理解和掌握基于归纳的递归算法。
教学难点：
递归算法的设计原理和算法实现。
课后作业：
（1）阅读教材对应部分内容；
（2）练习教材P136的习题2、3、4、6、8、13。
第5章贪婪方法
5.1贪婪法引言
5.1.1贪婪法的设计思想
5.1.2贪婪法的例子--货郎担问题
5.2背包问题
5.2.1背包问题贪婪算法的实现
5.2.2背包问题贪婪算法的分析
5.3单源最短路径问题
5.3.1解最短路径的狄斯奎偌算法
5.3.2狄斯奎偌算法的实现
5.3.3狄斯奎偌算法的分析
5.4最小花费生成树问题
5.4.1引言
5.4.2Kruskal算法
5.4.3Prim算法
教学重点：
理解贪婪方法的基本概念、设计思想，通过具体实例介绍贪婪方的设计原理。
教学难点：
贪婪算法的设计原理和算法分析。
课后作业：
（1）阅读教材对应部分内容；
（2）练习教材P164的习题1、2、3、4O
第6章动态规划
教学内容：
6.1动态规划的思想方法
6.1.1动态规划的最优决策原理
6」.2动态规划方法实例--货郎担问题
6.2多段图的最短路径问题
6.2.1多段图的决策过程
6.2.2多段图动态规划算法的实现
6.3资源分配问题
6.3.1资源分配问题的决策过程
6.3.2资源分配问题动态规划算法实现
6.4设备更新问题
6.4.1设备更新问题的决策过程
6.4.2设备更新问题算法的实现
6.50/1背包问题
6.5.10/1背包问题的求解过程
6.5.20/1背包问题的实现
教学重点：
动态规划方法的思想、基本概念、最优决策原理和基本方程。
教学难点：
动态规划方法的最优决策原理、基本方程。
课后作业：
（1）阅读教材对应部分内容；
（2）练习教材P199习题3、4、5、7、9。
第7章回溯方法
教学内容：
7.1回溯方法的基本思想
7.2n皇后问题
7.3图的着色问题
课后作业：
阅读教材对应部分内容；
练习教材的P227的习题1、5o
教学重点：
回溯方法的基本思想、基本概念、一般性描述和实现。
教学难点：
状态空间树的生成、深度优先搜索方法应用。
周教学进度安排及学时分配
周次
教学内容简要说明
学时
教学方式
作业
1
了解算法设计与分析在计算机科学与技术中的地位、算法（Algorithm）—词的由来。
熟悉算法的定义和特征，算法设计与分析的基本概念，掌握算法复杂性的概念和度量方法。
2
课堂讲授为主、结合课堂分组讨论
练习教材P17的习
题1、3、5、7、8
2
熟悉常用的函数和公式，掌握算法时间复杂性分析，掌握最好、最坏和平均情况分析，理解算法的空间复杂性。
2
课堂讲授为主、结合课堂分组讨论
练习教材P55的习题1、2
3
理解和掌握合并排序算法的分析、堆排序的实现和算法分析、基数排序方法和算法分析。
2
课堂讲授为主、结合课堂分组讨论
练习教材P80的习
题1、4、7、9
4
理解集合的Union.Find操作。
2
课堂讲授为主、结合课堂分组讨论
5
深刻理解递归内涵、设计原理、算法实现和算法分析.
2
课堂讲授为主、结合课堂分组讨论
练习教材P136的
习题2、3、6
6
深刻理解分治内涵、设计原理、算法实现和算法分析.
2
课堂讲授为主、结合课堂分组讨论
练习教材P136的习题4、8、13
7
递归与分治--作业讲解
2
8
理解和掌握贪婪方法的设计原理和特点
2
课堂讲授为主、结合课堂分组讨论
练习教材P164的
习题1、2
9
单源最短路径问题、最小花费生成树问题
2
课堂讲授为主、结合课堂分组讨论
练习教材P164的习题3、4
10
贪婪法--作业与习题讲解
2
11
动态规划的思想方法、多段图的最短路径问题
2
课堂讲授为主、结合课堂分组讨论
练习教材P199习题3、4
12
资源分配问题、设备更新问题
2
课堂讲授为主、结合课堂分组讨论
练习教材P199习题5、7
13
背包问题
2
课堂讲授为主、结合课堂分组讨论
练习教材P199习题9
14
动态规划法--作业与习题讲解
2
15
理解和掌握回溯方法的基本思想、基本概念、设计原理和算法实现
2
课堂讲授为主、结合课堂分组讨论
练习教材的P227的习题】、5
16
课程复习总结
2
答疑
课程考核方式
分类
考核方式
考核内容
成绩比重
过程考评
平时成绩
平时出勤和作业完成情况
20%
期中考评
随堂开卷
随堂作业完成
20%
期末考评
闭卷
算法基本概念、基本理论和基本技术
60%
备注
执笔人：
邱桃荣完成日期：
2017-01-04
审核人：
于海雯
审核日期：
2017-01-05
升级会员 