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

1 算法设计与分析 一 说明说明 一 一 课程性质课程性质 计算机科学是一种创造性思维活动 其教育必须面向设计 计算机算法设计与分 析正是一门面向设计 且处于计算机学科核心地位的教育课程 设计一个高效的程序 不仅需要编程小技巧 更需要合理的数据组织和清晰高效的算法 这正是计算机科学 领域里数据结构与算法设计所研究的主要内容 二 二 教学目的教学目的 通过对本课程的学习与研究 使学生掌握算法设计的主要方法 培养对算法的计 算复杂性正确分析的能力 为独立设计算法和对算法复杂性分析奠定坚实的理论基础 对学生将来从事计算机系统结构 系统软件和应用软件的研究与开发提供一个广泛扎 实的计算机算法知识基础 三 三 教学内容教学内容 算法及算法复杂性基本概念 算法描述 有效算法最常用的设计策略 递归和 分治法 动态规划法的设计要点与适用性 贪心算法 回溯法和分支限界法 许多难 解问题的高效算法 概率算法 以及 NP 完全理论和 NP 难问题的近似解法 传统算 法实例分析 算法领域研究热点介绍 四 四 教学时数教学时数 课堂教学 36 学时 实验部分 36 学时 总计 36 36 2 54 学时 五 五 教学方式教学方式 讲授 上机实验 课题设计 对每一教学内容 首先介绍一种算法设计策略的基本思想 然后从解决计算机科 学和应用中的实际问题入手 由简到繁地描述几个经典的精巧算法 同时对每个算法 所需的时间和空间进行分析 使学生既能学到一些常用的精巧算法 又能通过对算法 设计策略的反复应用 牢固掌握这些算法设计的基本策略 以期收到融会贯通之效 在为各种算法设计策略选择用于展示其设计思想与技巧的具体应用问题时 有意义重 复选择某些经典问题 使学生能深刻地体会到一个问题可以用多种设计策略求解 同 时通过对解同一问题的不同算法的比较 使学生更容易体会到每一种具体算法的设计 要点 随着内容的逐步展开 学生也将进一步感受到综合应用多种设计策略可以更有 效地解决问题 二 本文本文 一 一 课堂教学部分课堂教学部分 第一章第一章 算法概述算法概述 教学要点 教学要点 算法的基本概念 算法的计算复杂性 教学时数教学时数 建议 2 学时 教学内容 教学内容 第一节算法与程序 0 5 学时 掌握算法的概念及特性 2 理解算法与程序的区别 了解算法的描述方法 第二节算法复杂性分析 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 学时 掌握动态规划算法的基本思想 3 理解动态规划算法和分治法的异同 熟练掌握用动态规划算法求解问题的步骤 第二节 动态规划算法的基本要素 1 5 学时 熟练掌握用动态规划算法求解问题的两个重要性质 即 最优子结构性质和子问题重叠性质 理解自顶向下备忘录方法的基本思想 第三节 动态规划算法设计 2 学时 熟练应用动态规划思想解决具体应用问题 1 最长公共子序列 1 学时 2 最大子段和 1 学时 了解动态规划算法所能解决的一些典型问题 掌握动态规划算法的复杂性分析方法 考核要求 考核要求 领会动态规划算法的思想 算法设计步骤及基本要素 掌握用动态规划思想解决实际问题并设计动态规划算法 动态规划算法复杂性分析 第四章第四章 贪心算法贪心算法 教学要点 教学要点 贪心算法思想 基本要素及贪心算法设计 教学时数 教学时数 建议 3 学时 教学内容 教学内容 第一节 贪心算法的基本思想 1 学时 理解贪心算法的基本思想 理解局部最优和整体最优的概念 第二节 贪心算法的基本要素 1 学时 熟练掌握用贪心算法求解问题的两个重要性质 即 贪心选择性质和最优子结构性质 了解贪心选择性质和最优子结构性质的证明方法 理解贪心算法和动态规划算法的差异 第三节 贪心算法设计 1 学时 熟练应用贪心算法解决具体应用问题 了解贪心算法可能解决的一些典型问题 掌握贪心算法的复杂性分析方法 考核要求考核要求 领会贪心酸法的思想及基本要素 应用贪心算法思想解决实际问题并设计贪心算法 贪心算法复杂性分析 第五章第五章 回溯法回溯法 教学要点 教学要点 回溯放的基本思想及算法框架 递归回溯 迭代回溯 回溯算法设计 教学时数教学时数 4 建议 4 学时 教学内容 教学内容 第一节 回溯法的算法框架 2 学时 理解问题的解空间 掌握回溯法的基本思想 熟练掌握回溯法解题的步骤 理解递归回溯和迭代回溯 了解子集树与排列树的概念 第二节 回溯算法设计 2 学时 熟练应用回溯算法解决具体应用问题 转载问题 了解回溯法解决的一些典型问题 掌握回溯算法复杂性分析方法 考核要求 考核要求 领会回溯法的基本思想 识记用回溯算法解题的步骤 子集树 排列树 应用回溯法解决实际问题并设计回溯算法 回溯算法复杂性分析 第六章第六章 分支界限法分支界限法 教学要点 教学要点 分支界限法基本思想 分支界限法与回溯法的异同 分支界限算法设计 教学时数 教学时数 建议 3 学时 教学内容 教学内容 第一节分支界限法的基本思想 1 5 学时 掌握分支界限法的基本思想 理解分支界限法与回溯法的异同 理解分支界限法的搜索策略 熟练应用剪枝函数来加速搜索 第二节分支界限法算法设计 1 5 学时 熟练应用分支界限法解决具体应用问题 单源最短路径 设计和应用剪枝函数 了解分支界限法解决的一些典型问题 熟练应用队列式分支界限法和优先队列式分支界限法 考核要求 考核要求 领会分支界限法的基本思想 应用分支界限法设计算法 识记分支界限法与回溯法的异同 第七章第七章 概率算法概率算法 教学要点教学要点 数据概率算法 蒙特卡罗算法 拉斯维加斯算法 舍伍德算法 各类算法的优缺点 教学时数教学时数 建议 5 学时 5 教学内容教学内容 第一节 概率算法的描述 1 学时 理解概率算法的基本思想和基本特征 掌握概率算法的分类 区别各种概率算法 了解概率算法的复杂度 第二节 数据概率算法 1 学时 理解数据概率算法的内涵 掌握数据概率算法的设计 了解数据概率算法求解的一些典型问题 第三节 舍伍德 Sherwood 算法 1 学时 理解舍伍德算法的基本思想 了解舍伍德算法的复杂度 掌握舍伍德算法求解的一些典型问题 第四节 拉斯维加斯 Las Vegas 算法 1 学时 理解拉斯维加斯算法的基本思想和基本特征 了解拉斯维加斯算法的复杂性 掌握拉斯维加斯算法的设计 了解拉斯维加斯算法求解的一些经典问题 第五节 蒙特卡罗 Moute Carlo 理解蒙特卡罗算法的基本思想 应用蒙特卡罗算法解决实际应用问题 了解蒙特卡罗算法求解的一些经典问题 考核要求 考核要求 领会各类概率算法的基本思想 掌握各类概率算法的设计 识记各类概率算法的优缺点 第八章第八章 NPNP 完全性的理论完全性的理论 教学要点 教学要点 P 类与 NP 类问题 NP 完全问题 典型的 NP 完全问题 教学时数 教学时数 建议 5 学时 教学内容 教学内容 第一节计算模型 1 5 学时 理解三个重要的计算模型 即 随机存取和 RAM 随机存取存储程序机 RASP 图灵机 第二节 P 类与 NP 类问题 1 学时 理解 易 解和 难 解问题的概念 掌握非确定图灵机 DNTM 模型及其时间复杂度 理解 P 类与 NP 类语言 理解多项式时间验证的概念 理解 COOK 定理的内涵及其重要性 第三节典型的 NP 完全问题 1 学时 6 理解一些典型的 NP 完全问题 了解典型的 NP 完全问题的证明 考核要求 考核要求 领会三个重点的计算模型 领会 P 类与 NP 类问题 NP 完全问题的概念 设计 RAM 和 RASP 程序 识记一些典型的 NP 完全问题 第九章第九章 近似算法近似算法 教学要点 教学要点 NP 完全问题有数近似算法的设计与分析方法 教学时数 教学时数 建议 2 学时 教学内容 教学内容 第一节近似算法 1 学时 理解近似算法的思想的应用范围 理解近似算法的性能 第二节近似算法设计 1 学时 掌握近似算法的设计与分析方法 了解近似算法求解的一些典型问题 考核要求 考核要求 领会近似算法的设计与分析方法 二 二 实验部分实验部分 1 1 基本要求 基本要求 1 熟练操作有关 C JAVA 编程环境 2 运用理论部分介绍的各类算法设计思想在相关环境下设计 编写 调试和运行 求解实际问题的程序 2 2 项目总表 项目总表 序号 实验项目名称学时项目类别项目类型 1 熟悉 C 或 JAVA 编程的环境 2 基础 必做 2 排列问题 2 设计 必做 3 棋盘覆盖问题 2 设计 必做 4 用栈模拟递归 消去算法 Quick sort 中的递归 2 综合 必做 5 Sarassen 矩阵乘法 2 设计 选做 6 矩阵连乘问题 动态和备忘录 2 设计 必做 7 图象压缩 2 设计 必做 8 找硬币 递归算法 动态规划算法 贪心算法 4 综合 必做 9 活动安排问题 2 设计 必做 10 哈夫曼编码 2 设计 必做 11 多机调度问题 2 设计 选做 7 注 必做项目数 17 个 选做项目数 6 个 3 3 实验内容及其基本要求 实验内容及其基本要求 见实验教学大纲 4 4 考核要求 考核要求 熟练应用 C 或 JAVA 编程环境 综合分析各类应用问题并设计相应算法 编写 调试 运行程序 以求解相应问题 各实验项目实验报告 三 参考书目三 参考书目 1 王哓东 编著 计算机算法设计与分析 电子工业出版社 2001 年 11 月第一版 2 陈增武 编著 算法设计与分析 浙江大学出版社 1994 年 8 月第一版 3 Sara Baase Computer Algorithms Introduction to Design and Analysis Second edition Addison Wesley 1988 本课程使用教具和现代教育技术的指导性意见本课程使用教具和现代教育技术的指导性意见 微型计算机 C 编程环境 JAVA 编程环境 序号 实验项目名称学时项目类别项目类型 12 多会场多活动安排问题 2 综