算法设计与分析教学大纲及实验大纲

《算法设计与分析教学大纲及实验大纲》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《算法设计与分析》教学大纲课程名称（中、英文）：算法设计与分析、DesignandAnalysisofAlgorithm课程编号：0811031学分数：3总学时数：45(理教：40实验：6)适用专业：计算机科学与技术专业、软件工程、网络工程一、课程的性质、目的与任务随着计算机的广泛应用，对计算机算法的研究变得日益重要。本课程将覆盖计算机软件实现中的大部分算法，并具有一定的深度和广度，使学生对计算机常用算法有一个全盘的了解；本课程首先介绍计算复杂性的定义和算法分析的基本方法，结合计算机科学及应用领域中常见的有代表性的非数

2、值算法，介绍了几种重要的算法设计的方法：分治法、动态规划、贪心法、回朔法、分枝限界法，NP完全问题。使学生在掌握各种算法的同时，掌握算法分析的基本方法和技巧。本课程的任务是：培养学生具有针对给定问题设计和实现高效算法的能力。包括以下三方面：1．通过对常用的、有代表性的算法的研究，让学生理解并掌握算法设计的基本技术。2．培养学生分析算法复杂度的初步能力，锻炼其逻辑思维能力和想象力，并使之了解算法理论的发展。3．鼓励学生运用算法知识解决各自学科的实际问题，培养他们的独立科研的能力和理论联系实践的能力。二、课程的基本要求本课

3、程在学习之前，最好具有离散数学、程序设计、数据结构等方面的知识。在此基础上通过本课程的学习，掌握算法的定义及基本概念、计算模型和复杂度的质量；为分析算法的复杂性做准备，在这个基础上，学习一些常用的算法设计策略，掌握其基本思想和相应算法，编制出相应程序上机调试。三、基本教学内容与学时安排1.算法概述（4学时）(1)了解算法与程序的概念。(2)掌握算法复杂性分析及其有关的概念。2.递归与分治策略（8学时）(1)理解递归的概念。(2)了解分治法的基本思想。(3)掌握Strassen矩阵乘法、大整数乘法、线性时间选择、最接近点

4、对问题的算法。(4)理解合并排序和快速排序算法。3.动态规划（8学时）(1)掌握动态规划算法的概念和步骤。(2)掌握矩阵的连乘算法设计和分析。(3)掌握动态规划算法的基本要素。(4)掌握最长公共子序列、0-1背包问题的算法设计和分析。(5)了解凸多边形最优三角剖分、多边形游戏、流水作业调度问题的算法设计和分析。4.贪心算法（6学时）(1)掌握贪心算法的概念。(2)掌握贪心算法的基本要素。(3)了解最优装载问题的算法分析。(4)了解哈夫曼编码的算法分析。(5)了解单源最短路径的Dijkstra算法的设计与分析。(6)了解

5、最小生成树的Prim和Kruskal算法的设计与分析。5.回溯法（4学时）(1)掌握回溯法的算法框架。(2)掌握装载问题、批处理作业调度、符号三角形问题、0-1背包问题、图的m着色问题的算法设计与分析。(3)了解n后问题、最大团问题的回溯法的算法设计与分析。6.分支限界法（4学时）(1)掌握分支限界法的基本思想。(2)掌握单源最短路问题、0-1背包问题的分支限界法分析。(3)了解旅行售货员问题的算法设计与分析。7.随机化算法（2学时）(1)掌握随机化算法的特征。(2)掌握随机化算法的4种分类。(3)理解产生伪随机数的算

6、法。8.NP完全性问题（4学时）(1)了解NP完全性问题的概念。(2)理解求解问题的计算模型。(3)了解P类问题和NP类问题。(4)了解NP完全问题。(5)了解一些典型的NP完全问题。四、建议学时分配表序号教学内容课时分配讲课实验习题小计1第一章算法概述442第二章递归与分治策略82103第三章动态规划82104第四章贪心算法62105第五章回溯法446第六章分支限界法447第七章随机化算法227第八章NP完全性问题44合计40646五、使用教材及主要参考书课程教材：1.王晓东.《计算机算法设计与分析》.电子工业出版社

7、.2007年5月主要参考书：1.吕国英.算法设计与分析.清华大学出版社.2006.3(1)2.王晓东.算法设计与实验题解.电子工业出版社2006.9(1)3.T.H.Cormen,C.E.Leiserson,R.L.RivestandC.Stein(2001),IntroductiontoAlgorithms(thesecondedition).TheMITPress，中文名《算法导论（第二版）》（影印版），高等教育出版社六、考核方式考核方式：平时作业、课堂回答问题及考勤、实验占30%，期末考试占70%。制定：高艳霞执

8、笔，教研室集体讨论审定：批准：2007年11月《算法设计与分析》实验教学大纲课程名称（中、英文）：算法设计与分析、DesignandAnalysisofAlgorithm课程编号：0811031课程总学时/学分：45/3实验总学时：6适用专业：计算机科学与技术专业、网络工程、软件工程一、实验教学目标《算法设计与分析》旨在教会学生处