算法设计课程教学大纲.pdf

可编辑算法设计课程算法设计课程教教 学学 大大精品文档，欢迎下载纲纲可编辑【算法设计】课程教学大纲【算法设计】课程教学大纲【课程代码】04034109【课程类别】考查课【学分】3【总 学 时】72【讲授学时】42【实验学时】0【先修课程】C+程序设计、数据结构【适用专业】2012 级计算机科学与技术【教学目的】计算机算法设计与分析是计算机算法和软件的基础。本课程的目的是通过授课和实验的方式使学生掌握计算机算法的基本概念和基本理论，一些具体算法的复杂性分析；算法设计的基本方法、技术和分析方法；经典数值计算问题、递归与分治、动态规划、贪心法、回溯法、和分支限界法等解决问题的方法。【课程的基本内容和要求】【课程的基本内容和要求】（一）算法概述教学内容：1.1 算法与程序1.2 算法复杂性分析1.3 NP 完全理论教学要求：理解程序与算法的概念、区别与联系；掌握算法在最坏情况、最好情况和平均情况下的计算复杂性概念。（二）递归与分治教学内容：1.递归的概念2.分治法基本思想3.二分搜索技术4.合并排序5.快速排序6.大整数乘法教学要求：精品文档，欢迎下载可编辑理解递归的概念；掌握设计有效算法的分治策略，并掌握范例的设计技巧。（三）动态规划教学内容：1.矩阵连乘问题2.动态规划算法的基本要素3.最长公共子序列4.0-1 背包问题教学要求：理解动态规划算法的概念，掌握动态规划算法的基本要素，掌握设计动态规划算法的步骤，并通过应用范例学习动态规划算法的设计策略。（四）贪心算法教学内容：1.活动安排问题2.贪心算法的基本要素3.最优装载4.哈夫曼编码5.单源最短路径教学要求：掌握贪心算法的基本要素，理解贪心算法与动态规划算法的差异，理解贪心算法的一般理论。（五）回溯算法教学内容：1.回溯法的算法框架2.0-1 背包问题3.装载问题4.n 后问题5.旅行售货员问题教学要求：理解回溯法深度优先搜索策略，掌握用回溯法解题的算法框架，包括递归回溯、迭代回溯、子集树算法框架、排列树算法框架。（六）分支限界算法教学内容：1.分支限界法的基本思想2.单源最短路径问题3.装载问题4.0-1 背包问题精品文档，欢迎下载可编辑教学要求：理解分支限界法的基本思想与剪枝搜索策略；掌握分支限界法的算法框架，包括队列式(FIFO)分支限界法与优先队列式分支限界法。【学时分配表】【学时分配表】序号123456算法概述递归与分治动态规划贪心算法回溯算法分支限界算法小计内容讲授268881042实验04488630小计2101216161672【实验学时分配表】【实验学时分配表】序号实验一实验一实验二实验二实验三实验三实验四实验四实验五实验五实验六实验六实验七实验七实验八实验八实验九实验九内容二分搜索算法快速排序算法要求用分治思想设计实现二分搜索算法用分治思想设计快速排序算法，并分析算法的时间复杂性。利用动态规划思想对 0-1 背包问题进行编程练习贪心算法编程实现最优装载小计2 学时2 学时4 学时4 学时4 学时4 学时4 学时4 学时2 学时30 学时动态规划贪心算法-最优装载贪心算法-哈夫曼编码回溯法 0-1 背包回溯法 n 后问题分支限界 0-1 背包分支限界单源最短路径贪心算法编程实现哈夫曼编码用回溯法对 0-1 背包问题编程练习用回溯法对 n 后问题编程练习用分支限界法对 0-1 背包问题编程练习用分支限界法对单源最短路径问题编程练习小计【有关说明】【有关说明】精品文档，欢迎下载可编辑1、教学建议在教学中安排一定的习题讨论时间，使学生锻炼分析问题的能力。教学中的一些习题建议学生安排上机，这样才能全面掌握常用算法的分析和设计技术。2、课程建议教材计算机算法设计与分析3、课程建议参考书算法导论（原书第 3 版）（美）ThomasH.Cormen 著机械工业出版王晓东编著电子工业出版社社算法设计与分析【考核方式】【考核方式】：考查：考查吕国英编著精品文档，欢迎下载电子工业出版社.