算法分析及设计

算法分析及设计

课程名称：算法分析及设计 课程编码：C201 课程学分：2

适用学科：计算机应用技术

算法分析及设计

Design and Analysis of advanced

Algorithms 教学大纲

一、课程性质

算法的设计与分析是计算机科学的核心问题之一，是计算机科学与工程各专业学生及研究生的一门重要的专业基础课。其内容是研究计算机领域及相关领域中的一些常用的算法设计方法及算法的复杂性分析方法。同时，通过讲授NP理论的主要概念及一些近似算法，为学生从事计算机算法的研究工作奠定基础。学习和掌握这些知识不仅对计算机专业的技术人员，而且对使用计算机的其他各专业技术人员都是必不可少的。 二、课程教学目的

通过本课程的学习，应使学生掌握算法设计的常用方法，以便能够运用这些方法设计解决计算机应用中的实际问题的有效算法，并能够利用已有算法去解决实际问题。此外还要使学生学会分析算法，估计算法的时空复杂性，从而对算法做出科学的评价。 三、教学基本内容及基本要求 第一章 绪论

1、 2、 3、 4、 5、

算法定义（了解） 算法特征

计算机求解问题过程 算法描述语言 算法分类

第二章 算法复杂性分析（要求全部掌握）

1、 2、

算法复杂性 算法复杂性计量

3、 4、 5、

复杂性的渐进形态 渐进分析

递归方程解的渐进阶

第三章 算法设计的基本方法（要求全部掌握）

1、 2、 3、 4、 5、

第四章 图和网络算法（要求全部掌握）

1、 2、 3、 4、

第五章 计算几何（要求全部掌握）

1、 2、 3、 4、 5、

第六章 概率算法（要求全部掌握）

1、 2、 3、 4、 5、

第七章 NP完全性理论及近似算法（要求全部掌握）

1、 2、 3、 4、

确定性图灵机 非确定性图灵机

P类与NP类 Cook定理与NP完全问题

概率算法简介 随机数

素数的概率算法 线性时间选择算法 平面点集最近点对概率算法 相交问题 求夹角

求凸包 判断一点在几何体内部 Voronoi图 基本概念 树的算法

路的算法 流的算法

贪心法 分治法

动态规划 回溯法

分支限界法