算法分析与设计课程教学大纲《算法分析与设计》课程教学大纲一、课程基本信息课程代码：110426课程名称：算法分析与设计英文名称：Analysis and Design of Algorithms课程类别：专业基础课学时：45学分：2适用对象: 信息与计算科学专业本科生考核方式：考试（平时成绩占总成绩的30％）先修课程：数学分析、高级语言程序设计、数据结构二、课程简介中文简介《算法分析与设计》是软件开发人员必修专业课，软件的效率和稳定性取决于软件中所采用的算法；对于一般程序员和软件类专业学生，学习算法设计与分析课程，可以开阔编程思路，编写出优质程序。
英文简介Analysis and Design of Algorithms is a compulsory specialty course for software developer. Efficiency and stability of software depends on algorithms used in it. For common coders and software relative students, learning this course could expand their programming vision and help them programming high quality codes.三、课程性质与教学目的通过对常用的、有代表性的算法的研究，让学生理解并掌握算法设计的基本技术。
培养学生分析算法复杂度的初步能力，锻炼其逻辑思维能力和想象力，并使之了解算法理论的发展。
鼓励学生运用算法知识解决各自学科的实际问题，培养学生的独立科研的能力和理论联系实践的能力。
四、教学内容及要求第一章算法概述(一)目的与要求掌握算法，算法复杂度的基本概念，及时间复杂度的估算方法。
(二)教学内容1.主要内容算法，算法复杂度的基本概念，及时间复杂度。
2.基本概念和知识点算法，算法复杂度的基本概念，及时间复杂度。
3.问题与应用（能力要求）掌握算法，算法复杂度的基本概念，及时间复杂度的估算方法。
(三)课后练习函数的渐进表达式。
(四)教学方法与手段课堂讲授为主，结合课堂分组讨论。
第二章递归与分治法（一）目的与要求1.掌握递归的概念，学会用递归方法解决实际问题；2.熟练掌握利用分治法解决问题的基本思想，会用某高级语言对算法进行描述，并对算法复杂度（时间和空间）进行分析。
（二）教学内容1．主要内容递归概念，分治法基本思想，二分搜索技术，大整数乘法，矩阵乘法，棋盘覆盖，合并排序，快速排序，线性时间选择，最接近点对问题，循环赛日程表。
2．基本概念和知识点递归概念，分治法，二分搜索，大整数乘法，矩阵乘法，棋盘覆盖，合并排序，快速排序。
3．问题与应用（能力要求）掌握递归的概念，学会用递归方法解决实际问题，熟练掌握利用分治法解决问题的基本思想，会用某高级语言对算法进行描述，并对算法复杂度（时间和空间）进行分析。
（三）课后练习Hanoi塔问题的非递归算法。
（四）教学方法与手段课堂讲授为主，结合课堂分组讨论。
第三章动态规划（一）目的与要求1．熟练掌握利用动态规划方法解决问题的基本思想；2．学会如何将问题化为多阶段图的方法；3．能对具体问题写出正确的递推公式。
（二）教学内容1．主要内容动态规划的基本要素，矩阵连乘，最长公共子序列，最大子段和，凸多边形最优三角剖分，多边形游戏，图像压缩，电路布线，流水作业调度，0-1背包问题，最优二叉搜索树。
2．基本概念和知识点动态规划的基本要素，最长公共子序列，最大子段和，凸多边形最优三角剖分,0-1背包问题，最优二叉搜索树。
3．问题与应用（能力要求）熟练掌握利用动态规划方法解决问题的基本思想。
（三）课后练习最长单调递增子序列。
（四）教学方法与手段课堂讲授为主，结合分组课堂讨论。
第四章贪心算法（一）目的与要求1．掌握利用贪心算法解决问题的基本思想；2．会用某高级语言编写用贪心算法解决问题的程序，并能对算法的复杂度，可靠性进行分析。
（二）教学内容1．主要内容贪心算法的基本要素，活动安排问题，最优装载，哈夫曼编码，单源最短路径，最小生成树，多机调度。
2．基本概念和知识点贪心算法，哈夫曼编码，单源最短路径，最小生成树。
3．问题与应用（能力要求）掌握利用贪心算法解决问题的基本思想。
（三）实践环节与课后练习活动安排问题的贪心选择算法。
（四）教学方法与手段课堂讲授为主，结合课堂分组讨论。
第五章回溯法（一）目的与要求1．掌握利用回溯法解决问题的基本思想；2．会用回溯法解决：n个皇后问题，图的m着色问题，批处理作业调度问题等，并能准确地分析回溯法的效率及稳定性。
（二）教学内容1.主要内容回溯法的算法框架、符号，三角形问题，n个皇后问题，最大团问题，图的m着色问题，旅行售货员问题，圆排列问题，连续邮资问题，电路板排列问题。
2.基本概念和知识点回溯法，三角形问题，n个皇后问题，最大团问题，图的m着色问题，旅行售货员问题。
3.问题与应用（能力要求）掌握利用回溯法解决问题的基本思想。
（三）课后练习装载问题的改进回溯法。
（四）教学方法与手段课堂讲授为主，结合课堂分组讨论。
第六章分支限界法（一）目的与要求1.掌握利用分支限界法解决问题的基本思想；2.能用多种不同方法解法同一问题，并分析各方法的效率。
（二）教学内容1．主要内容分支限界的基本思想，单源最短路径，布线问题，0－1背包问题，批处理作业调度问题。
2．基本概念和知识点分支限界，单源最短路径，布线问题，0－1背包问题，批处理作业调度问题。
3.问题与应用（能力要求）掌握分支限界法解决问题的基本思想，能用多种不同方法解法同一问题，并分析各方法的效率。
（三）实践环节0-1背包问题的栈式分支限界法。
（四）教学方法与手段课堂讲授为主，结合课堂分组讨论。
*第七章概率算法（选学）（一）目的与要求1.掌握利用概率算法的基本思想；2.会用概率算法解决有关问题。
（二）教学内容1．主要内容概率算法的基本思想，随机数，数值概率算法，舍伍德算法，拉斯维加斯算法，蒙特卡罗算法。
2．基本概念和知识点概率算法，随机数，数值概率算法，舍伍德算法，拉斯维加斯算法，蒙特卡罗算法。
3.问题与应用（能力要求）掌握利用概率算法的基本思想,会用概率算法解决有关问题。
（三）实践环节与课后练习模拟正态分布随机变量。
（四）教学方法与手段课堂讲授为主，结合课堂分组讨论。
*第八章线性规划和网络流（自学）（一）目的与要求1.了解线性规划模型的特点、线性规划问题的标准型及退化处理；2.掌握线性规划问题解的概念、有关解的基本定理；3.掌握单纯形法的的原理和求解方法；4.掌握实践中常见问题的建模方法；5.掌握最大网络流问题的求解方法和最小费用流问题的求解方法。
（二）教学内容1．主要内容线性规划的基本概念、定理及单纯形算法，最大网络流和最小费用流问题的解法。
2．基本概念和知识点线性规划概念、定理及单纯形算法，最大网络流和最小费用流问题的解法。
3. 应用（能力要求）掌握线性规划问题解的概念、有关解的基本定理；掌握单纯形法的的原理和求解方法；掌握实践中常见问题的建模方法。
掌握最大网络流问题的求解方法和最小费用流问题的求解方法。
（三）实践环节与课后练习单源最短路径与线性规划。
（四）教学方法与手段课堂讲授为主，结合课堂分组讨论。
*第九章 NP完全性理论与近似算法（选学）（一）目的与要求1．了解NP完全性问题；2．掌握P类与NP类问题的划分；3．掌握利用近似算法解决问题的基本思想，能对其可靠性进行分析。
（二）教学内容1．主要内容计算模型，P类与NP类问题，NP完全问题，合取范式（CNF）顶点覆盖问题，哈密顿回路问题；近似算法的基本思想及性能，顶点覆盖问题的近似算法，集合覆盖问题的近似算法，子集合问题的近似算法。
2．基本概念和知识点计算模型，P类与NP类问题，NP完全问题，合取范式（CNF）顶点覆盖问题，哈密顿回路问题。
3．问题与应用（能力要求）了解NP完全性问题,掌握P类与NP类问题的划分。
掌握利用近似算法解决问题的基本思想，能对其可靠性进行分析。
（三）实践环节与课后练习RAM和RASP程序。
（四）教学方法与手段课堂讲授为主，结合课堂分组讨论。
六、推荐教材和教学参考资源推荐教材：王晓东，计算机算法设计与分析(第二版)，北京：电子工业出版社，2004。
教学参考资源：1. D．E．Knuth著，管纪文译，计算机程序设计技巧第一卷（1978），第二卷（1982），长沙：国防工业出版社，1978。
2. 卢开澄，计算机算法导引，北京：清华大学出版社，2000。
七、其他说明大纲修订人：吴东庆修订日期：2007.4.9大纲审定人：胡小健审定日期：2007.5.28。
