[教学目的要求.docVIP

教 案 2006-2007学年第一学期 课 程 名 称： 计算机算法设计与分析  课程简介 课程编号：4111309-1, 4111309-2, 2111309-0 课程名称：算法设计与分析 英文名称：The Design and Analysis of Algorithms 课程类别：专业课 先修课程：《C程序设计》、《离散数学》、《计算方法》、《数据结构》 周学时数：3 总学时数：54学时（理论54学时，实验0学时） 课程简介： 本课程主要介绍许多经典的非数值算法设计的常用方法，如贪婪法、递归、回溯法、动态规划法、分治法、探索法、分枝限界法等，分析这些算法的时间和空间复杂性。通过学习算法分析，掌握估计算法的时空复杂度的方法，从而能够正确地评价一个算法，设计出真正好的、有效的算法。 教材名称：计算机算法设计与分析 教材主编：王晓东 出版日期：2004年7月 出 版 社：电子工业出版社 参考书目： 1. 王若东. 算法设计与分析. 北京：清华大学出版社.2007 2. T.H.Cormen. 算法导论. 北京：高等教育出版社.2001 3. 苏德富、钟诚.计算机算法设计与分析. 北京：电子工业出版社, 2001,1  教学大纲 课程名称：算法设计与分析 英文名称：Design and Analysis of Algorithms 课程编号：4111309/2111309 课程类别：专业选修课 学时数：54学时（理论54学时，实验0学时） 先修课程：离散数学、程序设计语言、数据结构 适用年级：四年级（专升本二年级） 适用专业：计算机科学与技术 一、内容简介 本课程首先介绍计算复杂性的定义和算法分析的基本方法，结合计算机科学及应用领域中常见的有代表性的非数值算法，介绍了几种重要的算法设计的方法：分治法、动态规划、贪心法、回朔法、分支限界法，使学生在掌握各种算法的同时，掌握算法分析的基本方法和技巧。 二、本课程的性质、目的和任务 算法设计和分析是计算机软、硬件专业的选修课之一。 算法的研究是计算机科学的核心问题之一，具有极大的应用价值和理论价值，因为它所涉及的范围十分广泛，不论是从事计算机硬件设计，还是从事计算机软件设计，都需要认真研究算法。 本课程特别提倡学生广泛阅读参考书、独立思考、结合实际问题展开讨论的教学方式，并以此达到教师精讲、学生宽学的目的。 三、本课程与其它课程的关系 本课程的前导课程主要包括离散数学、程序设计语言、数据结构等。 其中，离散数学课程为算法设计和分析的学习和理解打下数学方面的基础；学习者需要依靠某种程序设计语言完成算法的计算机实现；算法设计，特别是对大型问题的算法设计，经常要用到表、堆栈、队列、树和图等，没有相应的数据结构方面的知识对算法设计和分析的学习是很困难的。 四、本课程的基本要求 通过本课程中许多常见且有代表性算法的学习，使学生理解和掌握算法设计的主要方法，同时掌握算法分析的基本方法和技巧，培养对算法时间、空间复杂性进行正确分析能力，为独立的设计算法和给定算法进行复杂性分析打下良好的基础。 五、课程内容与学时分配 理论教学内容 第1章 概论（4学时） 1、课程内容： 算法的概念、算法的特征 算法设计和分析的步骤 算法的复杂性 2、学习目的与要求 掌握基本知识：如算法的概念、特征；算法设计和分析的步骤 掌握算法计算复杂性的几个评价标准：时间复杂性、空间复杂性；平均复杂性、最坏情况下的复杂性；均匀耗费标准的复杂性分析、对数耗费标准的复杂性分析 本章重点：算法的计算复杂性分析 本章难点：对数耗费标准的复杂性分析 3、考核的知识点与考核要求 会复述算法的概念、特征；算法设计和分析的步骤 会对给出的算法从不同标准进行计算复杂性的分析 第2章 递归与分治策略（8学时） 1、课程内容： 递归的概念 分治法的基本思想 分治法：二分有哪些信誉好的足球投注网站技术、大整数的乘法、Strassen矩阵、棋盘覆盖、合并排序、快速排序、线性时间选择、最接近点对问题、循环赛日程表 2、学习目的与要求 掌握用递归技术解决实际问题，会用递归函数过程完成递归算法的实现；会求解递归方程 掌握整数乘法等问题的分治算法及该算法的计算复杂性分析 本章重点：排序算法、整数相乘和矩阵相乘、最接近点对问题 本章难点：算法的平均时间复杂性下界的证明 3、考核的知识点与考核要求 对一些具体实际问题，会书写递归算法；会求解递归方程 会给出Strassen矩阵乘法等问题的算法，能对具体实例给出算法的工作过程，并能对该算法进行分析 能用分治平衡法对具体问题进行算法实现 第3章 动态规划（8学时） 1、课程内容： 矩阵连乘问题 动态规划算法的基本要素 最长公共