《算法设计与分析A教学大纲》由会员分享，可在线阅读，更多相关《算法设计与分析A教学大纲（2页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析A教学大纲Design and Analysis of Algorithm A课程代码：课程性质：专业方向理论课/选修适用专业：信息计算、信息安全开课学期：7总学时数：56总学分数：3.5编写年月：2004年7月修订年月：2007年7月执 笔：王振友一、课程的性质和目的算法设计与分析是数学算法研究何计算机软件开发人员的一门重要课程，软件的效率和稳定性取决于软件中所采用的算法；对于一般程序员学生，学习算法设计与分析课程，可以开阔编程思路，编写出优质程序。二、课程教学内容及学时分配1.知识要求：通过一学期学习要达到如下要求（1）掌握算法的定义及基本概念、计算模型和复杂度的衡量；（2）
2、为分析算法的复杂性作准备，要了解相应的数学知识；（3）掌握算法设计的过程和方法；（4）学会分析算法的时间复杂度、空间复杂度和稳定性；（5）具有问题抽象和建模的初步能力。2. 能力要求：通过本课程的学习，学生要掌握几种常用的算法设计策略，包括递归与分治策略、动态规划算法、贪心算法、回溯法、分支限界法概率算法、线性规划和网络流法和NP完全性理论与近似算法等，并会分析算法的效率。能够用所学方法解决实际问题。3.教学内容和基本要求：第一章 算法概述（4学时）掌握算法，算法复杂度的基本概念，及时间复杂度的估算方法。第二章 递归与分治法（8学时，含2个学时实验上机）掌握递归的概念，学会用递归方法解决实际问
3、题，熟练掌握利用分治法解决问题的基本思想，会用某高级语言对算法进行描述，并对算法复杂度（时间和空间）进行分析。主要内容：递归概念，分治法基本思想，二分搜索技术，大整数乘法，矩阵乘法，棋盘覆盖，合并排序，快速排序，线性时间选择，最接近点对问题，循环赛日程表。重点：递归，分治法的基本思想第三章 动态规划（8学时）熟练掌握利用动态规划方法解决问题的基本思想，学会如何将问题化为多阶段图的方法，并能对具体问题写出正确的递推公式。主要内容：动态规划的基本要素，矩阵连乘，最长公共子序列，最大子段和，凸多边形最优三角剖分，多边形游戏，图像压缩，电路布线，流水作业调度，0-1背包问题，最优二叉搜索树。重点：动态
4、规划算法的基本要素。第四章 贪心算法（6学时，含2个学时实验上机）掌握利用贪心算法解决问题的基本思想，会用某高级语言编写用贪心算法解决问题的程序，并能对算法的复杂度，可靠性进行分析。主要内容：贪心算法的基本要素，活动安排问题，最优装载，哈夫曼编码，单源最短路径，最小生成树，多机调度。重点：贪心算法的基本要素第五章 回溯法（6学时）掌握利用回溯法解决问题的基本思想，会用回溯法解决：n个皇后问题，图的m着色问题，批处理作业调度问题等，并能准确地分析回溯法的效率及稳定性。主要内容：回溯法的算法框架、符号，三角形问题，n个皇后问题，最大团问题，图的m着色问题，旅行售货员问题，圆排列问题，连续邮资问题，
5、电路板排列问题。重点：回溯法的基本思想，回溯法的效率分析。第六章 分支限界法（6学时，含2个学时实验上机）掌握利用分支限界法解决问题的基本思想，能用多种不同方法解法同一问题，并分析各方法的效率。主要内容：分支限界的基本思想，单源最短路径，布线问题，01背包问题，批处理作业调度问题。重点：分支限界法的基本思想和各方法的效率分析。第七章 概率算法（6学时）掌握利用概率算法的基本思想，会用概率算法解决有关问题，主要内容：概率算法的基本思想，随机数，数值概率算法，舍伍德算法，拉斯维加斯算法，蒙特卡罗算法。重点：概率算法的基本思想及准确应用。第八章 线性规划和网络流（6学时）了解线性规划模型的特点、线性
6、规划问题的标准型及退化处理，掌握线性规划问题解的概念、有关解的基本定理；掌握单纯形法的的原理和求解方法；掌握实践中常见问题的建模方法。掌握最大网络流问题的求解方法和最小费用流问题的求解方法。主要内容：线性规划的基本概念、定理及单纯形算法，最大网络流和最小费用流问题的解法。重点：线性规划的思想及单纯形算法、最大网络流问题最小费用流问题的求解方法第九章 NP完全性理论与近似算法（6学时，含2个学时实验上机）了解NP完全性问题，掌握P类与NP类问题的划分。掌握利用近似算法解决问题的基本思想，能对其可靠性进行分析。主要内容：计算模型，P类与NP类问题，NP完全问题，合取范式（CNF）顶点覆盖问题，哈密
7、顿回路问题；近似算法的基本思想及性能，顶点覆盖问题的近似算法，集合覆盖问题的近似算法，子集合问题的近似算法。重点：NP完全问题、近似算法的设计与可靠性分析三、课程教学的基本要求本课程是信息与计算科学专业的重要专业方向理论课，是软件开发赖以生存的重要基础。在教学方法上，采用课堂讲授，课后自学，课堂讨论等教学形式。(一)课堂讲授本课程属于专业方向理论课程。在传授知识原理的前提下，配合实际应用例子，由浅入深善于诱导，使学生从被动吸收知识的状态下，转化到主动索取知识的状态中来，并采用多媒体辅助教学，加大课堂授课的知识含量。注重培养学生的学习兴趣，提高学生的基本素质。（二）课后自学为了培养学生整理归纳，
8、综合分析和处理问题的能力，每章都安排一部分内容，课上教师只给出自学提纲，不作详细讲解，课后学生自学。（三）课堂讨论课堂讨论的目的是活跃学习气氛，开拓思路。教师应认真组织，安排重点发言，充分调动每一名同学的学习积极性，做好总结。（四）课外作业为了让学生巩固所学的知识，每章都布置一定数量课外作业。（五）实验用C语言或C+语言完成一些算法设计题。培养学生的算法设计能力和程序设计能力。总评成绩：平时作业占30%，闭卷考试占70%。四、其他课程的联系：算法设计与分析以高级语言程序设计、数据结构、计算方法、数学等课程为基础，在具有雄厚的以上四门课基础上对解决问题的算法进行综合设计与分析。五、建议教材及教学参考书1王晓东主编 计算机算法设计与分析第2版 电子工业出版社出版 2006年出版2徐士良主编 计算机常用算法第2版 清华大学出版社出版3卢开澄主编 计算机指导引论-设计与分析 清华大学出版社出版
