《算法分析与设计》课程教学大纲

1、算法分析与设计课程教学大纲Algorithms Analysis and Design 一 课程教学目标：1 任务和地位： 算法分析与设计是计算机应用与技术专业（本科）的一门专业课，其内容是研究计算机领域及其它有关领域中的一些常用算法，它是计算机科学通常要解决的主要问题之一，因而也是各专业方向可以选修的一门重要的专业基础课。通过本课程的学习，使学生掌握算法设计的常用方法，以便运用这些方法来设计解决一些常用的或较为复杂的实际问题的算法，并力争做到快捷、有效，从而提高程序设计的质量。除此，还要使学生学会分析算法、估计算法的时空复杂性，以便理解并科学评估有关算法。因而，对于计算机专业的技术人员，学习

2、和掌握这方面的知识是很有必要的。2 知识要求：通过一学期学习要达到如下要求1) 掌握算法的定义及基本概念、计算模型和复杂度的质量；2) 为分析算法的复杂性作准备，要了解相应的数学知识；3) 了解各种分类方法，重点是学会分析分类方法的复杂性。3 能力要求：通过本课程的学习，学生要掌握几种常用的算法设计策略，包括递归与分治策略、动态规划算法、贪心算法、回溯法和分支限界法等，并会分析算法的效率。能够用所学方法解决实际问题。二、教学内容的基本要求和学时分配1 学时分配教学内容章目本课程学分：3学时分配讲课课堂讨论（讲解上机题及习题）小计第一章绪论33第二章递归与分治策略11314第三章动态规划算法72

3、9第四章贪心算法516第五章回溯法9211第六章分支限界法33复习 32合计 408482 具体要求第一章 算法概述目的要求 掌握算法基本概念及算法复杂性分析。教学内容 算法与程序、算法复杂性分析。重点难点 让同学们了解本门学科在科技发展中地位和作用，增强学好本课程的信心。教学方法 课堂讲授与自学（课外）相结合。课 时 3学时。第二章 递归与分治策略目的要求 掌握递归与分治策略设计算法。教学内容 递归的概念、分治法的基本思想、及分治算法实例。重点难点 分治法的基本思想的具体实现及时间复杂度分析。教学方法 课堂讲授与自学结合。课 时 14学时。第三章 动态规划目的要求 掌握用动态规划法设计算法。

4、教学内容 动态规划算法的基本要素、基本思想及算法实例。重点难点 动态规划算法基本思想的具体实现及时间复杂度分析。教学方法 课堂讲授与自学结合。课 时 9学时。第四章 贪心算法目的要求 掌握用贪心算法设计算法。教学内容 贪心算法的基本要素、基本思想及算法实例。重点难点 贪心算法基本思想的具体实现及时间复杂度分析。教学方法 课堂讲授与自学结合。课 时 6学时。第五章 回溯法目的要求 掌握回溯法算法的基本模式。教学内容 回溯法的算法框架及算法实例。重点难点 算法框架的具体应用。教学方法 课堂讲授与自学结合。课 时 11学时。第六章 分支限界法目的要求 了解分支限界法教学内容 分支限界法的基本思想及算

5、法实例。重点难点 算法框架的具体应用。教学方法 课堂讲授与自学结合。课 时 3学时。三 大纲说明1 考试方式闭卷考试2 实践性环节为配合理论教学，布置510个大作业题。3 考试成绩期末考试：70（80）%，平时30（20）%4 使用教材及主要参考书教材: 王晓东 计算机算法设计与分析 电子工业出版社 2002年参考资料:1严蔚敏 数据结构（C语言版） 清华大学出版社 2002年2郑莉 C语言程序设计（第二版）清华大学出版社 2001年3谭浩强 C程序设计（第二版）清华大学出版社 1999年西南交通大学峨眉校区课程简介课程名称中文算法分析与设计总学时48英文Algorithms Analysis

6、 and Design 学分3开课单位计算机与通信工程系授课方式讲授授课教师杨华莉撰搞人杨华莉适用专业计算机科学与技术、网络工程课程属性专业课先修课程高等数学、线性代数、概率论、程序设计语言C、数据结构课程简介本课程首先介绍计算机算法的基本概念，并对算法的特点、算法的计算复杂性和算法的描述作简要阐述，然后围绕算法设计常用的基本设计策略展开本课程的重要知识。算法设计的常用策略有：递归与分治策略、动态规划算法、贪心算法、回溯法和分支限界法。每一种策略，都先介绍其基本思想，然后从解决计算机科学和应用的实际问题入手，由简到繁的描述几个精典的精巧算法。同时对每个算法所需的时间和空间进行分析，让学生既能学到一些常用的精巧算法，又能通过从对算法设计策略的反复应用，牢固掌握这些算法设计的