Auto Byte

专注未来出行及智能汽车科技

微信扫一扫获取更多资讯

Science AI

关注人工智能与其他前沿技术、基础学科的交叉研究与融合发展

微信扫一扫获取更多资讯

思源 晓坤整理

集20年之大成,这是一本开源的算法教科书

算法这个词有一股魔力,似乎任何工作任务加上它就能变得自动化,任何神奇的新发现也都离不开算法的帮助。那么什么是算法,我们又该如何学习算法呢?在这一本开源书籍《算法》中,作者根据 20 年的算法教学经历反复使用与修正,并在几天前完成出版前的最终版。

《算法》基于伊利诺伊大学厄巴纳 - 香槟分校的计算机科学教授 Jeff Erickson 为多个算法课程写的讲义集合,这本教科书已经在伊利诺伊大学厄巴纳 - 香槟分校出版,自 1999 年 1 月以来 Jeff Erickson 每年都会使用这本书教授一次算法课程。由于本科理论课程的变化,Jeff Erickson 在 2016 年对讲义进行了重大修订;本书是 Erickson 教授修订的最基础课程材料的一部分,主要反映了新的初级理论课程的算法内容。

书籍开源主页:http://jeffe.cs.illinois.edu/teaching/algorithms/

Erickson 教授在伊利诺伊州教授的算法课程有两个重要的先决条件:离散数学课程和基础数据结构课程。因此,这本教科书可能不适合大多数学生作为数据结构和算法的第一门课程。特别是,Erickson 教授假设至少熟悉以下特定主题:离散数学、证明技巧、迭代编程概念、基础抽象数据类型、基础数据结构、基础算法、基本算法分析、数学能力成熟度。

关于此书的其它信息:

  • Erickson 教授打算在近期将这本书自印出版,但不用担心,出版后这个资源也仍然是免费的。

  • Erickson 教授有一个维护多年的 GitHub 项目,专门为这本书做 Bug 追踪。

  • Erickson 教授明确表示,欢迎任何人下载电子版或纸质打印,使用、复制和/或分发此页面上的任何内容都是允许的。

  • 这本书基于两门课程,分别是 CS 374 (Spring 2018) 和 CS 473 (Spring 2017),Erickson 还在另一个页面上提供了课程作业和测试。

  • GitHub 地址:https://github.com/jeffgerickson/algorithms

  • 作业地址:http://jeffe.cs.illinois.edu/teaching/algorithms/hwex.html

书籍下载

Erickson 教授为我们提供了两种下载方式,有单页版和双页版。单页版方便在电脑上浏览,双页版方便打印纸质书,良心~

  • 单页版:http://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE.pdf

  • 双页版:http://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE-2up.pdf

除了书籍下载,Jeff 还提供了很多课程资料,包括 CS374 的 PPT、本书没有涉及的 CS 473 主题以及形式化语言的一些课件。这些资源有的有独到的见解,但笔记仍然不会有教科书那么精炼,读者可在教程主页找到这些额外的课程资源。

算法

既然都准备入这个坑了,那么算法的具体定义又是什么?它和我们熟悉的机器学习算法又有什么不同?在书籍的第一章中,Jeff Erickson 给出了算法的具体定义与来源,现在让我们走进「算法」这一词吧。

算法是一组明确的、精准的、无歧义且机械执行的基本指令元素序列,通常旨在完成具体的目标任务。其中指令描述的是一个计算,当其运行时能从一个初始状态和初始输入(可能为空)开始,经过一系列有限而明确定义的状态最终产生输出并停止于一个终态。

例如下面的伪码定义了一种「算法」来唱「99 Bottles of Beer on the Wall」,我们只要将 n 设置为 99 就完全和原版一样了。这就是一组精准和无歧义的指令元素:从 n 到 1 每次赋值一个整数为 i,并将 i 带入歌词且唱出,最后结尾再唱两句就行了。

「算法」这个词最终是由「algorism」演化到现代的「algorithm」,它主要通过希腊算术(arithmos)这一民间词源演化而成。因此直到最近,算法一词还专门指代使用阿拉伯数字进行位-值计算的机械计算技术。经过训练,且能快速和可靠地执行这些过程的人,可以称为算术者或者是计算员。当然,你也可以更简单地称为计算机。

因此对于机器学习,算法一词非常广泛,只要是针对特定任务的确定性计算流程,我们都可以称之为算法。下面我们具体看看在这本书中,「算法」都涉及哪些主题与内容:

Jeff Erickson 是伊利诺伊大学厄巴纳 - 香槟分校的计算机科学教授,研究兴趣包括算法、数据结构和拓扑学等,曾获得美国国家科学基金会职业奖和本科教学最高奖。

图源:http://jeffe.cs.illinois.edu/(Jeff Erickson 主页)

这本书的重新出版在 ycombinator 上引起了很大反响,14 个小时内已经出现了 180 多条评论。

网友 primitivesuave 表示:

Jeff Erickson 是我 2012 年的算法教授。他是我见过的表达清晰、充满激情的教育者的典范。我曾经多次阅读这些笔记来准备相当困难的考试。偷偷告诉你一件上他的课的同学间流传的轶事:在 25% 的测试问题上,你只要写「我不知道」,反而能因为承认自身缺陷而得到嘉奖,还节省了教授纠正你的糟糕答案的时间。

网友 kaap 表示:

他是我在 1999 年的算法课程教授,并也在我的同学间获得了一致好评。他对递归的解释真是完美(章节 1.2):「递归算法希望为你解决所有的更简单的子问题,至于使用什么方法你别管,一边吃瓜就行。」

参考内容:https://news.ycombinator.com/item?id=18805624

入门算法Jeff Erickson
8
相关数据
机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

拓扑学技术

莫比乌斯带,只有一个面与一个边,为拓扑学所研究之一类对象。 在数学里,拓扑学(英语:topology),或意译为位相几何学,是一门研究拓扑空间的学科,主要研究空间内,在连续变化(如拉伸或弯曲,但不包括撕开或黏合)下维持不变的性质。在拓扑学里,重要的拓扑性质包括连通性与紧致性。

推荐文章
暂无评论
暂无评论~