算法设计课程教学大纲

算法设计课程教学大纲【算法设计】课程教学大纲【课程代码】04034109【课程类别】考查课【学分】3【总学时】72【讲授学时】42【实验学时】0【先修课程】《C++程序设计》、《数据结构》【适用专业】2012级计算机科学与技术【教学目的】计算机算法设计与分析是计算机算法和软件的基础。本课程的目的是通过授课和实验的方式使学生掌握计算机算法的基本概念和基本理论，一些具体算法的复杂性分析；算法设计的基本方法、技术和分析方法；经典数值计算问题、递归与分治、动态规划、贪心法、回溯法、和分支限界法等解决问题的方法。【课程的基本内容和要求】（一）算法概述教学内容：1.1算法与程序1.2算法复杂性分析1.3NP完全理论教学要求：理解程序与算法的概念、区别与联系；掌握算法在最坏情况、最好情况和平均情况下的计算复杂性概念。（二）递归与分治教学内容：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)分支限界法与优先队列式分支限界法。【学时分配表】序号内容讲授实验小计1算法概述2022递归与分治64103动态规划84124贪心算法88165回溯算法88166分支限界算法10616小计423072【实验学时分配表】序号内容要求小计实验一二分搜索算法用分治思想设计实现二分搜索算法2学时实验二快速排序算法用分治思想设计快速排序算法，并分析算法的时间复杂性。2学时实验三动态规划利用动态规划思想对0-1背包问题进行编程练习4学时实验四贪心算法-最优装载贪心算法编程实现最优装载4学时实验五贪心算法-哈夫曼编码贪心算法编程实现哈夫曼编码4学时实验六回溯法0-1背包用回溯法对0-1背包问题编程练习4学时实验七回溯法n后问题用回溯法对n后问题编程练习4学时实验八分支限界0-1背包用分支限界法对0-1背包问题编程练习4学时实验九分支限界单源最短路径用分支限界法对单源最短路径问题编程练习2学时小计30学时【有关说明】1、教学建议在教学中安排一定的习题讨论时间，使学生锻炼分析问题的能力。教学中的一些习题建议学生安排上机，这样才能全面掌握常用算法的分析和设计技术。2、课程建议教材《计算机算法设计与分析》王晓东编著电子工业出版社3、课程建议参考书《算法导论（原书第3版）》（美）ThomasH.Cormen著机械工业出版社《算法设计与分析》吕国英编著电子工业出版社【考核方式】：考查