第三知识单元动态规划 学时分配5学时 教学方式课堂讲授，PPT电子课件，板书 教学内容 重点难点 1动态规划的基本思想和多阶段决策和状态转移方程理解。 2动态规划法的主要性质和分析方法及最优子结构性质证明！ 3利用动态规划解决实际问题的一般步骤和实现框架。 动态规划法实例：树塔问题、01背包问题、最长公共子序 4 列问题、矩阵连乘问题，学习不同类型的阶段决策和状态转 移差异。 动态规划法的最优子结构和重叠子问题性质判断，扩展问题的 考核要点 状态转移方程定义，01背包问题、最长公共子序列问题、矩 阵连乘问题的动态规划法实现，扩展问题的动态规划法求解。 第四知识单元贪心算法 学时分配4学时 教学方式课堂讲授，PPT电子课件，板书 教学内容 重点难点 1贪心算法的基本思想，以及贪心算法与动态规划法的关系。 2贪心算法的主要性质，运用的条件和限制及性质证明。 贪心算法的实现框架和分析：贪心算法求解最优化问题和近 3 似最代求解。 贪心算法实例：活动安排问题、背包问题、最优装载问题、 单源最短路径、多机作业调度问题。 考核要点 贪心法的最优子结构和贪心选择性质判断及证明，背包问题、 最优装载问题、单源最短路径、多机作业调度问题求解及实现 第五知识单元回溯法 学时分配3学时教学方式课堂讲授，PPT电子课件，板书 教学内容 重点难点 1回溯法的基本思想，解空间树及深度优先搜索的概念。 2回溯法的设计步骤及典型的算法实现框架和剪枝函数设计。 3利用子集树和排列树实现回溯法求解问题表达的方式。 回溯法实例：0-1背包问题、两艘船的装载问题、批处理作 4 业调度问题。 问题的解空间树模型建立，剪枝函数设计，01背包问题、货 考核要点 郎问题、两艘船的装载问题、批处理作业调度问题的回溯法求 解和实现。 3 第三知识单元 动态规划 学时分配 5 学时 教学方式 课堂讲授，PPT 电子课件，板书 教学内容 重点 难点 1 动态规划的基本思想和多阶段决策和状态转移方程理解。 √ 2 动态规划法的主要性质和分析方法及最优子结构性质证明。 √ √ 3 利用动态规划解决实际问题的一般步骤和实现框架。 √ 4 动态规划法实例：树塔问题、0/1 背包问题、最长公共子序 列问题、矩阵连乘问题，学习不同类型的阶段决策和状态转 移差异。 √ √ 考核要点 动态规划法的最优子结构和重叠子问题性质判断，扩展问题的 状态转移方程定义，0/1 背包问题、最长公共子序列问题、矩 阵连乘问题的动态规划法实现，扩展问题的动态规划法求解。 第四知识单元 贪心算法 学时分配 4 学时 教学方式 课堂讲授，PPT 电子课件，板书 教学内容 重点 难点 1 贪心算法的基本思想，以及贪心算法与动态规划法的关系。 2 贪心算法的主要性质，运用的条件和限制及性质证明。 √ √ 3 贪心算法的实现框架和分析；贪心算法求解最优化问题和近 似最优求解。 √ 4 贪心算法实例：活动安排问题、背包问题、最优装载问题、 单源最短路径、多机作业调度问题。 √ 考核要点 贪心法的最优子结构和贪心选择性质判断及证明，背包问题、 最优装载问题、单源最短路径、多机作业调度问题求解及实现。 第五知识单元 回溯法 学时分配 3 学时 教学方式 课堂讲授，PPT 电子课件，板书 教学内容 重点 难点 1 回溯法的基本思想，解空间树及深度优先搜索的概念。 √ 2 回溯法的设计步骤及典型的算法实现框架和剪枝函数设计。 3 利用子集树和排列树实现回溯法求解问题表达的方式。 √ √ 4 回溯法实例：0-1 背包问题、两艘船的装载问题、批处理作 业调度问题。 √ 考核要点 问题的解空间树模型建立，剪枝函数设计，0-1 背包问题、货 郎问题、两艘船的装载问题、批处理作业调度问题的回溯法求 解和实现