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

《算法分析与设计》课程教学大纲课程代码：ABXX0432课程中文名称：算法分析与设计课程英文名称：AnalysisandDesignofAlgorithms课程性质：选修课程学分数：3学分课程学时数：48学时其中理论学时：32学时实验学时：164学时授课对象:计算科学与技术专业本课程的前导课程：计算机程序设计、数据结构一、课程简介本课程的研究内容取材于算法设计与分析领域的经典内容，主要包括非常经典的算法设计技术，例如递归与分治、动态规划、贪心、回溯、分支限界、图算法；也包括了一些高级的算法设计主题，例如网络流和匹配、启发式搜索、线性规划、数论以及计算几何等。在算法分析方面，介绍了概率分析以及最新的分摊分析和实验分析方法。在算法的理论方面，介绍了问题的下界、算法的正确性证明以及NP完全理论等方面的内容。二、课程性质和任务通过对常用的、有代表性的算法的研究，让学生理解并掌握算法设计的基本技术。培养学生分析算法复杂度的初步能力，锻炼其逻辑思维能力和想象力，并使之了解算法理论的发展。鼓励学生运用算法知识解决各自学科的实际问题，培养学生的独立科研的能力和理论联系实践的能力。三、教学内容及要求（一）算法概述教学内容：算法，算法复杂度的基本概念，及时间复杂度。重点难点：掌握算法，算法复杂度的基本概念，及时间复杂度的估算方法。目的与要求：掌握算法，算法复杂度的基本概念，及时间复杂度的估算方法。（二）递归与分治法教学内容：递归概念，分治法基本思想，二分搜索技术，大整数乘法，矩阵乘法，棋盘覆盖，合并排序，快速排序，线性时间选择，最接近点对问题，循环赛日程表。重点难点：掌握递归法、分治法解决实际问题的基本思想及能力，算法复杂度（时间和空间）的分析能力。目的与要求：掌握递归的概念，学会用递归方法解决实际问题；熟练掌握利用分治法解决问题的基本思想，会用某高级语言对算法进行描述，并对算法复杂度（时间和空间）进行分析。（三）动态规划教学内容：动态规划的基本要素，矩阵连乘，最长公共子序列，最大子段和，凸多边形最优三角剖分，多边形游戏，图像压缩，电路布线，流水作业调度，0-1背包问题，最优二叉搜索树。重点难点：问题分析及利用动态规划方法解决问题的基本思想及能力，矩阵连乘，最长公共子序列，流水作业调度，0-1背包问题，最优二叉搜索树。目的与要求：熟练掌握利用动态规划方法解决问题的基本思想；学会如何将问题化为多阶段图的方法；能对具体问题写出正确的递推公式。（四）贪心算法教学内容：贪心算法的基本要素，活动安排问题，最优装载，哈夫曼编码，单源最短路径，最小生成树，多机调度。重点难点：利用贪心算法解决问题的基本思想，最优装载，哈夫曼编码，单源最短路径，最小生成树。目的与要求：掌握利用贪心算法解决问题的基本思想；会用某高级语言编写用贪心算法解决问题的程序，并能对算法的复杂度，可靠性进行分析。（五）回溯法教学内容：回溯法的算法框架、符号，三角形问题，n个皇后问题，最大团问题，图的m着色问题，旅行售货员问题，圆排列问题，连续邮资问题，电路板排列问题。重点难点：回溯法，三角形问题，n个皇后问题，最大团问题，图的m着色问题，旅行售货员问题。掌握利用回溯法解决问题的基本思想。目的与要求：掌握利用回溯法解决问题的基本思想；会用回溯法解决：n个皇后问题，图的m着色问题，批处理作业调度问题等，并能准确地分析回溯法的效率及稳定性。（六）分支限界法教学内容：分支限界的基本思想，单源最短路径，布线问题，0－1背包问题，批处理作业调度问题。重点难点：分支限界，单源最短路径，布线问题，0－1背包问题，批处理作业调度问题。各方法的效率分析。目的与要求：掌握利用分支限界法解决问题的基本思想；能用多种不同方法解法同一问题，并分析各方法的效率。（七）概率算法教学内容：概率算法的基本思想，随机数，数值概率算法，舍伍德算法，拉斯维加斯算法，蒙特卡罗算法。重点难点：概率算法，随机数，数值概率算法，舍伍德算法，拉斯维加斯算法，蒙特卡罗算法。掌握利用概率算法的基本思想,会用概率算法解决有关问题。目的与要求：掌握利用概率算法的基本思想；会用概率算法解决有关问题。（八）线性规划和网络流（选学）教学内容：线性规划的基本概念、定理及单纯形算法，最大网络流和最小费用流问题的解法。重点难点：线性规划概念、定理及单纯形算法，最大网络流和最小费用流问题的解法。目的与要求：了解线性规划模型的特点、线性规划问题的标准型及退化处理；掌握线性规划问题解的概念、有关解的基本定理；掌握单纯形法的的原理和求解方法；掌握实践中常见问题的建模方法；掌握最大网络流问题的求解方法和最小费用流问题的求解方法。（九）NP完全性理论与近似算法（选学）教学内容：计算模型，P类与NP类问题，NP完全问题，合取范式（CNF）顶点覆盖问题，哈密顿回路问题；近似算法的基本思想及性能，顶点覆盖问题的近似算法，集合覆盖问题的近似算法，子集合问题的近似算法。重点难点：计算模型，P类与NP类问题，NP完全问题，合取范式（CNF）顶点覆盖问题，哈密顿回路问题。掌握利用近似算法解决问题的基本思想，能对其可靠性进行分析。目的与要求：了解NP完全性问题；掌握P类与NP类问题的划分；掌握利用近似算法解决问题的基本思想，能对其可靠性进行分析。四、实验教学内容及基本要求序号内容学时1递归与分治策略42动态规划23贪心算法24回溯法25分支界限法26概率算法4合计16五、理论教学环节学时分配课程内容课时习题课小计一、算法概述202二、递归与分治法426三、动态规划404四、贪心算法426五、回溯法404六、分支限界法426七、概率算法404八、线性规划和网络流（选学）000九、NP完全性理论与近似算法（选学）000合计26632六、考核方式与成绩评定标准考核方式：考试（平时成绩占总成绩的30％，期末考试60%，上机10%）七、推荐教材和教学参考资源参考书目：1.（美）Anany