《c程序设计教学大纲》由会员分享,可在线阅读,更多相关《c程序设计教学大纲(7页珍藏版)》请在金锄头文库上搜索。
1、教学大纲算法设计与分析算法设计与分析课程教学大纲一、课程基本信息课程名称(中文)算法设计与分析课程名称(英文)Algorithm Design and Analysis课程类型专业选修课学 分4总学时64适用对象信息与计算科学专业三年级考核方式闭卷笔试结合实践考核,平时成绩占总成绩的百分20%、实验成绩占总成绩的20%,期末考试成绩占总成绩的60%先修课程程序设计语言、离散数学、数据结构二、课程简介算法设计与分析是信息与计算科学专业的专业选修课。算法是计算机科学的灵魂,算法设计与分析是一门面向设计,且处于计算机科学核心地位的课程。本课程的主要内容包括:算法概述、递归与分治策略、动态规划、贪心算
2、法、回朔法、分枝限界法,随机化算法等。三、课程目标通过本课程中许多常见且有代表性算法的学习,使学生理解和掌握算法设计的主要方法,培养对算法时间复杂性进行正确分析能力,为独立的设计算法和给定算法进行复杂性分析打下良好的基础。培养学生具有针对给定问题设计和实现高效算法的能力。四、教学内容及要求(一)算法概述1,教学目的与要求(1)了解算法与程序的概念(2)掌握算法复杂性分析及其有关的概念(3)了解NP完全问题2,教学内容(1)算法与程序(2)算法复杂性分析(3)NP完全性理论(二)递归与分治策略1,教学目的与要求(1)理解递归的概念(2)了解分治法的基本思想(3)掌握二分搜索技术 (4)掌握Str
3、assen矩阵算法现(5)了解棋盘覆盖问题的算法(6)理解合并排序和快速排序算法(7)了解线性时间选择算法2,教学内容(1)递归的概念(2)分治法的基本思想(3)二分搜索技术 (4)大整数的乘法(5)Strassen矩阵乘法(6)棋盘覆盖(7)合并排序(8)快速排序(9)线性时间选择(10)最接近点对问题(11)循环日程表(三)动态规划1,教学目的与要求(1)掌握动态规划算法的概念、步骤和基本要素 (2)掌握最长公共子序列算法设计和分析 (3)掌握矩阵的连乘算法设计和分析 (4)了解凸多边形最优三角剖分算法 (5)了解多边形游戏问题的算法分析 (6)了解图像压缩算法分析(7)掌握电路布线问题的
4、算法分析 (8)掌握流水作业调度 (9)了解背包问题的算法分析 (10)了解最优二叉搜索树的算法分析 2,教学内容(1)矩阵的连乘问题(2)动态规划算法的基本要素(3)最长公共子序列(4)最大子段和(5)凸多边形最优三角剖分 (6)多边形游戏 (7)图像压缩(8)电路布线 (9)流水作业调度 (10)01背包问题 (11)最优二叉搜索树 (四)贪心算法1,教学目的与要求(1)掌握贪心算法的概念和基本要素(2)了解贪心算法的理论基础(3)了解最优装载问题的算法分析(4)了解哈夫曼编码的算法分析(5)了解单源最短路径的Dijkstra算法的设计与分析 (6)了解最小生成树的Prim和Kruskal
5、算法的设计与分析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)01背包问题(7)最
6、大团问题(8)图的m着色问题(9)旅行售货问题(10)圆排列问题(11)电路板排列问题(12)连续邮资问题(13)回溯法的效率分析(六)分支限界法1,教学目的与要求(1)掌握分支限界法的基本思想(2)掌握单源最短路问题的分支限界法分析(3)掌握背包问题的分支限界法分析(4)了解旅行售货员问题的算法设计与分析2,教学内容(1)分支限界法的基本思想(2)单源最短路问题(3)装载问题(4)布线问题(5)01背包问题(6)最大团问题(7)旅行售货员问题(8)电路板排列问题(9)批处理作业调度(七) 随机化算法1,教学目的与要求(1)理解数值随机化算法(2)了解Sherwood算法(3)了解Las Ve
7、gas算法(4)了解Monte Carlo算法 2,教学内容(1)随机数(2)数值随机化算法(3)Sherwood算法(4)Las Vegas算法(5)Monte Carlo算法 五、课时分配表序号课题名称课时分配小计理论实践其他1第1章算法概述4482第2章递归与分治策略68143第3章动态规划66124第4章贪心算法2465第5章回溯法64106第6章分支界限法4267第7章随机化算法448总课时3232064六、教材及参考书教材:计算机算法设计与分析(第四版) 电子工业出版社2012年7月出版王晓东著参考书:算法导论(影印版)高等教育出版社Thomas H.Cormen Charles
8、E.Leiserson Ronald L.Rivest Clifford Stein修订人 (签字) 梁新健 审核人 (签字) 黄可坤批准人(签字) 陈德华算法设计与分析实验教学大纲一、 基本信息课程名称(中文)算法设计与分析课程名称(英文)Algorithm Design and Analysis课程类型专业选修课学 分4实验学时32适用专业信息与计算科学专业三年级先修课程程序设计语言、离散数学、数据结构二、实验课程简介算法设计与分析实验课程是与算法设计与分析配套的课程。实验内容主要是使用C语言实验与理论课程相关的算法,主要包括:基本算法、递归、分治策略、动态规划、贪心算法、回溯法、分支界限
9、法的实现。三、实验目的算法设计与分析旨在教会学生处理各种问题的方法,而通过实验,使学生能够把所学的方法用于具体的问题,并对所用算法进行比较分析,从而提高学生分析问题、解决问题的能力。只有通过实验,学生才能判定自己所拟算法是否正确,是否算得上一个较优算法。通过该课程的实验,使学生对课堂中所讲述的内容有一个直观的认识,更好地掌握所学的知识。同时培养学生的实际动手能力,加强学生创新思维能力的培养。四、实验内容与要求(一)基本算法1实验目的与要求通过实验使学生掌握使用C语言实现排序算法的方法,了解一些常见问题的算法设计与实验方法。2实验内容(1)插入排序(2)合并排序(3)统计数字问题(4)字典序问题
10、(二)递归与分治策略1实验目的与要求通过实验使学生掌握使用递归和分治法实现算法的方法。2实验内容(1)递归的使用(2)分治法的实现(3)众数问题(4)有重复元素的排列问题(三)动态规划1实验目的与要求通过实验使学生掌握使用动态规划算法的基本设计思路,并用其解决实际问题。2实验内容(1)矩阵连乘问题(2)最大子段和问题(3)最长公共子序列(4)01背包问题(5)独立任务最优调度问题(6)数字三角形问题(四)贪心算法1实验目的与要求掌握贪心算法的基本设计思路,并用其解决实际问题。2实验内容(1)01背包问题(2)单源最短路径问题(3)会场安排问题(4)最优合并问题(五)回溯算法1实验目的与要求掌握
11、回溯法的算法框架和算法的基本思想。2实验内容(1)8皇后问题(2)批处理作业调度(3)01背包问题(4)子集和问题(六)分支界限法1实验目的与要求通过实现掌握分支界限法的基本思想,并能用其解决问题。2实验内容(1)01背包问题(2)最小权顶点覆盖问题(七)随机化算法1实验目的与要求了解随机化算法的基本思想。2实验内容模平方根问题。五、主要仪器设备计算机六、实验学时分配表序号实验项目名称学时实验内容实验性质每组人数必/选做演示验证设计综合1基本算法4221必做2递归与分治策略8621必做3动态规划6421必做4贪心算法441必做5回溯法441必做6分支界限法221必做7随机化算法441选做七、考
12、核方法上机考试采用开卷考试方式。八、教材及参考书建议教材: 计算机算法设计与分析(第四版) 电子工业出版社2012年7月出版王晓东著计算机算法设计与分析习题解答(第二版) 电子工业出版社2012年6月出版王晓东著参考书:算法导论(影印版)高等教育出版社Thomas H.Cormen Charles E.Leiserson Ronald L.Rivest Clifford Stein制订人(签字)梁新健审核人 (签字) 黄可坤批准人(签字) 陈德华财务盈利能力分析采用的主要评价指标包括静态评价指标和动态评价指标两类。其中静态评价指标主要有投资回收期,投资利润率,投资利税率和资本金利润率;动态评价指标主要有投资回收期,净现值、净现值率,内部收益率。7