课程简介

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

课程大纲

课程大纲

一、概述

101 引子:数据时代 9m53s

102 问题求解的计算之道 12m20s

103 图灵机计算模型 14m49s

104 算法和计算复杂性 14m28s

105 突破计算极限 9m08s

106 什么是抽象和实现 9m00s

107 为什么研究数据结构与算法 10m02s

108 从C转换到Python

第一周测验


二、算法分析

201 什么是算法分析 16m49s

202 大O表示法 13m06s

203 “变位词”判断问题(上) 10m27s

204 “变位词”判断问题(下) 9m54s

205 Python数据类型的性能(上) 12m37s

206 Python数据类型的性能(下) 10m18s

207 怎么做慕课Python在线评测OJ作业

第二周测验

OJ的适应性测试


三、基本结构(上)

301 什么是线性结构 6m59s

302 栈抽象数据类型及Python实现 10m14s

303 栈的应用:简单括号匹配 11m19s

304 栈的应用:十进制转换为二进制 9m34s

305 表达式转换(上) 11m24s

306 表达式转换(下) 12m36s

307 后缀表达式求值 8m18s

第三周测验

第三周作业


四、基本结构(下)

308 队列抽象数据类型及Python实现 10m01s

309 队列的应用:热土豆 7m52s

310 队列的应用:打印任务(上) 7m37s

311 队列的应用:打印任务(下) 17m23s

312 双端队列抽象数据类型及Python实现+回文词判定 7m25s

313 无序表抽象数据类型及Python实现 11m03s

314 无序表的链表实现 12m54s

315 有序表抽象数据类型及Python实现 13m14s

316 线性结构小结 6m08s

第四周测验

第四周作业


五、递归(上)

401 什么是递归 13m20s

402 递归的应用:任意进制转换 6m32s

403 递归调用的实现 8m32s

404 递归可视化:分形树 10m54s

405 递归可视化:谢尔宾斯基三角 10m31s

406 递归的应用:汉诺塔 10m37s

407 递归的应用:探索迷宫 16m35s

第五周测验

第五周作业


六、递归(下)

408 分治策略 5m34s

409 优化问题和贪心策略 7m49s

410 找零兑换问题的递归解法 12m32s

411 找零兑换问题的动态规划解法 13m26s

412 动态规划案例分析 17m53s

413 递归小结 6m51s

第六周测验

第六周作业


七、排序与查找(上)

501 顺序查找算法及分析 9m41s

502 二分查找算法及分析 12m20s

503 冒泡和选择排序算法及分析 12m14s

504 插入排序算法及分析 7m06s

505 谢尔排序算法及分析 6m15s

506 归并排序算法及分析 9m13s

507 快速排序算法及分析 12m30s

第七周测验

第七周作业


八、排序与查找(下)

508 什么是散列 7m21s

509 完美散列函数 15m02s

510 区块链技术 17m20s

511 散列函数设计 8m47s

512 冲突解决方案 11m59s

513 映射抽象数据类型及Python实现 14m58s

514 排序与查找小结 9m45s

第八周测验

第八周作业


九、树及算法(上)

601 什么是树 8m37s

602 树结构相关术语 8m23s

603 树的嵌套列表实现 11m00s

604 树的链表实现 6m57s

605 树的应用:表达式解析(上) 13m03s

606 树的应用:表达式解析(下) 15m15s

607 树的遍历 10m11s

608 优先队列和二叉堆 11m45s

609 二叉堆的Python实现 13m14s

第九周测验

第九周作业


十、树及算法(下)

610 二叉查找树及操作 8m59s

611 二叉查找树实现及算法分析(上) 11m55s

612 二叉查找树实现及算法分析(下) 14m39s

613 AVL树的定义和性能 7m08s

614 AVL树的Python实现 20m04s

615 树结构小结 7m39s

第十周测验

第十周作业


十一、图及算法(上)

701 图的基本概念及相关术语 11m51s

702 图抽象数据类型 5m57s

703 图抽象数据类型的Python实现 5m26s

704 图的应用:词梯问题 8m20s

705 实现广度优先搜索 15m07s

706 图的应用:骑士周游问题 6m37s

