算法基础

课程概况

算法代表着用系统的方法描述解决问题的策略机制，北京大学《算法基础》课程将带你一一探索枚举、二分、贪心、递归、深度优先搜索、广度优先搜索、动态规划等经典算法，体会他们巧妙的构思，感受他们利用计算解决问题的独特魅力。顺利完成本课程，你将不但能够掌握这些算法的原理，还能够对这些算法进行灵活应用以及准确实现。本课程的中的编程任务，将充分训练你的思维能力和动手能力，促成全面、缜密思考问题的习惯。达到本门课程的要求，即意味者你具备了初步的算法基础和较强的编程实现能力。

课程大纲

周1
完成时间为 24 分钟
欢迎加入我们！
好的算法是程序设计的灵魂！拥有了骄人战绩的你，在熟练掌握程序设计语言的同时，只有掌握了算法这个利器之后，才能在驾驭程序开发项目中出其不意、鬼斧神工！欢迎加入《算法基础》课程，为你的程序插上飞翔的翅膀！PS：我们这门课程一直处在不断地建设与优化当中，吸取了很多以往课程的经典视频，所以如果你看到视频中出现了不同课程的名字，也不要惊讶哦，因为你正在集百家所长：）
2 个视频 （总计 4 分钟）, 2 个阅读材料

周2
完成时间为 4 小时
枚举
在日常生活中我们经常遇到这样的情景：数字密码最后一位忘记了，就从0~9逐个尝试；去提货点取快递，快递员检查完所有包裹才找到属于你的；警察列举出所有的嫌疑人才有可能发现真凶…以上在进行归纳推理时，逐个考察了某类事情的所有可能情况，并逐一进行检验，这种方法叫做枚举。枚举比较直观，易于理解，本模块将介绍枚举算法的基本数学模型和常用策略，从而解决通过公式推导、规则演绎的方法不能解决的问题。PS：我们这门课程一直处在不断地建设与优化当中，吸取了很多以往课程的经典视频，所以如果你看到视频中出现了不同课程的名字，也不要惊讶哦，因为你正在集百家所长：）
3 个视频 （总计 76 分钟）, 1 个阅读材料, 1 个测验

周3
完成时间为 5 小时
递归
递归调用是设计和描述算法的一种有力工具，尤其是在解决复杂问题时经常采用。它的基本思想是要解决某一问题A，可以先解决一个形式相同，但规模小一点的问题B。问题B如果解决了，那么问题A也就迎刃而解。有些问题使用传统的迭代算法是很难求解甚至无解的，而使用递归却可以很容易地解决。本模块将通过具体的例题介绍如何构造递归函数，如何设置递归终止的条件以及分析递归算法的复杂度。
4 个视频 （总计 97 分钟）, 1 个阅读材料, 1 个测验

周4
完成时间为 5 小时
动态规划（1）
通过上一模块的学习，你已经了解如何通过递归的办法解决问题，但是单纯的递归往往会导致子问题被重复计算，因此在解决某些问题的时候，效率会很低。而将一个问题分解为子问题递归求解，并且将中间结果保存以避免重复计算的方法就叫做“动态规划”。本模块将初步介绍对于特定的问题如何寻找子问题、定义问题的状态以及状态转移方程。
3 个视频 （总计 96 分钟）, 1 个阅读材料, 1 个测验

周5
完成时间为 4 小时
动态规划（2）
如何进行动态规划，没有一定之规，需要具体问题具体分析。本模块首先由典型的“最长上升子序列”引入，进一步展示几个较难的动规例题，深入探讨动态规划算法中状态的设计以及状态转移关系的构建。
4 个视频 （总计 71 分钟）, 1 个阅读材料, 1 个测验

