课件说明:
计算机及相关学科硕士研究生基础课《计算机算法设计与分析》,pdf格式,共八章。包含分治、贪心、动态规划、回溯、分支定界等方法:
第一章 引言: 介绍算法概念及相关领域、算法的时间和空间复杂性分析基础知识。
第二章 基本搜索和遍历技术:介绍二叉树、树及图的遍历和搜索技术,BFS 算法及其复杂性分析。
第三章 分治算法:算法的基本思想、归并排序、快速排序、最短路经、选择问题等实例分析。
第四章 贪心算法:最优化问题、贪心算法的基本思想、背包问题、旅行商问题、最短路径问题等实例分析。
第五章 动态规划方法:问题背景、0/1 背包问题、矩阵乘法链、旅行商问题等。
第六章 回溯法:算法基本思想、装箱问题、背包问题、旅行商问题、电路板排列问题等实例分析。
第七章 分支定界法:算法思想、装箱问题、0/1 背包问题、旅行商问题、电路板排列等实例分析。
第八章 NP-难度问题和NP-完全问题简介,证明NP 完全性的方法介绍。
主要参考书:
1. 余祥宣等,《计算机算法基础》,华中理工大学出版社,2000。
2.(美)Cormen,T.H. 等,《算法导论》,高等教育出版社,2001。
3. 王晓东,《计算机算法设计与分析》,电子工业出版社,2001。