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

1、算法分析与设计I Design and Analysis of Algorithms I一、课程基本情况课程类别：专业任选课课程学分：2学分课程总学时：32学时，其中讲课： 24学时，上机： 8学时课程性质：选修开课学期：第7学期先修课程：C语言程序设计、数据结构、离散数学、数学分析、概率论与数理统计适用专业：信息与计算科学教 材：王晓东，算法设计与分析清华大学出版社，第二版，2008开课单位：数学与统计学院信息与计算科学系二、课程性质、教学目标和任务算法分析与设计是计算机软件及相关专业的一门重要课程，通过对常用的、有代表性的算法的研究，让学生理解并掌握算法设计的基本技术。培养学生分析算法复杂

2、度的初步能力，锻炼其逻辑思维能力和想象力，并使之了解算法理论的发展。鼓励学生运用算法知识解决各自学科的实际问题，培养他们的独立科研的能力和理论联系实践的能力。三、教学内容和要求第1章 导论 (2学时)理解算法的基本概念和特点 ； 掌握：算法分析的准则算法分析的若干准则：正确性、工作量、占用空间、简单性、最佳性；了解基本操作的概念、平均性态和最坏性态的分析，算法分析的目的；重点：算法的概念和算法分析的准则难点：平均性态和最坏性态的分析第2章 分治与递归算法 (6学时)掌握分治法与递归的概念，熟悉用递归方法解决实际问题，熟练掌握利用分治法解决问题的基本思想；理解用分治算法的实现：折半查找、搜索二叉

3、排序树、大整数乘法；了解矩阵乘法的Strassen算法；了解用分治法实现棋盘覆盖的思想方法；重点： 分治与递归的概念，分治算法的实现难点： 递归算法的理解，大整数乘法的实现第3章 排序算法与递归 (4学时)掌握用递归算法实现：冒泡排序算法及其分析、快速排序算法及其分析；理解比较排序法的下界；理解堆排序（HEAPSORT）算法及其分析；了解分治与递归在合并排序，二分合并等问题中应用；重点： 快速排序算法及其分析，堆排序的算法及其分析难点： 基于比较排序算法的下界第4章 贪心算法 (6学时)掌握利用贪心算法解决问题的基本思想掌握最小生成树算法的贪心算法及其分析、单源最短路径算法的贪心算法及其分析；

4、理解旅行商问题的贪心算法及其分析方法；了解贪心法在典型应用领域的方法；重点： 最小生成树算法和单点源最短路径算法的贪心法实现难点： 旅行商问题的贪心算法及其分析第5章 回溯法 (6学时)掌握利用回溯法解决问题的基本思想，并能准确地分析回溯法的效率及稳定性；掌握树的深度优先遍历、数的全排列方法；了解n皇后问题和迷宫问题，回溯法在0-1背包问题问题的应用；重点： 回溯算法的效率及稳定性，树的深度优先算法难点： 回溯算法的稳定性第6章 分支限界法 (4学时)掌握利用分支限界法解决问题的基本思想；掌握分支界限法在背包问题、旅行商等问题中的应用；了解最小耗费搜索，树的层次遍历问题；了解分治界限法在单源最

5、短路径问题、装载问题中的应用；重点： 分支定界算法在背包问题和旅行商问题中的应用难点： 分支定界算法的基本思想第7章 动态规划法（4学时）掌握动态规划法的基本思想与解题步骤；掌握动态规划法在多边形游戏、凸多边形剖分、0-1背包问题中的应用；了解动态规划法在图像压缩问题中的应用；重点： 动态规划算法的基本思想，0-1背包问题的动态规划算法难点： 动态规划算法的基本思想与解题步骤四、课程考核作业和报告：作业：0次，课程论文： 0 篇；实验实习报告：4次，课程设计论文： 0 篇；报告含算法论述，流程图，可执行的源代码，运行结果，以及结果分析，并计入平时成绩，每篇满分5分考核方式：开卷考试总评成绩计算方式：平时成绩*20期末考试成绩*80五、参考书目周培德编著，