算法分析.docVIP

算法分析 课程名称：算法分析 英文名称： Algorithm Analysis 课程编码：070102B11 适用专业：信息与计算科学 课程类别：专业选修 学时：64 学分：4 编写执笔人：曾凯 审定人： 编写日期：200年月日 《算法分析》是计算科学的核心问题之一，也是专业本科的一门重要的专业基础课。算法分析是计算机软件开发人员必修课，软件的效率和稳定性取决于软件中所采用的算法；对于一般程序员和学生，学习算法设计与分析课程，可以开阔编程思路，编写出优质程序。本课程用严格的解析方法培养学生怎样分析算法的“好”于“坏”，怎样设计算法，并以广泛用于计算机科学中的算法为例，对种类不同难度的算法设计进行系统的介绍与比较。本课程将培养学生严格的设计与分析算法的思维方式，改变随意拼凑算法的习惯。本课程要求具备离散数学、程序设计语言、数据结构等先行课课程的知识。 通过本课程的学习，应完成如下任务： 通过对常用的、有代表性的算法的研究，让学生理解并掌握算法设计的基本技术。 培养学生分析算法复杂度的初步能力，锻炼其逻辑思维能力和想象力，并使之了解算法理论的发展。 鼓励学生运用算法知识解决各自学科的实际问题，培养他们的独立科研的能力和理论联系实践的能力。 第一章 算法概述（2学时） 1、教学内容 算法，算法复杂度的基本概念，时间复杂度的估算方法。 2、教学目的及要求 掌握算法，算法复杂度的基本概念，及时间复杂度的估算方法递归与分治法递归概念，分治法基本思想二分有哪些信誉好的足球投注网站技术，大整数乘法，矩阵乘法棋盘覆盖，合并排序，快速排序，线性时间选择最接近点对问题，循环赛日程表掌握递归的概念学会用递归方法解决实际问题熟练掌握利用分治法解决问题的基本思想会用某高级语言对算法进行描述，并对算法复杂度（时间和空间）进行分析。 动态规划的基本要素矩阵连乘，最长公共子序列，最大子段和凸多边形最优三角剖分，多边形游戏图像压缩，电路布线，流水作业调度0－1背包问题，最优二叉有哪些信誉好的足球投注网站树熟练掌握利用动态规划方法解决问题的基本思想学会如何将问题化为多阶段图的方法，并能对具体问题写出正确的递推公式。贪心算法的基本要素，活动安排问题最优装载，哈夫曼编码单源最短路径，最小生成树，多机调度掌握利用贪心算法解决问题的基本思想会用某高级语言编写用贪心算法解决问题的程序，并能对算法的复杂度，可靠性进行分析。回溯法回溯法的算法框架、符号三角形问题，n个皇后问题，最大团问题，图的m着色问题，旅行售货员问题，圆排列问题，连续邮资问题，电路板排列问题 掌握利用回溯法解决问题的基本思想，会用回溯法解决：n个皇后问题，图的m着色问题，批处理作业调度问题等，并能准确地分析回溯法的效率及稳定性。 分支限界法分支限界的基本思想单源最短路径，布线问题，0－1背包问题，批处理作业调度问题掌握利用分支限界法解决问题的基本思想能用多种不同方法解法同一问题，并分析各方法的效率。 概率算法概率算法的基本思想随机数，数值概率算法，舍伍德算法，拉斯维加斯算法，蒙特卡罗算法 2、教学目的以及要求 掌握利用概率算法的基本思想会用概率算法解决有关问题。 NP完全性理论计算模型 P类与NP类问题，NP完全问题，合取范式（CNF）顶点覆盖问题，哈密顿回路问题 了解NP完全性问题掌握P类与NP类问题的划分。近似算法的基本思想及性能顶点覆盖问题的近似算法，集合覆盖问题的近似算法，子集合问题的近似算法 2、教学目的以及要求 掌握利用近似算法解决问题的基本思想能对其可靠性进行分析。课程教学环节 .课堂教学学时，习题课学时，每次课后均布置作业，根据学生情况不定期答疑. 序号 课程内容 理论教学 课内实践教学 课时小计 备注 课时数 教学方式手段 课时数 教学方式手段 1 第1章算法概述 2 课堂讲授 0 ? 2 ? 2 第2章递归与分治法 6 课堂讲授 ? 0 ? 6 ? 3 第3章动态规划 ? 0 ? 12 ? 4 第4章贪心算法 0 ? 10 ? 5 第五章回溯法 8 6 第六章分支限法 6 第七章概率算法 8 第八章NP完全性理论 6 第九章近似算法 6 五、本课程与其它课程的联系与分工 本课程是《数据结构与算法分析》、《离散数学》、《C++程序设计》、《计算方法》等课程的后续课程。 推荐教材：《计算机算法设计与分析》王晓东 主编电子工业出版社 参考资料： 1.《数据结构与算法分析》张铭、刘晓丹 译电子工业出版社出版。 2.《计算机常用算法》第二版徐士良 主编清华大学出版