《算法设计与分析》教学大纲VIP专享VIP免费

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