2315200201_算法设计与分析_刘刚(软件)_教学大纲doc

《2315200201_算法设计与分析_刘刚(软件)_教学大纲doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、深圳大学课程教学大纲课程编号:2315120101/2/3课程名称:算法分析与设计开课院系:计算机与软件学院软件工程系制订(修订)人:卢亚辉刘刚审核人:批准人：2012年09月2日制(修)订课程名称:算法分析与设计英文名称:DesignandAnalysisofAlgorithms总学时:54其中:实验课18学时学分:2.5先修课程:高级语言程序设计、高等数学、线性代数、离散数学、数据结构教材:潘彦译（[美]AnanyLevitin），算法设计与分析基础（IntroductiontoDesignandAnalysisofAlgorithms），清

2、华大学出版社，2004.6参考教材:王晓东，计算机算法设计与分析（第2版），电子工业出版社，2004.7课程性质:□综合必修□专业必修■专业选修□全校公选教学目标:算法设计与分析课程是计算机类专业的专业基础课。是一门面向设计，处于计算机科学与技术学科核心地位的教育课程。通过对计算机算法系统的学习与研究，理解和掌握算法设计的主要方法，培养对算法的计算复杂性进行正确分析的能力，为独立地设计算法和对给定算法进行复杂性分析奠定坚实的理论基础。本课程以算法设计策略为知识单元，系统地介绍计算机算法的设计方法与分析技巧，以期为计算机学科的学生提供广泛坚实的计算

3、机算法基础知识。教学内容：1．算法引论算法定义及特征，算法设计的例子，时间复杂性，时间复杂性分析,空间复杂度分析*。要求：了解计算机算法的定义以及特征。掌握算法设计的例子。理解时间复杂性的定义以及相关概念，掌握复杂性分析的几种类型以及分析方法。2．递归与分治策略递归的基本思想，递归算法的例子，分治的基本思想，Strassen矩阵乘法，最小闭包问题要求：理解递归算法以及分治算法的基本思想，掌握多项式乘积的分治方法。能对递归算法以及分治算法进行分析。理解大整数乘法的理论分析以及编程实现。掌握合并排序算法。3．贪心算法，贪心算法的设计思想，背包问题，单

4、源最短路径问题，Huffman编码。要求：理解贪心算法的设计思想以及适用范围，掌握贪心算法典型例子如背包问题，单元最短路径问题。4．动态规划算法，动态规划的思想方法，最优决策原理，多段图的最短路径问题，0/1背包问题，Floyd算法要求：理解动态规划算法的设计思想以及适用范围，掌握最优决策原理的概念以及分析方法。掌握动态规划算法典型例子如多段图的最短路径问题，0/1背包问题的解决方案。5．回溯法回溯法的思想方法，N后问题，回溯法解0/1背包问题，哈密顿回路问题*，回溯法的效率分析要求：理解回溯法的设计思想以及适用范围，掌握解空间树的概念并能熟练应

5、用于回溯法。掌握回溯算法典型例子如N后问题，0/1背包问题的解决方案。了解回溯法的效率分析方法。掌握N后问题能程序实现的方法。6．分支限界法分支限界法的基本思想，0/1背包问题，货郎担问题,要求：理解分支限界法的设计思想以及适用范围，掌握分支限界法典型例子如0/1背包问题，货郎担问题的解决方案。7．NP问题NP问题基本概念，一些典型的NP完全问题，近似算法及实例要求：了解P，NP，NPC问题的分类，概念以及关系，了解典型的NP问题的例子。(注：带*号者为选讲内容。根据学生其他内容的掌握情况而定)学时分配：（请填写下表）序号教学内容课堂讲授习题课讨

6、论课上机实验1算法引论42递归与分治策略6263贪心算法44动态规划425回溯法3106分支限界法37NP完全性理论简介22合计3216五、实验内容及安排《算法分析与设计》课程是一门理论与实践性并重的课程，它不仅要求掌握学习算法设计的主要策略方法，而且还要掌握算法设计的实现。本课程实验目的是验证、巩固和补充课堂讲授的理论知识。培养学生初步具备独立设计算法和对给定算法进行复杂性分析的能力，为实际工作打下基础。实验的安排和要求是：用程序实现经典算法，学习算法设计的主要策略方法、原理并根据实例加以调试，培养动手设计、分析和综合实验结果以及撰写实验报告的

7、能力。在实验中养成严肃认真的治学态度和踏实细致、实事求是的作风。实验内容如下：注：带’*’号实验中，由教师按照学生实际情况选择其一要求学生完成。序号实验项目名称实验内容实验要求实验时数每组人数实验类型1基于分治法的大整数乘法理解分治法编写程序并记录运行结果，分析复杂度并整理成实验报告61-3综合2*基于Huffman算法的压缩软件设计实验*理解Huffman算法用程序设计huffman编码器以及huffman解码器软件。验证其正确性。计算出其压缩率。分析huffman算法的压缩原理，实现压缩软件。101-3综合3*背包算法及其分析试验理解背包算法

8、，用程序设计背包算法。验证其正确性。计算出其压缩率。编写程序并记录运行结果，分析复杂度并整理成实验报告101-3综合3*图形化N后问题解