算法基礎研究生課程是計算機在職研究生專業(yè)一門重要的課程，算法基礎研究生課程教學大綱如下：

　　課程簡介

　　在學習數(shù)據(jù)結構與算法的基礎上，進一步學習算法的設計方法、技巧和具體實現(xiàn)方法與應用。使學生掌握算法的基本設計方法和分析方法，常用數(shù)據(jù)結構和算法，通過實踐掌握基本算法的實現(xiàn)技能。主要內容包括：算法的基本概念和基本分析方法，遞歸算法、貪心算法、動態(tài)規(guī)劃算法的設計和實現(xiàn)，算法的應用與實踐。 培養(yǎng)學生運用算法技術解決問題的實際能力。

　　教學內容

　　及學時安排 本課程教學內容及學時安排如下(64學時)：

　　第一章引言(6學時)

　　1.1算法的基本概念

　　1.2抽象數(shù)據(jù)類型與基本數(shù)據(jù)結構

　　1.3算法的時空復雜度

　　1.4算法設計的基本步驟

　　第二章 排序(8學時)

　　2.1 簡單排序算法

　　2.2 希爾排序與快速排序

　　2.3 歸并排序與堆排序

　　2.4 排序算法的分析、比較與改進

　　2.5 大規(guī)模數(shù)據(jù)的排序

　　第三章 查找(12學時)

　　3.1 順序查找

　　3.2 Hash表

　　3.3 二叉查找樹

　　3.4 B-樹與B+ 樹

　　3.5 倒排索引及其壓縮

　　3.6 跳表及其應用

　　3.7 集合與字典

　　第四章遞歸算法(9學時)

　　4.1 遞歸算法的設計與實現(xiàn)

　　4.2 遞歸算法實例

　　4.3 遞歸算法轉換為非遞歸的方法

　　4.4 遞歸算法的分析

　　第五章貪心算法(5學時)

　　5.1 貪心算法的設計與實現(xiàn)

　　5.2 貪心算法實例

　　第六章動態(tài)規(guī)劃算法(8學時)

　　6.1 動態(tài)規(guī)劃算法的設計

　　6.2基于遞歸的動態(tài)規(guī)劃算法

　　6.3 動態(tài)規(guī)劃算法的實例與實現(xiàn)

　　第七章圖論算法 (10學時)

　　7.1 圖的搜索

　　7.2 有向圖和有向無環(huán)圖

　　7.3 最小生成樹

　　7.4 最短路徑

　　7.5 網絡流

　　第八章 概率算法 (6學時)

　　8.1 簡介

　　8.2 偽隨機數(shù)生成

　　8.3 數(shù)字概率算法

　　8.4 Mont Carlo 算法

　　8.5 Las Vegas 算法

　　考核方式

　　總成績構成情況：

　　(1)實驗與報告(50%)

　　(2)期末考試(50%)

　　參考書目

　　[1] 計算機算法導論，清華大學出版社，盧開澄，2006年;

　　[2] 算法：C語言實現(xiàn)(第1-第5)，機械工業(yè)出版社，2009年;

　　[3] 算法設計與分析導論，機械工業(yè)出版社，2008年;

　　[4] G. Brassard /邱仲潘等譯，F(xiàn)undamentals of Algorithmics，清華大學出版社，2005年;