《算法设计与分析》教学大纲

PAGE1PAGE4“算法设计与分析”课程教学大纲课程编号：08051100课程名称：算法设计与分析/TheDesignandAnalysisofComputerAlgorithms学时：48学分：3适用专业：软件工程开课学期：6开课部门：数学与计算机科学学院先修课程：C++语言程序设计、数据结构考核要求：考试使用教材及主要参考书：教材：王红梅编，《算法设计与分析（第2版）》，清华大学出版社，2013年参考书：王晓东主编，《计算机算法设计与分析（第4版）》，电子工业出版社，2012年徐子珊，《算法设计、分析与实现从入门到精通》，人民邮电出版社，2010H.Comen著，殷建平译，《算法导论（原书第3版）》，机械工业出版社，2012年Levitin著，潘彦译，《算法设计与分析基础》，清华大学出版社，2008年一、课程的性质和任务本课程是计算机科学与技术专业的专业必修课。本课程旨在培养学生分析问题和解决问题的能力，使学生掌握算法设计的基本方法，熟悉算法分析的基本技术，并能熟练运用一些常用算法，为学生进一步学习奠定良好的基础。本课程着重于培养学生的算法设计与分析能力，程序设计和实现能力。二、教学目的与要求1、学习掌握几种基本的算法：分治算法、动态规划、贪心算法、回溯法、分支限界法；2、掌握算法设计的基本思想和策略、算法优化的技巧、算法性能分析的方法。三、学时分配章节课程内容学时1算法概述62分治法83动态规划84贪心算法65回溯法86分支限界法67概率算法6四、教学中应注意的问题要注重使用案例教学法，注重实例。五、教学内容第一章算法概述基本内容：算法与程序、算法复杂性分析教学基本要求：掌握算法，算法复杂度的基本概念，及时间复杂度的估算方法。第二章分治法基本内容：主要内容：递归概念，分治法基本思想，二分搜索技术，大整数乘法，矩阵乘法，棋盘覆盖，合并排序，快速排序，线性时间选择，最接近点对问题，循环赛日程表。教学基本要求：掌握递归的概念，学会用递归方法解决实际问题，熟练掌握利用分治法解决问题的基本思想，会用某高级语言对算法进行描述，并对算法复杂度（时间和空间）进行分析。教学重点难点：递归，分治法的基本思想第三章：动态规划基本内容：动态规划的基本要素，矩阵连乘，最长公共子序列，最大子段和，凸多边形最优三角剖分，多边形游戏，图像压缩，电路布线，流水作业调度，0－1背包问题，最优二叉搜索树。教学基本要求：熟练掌握利用动态规划方法解决问题的基本思想，学会如何将问题化为多阶段图的方法，并能对具体问题写出正确的递推公式。教学重点难点：动态规划算法的基本要素。第四章：贪心算法基本内容：贪心算法的基本要素，活动安排问题，最优装载，哈夫曼编码，单源最短路径，最小生成树，多机调度。教学基本要求：掌握利用贪心算法解决问题的基本思想，会用某高级语言编写用贪心算法解决问题的程序，并能对算法的复杂度，可靠性进行分析。教学重点难点：贪心算法的基本要素第五章：回溯法基本内容：回溯法的算法框架、符号，三角形问题，n个皇后问题，最大团问题，图的m着色问题，旅行售货员问题，圆排列问题，连续邮资问题，电路板排列问题。教学基本要求：掌握利用回溯法解决问题的基本思想，会用回溯法解决：n个皇后问题，图的m着色问题，批处理作业调度问题等，并能准确地分析回溯法的效率及稳定性。教学重点难点：回溯法的基本思想，回溯法的效率分析。第六章：分支限界法基本内容：分支限界的基本思想，单源最短路径，布线问题，0－1背包问题，批处理作业调度问题。教学基本要求：掌握利用分支限界法解决问题的基本思想，能用多种不同方法解法同一问题，并分析各方法的效率。教学重点难点：分支限界法的基本思想和各方法的效率分析。第七章：概率算法基本内容：概率算法的基本思想，随机