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

PAGE PAGE # 算法设计与分析 、说明 课程性质 计算机科学是一种创造性思维活动，其教育必须面向设计。计算机算法设计与分析正是一门面向设计，且处于计算机学科核心地位的教育课程。设计一个高效的程序不仅需要编程小技巧，更需要合理的数据组织和清晰高效的算法，这正是计算机科学领域里数据结构与算法设计所研究的主要内容。 教学目的 通过对本课程的学习与研究，使学生掌握算法设计的主要方法，培养对算法的计算复杂性正确分析的能力，为独立设计算法和对算法复杂性分析奠定坚实的理论基础，对学生将来从事计算机系统结构、系统软件和应用软件的研究与开发提供一个广泛扎实的计算机算法知识基础。 教学内容 算法及算法复杂性基本概念，算法描述，有效算法最常用的设计策略——递归和分治法，动态规划法的设计要点与适用性，贪心算法，回溯法和分支限界法，许多难解问题的高效算法——概率算法，以及NP完全理论和NP难问题的近似解法。传统算法实例分析，算法领域研究热点介绍。 教学时数 课堂教学36学时，实验部分36学时，总计36+36/2=54学时 教学方式 讲授+上机实验+课题设计 对每一教学内容，首先介绍一种算法设计策略的基本思想，然后从解决计算机科学和应用中的实际问题入手，由简到繁地描述几个经典的精巧算法。同时对每个算法所需的时间和空间进行分析，使学生既能学到一些常用的精巧算法，又能通过对算法设计策略的反复应用，牢固掌握这些算法设计的基本策略，以期收到融会贯通之效。在为各种算法设计策略选择用于展示其设计思想与技巧的具体应用问题时，有意义重复选择某些经典问题，使学生能深刻地体会到一个问题可以用多种设计策略求解。同时通过对解同一问题的不同算法的比较，使学生更容易体会到每一种具体算法的设计要点。随着内容的逐步展开，学生也将进一步感受到综合应用多种设计策略可以更有效地解决问题。 、本文 （一） 课堂教学部分 第一章算法概述 教学要点： 算法的基本概念，算法的计算复杂性 教学时数： 建议2学时 教学内容： 第一节算法与程序（0.5学时） 掌握算法的概念及特性 理解算法与程序的区别 了解算法的描述方法 第二节算法复杂性分析（1.5学时） 掌握算法复杂性分析的概念 熟练掌握算法时间复杂性和空间复杂性的表示方法及O的定义了解Ω，θ和O的定义 考核要求： 识记相关概念，领会复杂性分析方法 第二章递归与分治策略 教学要点： 递归概念，分治策略，递归算法设计 教学时数： 建议5学时 教学内容： 第一节递归概念（1学时） 熟练掌握递归概念 说明递归算法的工作原理 第二节分治法的基本思想（0.5学时） 熟练掌握分治法的基本思想和一般原则 理解分治算法设计模式 掌握分治算法的复杂性分析方法 第三节基与分治策略的递归算法设计（3.5学时） 熟练应用分治法设计递归算法： .大整数乘法（0.5学时） .Strassen矩阵乘法（0.5学时） .棋盘覆盖（0.5学时） 4.归并排序（0.5学时） .快速排序（0.5学时） 了解分治法所能解决的一些典型问题 应用递归算法复杂性分析的一般方法分析各种具体算法的复杂性考核要求： 领会递归与分治的基本概念 应用分治策略解决实际问题并设计递归算法 递归算法的复杂性分析 第三章动态规划 教学要点： 动态规划算法的设计思想、适用性以及算法的设计要点。 教学时数： 建议6学时。 教学内容： 第一节动态规划算法的基本思想（2.5学时） 掌握动态规划算法的基本思想 理解动态规划算法和分治法的异同 熟练掌握用动态规划算法求解问题的步骤 第二节动态规划算法的基本要素（1.5学时） 熟练掌握用动态规划算法求解问题的两个重要性质，即：最优子结构性质和子问题重叠性质 理解自顶向下备忘录方法的基本思想 第三节动态规划算法设计（2学时） 熟练应用动态规划思想解决具体应用问题 .最长公共子序列（1学时） .最大子段和（1学时） 了解动态规划算法所能解决的一些典型问题 掌握动态规划算法的复杂性分析方法 考核要求： 领会动态规划算法的思想、算法设计步骤及基本要素 掌握用动态规划思想解决实际问题并设计动态规划算法 动态规划算法复杂性分析 第四章贪心算法 教学要点： 贪心算法思想、基本要素及贪心算法设计 教学时数： 建议3学时 教学内容： 第一节贪心算法的基本思想（1学时） 理解贪心算法的基本思想 理解局部最优和整体最优的概念 第二节贪心算法的基本要素（1学时） 熟练掌握用贪心算法求解问题的两个重要性质。即： 贪心选择性质和最优子结构性质 了解贪心选择性质和最优子结构性质的证明方法 理解贪心算法和动态规划算法的差异 第三节贪心算法设计（1学时） 熟练应用贪心算法解决具体应用问题了解贪心算法可能解决的一些典型问题掌握贪心算法的复杂性分析方法 考核要求： 领会贪心酸法的思想及基本要素 应用