高级算法分析及设计
Advanced Algorithm Analysis and Design
教学大纲
课程编码：M732001
课程学分：32学时，2学分
适用学科/专业：计算机科学与技术、软件工程、计算机技术、软件工程（专业学位）
开课学院：计算机学院
一、课程性质
    课程的授课对象为计算机科学与技术、软件工程、计算机技术、软件工程（专业学位）的研究生，高级算法的设计与分析是计算机科学的核心问题之一，其内容是研究计算机领域及相关领域中的一些常用的算法设计方法及算法的复杂性分析方法。同时，通过讲授NP理论的主要
概念及一些近似算法，为学生从事计算机算法的研究工作奠定基础，课程中还介绍相关的算法，如并行算法、近似算法、机器学习算法等。学习和掌握这些知识不仅对计算机专业的技术人员，而且对使用计算机的其他各专业技术人员都是必不可少的。
二、课程教学目的
通过本课程的学习，应使学生掌握算法设计的常用方法，以便能够运用这些方法设计解决计算机应用中的实际问题的有效算法，并能够利用已有算法去解决实际问题。此外还要使学生学会分析算法，估计算法的时空复杂性，从而对算法做出科学的评价。
三、教学基本内容及基本要求
第1章 绪论
（一） 教学基本内容
  1.1算法定义
  1.2算法特征
  1.3计算机求解问题过程
  1.4算法描述语言
  1.5算法分类 
（二） 教学基本要求
      了解：算法的基本知识。
第2章 算法复杂性分析
（一） 教学基本内容
  2.1算法复杂性       
  2.2算法复杂性计量
  2.3复杂性的渐进形态    　   
  2.4渐进分析
  2.5递归方程解的渐进阶
（二） 教学基本要求
  掌握：算法复杂分析的三种基本分析思路。
第3章 算法设计的基本方法
（一） 教学基本内容
  3.1贪心法       
  3.2分治法
  3.3动态规划  　         
  3.4回溯法
  3.5分支限界法
（二） 教学基本要求
  掌握：五种基本算法策略的基本思想，并能够实现。
第4章 NP完全性理论及近似算法
（一） 教学基本内容
  4.1  确定性图灵机  　       
  4.2  非确定性图灵机
  4.3  P类与NP类       
  4.4  Cook定理与NP完全问题
  4.5  NP完全问题近似解法 
（二） 教学基本要求
  了解：算法复杂性与问题复杂性
  掌握：确定与非确定图灵机的理论，NP完全问题的近似解法。
第5章  网络算法
（一） 教学基本内容
  5.1 基本概念      　             
  5.2 树的算法
  5.3 路的算法                   
  5.4 流的算法数据结构与算法论文
（二） 教学基本要求
  了解：树、路、流的基本概念。
  掌握：树、路、流的基本算法的思想以及实现与应用。
第6章  几何算法
（一） 教学基本内容
  6.1 几何算法基础                 
  6.2 几何算法的基本设计技术及问题求解方法
（二） 教学基本要求
  了解：几何算法的基本概念。
  掌握：几何算法中涉及基本算法策略的求解与运用。       
第7章　概率算法
（一） 教学基本内容
  7.1概率算法简介    　     
  7.2随机数
  7.3素数的概率算法 
  7.4线性时间选择算法     
  7.5平面点集最近点对概率算法
（二） 教学基本要求
  掌握：四种概率算法的基本思想以及应用。
第8章 智算法
（一） 教学基本内容
  8.1 算法简介
  8.2 几种经典得智能算法
（二） 教学基本要求
  了解：熟悉至少4种以上智算法，并运用于旅行商问题。
第9章 单纯形算法
（一） 教学基本内容
  9.1 算法简介
  9.2 算法实例
（二） 教学基本要求
  了解：单纯型算法的基本思想与计算。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。