课程概述

算法导论作为计算机科学与技术专业的专业主干课程，先修课程是高级语言程序设计、数据结构，主要讲授经典算法，包括递归与分治算法、动态规划算法、贪心算法、回溯算法、分支界限算法的基本原理、实现方法和应用实例，通过该课程的学习，使学生熟悉算法复杂性分析理论和评价算法性能的标准，掌握基本的算法设计方法，能运用一些常用算法去分析和解决实际问题，具有较强的问题抽象和建模的能力，为学生进一步分析和解决计算机科学与技术领域的复杂工程问题奠定良好的基础。

算法导论课程的教学目标有两个：

1）能够针对待解决的具体问题，在满足问题约束条件的前提下，分析多种解决方案在时间、空间复杂度及算法效率上的优劣，选择合理的算法进行解决。

2）能够结合具体应用案例，合理选择经典算法，并能在此基础上设计出复杂算法，使之针对具体应用能够高效地存储和处理数据，并对算法进行有效分析和评价。


证书要求

采取百分制，60分-79分可申请合格证书，80分以上可申请优秀证书，成绩达到相应要求即可申请证书。


预备知识

先修课程为数据结构和高级语言程序设计


授课大纲

算法概述

理解并掌握算法复杂性分析的基本方法

课时

  • 1.1 算法及复杂性
    • ,
  • 1.2 算法复杂性分析
    • ,

分治与递归

理解递归的概念，掌握设计有效算法的分治策略，通过范例学习分治策略的设计技巧

课时

  • 2.1 递归的概念
    • ,
  • 2.2 分治法的基本思想
    • ,
  • 2.3 二分搜索技术
    • ,
  • 2.4 合并
    • ,
  • 2.5 线性时间选择
    • ,
  • 2.6 大整数的乘法
    • ,
  • 2.7 最接近点对
    • ,
  • 2.8 棋盘覆盖
    • ,

动态规划

掌握动态规划算法的基本要素，掌握设计动态规划算法的步骤，通过应用范例学习动态规划算法设计策略

课时

  • 3.1 动态规划概述
    • ,
  • 3.2 矩阵连乘
    • ,
  • 3.3 最长公共子序列
    • ,
  • 3.4 最大子段和
    • ,
  • 3.5 凸多边形最优剖分
    • ,
  • 3.6 流水作业调度
    • ,
  • 3.7 图像压缩
    • ,
  • 3.8 0-1背包
    • ,
  • 3.9 电路布线
    • ,
  • 3.10 最优二叉搜索树
    • ,

贪心算法

理解并掌握使用贪心策略设计算法的方法

课时

  • 4.1活动安排问题
    • ,
  • 4.2贪心算法的基本要素
    • ,
  • 4.3最优装载
    • ,
  • 4.4哈夫曼编码
    • ,
  • 4.5哈夫曼编码理论证明
    • ,
  • 4.6单源最短路径
    • ,
  • 4.7最小生成树
    • ,

回溯法

理解回溯法的深度优先搜索策略，掌握用回溯法解题的算法框架：子集树算法框架、排列树算法框架，通过应用范例学习回溯法的设计策略

课时

  • 5.1回溯法基本概念
    • ,
  • 5.2 0-1背包问题
    • ,
  • 5.3 旅行商问题
    • ,
  • 5.4 图的着色问题
    • ,

分支限界法

理解分支限界法的剪枝搜索策略，掌握分支限界法的算法框架：队列式(FIFO)分支限界法、优先队列式分支限界法，通过应用范例学习分支限界法的设计策略

课时

  • 6.1 分支限界法概述
    • ,
  • 6.2 单源最短路径
    • ,
  • 6.3 装载问题
    • ,
  • 6.4 最大团问题
    • ,

参考资料

1王晓东编，计算机算法设计与分析（第5版），电子工业出版社，2018年

2 Thomas H. Cormen等著，潘金贵等译，算法导论，机械工业出版社

3 R.C.T.Lee等著，王卫东译，算法设计与分析导论，机械工业出版社