算法設計與分析(北京大學提供的慕課)

課程性質

課程定位

算法設計與分析是算法設計與分析系列MOOC課程之基礎篇。該課程是計算機專業的核心課程。學習該課程對學習其他專業課奠定了基礎，也對培養計算思維和求解問題的能力起到作用。

適應專業

算法設計與分析課程適用計算機類專業進行學習。

開課信息

開課次數	開課時間	參與人數
第1次開課	2018年03月12日~2018年07月30日	75870
第2次開課	2020年03月01日~2020年06月01日	20781
註：該課程第1~2次課程學時安排均為2-3小時每周。（參考資料：）

課程簡介

算法設計與分析課程的內容分成兩大部分：算法的基礎知識和通用算法設計技術與分析方法。算法基礎知識部分主要介紹算法相關的基本概念和數學基礎；通用算法設計技術與分析方法部分主要介紹分治策略、動態規劃、貪心法、回溯與分支限界等算法設計技術。重點介紹這些設計技術的使用條件、分析方法、改進途徑，並給出一些重要的套用。該課程主要內容涉及：面對實際問題建立數學模型、設計正確的求解算法、算法的效率估計、改進算法的途徑、問題計算複雜度的估計、難解問題的確定和應對策略等。該課程是算法課程的基礎部分，主要涉及算法的設計、分析與改進途徑。

課程大綱

01 第一周基礎知識（1）

1.1 本周教學內容簡介

1.2 算法設計的兩個例子

1.3 問題的計算複雜度：排序問題

1.4 貨郎問題與計算複雜性

1.5 算法及其時間複雜度

1.6 算法的偽碼錶示

1.7 函式的漸近的界

1.8 有關函式漸近的界的定理

1.9 幾類重要函式

02 第二周基礎知識（2）

2.1 本周教學內容簡介

2.2 序列求和的方法

2.3 遞推方程與算法分析

2.4 疊代法求解遞推方程

2.5 差消法化簡遞推方程

2.6 遞歸樹

2.7 主定理及其證明

2.8 主定理的套用

03 第三周分治策略（1）

3.1 本周教學內容簡介

3.2 分治策略的設計思想

3.3 分治策略的一般描述和分析方法

3.4 晶片測試

3.5 快速排序

3.6 冪乘算法及套用

3.7 改進分治算法的途徑1：減少子問題數

3.8 改進分治算法的途徑2：增加預處理

04 第四周分治策略（2）

4.1 本周內容簡介

4.2 選最大與最小

4.3 選第二大

4.4 一般選擇問題的算法設計

4.5.選擇問題的算法分析

4.6 卷積及套用

4.7 卷積計算

4.8 快速傅立葉變換FFT算法

4.9 平麵點集的凸包

05 第五周動態規劃（1）

5.1 本周教學內容簡介

5.2 動態規划算法的例子

5.3 動態規划算法設計

5.4 動態規划算法的遞歸實現

5.5 動態規划算法的疊代實現

5.6 投資問題

5.7 背包問題

5.8 最長公共子序列

06 第六周動態規劃（2）

6.1 本周教學內容簡介

6.2 圖像壓縮

6.3 最大子段和

6.4 最優二叉檢索樹的概念

6.5 最優二叉檢索樹的算法

6.6 RNA二級結構預測

6.7 序列比對

07 第七周貪心法（1）

7.1 本周教學內容簡介

7.2 貪心法的例子

7.3 貪心法的正確性證明

7.4 最優裝載問題

7.5 最小延遲調度

7.6 得不到最優解的處理方法

08 第八周貪心法（2）

8.1 本周教學內容簡介

8.2 最優前綴碼及哈夫曼算法

8.3 哈夫曼算法的正確性證明

8.4 最小生成樹

8.5 Prim算法

8.6 Kruskal算法

8.7 單源最短路徑問題及算法

8.8 Dijkstra算法的證明

09 第九周回溯與分支限界（1）

9.1 本周教學內容簡介

9.2 幾個回溯算法的例子

9.3 回溯算法的設計思想和適用條件

9.4 回溯算法實現及實例

9.5 圖的著色

9.6 搜尋樹結點數的估計

10 第十周回溯與分支限界（2）

10.1 本周教學內容簡介

10.2 分支限界

10.3 最大團問題

10.4 貨郎問題

10.5 圓排列問題

10.6 連續郵資問題

10.7 課程總結

參考資料：

課前預備

預備知識

算法設計與分析課程要求預備程式設計基礎、數據結構與算法、高等數學、高等代數知識。

學習資料

書名	作者	ISBN	出版社	出版時間
《算法設計與分析（第2版）》	屈婉玲、劉田、張立昂、王捍貧	9787302424505	清華大學出版社	2016年
參考資料：

授課目標

算法設計與分析課程從算法複雜性分析的基本方法和原理入手，以講授算法設計的基本方法和原理、算法最佳化的基本方法和技巧為主，通過典型的問題及其相應的求解算法，以及算法複雜性的分析，旨在完善學生的知識體系、培養學生的分析能力、拓展學生的思維方法，並鼓勵學生把理論與實踐相結合。

所獲榮譽

2018年，算法設計與分析被中華人民共和國教育部認定為“國家精品線上開放課程”。

教師簡介

汪小林，男，北京大學信息科學技術學院網路與信息系統研究所教授。

蔣婷婷，女，北京大學信息科學技術學院數字媒體所副教授。

羅國傑，男，北京大學信息科學技術學院副教授。