《算法分析与设计教案》由会员分享，可在线阅读，更多相关《算法分析与设计教案（66页珍藏版）》请在金锄头文库上搜索。
1、 算法分析与设计 课程教教案案课程编号：50c24037-01总学时：51 周学时：4 适用年级专业（学科类）：2007 级计科专业开课时间：20102011 学年第 1 学期 使用教材：王晓东编著 计算机算法设计与分析第 3版 授课教师姓名：李凯教师备课专用章节第 1 章 1.1 1.2 第 2 章 2.1课时2教学目的理解程序与算法的概念、区别与联系；掌握算法在最坏情况、最好情况和平均情况下的计算复杂性概念；掌握算法复杂性的渐近性态的数学表述；理解递归的概念。教学 重点 及 突出 方法重点：程序与算法的概念、算法的时间复杂性、算法复杂性的渐近性态的数学表述以及递归的概念。通过讲解、举例方法
2、。教学 难点 及 突破 方法难点：算法复杂性与递归通过讲解、举例、提问与引导方法。相关内容素材此部分内容基础知识可参考清华大学出版社出版严蔚敏编著的数据结构教师备课专用（教师授课思路、设问及讲解要点）教学过程回顾数据结构课程中的算法概念、排序算法等知识，从而引出本课程内容。提问算法与程序的区别、联系以及算法具有的特性。讲解算法的复杂性，主要包括时间复杂性与空间复杂性。讲解最坏情况、最好情况与平均情况的时间复杂性。讲解算法复杂性在渐近意义下的阶，主要包括、与 o，并通过具体例子说明。通过具体例子说明递归技术。主要包括阶乘函数、Fibonacci 数列、Ackerman 函数、排列问题、整数划分问
3、题、Hanoi 塔问题等。教师备课专用第 页章节第 2 章 2.22.5课时2教学目的掌握设计有效算法的分治策略，并掌握范例的设计技巧，掌握计算算法复杂性方法。教学 重点 及 突出 方法重点：分治法的基本思想及分治法的一般设计模式。通过讲解、举例方法。教学 难点 及 突破 方法难点：计算算法复杂性。通过讲解、举例、提问与引导方法。相关内容素材教师备课专用（教师授课思路、设问及讲解要点）教学过程通过生活中解决复杂问题的分解方法，引出分治方法。讲解分治法的基本思想及其一般算法的设计模式，介绍分治法的计算效率。通过具体例子采用分治思想来设计有效算法。主要包括二分搜索技术、大整数乘法、Strassen
4、 矩阵乘法。1、 二分搜索技术先介绍顺序搜索方法；然后介绍二分搜索算法；最后分析算法的时间复杂性。2、 大整数乘法先介绍当计算机硬件不能直接处理整数时的问题；然后引出用软件方法实现大整数乘法算法；最后分析算法的效率。3、 Strassen 矩阵乘法先引入一般矩阵乘法算法并分析时间复杂性；然后再给出另一种方法，但其效率并没有提高；最后介绍提高矩阵乘法效率的算法并分析时间复杂性。第 页教师备课专用章节第 2 章 2.62.8课时2教学目的掌握设计有效算法的分治策略，并掌握范例的设计技巧，主要包括棋盘覆盖、合并排序与快速排序，掌握计算算法复杂性方法。教学 重点 及 突出 方法重点：分治法的基本思想及
5、分治法的一般设计模式。通过讲解、举例方法。教学 难点 及 突破 方法难点：计算算法复杂性。通过讲解、举例、提问与引导方法。相关内容素材教师备课专用（教师授课思路、设问及讲解要点）教学过程回顾分治法的基本思想及其一般算法的设计模式，介绍分治法的计算效率。通过棋盘覆盖、合并排序与快速排序具体例子讲解采用分治思想设计有效的算法。1、棋盘覆盖先介绍问题描述；然后介绍如何使用分治方法解决棋盘覆盖问题；最后分析算法的时间复杂性。2、 合并排序先介绍使用分治策略的递归排序算法并分析算法时间复杂性；然后介绍非递归算法及自然合并排序算法；最后分析算法的效率。3、 快速排序先介绍使用分治策略的快速排序算法的基本思
6、想；然后给出基于分治策略的快速排序算法并分析时间复杂性；最后介绍随机化的快速排序算法。第 页教师备课专用章节第 2 章 2.92.11课时2教学目的掌握设计有效算法的分治策略，并掌握范例的设计技巧，主要包括线性时间选择与最接近点对问题，掌握计算算法复杂性方法。教学 重点 及 突出 方法重点：分治法的基本思想及分治法的一般设计模式。通过讲解、举例方法。教学 难点 及 突破 方法难点：鸽舍原理与二维点集算法。通过讲解、举例、提问与引导方法。相关内容素材教师备课专用（教师授课思路、设问及讲解要点）教学过程回顾分治法的基本思想及其一般算法的设计模式，介绍分治法的计算效率。通过线性选择问题与最接近点对问
7、题具体例子讲解采用分治思想设计有效的算法。1、线性时间选择先介绍元素选择问题的一般提法；然后介绍如何使用分治方法解决线性时间选择问题；最后分析算法的时间复杂性。2、 最接近点对问题先介绍分治策略的最接近点对问题的提法并给出常用的解决方法并分析算法时间复杂性；然后介绍一维与二维情形下的最接近点对算法；最后分析算法的效率。第 页教师备课专用章节第 3 章 3.13.2课时2教学目的理解动态规划算法的概念，掌握动态规划算法的基本要素，掌握设计动态规划算法的步骤，并通过应用范例学习动态规划算法的设计策略。教学 重点 及 突出 方法重点：动态规划算法的基本思想及设计动态规划算法的步骤。通过讲解、举例方法
8、。教学 难点 及 突破 方法难点：最优子结构性质、重叠子问题性质与计算最优值。通过讲解、举例、提问与引导方法。相关内容素材教师备课专用教学过程（教师授课思路、设问及讲解要点）回顾分治法的基本思想及其一般算法的设计模式，介绍动态规划算法的基本思想并给出他们之间的区别。1、设计动态规划算法的步骤1）找出最优解的性质，并刻画其结构特征。2）递归定义最优值。3）以自底向上的方式计算出最优值。4）根据计算最优值时得到的信息，构造最优解。2、矩阵连乘问题1）根据矩阵乘法满足的结合率，介绍矩阵连乘可归结为两个矩阵的相乘，其中主要涉及完全加括号的矩阵连乘积的递归定义。介绍矩阵的连乘积的计算次序与计算量有密切关
9、系。从而引出动态规划法解矩阵连乘问题。2）动态规划法解矩阵连乘问题分析最优解的结构最优子结构性质建立递归关系递归定义最优值计算最优值动态规划算法及算法复杂性构造最优解算法3、动态规划算法的基本要素1）最优子结构性质2）子问题重叠性质3）备忘录算法及算法复杂性第 页章节第 3 章 3.33.4课时2教学目的掌握设计动态规划算法的步骤，理解子序列、公共子序列与最长公共子序列的定义，掌握构造最长公共子序列的算法，掌握最大字段和问题的动态规划算法，并能够分析算法的时间复杂性。教学 重点 及 突出 方法重点：最长公共子序列的结构、子问题的递归结构、最优值的求法与如何构造最长公共子序列；求最大子段和问题的
10、不同算法。通过讲解、举例方法。教学 难点 及 突破 方法难点：最优子结构性质、重叠子问题性质与计算最优值。通过讲解、举例、提问与引导方法。相关内容素材教师备课专用教学过程（教师授课思路、设问及讲解要点）教师备课专用回顾动态规划算法的基本思想。1、设计动态规划算法的步骤1）找出最优解的性质，并刻画其结构特征。2）递归定义最优值。3）以自底向上的方式计算出最优值。4）根据计算最优值时得到的信息，构造最优解。2、最长公共子序列问题1）子序列、公共子序列及最长公共子序列的定义。2）动态规划法解最长公共子序列问题最长公共子序列问题的最优子结构性质建立递归关系递归定义最优值计算最优值算法及复杂性构造最长公
11、共子序列3）算法的改进3、最大子段和问题1）介绍最大子段和问题的简单算法、分治算法、动态规划算法。2）分析上述算法的复杂性。第 页教师备课专用章节第 3 章 3.5、3.7课时2教学目的掌握凸多边形及最优三角剖分的概念，理解凸多边形的三角剖分的语法树表示，掌握凸多边形最优三角剖分的动态规划算法，并能够分析算法的时间复杂性；理解图像的表示以及图像的变位压缩存储格式，掌握构造图像压缩问题的动态规划算法及复杂性。教学 重点 及 突出 方法重点：凸多边形的三角剖分的语法树表示、最优子结构性质、凸多边形最优三角剖分的动态规划算法、时间复杂性；图像的变位压缩存储格式，构造图像压缩问题的动态规划算法及复杂性
12、。通过讲解、举例方法。教学 难点 及 突破 方法难点：最优子结构性质、图像的变位压缩存储格式、复杂性分析。通过讲解、举例、提问与引导方法。相关内容素材教师备课专用（教师授课思路、设问及讲解要点）教学过程回顾动态规划算法的基本思想。1、设计动态规划算法的步骤1）找出最优解的性质，并刻画其结构特征。2）递归定义最优值。3）以自底向上的方式计算出最优值。4）根据计算最优值时得到的信息，构造最优解。2、凸多边形最优三角剖分问题1）多边形、凸多边形、多边形的三角剖分及凸多边形的最优三角剖分的概念。2）动态规划法解凸多边形最优三角剖分问题凸多边形最优三角剖分问题的最优子结构性质建立递归关系递归定义最优值计
13、算最优值算法及复杂性构造凸多边形最优三角剖分3、图像压缩问题1）图像变位压缩存储格式、使用变长模式的步骤及举例说明。2）动态规划解决图像压缩算法并分析算法的复杂性。第 页章节第 3 章 3.103.11课时2教学目的理解 01 背包问题，掌握该问题的动态规划算法，并能够分析算法的时间复杂性；理解最优二叉搜索树问题，掌握最优二叉搜索树的动态规划算法，并能够分析算法的时间复杂性；了解该问题的改进算法及时间复杂性。教学 重点 及 突出 方法重点：最优子结构性质及递归关系。通过讲解、举例方法。教学 难点 及 突破 方法难点：递归关系及时间复杂性分析。通过讲解、举例、提问与引导方法。相关内容素材教师备课
14、专用教师备课专用（教师授课思路、设问及讲解要点）教学过程回顾动态规划算法的基本思想。1、设计动态规划算法的步骤1）找出最优解的性质，并刻画其结构特征。2）递归定义最优值。3）以自底向上的方式计算出最优值。4）根据计算最优值时得到的信息，构造最优解。2、01 背包问题1）01 背包问题的形式化描述。2）动态规划法解 01 背包问题问题的最优子结构性质。建立递归关系递归定义最优值。计算最优值算法及复杂性。构造最优解。3、最优二叉搜索树问题1）二叉搜索树与最优二叉搜索树的概念。2）动态规划解决最优二叉搜索树算法并分析算法的复杂性。第 页章节第 4 章 4.14.2课时2教学目的理解贪心算法的概念，掌
15、握贪心算法的基本要素，理解贪心算法与动态规划算法的差异，理解贪心算法的一般理论，通过活动安排问题、最优装载问题范例学习贪心设计策略。教学 重点 及 突出 方法重点：贪心算法的基本要素及一般理论，贪心算法与动态规划算法的差异。通过讲解、举例方法。教学 难点 及 突破 方法难点：贪心算法的基本要素。通过讲解、举例、提问与引导方法。相关内容素材教师备课专用（教师授课思路、设问及讲解要点）教学过程回顾动态规划算法的基本思想，然后通过找硬币例子引出贪心算法，并说明有些问题即可以用动态规划方法求解，也可以用贪心算法求解。1、贪心算法的概念并强调贪心选择方法不一定得到整体最优解。2、活动安排问题1）活动安排
16、问题的描述。2）贪心算法求解活动安排问题解活动安排问题的算法及时间复杂性。通过实例讲解计算过程。3、用贪心算法求解的问题的一般特征1）详细讲解贪心选择性质与最优子结构性质。2）讲解动态规划算法与贪心算法的差异，并通过 01 背包问题与背包问题介绍它们的不同，重点介绍用贪心算法求解背包问题。4、详细讲解使用贪心算法求解最优装载问题1）最优装载问题的贪心选择性质。2）最优装载问题的最优子结构性质。3）算法描述。教师备课专用第 页章节第 4 章 4.3、4.7课时2教学目的理解贪心算法的概念，掌握贪心算法的基本要素，理解贪心算法与动态规划算法的差异，理解贪心算法的一般理论，通过最优装载问题、多机调度问题范例学习贪心设计策略。教学 重点 及 突出 方法重点：贪心算法的基本要素及一般理论，贪心算法与动态规划算法的差异。通过
