还剩1页未读,继续阅读
文本内容:
《算法分析与设计》课程教学大纲课程英文名称AlgorithmAnalysisandDesign课程编号0800360学分3学时48
一、课程教学对象本教学大纲适用于计算机学院计算机相关专业普通本科学生的课程教学
二、课程性质及教学目的(属于公共课、专业基础课、核心专业课或专业选修课;必修或选修通过本课程的学习,使学生系统地掌握算法的基本概念,掌握算法设计的主要方法,学会分析算法的时间复杂度、空间复杂度和稳定性,为学生提供一个广泛扎实的计算机算法知识基础锻炼学生逻辑思维能力和想象力,培养学生问题抽象能力、算法设计与分析能力、程序设计与实践能力
三、对先修知识的要求本课程的先修课程为C++程序设计、离散数学、数据结构等通过离散数学课程的学习,使学生具备基本的计算机科学的抽象思维能力和逻辑思维能力;而掌握C++程序设计和数据结构的基本知识后,学生能够用高级语言表达算法和问题,熟练编程并求解这些都将为算法分析与设计课程的学习打下基础
四、课程的主要内容、基本要求和学时分配建议(总学时数:36)注知识点中粗体字部分为本课程的重点或难点(按照本课程知识体系列出知识模块及知识点,其中重点或难点用粗体字标注;要求按“了解(C)工“熟悉(B)工“熟练掌握(A)”三个层次描述学生对知识点应达到的要求)
五、建议使用教材及参考书
[1]王晓东.计算机算法设计与分析[M].北京电子工业出版社,2007
[2]余祥宣,崔国华,邹海明.计算机算法基础(第三版)[M].武汉华中科技大学出版社,2006
[3]苏德富,钟诚.计算机算法设计与分析[M].北京电子工业出版社,2001
[4]曹新谱.算法设计与分析[M].长沙湖南科学技术出版社,1984
[5]王晓东.算法设计与分析习题解答[M].北京清华大学出版社,2006
[6]张永,李睿,年福忠.算法与数据结构[M].北京国防工业出版社,2008
六、课程考核方式本课程采用笔试闭卷的考核方式,要求学生熟练掌握课程教学目标要求的内容,并能有效表达和运用,以达到该课程的能力培养目标采用平时成绩和期末考试成绩相结合的方式平时表现(考勤、随堂提问、作业、实验环节)30%期末考试70%
七、课内实验(实训)环节及要求(总学时数12)知识模块知识点要求学时学习方式课外学习要求
1、算法概述
1.1算法与程序A2课堂讲授
1.2算法复杂性分析B课堂讲授
2、递归与分治策略
2.1递归的概念A6课堂讲授
2.2分治法的基本思想A课堂讲授
2.3二分搜索技术A课堂讲授
2.4大整数的乘法A课堂讲授
2.5Strassen矩阵乘法A课堂讲授
2.6棋盘覆盖问题A课堂讲授
2.7合并排序A课堂讲授
2.8快速排序A课堂讲授
2.9循环赛日程表C课堂讲授
3、动态规划
3.1动态规划算法的基本思想B8课堂讲授
3.2动态规划算法的基本要素A课堂讲授
3.3矩阵连乘问题A课堂讲授
3.4最长公共子序列A课堂讲授
3.5最大子段和问题B课堂讲授
3.6电路布线A课堂讲授
3.7流水作业调度A课堂讲授
3.8图像压缩问题C课堂讲授
3.90-1背包问题A课堂讲授
3.10动态规划加速原理C课堂讲授
4、贪心算法
4.1贪心算法的基本思想B8课堂讲授
4.2贪心算法的基本要素A课堂讲授
4.3贪心算法与动态规划算法B课堂讲授
4.4活动安排问题A课堂讲授
4.5最优装载问题A课堂讲授
4.6哈夫曼编码A课堂讲授
4.7单源最短路径A课堂讲授
4.8最小生成树A课堂讲授
4.9多机调度问题B课堂讲授
4.10贪心算法的理论基础C课堂讲授
5、回溯法
5.1回溯法的算法框架A6课堂讲授
5.20-1背包问题A课堂讲授
5.3装载问题A课堂讲授
5.4批处理作业调度B课堂讲授
5.5n后问题A课堂讲授
5.6最大团问题A课堂讲授
5.7回溯法的效率分析C课堂讲授
6、分支限界法
6.1分支限界法的基本思想B6课堂讲授
6.2分支限界法的种类A课堂讲授
6.3单源最短路径问题A课堂讲授
6.4装载问题A课堂讲授
6.50-1背包问题A课堂讲授
6.6布线问题B课堂讲授序号实验(实训)项目实验(实训)内容实验(实训)目的及要求学时1递归与分治策略及其应用运用C++语言求解输油管道问题学会使用递归与分治策略解决实际问题22动态规划及其应用运用C++语言求解
①租用游艇问题
②最少费用购物问题学会使用动态规划解决实际问题43贪心算法及其应用运用C++语言求解硬币找钱问题学会使用贪心算法解决实际问题24回溯法及其应用运用C++语言求解迷宫问题学会使用回溯法解决实际问题25分支限界法及其应用运用C++语言求解:n后问题学会使用分支限界法解决实际问题2。