複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/算法設計與分析/53890284
複製
複製成功

算法設計與分析

（北京大學提供的慕課）

鎖定
算法設計與分析是北京大學於2018年3月12日首次在中國大學MOOC開設的慕課課程，是國家精品在線開放課程。該課程授課教師是汪小林、蔣婷婷、羅國傑、屈婉玲。據2020年9月中國大學MOOC官網顯示，該課程已開課2次。 [1-2] 
算法設計與分析課程是算法設計與分析系列MOOC課程之基礎篇，課程的內容分成兩大部分：算法的基礎知識和通用算法設計技術與分析方法。課程主要內容涉及：面對實際問題建立數學模型、設計正確的求解算法、算法的效率估計等。 [2] 
中文名
算法設計與分析
類 別
慕課、國家精品在線開放課程
授課平台
中國大學MOOC
提供院校
北京大學
開課時間
2018年3月12日（首次）
授課教師
汪小林、蔣婷婷、羅國傑、屈婉玲

目錄

  1. 1 課程性質
  2. ▪ 課程定位
  3. ▪ 適應專業
  4. 2 開課信息
  5. 3 課程簡介
  1. 4 課程大綱
  2. 5 課前預備
  3. ▪ 預備知識
  4. ▪ 學習資料
  5. 6 授課目標
  1. 7 所獲榮譽
  2. 8 教師簡介

算法設計與分析課程性質

算法設計與分析課程定位

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

算法設計與分析適應專業

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

算法設計與分析開課信息

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

算法設計與分析課程簡介

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

算法設計與分析課程大綱

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 課程總結
參考資料： [1-2] 

算法設計與分析課前預備

算法設計與分析預備知識

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

算法設計與分析學習資料

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

算法設計與分析授課目標

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

算法設計與分析所獲榮譽

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

算法設計與分析教師簡介

汪小林，男，北京大學信息科學技術學院網絡與信息系統研究所教授。 [5] 
蔣婷婷，女，北京大學信息科學技術學院數字媒體所副教授。 [6] 
羅國傑，男，北京大學信息科學技術學院副教授。 [7] 
屈婉玲，女，北京大學信息科學技術學院、軟件與微電子學院教授。 [8] 
參考資料