707 骑士周游问题算法实现 7m56s

708 骑士周游问题算法分析与改进 8m45s

第十一周测验

第十一周作业


十二、图及算法(下)

709 通用的深度优先搜索 10m27s

710 图的应用:拓扑排序 9m30s

711 图的应用:强连通分支 11m16s

712 图的应用:最短路径 16m54s

713 图的应用:最小生成树 12m08s

714 图结构小结 6m33s

第十二周测验

第十二周作业


课程说明

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

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


参考资料

已出版纸质教材:Python数据结构与算法分析 第2版,[美] 布拉德利·米勒(Bradley N.Miller),戴维·拉努姆(David L.Ranum) 著,吕能,刁寿钧 译,人民邮电出版社,2019

[数据结构与算法Python-中文版-内部教材](https://gis4g.pku.edu.cn/download/sessdsa-textbook/  )

[在线英文版教材](https://runestone.academy/runestone/books/published/pythonds/index.html  )


拓展阅读

[Python3官方中文版文档](https://docs.python.org/zh-cn/3/  )

[Python3烹饪书](https://python3-cookbook.readthedocs.io/zh_CN/latest/index.html  )

[在线Python代码规范](https://python-guide.gitbooks.io/python-style-guide/content/  )



其他

主讲教师

陈斌   计算机软件、地理信息系统

北京大学地球与空间科学学院教师,博士,教学教授。获得北京大学计算机科学技术系学士、硕士和博士学位。主讲本科生课程《数据结构与算法(Python版)》、《离散数学》、北京大学通识教育核心课程《地球与人类文明》,研究生课程《空间数据库》、《开源空间信息软件》,深受学生欢迎,荣获北京市高等学校教学名师奖,北京大学首届教学卓越奖,另获得多项市校级教学奖。主要研究方向为虚拟地理环境和空间信息分布式计算,主持并参与多项国家自然科学基金、863、973、国家科技支撑计划及国家重点研发计划项目课题。

课程助教

  • zhangyuhao415

  • kuuhakuj

  • wcb

  • 张晓媛

  • 1800011308

相关课程推荐

  • 正在进行
    Java程序设计
    《Java程序设计》课程是使用Java语言进行应用程序设计的课程,针对各专业的大学本科生开设。课程的主要目标有三: 一、掌握Java语言的语法,能够较为深入理解Java语言机制,掌握Java语言面向对象的特点。 二、掌握JavaSE中基本的API,掌握在集合、线程、输入输出、图形用户界面、网络等方面的应用。三、能够编写有一定规模的应用程序,养成良好的编程习惯,会使用重构、设计模式、单元测试、日志、质量管理工具提高代码的质量。 对于学过“计算机基础、计算概论或C语言的学生”尤为适用。
  • 正在进行
    翻译与本地化工程
    本课程将讲授现代语言服务行业中相关的翻译与本地化工程知识,选修本课程的同学,需要具备一定的计算机基础知识,并在修课之前完成预修任务。
  • 正在进行
    大数据分析中的算法
    大数据给数据分析和处理带来了前所未有的机遇和挑战。本课程介绍大数据分析中一些算法:数据的稀疏和低秩表达,稀疏和低秩矩阵优化,社交网络计算中的图与网络流问题,机器学习和数据挖掘的最优化算法,随机优化算法,强化学习等等。通过本课程学习,掌握最优化的基本概念,典型的几类最优化建模方法,相关优化问题的基本计算方法,并能熟练调用基于MATLAB或Python等语言的典型优化软件程序求解一些标准的优化问题,灵活运用所讲授的算法和理论求解一些非标准的优化问题。达到锻炼将实际问题建立合适最优化模型的能力,选择合适的现有软件包和算法的能力,遇到没有现成算法自己实现简单算法的能力。

恭喜,报名成功

进入学习中心

恭喜,报名成功

确定

请进入开课界面预览

确定

X

请去您的邮箱验证

还没收到验证邮件?

1. 试试去广告邮件、垃圾邮件目录看看

2. 再次发送验证邮件

对不起,班次容量已满

请报名下一班次

知道了~!

对不起,您没有操作权限

知道了~!