周6
完成时间为 4 小时
深度优先搜索（1）
想象我们在一座迷宫里，如何才能找到出口呢？最直观的方法是从入口开始沿着一条路一直走到底，如果遇到分叉路口就选择其中一条道路走下去，如果遇到死胡同就退回到上一个分叉路口，选择另一条道路走下去，如果遇到出口就成功走出迷宫了。这种尽量往深处走的做法即是深度优先搜索(深搜）。深搜算法编程简单，简洁易懂，空间需求也比较低，但是这种方法的时间复杂度往往是指数级的，如果不加以优化，时间效率无法忍受。本模块将通过实例继续讨论深度优先搜索算法中优化程序的基本方法“剪枝”，即在设计剪枝判断方法的基础上，避免一些不必要的遍历过程，从而提高算法效率。
3 个视频 （总计 73 分钟）, 1 个阅读材料, 1 个测验

周7
完成时间为 4 小时
深度优先搜索（2）
本模块继续通过两道例题，强调了两种最通用的剪枝方法：可行性剪枝和最优性剪枝的应用。可行性剪枝即在寻找解的过程中，预判出从当前状态出发不可能找到解，从而不再从当前状态继续；最优性剪枝就是记录到目前为止找到的最优解，当发现正在探索的解其代价已经不小于最优解，或预测出其最终代价必将不小于最优解，则停止当前解的探索。
2 个视频 （总计 42 分钟）, 1 个阅读材料, 1 个测验

周8
完成时间为 5 小时
广度优先搜索
与深度优先搜索算法类似，广度优先搜索(广搜)也是常用的搜索图的算法。它的思想是从一个顶点开始，辐射状地优先遍历其
周围较广的区域。一般可以用它做什么呢？一个最直观经典的例子就是走迷宫，从起点开始，找出到终点的最短路程，很多最短路径算法都是基于广搜的思想。广索的基本方法是使用队列存放已经扩展过的节点。本模块先以简单例题引入广搜的基本实现方法，然后再通过经典的"八数码"问题，进一步介绍状态表示、判重的节省时间和空间的技巧。
4 个视频 （总计 90 分钟）, 1 个阅读材料, 1 个测验

周9
完成时间为 4 小时
二分与贪心
二分法是在有序或单调的区间中快速寻找答案的有效方法，当数据量很大适宜采用该方法。所谓贪心算法，即总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。但是，贪心算法对很多问题都能得到整体最优解。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。本模块将介绍二分与贪心这两个对很多问题都非常有效的算法策略。
4 个视频 （总计 70 分钟）, 1 个阅读材料, 1 个测验

周10
完成时间为 3 小时
期末考试
3个小时11道题目，这就是每年我们程序设计实习课程在校内的收官之作，让无数北大学生魂牵梦绕又各种怨念纠结的期末盛宴。你是不是准备好了呢？快来测测吧！也别忘了，搞定了基本算法并不代表着你作为程序员所向披靡啦，毕竟好的 程序=数据结构+算法。快去参加张铭老师的《数据结构基础》吧，你值得拥有！
1 个测验

周11
完成时间为 分钟
结束语
真的要把课程的接力棒传给张老师了，颇有些不舍！很高兴通过MOOC专项课程的方式结识不一样的你。希望我们的课程能带给你收获与思考，加油，你会是一位出色的程序员！

预备知识

先修课程：计算导论，C语言程序设计

参考资料

《程序设计导引及在线实践》，李文新，郭炜，余华山，清华大学出版社，2007

常见问题

Q: 学这门课需要数学基础吗?
A: 不需要，是算法课，不是数学课。有高中数学知识足矣。

Q: 这门课的程序用什么语言编写? 学这门课是否一定要会C++?
A: 课堂的例程都是用C++编写的，要看懂需要一定C++的知识。至于完成作业，用C, C++, Java,Pascal语言都可以。

Q: 还是不明白算法到底有什么用。会各种编程语言不就行了吗？
A: 语言只是实现算法的工具。没有好的算法，许多问题，计算机是不能够在人可以接受的时间内计算出结果的。各大IT公司招聘时往往会考察算法，而不是只问你会哪些语言。不会算法，掌握再多种语言，也很难说是一个好的程序员。