201411226算法设计与分析

1、算法设计与分析课程教学大纲、课程基本信息课程编号：201411226课程中文名称：算法设汁与分析课程英文名称：Design and Analysis of Algorithms课程性质：片业选修课程开课专业：数学与应用数学开课学期：5总学时：36 （其中理论36学时）总学分：1.5二、课程目标计算机算法设计与分析是研究设计和分析各种算法的基本原理、方法和技术的理论，它 是编写髙效汁算机程序、开发优秀软件的基础。本课程通过讲述讣算机应用中经常遇到的诸 如排序、查找、选择、矩阵运算等重要的实际问题，使学生获得设汁和分析算法的理论和技 术及其有关的基础知识，并能够运用这些技术设计出新算法，解决新问题

2、，同时实现培养学 生的逻辑推理能力和汁算编程的能力，从而为设汁新算法，提高算法效率提供帮助。三、教学基本要求（含素质教育与创新能力培养的要求）（1）通过对一些典型问题和常用算法的学习，使学生了解算法设计的基本策略，掌握 算法设il的求解思想；（2）通过对实践类题目的练习，使学生能够应用算法设计方法和分析技巧解决程序设 il中遇到的各类问题：（3）通过对算法热点领域的了解，培养学生创新素质，提髙学生科研创新意识。四、教学内容与学时分配（小4号黑体）1算法概述（2学时）1.1算法与程序1.2算法复杂性分析2递归与分治策略（6学时）2.1递归的概念2. 2分治法的基本思想2. 3二分搜索技术2.4大

3、整数的乘法2. 5 Strassen矩阵乘法2.6棋盘覆盖结合课后习题，对以上内容进行研讨3动态规划（6学时）3.1矩阵连乘问题3. 2动态规划算法的基本要素3.3最长公共子序列3.4最大子段和3.5凸多边形最优三角剖分3.6多边形游戏3.8电路布线3. 9流水作业调度3. 10 0-1背包问题结合课后习题，对以上内容进行研讨4贪心算法（6学时）4.1活动安排问题4.2贪心算法的基本要素4. 3最优装载4.4哈夫曼编码4. 5单源最短路径4. 6最小生成树结合课后习题，对以上内容进行研讨5回溯法（8学时）5. 1回溯法的算法框架5.2装载问题5. 3批处理作业调度5.4符号三角形问题5. 5

4、n后问题5. 6 0-1背包结合课后习题，对以上内容进行研讨5.7最大团问题5.8图的m着色问题5.9旅行售货员问题5. 10圆排列问题5.11电路板排列问题结合课后习题，对以上内容进行研讨6分支限界法（8学时）6. 1分支限界法的基本思想6.2单源最短路径问题6. 3装载问题6.4布线问题6.5 0-1背包问题6.6最大团问题6.7旅行售货员问题6.8电路板问题6. 9批处理作业调度结合课后习题，对以上内容进行研讨五、教学方法及手段（含现代化教学手段及研究性教学方法）本课程教学方法和教学手段是课堂讲授，以多媒体教学为辅助教学的方式.并且在每章 中布置研讨题目，课堂上每章安排12次研讨六、实验（或）上机内容无七、前续课程、后续课程前续课程：大学计算机基础，C语言，数据结构八、参考教材及学习资源1 王晓东.计算机算法设计与分析（第4版）电子工业出版社，2012. 032 Nany Levitin著，潘彦 议.计算机算法设计与分析.电子工业出版社,2005年3 http：/algorithm fzu edu. cn4 http：/ds fzu. edu. cn/fine/index