第三章 分治算法:算法的基本思想、归并排序、快速排序、最短路经、选择问题等实例分析。

内容提要:计算机及相关学科硕士研究生的学科基础课。使学生掌握计算机算法的通用设计方法,学会分析算法的空间和时间复杂性。计算机及相关学科硕士研究生的学科基础课。使学生掌握计算机算法的通用设计方法,学会分析算法的空间和时间复杂性。

    第一章 引言:算法的时间和空间复杂性分析基础知识。

    第二章 基本搜索和遍历技术:介绍二叉树、树及图的遍历和搜索技术,BFS算法、DFS算法及其复杂性分析。

    第三章 分治算法:算法的基本思想、归并排序、快速排序、最短路经、选择问题等实例分析。

    第四章 贪心算法:最优化问题、贪心算法的基本思想、0/1背包问题、旅行商问题、最短路径问题等实例分析。

    第五章 动态规划方法:问题背景、0/1背包问题、矩阵乘法链、旅行商问题、多段图问题等。

    第六章 回溯法:算法基本思想、装箱问题、背包问题、旅行商问题等实例分析。

第七章 分支定界法:算法思想、装箱问题、0/1背包问题、旅行商问题、电路板布线等实例分析。

第八章 NP-难度问题和NP-完全问题。