算法分析与设计课程教学大纲.doc

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

1、《算法分析与设计》课程教学大纲课程编号： 00600660课程名称：算法分析与设计英文名称：AnalysisandDesignofComputerAlgorithms课程类别：专业基础课授课对象：硕士学分：3学时：60开课学期：2开课周次：1-16开课系及教研室：计算机科学与技术任课教师及职称：王默玉副教授先修课程：高等数学、离散数学、高级语言、数据结构适用专业：计算机科学与技术、软件工程专业主要内容和要求：（1）算法及计算复杂性：阐述算法及其算法的计算复杂性的主要内容，渐近时间复杂性，时间复杂性的上界、下界；多项式时间与指数时

2、间对算法的影响。（2）介绍递归技术、递归方程的求解：包括递归算法的构成，递归方程的求解。（3）介绍分治法的思想和解决方法：包括一般方法，分治法的效率分析，并介绍分治法应用的典型实例，如二分搜索法，找最大最小值，快速分类，归并分类，大整数乘法，斯特拉斯矩阵乘法，循环赛安排等。（4）介绍贪心方法的内容及应用实例：包括一般方法，贪心法的基本要素，背包问题，最优装载问题，活动安排问题，多机调度问题，货郎担问题，最优归并模式等。（5）介绍动态规划方法的思想及应用条件，用实例介绍动态规划方法的应用：包括一般方法，最优性原理，动态规划算法与分

3、治算法、贪心算法的区别，动态规划算法的设计步骤，动态规划算法的基本要素，多段图问题，0/1背包问题，资源分配问题，货郎担问题，可靠性问题（6）介绍回溯法的一般方法，效率估计，典型事例有：N皇后问题，子集和数问题，图的M着色问题，背包问题等。（7）介绍分枝-限界法的核心思想及实例：主要有分枝限界算法的基本思想，FIFO检索和LIFO检索与最小代价搜索(LC搜索)的不同，LC-检索的抽象化控制，LC-检索的特性；使用分枝限界算法分析和解决具体问题有：15谜问题，带限期的作业排序，0-1背包问题等。（8）介绍NP-完全问题：主要介绍三

4、种计算模式，图灵机工作原理，COOK定理，NP难度问题与完全问题的可转化问题。使用教材：《计算机算法基础》,余翔宣主编，华中科技出版社，2006年第3版参考书目：《算法分析与设计》，校内自编讲义，2000年《算法分析与设计》，霍红卫主编，西安电子大学出版社，2005年《计算机算法分析与设计》，王晓东主编，电子工业出版社，2001年《计算机算法基础》，邹海明等，华中理工大学出版社,1985年《算法设计与分析》，原福永等，机械工业出版社,1998年教研室意见：系（院、部）意见：研究生院审核意见：华北电力大学专业学位硕士研究生自学指导

5、书年级、专业：计算机应用技术课程名称：算法分析与设计自学时间：8周教材名称：《计算机算法基础》自学学时：40学时编写教师：王默玉周次学时学习内容对应章节习题、思考题、测试题（可另附录）14算法及其算法的计算复杂性第一章24递归技术与递归方程的求解第二章36分治法第三章44贪心方法第四章56动态规划方法第五章66回溯法第六章76分枝限界法第七章84NP完全问题第八章备：授课学时为计划学时的2/3左右，自学学时为计划学时的1-2倍。