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

《算法设计与分析课程教学大纲.docx》由会员分享，可在线阅读，更多相关《算法设计与分析课程教学大纲.docx（2页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、算法选汁苞扮淅课程教学大纲一、课程的基本信息适应对象：信息与计算科学专业课程代码：15E03127学时分配：54赋予学分：3先修课程：数学分析、高的代数、离散数学、算法与数据结构后续课程：毕业综合训练二、课程性质与任务算法设计与分析是信息与计算科学专业一门专业选修课。课程介绍算法设计的基本 原理、方法和技术，通过算法分析与设计学习与研究，对算法的时间复杂度、空间复杂度和 稳定性分析有较高的认识，为后续的毕业综合训练和今后的实际应用提供支撑。三、教学目的与要求通过本课程的学习，学生要掌握算法设计的基本原理、方法和技术，培养学生对算法复 杂性进行正确分析的能力。通过对常用的、有代表性的算法的研究，

2、要求学生掌握递归与分 治策略、动态规划算法、贪心算法、回溯法、分支限界法、概率算法、NP完全性理论与近 似算法几种常用的算法设计策略，理解并掌握算法设计的基本技术，并学会分析算法的时间 复杂度、空间复杂度和稳定性，具有问题抽象和建模的初步能力。四 教学内容与安排教学内容第一章算法概述掌握算法，算法复杂度的基本概念，及时间复杂度的估算方法第二章递归与分治法递归概念，分治法基本思想，二分搜索技术，大整数乘法，矩阵乘法，棋 盘覆盖，合并排序，快速排序，线性时间选择，最接近点对问题，循环赛日程表。第三章动态规划动态规划的基本要素，矩阵连乘，最长公共子序列，最大子段和，凸多边 形最优三角剖分，多边形游戏

3、，图像压缩，电路布线，流水作业调度，0 1背 包问题，最优二叉搜索树。第四章贪心算法贪心算法的基本要素，活动安排问题，最优装载，哈夫曼编码，单源最短 路径，最小生成树，多机调度。第五章 回溯法回溯法的算法框架、符号，三角形问题，n个皇后问题，最大团问题，图 的m着色问题，旅行售货员问题，圆排列问题，连续邮资问题，电路板排列问题。第六章分支限界法分支限界的基本思想，单源最短路径，布线问题，01背包问题，批处理 作业调度问题。第七章概率算法概率算法的基本思想，随机数，数值概率算法，舍伍德算法，拉斯维加斯 算法，蒙特卡罗算法。第八章 NP完全性理论计算模型，P类与NP类问题，NP完全问题，合取范式（

4、CNF）顶点覆盖问 题，哈密顿回路问题。第九章近似算法近似算法的基本思想及性能，顶点覆盖问题的近似算法，集合覆盖问题的 近似算法，子集合问题的近似算法。教学安排五、附录课程内“数授课实验小 计第一章算法概述22第二章递归与分治法448第三章动态规划628第四章贪心算法6410第五章回溯法426第六章分支限法448第七章概率算法44第八章 NP完全性理论22第九章近似算法426合计361854教学参考文献目录:1、王晓东主编2、徐士良主编3、周培德编著计算机算法设计与分析计算机常用算法第3版算法设计与分析第3版电子工业出版社出版第3版2014年 清华大学出版社出版2014年1月 机械工业出版社2014年1月