计算机算法设计与分析教案

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

1、教案2006-2007学年第一学期课程名称：计算机算法设计与分析课程编号：4111309-1/2+2111309-0学院、专业、年级：信息、计算机、03计本+05计升任课教师：徐连诚教师所在单位：信息科学与工程学院山东师范大学本电子书源于网络，由网金号http://www.egship.com搜集整理，严禁任何商业用途！《算法设计与分析》教案课程简介课程编号：4111309-1,4111309-2,2111309-0课程名称：算法设计与分析英文名称：TheDesignandAnalysisofAlgorithms课程类别：专业课先修课程：《C程序设计》、《

2、离散数学》、《计算方法》、《数据结构》周学时数：3总学时数：54学时（理论54学时，实验0学时）课程简介：本课程主要介绍许多经典的非数值算法设计的常用方法，如贪婪法、递归、回溯法、动态规划法、分治法、探索法、分枝限界法等，分析这些算法的时间和空间复杂性。通过学习算法分析，掌握估计算法的时空复杂度的方法，从而能够正确地评价一个算法，设计出真正好的、有效的算法。教材名称：计算机算法设计与分析教材主编：王晓东出版日期：2004年7月出版社：电子工业出版社参考书目：1.T.H.Cormen.算法导论.北京：高等教育出版社.20012.苏德富、钟诚.计算机算法设计与

3、分析.北京：电子工业出版社,2001,1本电子书源于网络，由网金号http://www.egship.com搜集整理，严禁任何商业用途！《算法设计与分析》教案教学大纲课程名称：算法设计与分析英文名称：DesignandAnalysisofAlgorithms课程编号：4111309/2111309课程类别：专业选修课学时数：54学时（理论54学时，实验0学时）先修课程：离散数学、程序设计语言、数据结构适用年级：四年级（专升本二年级）适用专业：计算机科学与技术一、内容简介本课程首先介绍计算复杂性的定义和算法分析的基本方法，结合计算机科学及应用领域中常见的有代

4、表性的非数值算法，介绍了几种重要的算法设计的方法：分治法、动态规划、贪心法、回朔法、分支限界法，使学生在掌握各种算法的同时，掌握算法分析的基本方法和技巧。二、本课程的性质、目的和任务算法设计和分析是计算机软、硬件专业的选修课之一。算法的研究是计算机科学的核心问题之一，具有极大的应用价值和理论价值，因为它所涉及的范围十分广泛，不论是从事计算机硬件设计，还是从事计算机软件设计，都需要认真研究算法。本课程特别提倡学生广泛阅读参考书、独立思考、结合实际问题展开讨论的教学方式，并以此达到教师精讲、学生宽学的目的。三、本课程与其它课程的关系本课程的前导课程主要包括离散

5、数学、程序设计语言、数据结构等。其中，离散数学课程为算法设计和分析的学习和理解打下数学方面的基础；学习者需要依靠某种程序设计语言完成算法的计算机实现；算法设计，特别是对大型问题的算法设计，经常要用到表、堆栈、队列、树和图等，没有相应的数据结构方面的知识对算法设计和分析的学习是很困难的。四、本课程的基本要求通过本课程中许多常见且有代表性算法的学习，使学生理解和掌握算法设计的主要方法，同时掌握算法分析的基本方法和技巧，培养对算法时间、空间复杂性进行正确分析能力，为独立的设计算法和给定算法进行复杂性分析打下良好的基础。五、课程内容与学时分配本电子书源于网络，由网

6、金号http://www.egship.com搜集整理，严禁任何商业用途！《算法设计与分析》教案�理论教学内容第1章概论（4学时）1、课程内容：♦算法的概念、算法的特征♦算法设计和分析的步骤♦算法的复杂性2、学习目的与要求♦掌握基本知识：如算法的概念、特征；算法设计和分析的步骤♦掌握算法计算复杂性的几个评价标准：时间复杂性、空间复杂性；平均复杂性、最坏情况下的复杂性；均匀耗费标准的复杂性分析、对数耗费标准的复杂性分析本章重点：算法的计算复杂性分析本章难点：对数耗费标准的复杂性分析3、考核的知识点与考核要求♦会复述算法的概念、特征；算法设计和分析的步骤♦会对

7、给出的算法从不同标准进行计算复杂性的分析第2章递归与分治策略（8学时）1、课程内容：♦递归的概念♦分治法的基本思想♦分治法：二分搜索技术、大整数的乘法、Strassen矩阵、棋盘覆盖、合并排序、快速排序、线性时间选择、最接近点对问题、循环赛日程表2、学习目的与要求♦掌握用递归技术解决实际问题，会用递归函数过程完成递归算法的实现；会求解递归方程♦掌握整数乘法等问题的分治算法及该算法的计算复杂性分析本章重点：排序算法、整数相乘和矩阵相乘、最接近点对问题本章难点：算法的平均时间复杂性下界的证明3、考核的知识点与考核要求♦对一些具体实际问题，会书写递归算法；会求解

8、递归方程♦会给出Strassen矩阵乘法等问题的算法，能对具体实例