hi,小慕
课程

中国大学MOOC,为你提供一流的大学教育

hi,小mooc
数据结构与算法Python版
第1次开课
开课时间: 2019年09月12日 ~ 2019年12月12日
学时安排: 2-3小时每周
当前开课已结束 已有 26195 人参加
老师已关闭该学期,无法查看
课程详情
课程评价(333)
spContent=本课基于主讲教师在北京大学讲授数据结构与算法课(Python版)的多年教学实践经验,面向具有Python语言程序设计基础的大学生和社会公众,介绍常见的基本数据结构以及相关经典算法,强调问题-数据-算法的抽象过程,关注数据结构与算法的时间空间效率,培养学生编写出高效程序,具备解决问题的综合能力。
本课基于主讲教师在北京大学讲授数据结构与算法课(Python版)的多年教学实践经验,面向具有Python语言程序设计基础的大学生和社会公众,介绍常见的基本数据结构以及相关经典算法,强调问题-数据-算法的抽象过程,关注数据结构与算法的时间空间效率,培养学生编写出高效程序,具备解决问题的综合能力。
—— 课程团队
课程概述

本课基于主讲教师在北京大学讲授数据结构与算法课(Python版)的多年教学实践经验,面向具有Python语言程序设计基础的大学生和社会公众,介绍常见的基本数据结构以及相关经典算法,强调问题-数据-算法的抽象过程,关注数据结构与算法的时间空间效率,培养学生编写出高效程序,从而解决实际问题的综合能力。


本课内容包括课程概述、算法分析、基本线性结构、递归与动态规划、排序与查找、树及其算法、图及其算法等。课程将围绕着“算法+数据结构=程序”的思路,以问题求解为导向进行学习,帮助学生提高理论、抽象、设计的能力。


本课注重数据结构与算法的实践与应用,在课程中穿插了生动案例和编程练习,引导学生积极建立数据抽象和层次分析的思维模式,通过解决实际问题来加深对数据组织结构和相应处理算法的学习体会,并学会通过实际应用情况来权衡时空和其它资源开销,达到最优的应用效果。

授课目标

本课注重数据结构与算法的实践与应用,在课程中穿插了生动案例和编程练习,引导学生积极建立数据抽象和层次分析的思维模式,通过解决实际问题来加深对数据组织结构和相应处理算法的学习体会,并学会通过实际应用情况来权衡时空和其它资源开销,达到最优的应用效果。

课程大纲
概述(1周)
课时目标:介绍计算理论和计算复杂性
1. 引子
2. 关于计算的概念和定义:问题求解的计算之道
3. 图灵机计算模型
4. 可计算性和计算复杂度;
5. 什么是抽象
6. 什么是编程实现
7. 为什么研究数据结构与抽象数据类型
8. 为什么研究算法
算法分析(1周)
课时目标:介绍算法分析,大O表示法,以及用实例来演示同一个问题的不同解决方案的算法分析。
1. 什么是算法分析?
2. 大O表示法
3. 案例分析:“变位词”判断问题
4. Python数据结构的性能:列表List和字典Dictionary
基本结构(2周)
课时目标:介绍栈、队列、双端队列和列表等线性结构。
1. 什么是线性结构?
2. 栈Stack抽象数据类型及Python实现
3. 栈的应用:简单括号匹配
4. 栈的应用:十进制转换为二进制
5. 栈的应用:中缀、前缀和后缀表达式
6. 队列Queue抽象数据类型及Python实现
7. 队列的应用:热土豆
8. 队列的应用:打印任务
9. 双端队列Deque抽象数据类型及Python实现
10. 双端队列应用:回文词判定
11. 列表List抽象数据类型及Python实现
12. 无序表实现及链表
13. 有序表抽象数据类型及Python实现
递归(3周)
课时目标:介绍递归和动态规划算法,以及分治策略解决问题。
1. 什么是递归
2. 实例分析:列表求和的递归算法
3. 递归“三定律”
4. 递归的应用:任意进制转换
5. 实现递归:调用栈
6. 递归的可视化
7. 递归的应用:塞宾斯基三角形绘制
8. 复杂递归问题
9. 递归的应用:汉诺塔
10. 递归的应用:探索迷宫
11. 动态规划Dynamic Programming
排序与查找(2周)
课时目标:介绍经典的排序和查找算法
1. 什么是查找?
2. 顺序查找算法及分析
3. 二分查找算法及分析
4. 散列:散列函数、碰撞解决和映射数据类型
5. 什么是排序?
6. 冒泡排序算法及分析;
7. 选择排序算法及分析;
8. 插入排序算法及分析;
9. 谢尔排序算法及分析;
10. 归并排序算法及分析;
11. 快速排序算法及分析。
树及算法(3周)
课时目标:介绍树结构和树结构的处理算法,以及应用
1. 树的基本概念及相关术语
2. 树的列表实现;
3. 树的链表实现;
4. 树的应用:表达式解析
5. 树的遍历
6. 二叉堆实现的优先队列
7. 二叉堆的实现
8. 二叉查找树及操作
9. 二叉查找树实现及算法分析
10. 平衡的二叉查找树
11. AVL树的性能
12. AVL树的实现
图及算法(3周)
课时目标:介绍图结构和图的应用。
1. 图的基本概念及相关术语
2. 图抽象数据类型
3. 邻接矩阵和邻接表
4. 图的实现
5. Word Ladder词梯问题
6. 构建词梯问题的图数据结构
7. 实现广度优先搜索BFS
8. BFS算法分析
9. 骑士周游问题
10. 构建骑士周游问题的图数据结构
11. 骑士周游问题算法实现
12. 骑士周游问题算法分析
13. 通用的深度优先搜索DFS
14. DFS算法分析
15. 拓扑排序
16. 强连通分支
17. 最短路径问题Dijkstra算法及算法分析
18. Prim最小生成树算法
展开全部
预备知识

具备基本的Python语言程序设计能力,比如学习过这门慕课:[Python语言基础与应用](https://www.icourse163.org/course/0809PKU036-1003479006

证书要求
  • 本课程采取百分制,单元测验和作业占45分,讨论区讨论占5分,期末在线考试占50分。

  • 60分-84分可获得合格证书,85分(含)以上可申请优秀证书。证书自愿申请。



参考资料
常见问题

Q :  学习这门课需要什么基础?
A :  具备基本的Python语言程序设计能力即可,比如学习过这门慕课:[Python语言基础与应用](https://www.icourse163.org/course/0809PKU036-1003479006)。


Q :  本课程教学使用的Python语言是哪个版本?

A :  Python 3.x,本课程代码示例均采用Python 3.x版本。虽然众所周知3.x版本与2.x版本并不兼容,但如今所有Python主流功能库都可以稳定运行在Python 3.x版本下,绝大多数Python程序员都已经使用Python 3.x版本。


Q :  通过Python语言学习数据结构与算法有什么优势呢?

A :  相比传统的C/C++/Java语言描述数据结构与算法,Python语言的抽象层次更高,代码描述更简洁,学习者可以集中注意力在数据的操作语义及其应用,更多关注用合适的数据结构和算法来进行问题求解,而不会被繁杂的代码描述细节所干扰。

北京大学
1 位授课老师
陈斌

陈斌

教授

推荐课程

【DeepSeek适用】小白玩转AI大模型应用开发

林粒粒

204人参加

小白玩转 Python 数据分析

林粒粒

78人参加
下载
下载

下载App