算法设计与分析教与学教学大纲.docx

《算法设计与分析教与学教学大纲.docx》由会员分享，可在线阅读，更多相关《算法设计与分析教与学教学大纲.docx（8页珍藏版）》请在优知文库上搜索。

1、算法设计与分析教与学教学大纲课程代码：*课程负责人：*课程中文名称：算法设计与分析课程英文名称：DesignandAnalysisofAlgorithms课程类别：必修课程学分数：3+0.5课程学时数：48（课堂学时）+12（实验学时）授课对象：计算机科学与技术及相关专业本科本课程的前导课程：C/C+程序设计、离散数学、数据结构1教学目的本课程是计算机科学与技术专业的专业课。通过课堂讲授、课堂练习和讨论互动、课后作业和上机实验等教学手段，系统掌握算法的有关概念和算法设计的基本策略。使学生掌握计算机算法的基本概念和特性，了解计算机相关学科中算法设计技术的重要性，掌握算法时间复杂性的分析方法。结合

2、典型示例和实战问题求解过程，使学生重点掌握分治法、回溯法、分支限界法、贪心法和动态规划法等算法设计策略，具备灵活运用所学解决复杂工程应用问题的能力。2课程教学目标本课程的目的在于培养学生掌握算法设计与分析的基本理论和方法，并且能够针对具体问题综合利用算法设计与分析的理论和方法分析实际问题；培养学生解决实际问题的能力。通过对该课程的学习，应达到以下课程目标：课程目标1：掌握算法的基本概念和特性,掌握算法时间复杂度的分析方法。课程目标2:掌握递归和迭代基本算法设计技术，掌握分治法、回溯法、分支限界法、动态规划和贪心法等常见的算法设计策略。课程目标3:通过理论学习和实验训练，能够从问题需求出发，合理

3、地组织数据结构、采用正确的算法设计策略并实现算法，编写程序，分析实验结果以获得合理有效的结论。3课程内容与学时分配主要内容：1 .绪论：算法的概念，算法分析方法和算法设计工具一STL教学重点：算法时间复杂度分析和各种STL数据结构容器的使用方法。教学难点：使用各种STL数据结构容器设计相关问题的求解算法。能力点：培养学生具有算法分析的能力，利用各种STL容器设计求解相关问题的算法设计。2 .递归算法设计技术：递归的概念，递归算法设计方法，递归的典型应用示例（直接插入排序，0/1背包问题，求表达式值）和递推式计算。教学重点：基于递归数据结构的递归算法设计和基于归纳思想的递归算法设计。教学难点：建

4、立求解问题的递归模型并转换为递归算法。3 .穷举法：穷举法的概念，穷举算法优化和穷举法的典型应用示例（求回文串个数，最大连续子序列和，求幕集，0/1背包问题，求全排列，n皇后问题，任务分配问题，旅行商问题）。教学重点：各种基本算法设计方法求解问题的思路。教学难点：如何优化穷举法算法和利用归纳法建立求解问题的递推关系，如何建立求解问题的递归模型以及递推式计算方法。4 .分治法：分治法的概念，分治法的基本步骤和分治法的典型应用示例（快速排序、二路归并排序、二分查找及其扩展算法、最大连续子序列、棋盘覆盖问题、循环日程安排问题和旅行商问题）。教学重点：分治法的基本策略和框架，快速排序和归并排序，二分查

5、找，查找假币问题（三分查找），最大连续子序列和，求最近点对距离。教学难点：利用分治法求解问题的一般思路，快速排序、归并排序和二分查找及其扩展应用。5 .回溯法：回溯法的概念，基于子集树的算法框架和基于排列树的算法框架，分治法的典型应用示例（求幕集，图的路径搜索，构造表达式，图的m着色问题，子集和问题，简单装载问题，0/1背包问题，完全背包问题，求全排列，n皇后问题，任务分配问题，旅行商问题）教学重点：解空间为子集树和排列树的算法框架，用回溯法求解简单装载问题，0/1背包问题，任务分配问题，货郎担问题。教学难点：利用回溯法求解问题的一般思路，回溯法中的剪支操作。6 .分支限界法：分支限界法的概念

6、，广度优先搜索，队列式分支限界法和优先队列式分支限界法，分支限界法的典型应用示例（图的单源最短路径，0/1背包问题，任务分配问题，旅行商问题）和A*算法。教学重点：各种广度优先搜索，用分支限界法求解图的单源最短路径，0/1背包问题，任务分配问题和货郎担问题。教学难点：利用分支限界法求解问题的一般思路，分支限界法中的限界函数设计。7 .动态规划：动态规划的概念，动态规划求解问题的性质和动态规划的典型应用示例（最大连续子序列和，最长递增子序列，三角形最小路径，最长公共子序列，编辑距离，0/1背包问题，完全背包问题，扔鸡蛋问题，资源分配问题，旅行商问题，最少士兵数问题，矩阵连乘问题）教学重点：动态规

7、划原理和要点，一维动态规划，二维动态规划，三维动态规划，背包动态规划。教学难点：利用动态规划求解问题的一般思路，动态规划算法中的空间优化。8 .贪心法：贪心法的概念，贪心法框架，贪心法求解问题的性质，动态规划的典型应用示例（区间问题，背包问题，田忌赛马问题，零钱兑换问题，哈夫曼编码）和拟阵。教学重点：活动安排问题I,背包问题,Prim算法、Kruskal算法和Dijkstra算法，不带惩罚的调度问题和带惩罚的调度问题。教学难点：利用贪心法求解问题的一般思路，如何在求解问题中选择正确的贪心策略。9 .图算法：图的最小生成树，图的最短路径和网络流。教学重点：求图最短路径的DijkstraxBell

8、man-FordxSPFA和Floyd算法。教学难点：求最大流的Ford-Fulkerson.EdmOndS-KraP和DiniC算法。10 .计算几何：向量的基本运算，凸包问题，最近点对问题和最远点对问题。教学重点：利用向量基本运算求三角形面积和多边形面积等几何计算。教学难点：求凸包的礼品包裹算法和Graham算法，求最近点对的分治算法。11 .计算复杂性：判定问题，P类，NP类，多项式时间变换和NP完全问题。教学重点：P类、NP类和NP完全问题的概念。教学难点：NP完全问题。12 .概率算法和近似算法：概率算法和近似算法的概念，常用的概率算法类型。教学重点：蒙特卡罗、拉斯维加斯类型和舍伍德

9、类型概率算法。教学难点：近似算法的近似性能比分析。课程内容与学时分配表（48学时）内容学时1、绪论32、递归算法设计技术33、穷举法34、分治法65、回溯法66、分支限界法67、动态规划68、贪心法39、图算法310、计算几何311、计算复杂性312、概率算法和近似算法3小计484考核方式期末考试（60%）,上机实验（20%）,作业（10%）,其他（10%）教材与参考书电子 IMo W3 曲Mt。*UMfiHeSmmA.t2amm!的我俄潮， 示9俾MB.书中网RW所州值代表性的EW示例.XKfttfrWMItBa.晨示其法设计温升连看, NB求财的多性.ISi5国用肄浦卿黑三vW网洞H-决亶例殖的助. SiUiii法宏观相对SJ-力的壤葬,U中信选大Aur通中的在找aHLait者的曜力,?助港者面各类竞ID求职巾场.编著：李春葆刘娟哈丹丹刘斌定价:5980元ISBN：978-7-302-64115-5