數據結構與算法(北京大學提供的慕課)

數據結構與算法(北京大學提供的慕課)

本詞條是多義詞,共20個義項
更多義項 ▼ 收起列表 ▲

數據結構與算法是北京大學於2018年02月26日首次在中國大學MOOC開設的慕課課程,是國家精品線上開放課程。該課程授課教師為張銘、陳斌、盧宗青、劉雲淮、趙海燕、宋國傑、黃駿、鄒磊、王騰蛟。據2021年2月中國大學MOOC官網顯示,該課程已開課4次。

數據結構與算法課程內容包括數據結構與抽象數據類型、算法特性及分類、算法效率與度量、線性結構、順序表、鍊表、棧與佇列、棧與遞歸、遞歸轉非遞歸、字元串的存儲結構、字元串運算的算法實現、字元串的快速模式匹配、二叉樹的抽象數據類型、二叉樹的搜尋、二叉樹的存儲結構、樹與二叉樹的等價轉換、樹的抽象數據類型及樹的遍歷、樹的鏈式存儲結構、樹的父指針表示法、樹的順序存儲和K叉樹、圖的概念和抽象數據類型、圖的存儲結構、圖的遍歷、內排序、檢索等內容。

基本介紹

  • 中文名:數據結構與算法
  • 開課時間:2018年02月26日(首次)
  • 提供院校:北京大學
  • 類別:國家精品線上開放課程
  • 授課平台:中國大學MOOC
  • 授課教師:張銘、陳斌、盧宗青、劉雲淮、趙海燕、宋國傑、黃駿、鄒磊、王騰蛟
課程性質,課程背景,課程定位,適應對象,開課信息,課程簡介,課程大綱,課前預備,預備知識,學習資料,授課目標,所獲榮譽,教師簡介,

課程性質

課程背景

計算機是現代社會中用於解決問題的重要工具,支撐這個工具高效運轉的就是其後的各種系統程式、應用程式。數據結構,是抽象的表示數據的方式;算法,則是計算的一系列有效、通用的步驟。算法與數據結構是程式設計中相輔相成的兩個方面,是計算機學科的重要基石。

課程定位

數據結構與算法是介紹基本數據結構以及相關的經典算法,強調問題-數據-算法的抽象過程,關注數據結構與算法的時間空間效率,培養學生編寫出高效程式從而解決實際問題的綜合能力的一門課程。

適應對象

數據結構與算法適合計算機以及相關理工專業的本科生學習。對於具有C語言結構化程式設計基礎的學生,該課程第0章補充了一些面向對象的基本內容。

開課信息

