算法分析与设计教案

《算法分析与设计教案》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、算法分析与设计课程教案课程编号：50c24037-01总学时：51周学时：4适用年级专业（学科类）：2007级计科专业开课时间：2010－2011学年第1学期使用教材：王晓东编著计算机算法设计与分析第3版授课教师姓名：李凯教师备课专用章节第1章1.1~1.2第2章2.1课时2教学目的理解程序与算法的概念、区别与联系；掌握算法在最坏情况、最好情况和平均情况下的计算复杂性概念；掌握算法复杂性的渐近性态的数学表述；理解递归的概念。教学重点及突出方法重点：程序与算法的概念、算法的时间复杂性、算法复杂性的渐近性态的数学表述以及递归的概念。通过讲解、举

2、例方法。教学难点及突破方法难点：算法复杂性与递归通过讲解、举例、提问与引导方法。相关内容素材此部分内容基础知识可参考清华大学出版社出版严蔚敏编著的《数据结构》教师备课专用教学过程（教师授课思路、设问及讲解要点）回顾数据结构课程中的算法概念、排序算法等知识，从而引出本课程内容。提问算法与程序的区别、联系以及算法具有的特性。讲解算法的复杂性，主要包括时间复杂性与空间复杂性。讲解最坏情况、最好情况与平均情况的时间复杂性。讲解算法复杂性在渐近意义下的阶，主要包括、、与o，并通过具体例子说明。通过具体例子说明递归技术。主要包括阶乘函数、Fibonac

3、ci数列、Ackerman函数、排列问题、整数划分问题、Hanoi塔问题等。教师备课专用第页章节第2章2.2~2.5课时2教学目的掌握设计有效算法的分治策略，并掌握范例的设计技巧，掌握计算算法复杂性方法。教学重点及突出方法重点：分治法的基本思想及分治法的一般设计模式。通过讲解、举例方法。教学难点及突破方法难点：计算算法复杂性。通过讲解、举例、提问与引导方法。相关内容素材教师备课专用教学过程（教师授课思路、设问及讲解要点）通过生活中解决复杂问题的分解方法，引出分治方法。讲解分治法的基本思想及其一般算法的设计模式，介绍分治法的计算效率。通过具体

4、例子采用分治思想来设计有效算法。主要包括二分搜索技术、大整数乘法、Strassen矩阵乘法。1、二分搜索技术先介绍顺序搜索方法；然后介绍二分搜索算法；最后分析算法的时间复杂性。2、大整数乘法先介绍当计算机硬件不能直接处理整数时的问题；然后引出用软件方法实现大整数乘法算法；最后分析算法的效率。3、Strassen矩阵乘法先引入一般矩阵乘法算法并分析时间复杂性；然后再给出另一种方法，但其效率并没有提高；最后介绍提高矩阵乘法效率的算法并分析时间复杂性。教师备课专用第页章节第2章2.6~2.8课时2教学目的掌握设计有效算法的分治策略，并掌握范例的设

5、计技巧，主要包括棋盘覆盖、合并排序与快速排序，掌握计算算法复杂性方法。教学重点及突出方法重点：分治法的基本思想及分治法的一般设计模式。通过讲解、举例方法。教学难点及突破方法难点：计算算法复杂性。通过讲解、举例、提问与引导方法。相关内容素材教师备课专用教学过程（教师授课思路、设问及讲解要点）回顾分治法的基本思想及其一般算法的设计模式，介绍分治法的计算效率。通过棋盘覆盖、合并排序与快速排序具体例子讲解采用分治思想设计有效的算法。1、棋盘覆盖先介绍问题描述；然后介绍如何使用分治方法解决棋盘覆盖问题；最后分析算法的时间复杂性。2、合并排序先介绍使用

6、分治策略的递归排序算法并分析算法时间复杂性；然后介绍非递归算法及自然合并排序算法；最后分析算法的效率。3、快速排序先介绍使用分治策略的快速排序算法的基本思想；然后给出基于分治策略的快速排序算法并分析时间复杂性；最后介绍随机化的快速排序算法。教师备课专用第页章节第2章2.9~2.11课时2教学目的掌握设计有效算法的分治策略，并掌握范例的设计技巧，主要包括线性时间选择与最接近点对问题，掌握计算算法复杂性方法。教学重点及突出方法重点：分治法的基本思想及分治法的一般设计模式。通过讲解、举例方法。教学难点及突破方法难点：鸽舍原理与二维点集算法。通过讲

7、解、举例、提问与引导方法。相关内容素材教师备课专用教学过程（教师授课思路、设问及讲解要点）回顾分治法的基本思想及其一般算法的设计模式，介绍分治法的计算效率。通过线性选择问题与最接近点对问题具体例子讲解采用分治思想设计有效的算法。1、线性时间选择先介绍元素选择问题的一般提法；然后介绍如何使用分治方法解决线性时间选择问题；最后分析算法的时间复杂性。2、最接近点对问题先介绍分治策略的最接近点对问题的提法并给出常用的解决方法并分析算法时间复杂性；然后介绍一维与二维情形下的最接近点对算法；最后分析算法的效率。教师备课专用第页章节第3章3.1~3.2课

8、时2教学目的理解动态规划算法的概念，掌握动态规划算法的基本要素，掌握设计动态规划算法的步骤，并通过应用范例学习动态规划算法的设计策略。教学重点及突出方法重点：动态规划算法的基本思