算法分析与设计 教学大纲

第页算法分析与设计一、课程说明课程编号：090210Z10课程名称（中/英文）：算法分析与设计/TheAnalysis&DesignofAlgorithms课程类别：专业教育课程学时/学分：48/3 先修课程：离散数学、数据结构、计算机程序设计基础（C++）适用专业：计算机科学与技术、信息安全、物联网工程教材、教学参考书：1.AnanyV.Levitin著,潘彦译.算法设计与分析基础.北京:清华大学出版社,2014年2.AnanyV.Levitin.IntroductiontoTheDesign&AnalysisofAlgorithms,VillanovaUniversity,2003年

3.王晓东.计算机算法设计与分析(第4版).北京:电子工业出版社,2012年4.SartajShani,DataStructures,Algorithms,andApplicationsinC++.Prentice-Hall,1999（中译本:汪诗林,数据结构算法与应用－C++语言描述,机械工业出版社）5.刘汝佳,黄亮.算法艺术与信息学竞赛.北京:清华大学出版社,2003二、课程设置的目的意义本课程是计算机科学的核心课程。课程目的是通过对常用的、有代表性的算法的研究，让学生理解并掌握算法设计的基本技术；培养学生分析算法的时间和空间的复杂度的初步能力，锻炼其逻辑思维能力和想象力，并使之了解算法理论的发展；本课程本着理论联系实际、以实际问题为背景、学以致用的原则，鼓励学生运用算法知识解决各自学科的实际问题，培养他们的独立科研的能力和理论联系实践的能力，为学生从事计算机算法的研究工作奠定基础。三、课程的基本要求知识：掌握算法的基本概念，熟悉算法的描述方法、掌握算法的复杂性度量及复杂性分析方法；掌握分治法的基本思想和递归算法的设计；掌握最优子结构原理和动态规划算法的设计；掌握贪心算法的基本思想和算法设计；掌握回溯算法和分支限界算法的基本思想及两类算法的异同点；掌握P、NP问题和NP完全理论。能力：通过掌握五种基本的算法设计方法，能够利用其对具体实际问题进行分析和设计，培养严谨的逻辑分析能力和解决实际计算问题的能力；通过上机实现算法，验证算法的时间复杂性函数，提高学生的动手能力和分析能力；通过对不同类型设计方法的比较分析，能够针对具体问题选择较优的设计方法，在讨论中培养创新意识，提高分析、发现、研究和解决问题的能力。素质：建立问题－模型－算法－实现（应用）一体的观念，通过课程中的分析讨论建立算法设计到实际应用的思维模式，提升利用所学解决实际问题的基本素质和专业素质。通过课外导学的模式，提升自主学习和终身学习的意识，形成不断学习和适应发展素质。四、教学内容、重点难点及教学设计章节教学内容总学时学时分配教学重点教学难点教学方案设计（含教学方法、教学手段）讲课(含研讨)实践第1章介绍算法的概念及相关领域22算法及分析的重要性算法的定义及与程序的区别教学思路：从狼、羊、菜过河的故事和无限容积的罐子取球问题引导学生对“算法”进行思考，进而讲述算法的定义。教学模式：课堂讲授、数据结构相关知识回顾与提问相结合。第2章算法设计和时间、空间复杂性分析基础44算法及分析技术递归教学思路：通过相同问题用不同方法解决时效率上的差异，讲解算法的时间复杂度。教学模式：课堂讲授与课后作业相结合的方法。第3章分治法862分治法的一般方法、归并分类和快速分类算法等斯特拉森矩阵乘法教学思路：以数据结构中涉及到的归并排序和快速排序引入分治的概念，讲解递归的思想；以斯特拉森矩阵乘法、棋盘覆盖、最近对等具体例子进一步讲解分治与递归。教学模式：课前导学和课堂作业相结合；一般归纳和重点解析相结合。第4章减治法、深度优先、广度优先搜索方法44深度优先、广度优先搜索方法深度优先与广度优先的区别及应用教学思路：以二分查找和找假币简单的问题引导学生思考“减治策略”。以图和动画的方式讲解深度优先和广度优先的方法。教学模式：课前导学、课堂讲授与课堂作业相结合；比较分析与问答相结合。第5章堆排序问题22堆排序问题“变治”的概念，堆排序问题教学思路：以google等面试题目为了，引导学生从“变治”的角度思考解决问题；以案例分析的方式讲授堆排序方法。教学模式：课堂讲授与课堂问答相结合；。第6章动态规划方法862动态规划的一般方法、最优二分检索树、0/1背包问题、旅行商问题等最优二分检索树、0/1背包问题教学思路：以数字三角形的最短路径和多段图等简单的实际问题讲解“最优化原理”，引导学生逐步掌握动态规划的思路和设计方法。教学模式：课前导学和课堂作业相结合；一般归纳和重点解析相结合；课外作业与成果展示相结合第7章贪心法、UNION-FIND问题662（课外）贪心设计策略的一般方法、最小生成树算法、UNION-FIND问题最小生成树算法、最短路径算法教学思路：以0/1背包问题为例，引导学生思考“贪心策略”，并分析与动态规划等其他方法的不同；以最小生成树、最短路径为例讲授贪心算法的设计。教学模式：课前导学和课堂问答相结合；一般归纳和重点解析相结合；课外作业与成果展示相结合第8章回朔法662（课外）回溯的一般方法、8-皇后问题、图的着色N皇后问题教学思路：以8皇后问题为例，通过回顾深度优先搜索方法，由浅入深，不断优化，讲授递归和非递归的回溯算法；在此基础上进一步引导学生用回溯法解决0/1背包问题和图的着色问题等。教学模式：课前导学和课堂问答相结合；一般归纳和重点解析相结合。第9章分支-限界方法642分支-限界的一般方法0/1背包、旅行商等问题教学思路：比照之前讲过的回溯法，逐步讲授分支-限界方法与回溯法的异同点；在此基础上进一步引导学生用分支-限界解决0/1背包和旅行商等问题。教学模式：课前导学和课堂作业相结合；课堂分析、讨论回溯法与分支限界解决相同问题的异同点；一般归纳和重点解析相结合。第10章NP－难度问题和NP－完全问题简介22NP－难度问题和NP－完全问题证明问题是NP－完全的教学思路：从0/1背包和旅行商等学生熟悉的问题开始，引导大家理解NP问题和NP完全理论，以可满足性问题、独立集和点覆盖问题为例讲授NP难和NP完全问题的证明。教学模式：课前导学和课堂讨论相结合；一般归纳和重点解析相结合。注：实践包括实验、上机等五、实践教学内容和基本要求实验名称实验内容学时基本要求递归与分治利用递归与分治策略解题2掌握递归与分治方法的基本思想，并利用其解决至少一个实际应用问题动态规划与贪心策略分别利用动态规划与贪心策略解题2掌握动态规划与贪心策略的基本思想及区别，分析其在解决实际问题上的区别回朔与分枝-限界分别利用回朔与分枝-限界策略解题2掌握回朔与分枝-限界的基本思想，并利用其解决至少一个实际应用问题六、考核方式及成绩评定教学过程中采取课前导学、讲授、讨论、分析、课堂及课后作业等方式进行，注重过程考核，考核方式包括：课堂讨论、作业、平时测评、上机实践等；过程考核占总评成绩的50%，期末考试点50%。考核方式考核内容成绩比