算法設計與問題求解課程是北京交通大學建設的慕課、國家精品線上開放課程。該課程於2018年12月28日首次在中國大學MOOC開課。該課程授課教師是李清勇、張英俊、王公僕、趙宏智、李強、劉銘等。據2021年6月中國大學MOOC官網顯示，該課程已開課6次。
該課程共六章，包括緒論、枚舉算法（大道至簡）、遞歸與分治（庖丁解牛）、動態規劃（跬步千里）、貪心算法（局部尋優）、搜尋技術（按圖索驥）等。
基本介紹
- 中文名：算法設計與問題求解
- 授課平台：中國大學MOOC
- 建設院校：北京交通大學
- 授課教師：李清勇、張英俊、王公僕、趙宏智、李強、劉銘等
- 類別：慕課、國家精品線上開放課程
- 開課時間：2018年12月28日（首次）
課程性質,課程背景,課程定位,課程簡介,課程大綱,開課信息,教學目標,學習預備,課程特色,考核標準,所獲榮譽,教師簡介,
課程性質
課程背景
“軟體=算法+數據結構”，算法是軟體的靈魂。21世紀，在物聯網大數據和人工智慧等信息技術廣泛套用的資訊時代，社會生活和工業生產中的很多問題都需要藉助計算機來求解，而計算思維是分析複雜工程問題的重要思維方式， 計算機則是求解問題的重要工具。
課程定位
學習算法設計與問題求解課程將幫助學員提高計算思維和程式設計能力，幫助學員應對IT公司的算法筆試/面試或者研究生入學考試的機考/面試。
課程簡介
算法設計與問題求解課程共六章內容。該課程主要講授計算機問題求解的經典算法設計方法和算法複雜度分析方法，主要內容包括算法複雜度分析，枚舉算法（大道至簡），遞歸與分治策略（庖丁解牛），動態規劃（跬步千里），貪心算法（局部尋優）和通用搜尋技術（按圖索驥）。該課程除了強調經典的算法理論和模型，亦兼顧編程實踐能力。
課程大綱
第一章 緒論 | 4.7 最長公共子序列 - 問題分析 |
1.1 什麼是算法 | 4.8 最長公共子序列 - 算法與實現 |
1.2 計算機問題求解周期 | 4.9 0-1背包 - 問題分析 |
1.3 為什麼要學習算法 | 4.10 0-1背包 - 算法與實現 |
1.4 算法複雜度之大O定義 | 4.11 0-1背包 - 最佳化方法 |
1.5 算法複雜度之大O運算 | 4.12 最大上升子序列 - 問題分析 |
1.6 算法複雜度分析實例-非遞歸 | 4.13 最大上升子序列 - 算法與實現 |
1.7 算法複雜度分析實例-遞歸 | 4.14 小結 |
1.8 小結 | 收集控的決策問題 |
時間複雜度分析作業 | 第五章. 貪心算法（局部尋優）-1 |
第二章 枚舉算法（大道至簡） | 5.1 基本原理 |
2.1 基本原理 | 5.2 活動安排問題-算法與實現 |
2.2 模糊數字問題 | 5.3 活動安排問題-正確性證明 |
2.3 百錢百雞問題 | 5.4 小數背包問題 |
2.4 數組配對問題 | 5.5 哈夫曼編碼-算法與實現 |
2.5 繩子切割問題 | 5.6 哈夫曼編碼-正確性證明 |
2.6 石頭移動問題 | 5.7 單源最短路徑-Dijkstra與實現 |
2.7 小結 | 5.8 單源最短路徑-正確性證明 |
枚舉算法作業 | 數字刪除問題 |
第三章 遞歸與分治（庖丁解牛）-1 | 第五章. 貪心算法（局部尋優）-2 |
3.1 遞歸基本思想 | 5.9 最小生成樹-問題分析 |
3.2 遞歸實例 | 5.10 最小生成樹-Prim算法與實現 |
3.3 分治基本原理 | 5.11 最小生成樹-Prim證明 |
3.4 Master定理 | 5.12 並查集基礎 |
3.5 合併排序 | 5.13 最小生成樹- Kruskal算法與實現 |
遞歸算法實踐 | 5.14 最小生成樹- Kruskal證明 |
第三章 遞歸與分治（庖丁解牛）- 2 | 5.15 小結 |
3.6 逆序對問題 | 貪心算法實踐 |
3.7 快速排序 | 第六章. 搜尋技術（按圖索驥）-1 |
3.8 最接近點對 | 6.1 狀態空間圖 |
3.9 乘方運算 | 6.2 深度優先搜尋 |
3.10 線性時間選擇 | 6.3 廣度優先搜尋 |
3.11 小結 | 6.4 回溯算法-原理 |
矩陣搜尋問題 | 6.5 回溯算法-實例 |
第四章. 動態規劃（跬步千里）-1 | 搜尋算法實踐 |
4.1 基本原理 | 第六章. 搜尋技術（按圖索驥）-2 |
4.2 矩陣連乘 - 問題分析 | 6.6 分支限界法-原理 |
4.3 矩陣連乘 - 算法與實現 | 6.7 分支限界法-實例 |
4.4 矩陣連乘 - 備忘錄方法 | 6.8 啟發式搜尋-原理 |
4.5 多段圖最短路徑 - 問題分析 | 6.9 A*算法-原理 |
4.6 多段圖最短路徑 - 算法與實現 | 6.10 啟發式搜尋-實例 |
編輯距離問題 | 6.11 小結 |
第四章. 動態規劃（跬步千里）-2 | 搜尋算法實踐 |
開課信息
開課次數 | 開課時間 | 授課教師 | 學時安排 | 參加人數 |
|---|---|---|---|---|
第1次開課 | 2018年12月28日~2019年03月29日 | 李清勇、張英俊 | 待定 | 4443 |
第2次開課 | 2019年05月13日~2019年07月20日 | 4小時每周 | 4013 | |
第3次開課 | 2019年09月01日~2019年11月22日 | 李清勇、張英俊、王公僕、趙宏智、劉銘 | 3297 | |
第4次開課 | 2020年02月25日~2020年05月31日 | 李清勇、張英俊、王公僕、趙宏智、李強、劉銘 | 3578 | |
第5次開課 | 2020年10月10日~2021年01月31日 | 3452 | ||
第6次開課 | 2021年05月01日~2021年07月15日 | 待定 | ||
表格內容參考資料 | ||||
教學目標
1、培養算法思維，掌握枚舉算法、分治策略、動態規劃、貪心算法和搜尋算法等經典算法模型。
2、培養實踐能力，掌握在存儲空間和時間開銷受限情況下的程式設計方法。
3、培養理論思維，掌握問題求解的算法設計與分析方法。
學習預備
- 預備知識
1、高級程式設計語言基礎，熟悉C/C++，Java，Python中的任何一種。
2、高等數學、線性代數等基本工科數學基礎。
3、了解基本的數據結構知識。
4、了解Online Judge。
- 學習資料
課程特色
算法設計與問題求解課程以計算機經典問題求解為導向，通用算法思維和編碼能力培養為目標，引入ACM國際大學生程式設計競賽的有益元素，安排課程的理論教學和編程實踐，使得學員面對複雜問題時，既能“想到”還能“做到”。
考核標準
學習該課程，積極參與課程討論，完成本課的單元測試、單元作業和期末測驗，成績合格獲得合格證書，成績優秀獲得優秀證書。
評分依據：課程滿分100分。單元作業占55分，考試占45分，60分獲得合格證書，80~100分獲得優秀證書。
所獲榮譽
2019年，算法設計與問題求解課程中華人民共和國教育部認定為“國家精品線上開放課程”。
教師簡介
李清勇，男，博士，北京交通大學計算機與信息技術學院副院長，教授。
張英俊，男，博士，北京交通大學計算機與信息技術學院副教授。
王公僕，男，博士，北京交通大學教授、博士生導師。
趙宏智，男，博士，北京科技大學信息工程學院副教授。
李強，男，博士，北京交通大學教授，中國安全科學技術學會理事。
劉銘，男，博士，北京交通大學副教授、博士生導師。
