华侨大学

　　算法基础研究生课程是计算机在职研究生专业一门重要的课程，算法基础研究生课程教学大纲如下：

　　课程简介

　　在学习数据结构与算法的基础上，进一步学习算法的设计方法、技巧和具体实现方法与应用。使学生掌握算法的基本设计方法和分析方法，常用数据结构和算法，通过实践掌握基本算法的实现技能。主要内容包括：算法的基本概念和基本分析方法，递归算法、贪心算法、动态规划算法的设计和实现，算法的应用与实践。 培养学生运用算法技术解决问题的实际能力。

　　教学内容

　　及学时安排 本课程教学内容及学时安排如下(64学时)：

　　第一章引言(6学时)

　　1.1算法的基本概念

　　1.2抽象数据类型与基本数据结构

　　1.3算法的时空复杂度

　　1.4算法设计的基本步骤

　　第二章 排序(8学时)

　　2.1 简单排序算法

　　2.2 希尔排序与快速排序

　　2.3 归并排序与堆排序

　　2.4 排序算法的分析、比较与改进

　　2.5 大规模数据的排序

　　第三章 查找(12学时)

　　3.1 顺序查找

　　3.2 Hash表

　　3.3 二叉查找树

　　3.4 B-树与B+ 树

　　3.5 倒排索引及其压缩

　　3.6 跳表及其应用

　　3.7 集合与字典

　　第四章递归算法(9学时)

　　4.1 递归算法的设计与实现

　　4.2 递归算法实例

　　4.3 递归算法转换为非递归的方法

　　4.4 递归算法的分析

　　第五章贪心算法(5学时)

　　5.1 贪心算法的设计与实现

　　5.2 贪心算法实例

　　第六章动态规划算法(8学时)

　　6.1 动态规划算法的设计

　　6.2基于递归的动态规划算法

　　6.3 动态规划算法的实例与实现

　　第七章图论算法 (10学时)

　　7.1 图的搜索

　　7.2 有向图和有向无环图

　　7.3 最小生成树

　　7.4 最短路径

　　7.5 网络流

　　第八章 概率算法 (6学时)

　　8.1 简介

　　8.2 伪随机数生成

　　8.3 数字概率算法

　　8.4 Mont Carlo 算法

　　8.5 Las Vegas 算法

　　考核方式

　　总成绩构成情况：

　　(1)实验与报告(50%)

　　(2)期末考试(50%)

　　参考书目

　　[1] 计算机算法导论，清华大学出版社，卢开澄，2006年;

　　[2] 算法：C语言实现(第1-第5)，机械工业出版社，2009年;

　　[3] 算法设计与分析导论，机械工业出版社，2008年;

　　[4] G. Brassard /邱仲潘等译，Fundamentals of Algorithmics，清华大学出版社，2005年;