開課次數
開課時間
學時安排
授課教師
參與人數
第1次開課
2018年02月26日 ~ 2018年07月01日
4-8小時每周
張銘、陳斌、盧宗青、劉雲淮、趙海燕、宋國傑、黃駿、鄒磊
30697
第2次開課
2018年09月17日 ~ 2019年01月13日
4-8小時每周
張銘、陳斌、趙海燕、宋國傑、黃駿、鄒磊、王騰蛟
50179
第3次開課
2019年09月09日 ~ 2020年01月13日
3-5小時每周
張銘、趙海燕、王騰蛟、宋國傑、黃駿、鄒磊
55514
第4次開課
2020年09月21日 ~ 2021年01月20日
3-5小時每周
張銘、王騰蛟、趙海燕、宋國傑、鄒磊
13281
(以上表格內容參考資料:

課程簡介

數據結構與算法圍繞著“算法+數據結構=程式”的思路,以問題求解為導向進行學習,運用問題抽象、數據抽象、算法抽象來分析問題,套用適當的數據結構和算法來設計和實現相應的程式。在求解實際問題方面,該課程會學習到通過權衡時空和其他資源開銷,利用數據結構來組織數據、設計高效的算法、完成高質量的程式以滿足錯綜複雜的實際套用需要。課程所學到的內容會被利用到計算機科學後續的各個課程中,如作業系統、軟體工程、資料庫概論、編譯技術、計算機圖形學、人機互動等。

課程大綱

第一章 概論(兩周)
4.4字元串的快速模式匹配(選修)
8.4交換排序(冒泡排序、快速排序)
1.1課程介紹
第五章 二叉樹(兩周)
8.5歸併排序
1.2問題求解
5.1二叉樹的概念
8.6桶排序
1.3數據結構與抽象數據類型
5.2二叉樹的抽象數據類型
8.7靜態基數排序(選修)
1.4算法特性及分類
5.3二叉樹的搜尋
8.8鏈式基數排序(選修)
1.5算法效率與度量
5.4二叉樹的存儲結構
8.9索引排序(選修)
1.6補充 面向對象簡介(選修)
5.5二叉搜尋樹
8.10排序算法的時間代價
1.7補充 類的特殊成員(選修)
5.6堆與優先佇列
第十章 檢索
1.8補充 模版函式與模版類(選修)
5.7 Huffman樹及其套用
10.1檢索的概念
1.9補充 輸入輸出流(選修)
第六章 樹
10.2基於線性表的檢索
第二章 線性表
6.1樹的定義、樹與二叉樹的等價轉換
10.3集合的檢索
2.1線性結構
6.2樹的抽象數據類型及樹的遍歷
10.4散列表的概念和散列函式
2.2順序表
6.3樹的鏈式存儲結構
10.5散列衝突處理
2.3鍊表
6.4樹的父指針表示法(選修)
10.6散列的實現及性能分析
2.4順序表和鍊表的比較
6.5樹的順序存儲和K叉樹
擴展:第九章(選修)
第三章 棧與佇列
第七章 圖
9.1 主存儲器和外存儲器
3.1棧
7.1圖的概念和抽象數據類型
9.2 檔案的組織和管理
3.2棧與遞歸
7.2圖的存儲結構
9.3 外排序
3.3遞歸轉非遞歸(選修)
7.3圖的遍歷
擴展:字典(選修)
3.4佇列
7.4最短路徑
B樹B+樹
3.5佇列的套用
7.5最小生成樹
Trie 樹
第四章 字元串
第八章 內排序(兩周)
AVL樹
4.1字元串基本概念
8.1 排序問題的基本概念
Splay樹
4.2字元串的存儲結構
8.2插入排序 ( Shell 排序)
(課程大綱排版從左到右列
4.3字元串運算的算法實現
8.3選擇排序 (堆排序)

課前預備

預備知識

學習數據結構與算法課程需要下面課程裡面的部分基本知識:
建議先修過計算概論等課程,最好具備C++等面向對象的程式設計基礎。

學習資料

書名
作者
ISBN
出版時間
出版社
《數據結構與算法》
張銘,王騰蛟,趙海燕
9787040239614
2008年6月
高等教育出版社
《數據結構與算法實驗教程》
張銘,趙海燕,王騰蛟
9787040302141
2011年1月
《數據結構與算法--學習指導與習題解析》
張銘、趙海燕、王騰蛟
704017829X
2005年10月
高等教育出版社
《數據結構算法與套用—C++語言描述》
S. Sahni著,汪詩林等譯
9787111076452
2000年
Algorithms Design Techniques and Analysis
M. H. Alsuwaiyel
9789810237400
2003年1月
電子工業出版社影印
Inroduction to Algorithms
T. H.Cormen, C. E.Leiserson, R. L. Rivest, C. Stein
/
2002年5月
高等教育出版社影印
《電腦程式設計藝術,第1卷基本算法》
D. E.Knuth著,蘇運霖譯
9787118027990
2002年
Algorithm Design
J. Kleinberg, E. Tardos
9780321295354
2005年
Addison Wesley
Data Structures and Algorithm Analysis in C++, Third Edition
C. A. Shaffer
9780486485829
2011年
Dover Publications
《算法設計與分析》
王曉東
9787302061861
2003年1月
清華大學出版社
(表格內容參考資料:

授課目標

通過學習此課程,提高理論、抽象、設計的能力;在紮實的經典理論基礎上,運用問題抽象、數據抽象、算法抽象來分析問題,套用適當的數據結構和算法來設計和實現相應的程式;通過課程學習,抽象思維能力、問題求解能力能得到較大提升,編程能力和代碼質量會有質的飛躍。

所獲榮譽

2019年1月8日,數據結構與算法被中華人民共和國教育部認定為“國家精品線上開放課程”。

教師簡介

盧宗青,北京大學助理教授。
劉雲淮,北京大學研究員。
趙海燕,北京大學副教授。
宋國傑,北京大學信息科學技術學院副教授。
鄒磊,北京大學教授。
王騰蛟,北京大學信息科學技術學院教授。

相關詞條

熱門詞條

聯絡我們