历史上的第一个算法,竟然至今还能用!
↑↑↑点击上方蓝字,回复资料,10个G的惊喜
算法一直是程序员们“难啃的骨头”。但早在计算机被发明以前,人们对于算法就已经研究了很长的时间。
算法历史上的每一个“第一次”,都为计算机的发展带来了重大影响。那算法为什么是计算机程序的灵魂?其实可以从它的发展史中略窥一二。
异步君将带领大家从算法的每个“第一次”开始,了解“好”算法的性质,还会送给大家一些算法的基础学习方法!
1
算法的每一个“第一次”
算法概念的第一次被提出
自古老的公元前1世纪开始,《周髀算经》就作为中国最古老的天文学和数学著作,在算法的历史上写下了浓墨重彩的一笔。
作为算经的十书之一,《周髀算经》采用最简便可行的方法确定天文历法,揭示日月星辰的运行规律,囊括四季更替,气候变化,包涵南北有极,昼夜相推的道理。为后来者的生活作息提供了有力保障。
经过几个世纪的发展,到公元9世纪,波斯数学家al-Khwarizmi第一次在数学上提出了“算法”这个概念——演算法(algorithm)。他提出的算法概念,仍旧沿用至今:
1.算术运算
指按照规定的法则和顺序对式题或算式进行运算,并求出结果的过程。包括:加法、减法、乘法、除法、乘方、开方等几种运算形式。
运算和计算略有区别,计算是指把横式中的数按运算符号和规定的顺序求得结果,可以按运算法则,也可以按口算或其他简便的方式直接求得结果。而运算则是指求得结果的过程。
2.关系运算
关系的基本运算有两类:一类是传统的集合运算(并、差、交等),另一类是专门的关系运算(选择、投影、连接、除法、外连接等),有些查询需要几个基本运算的组合,要经过若干步骤才能完成。
3.逻辑运算
逻辑运算又称布尔运算。布尔用数学方法研究逻辑问题,成功地建立了逻辑演算。他用等式表示判断,把推理看作等式的变换。这种变换的有效性不依赖人们对符号的解释,只依赖于符号的组合规律 。这一逻辑理论人们常称它为布尔代数。
历史上第一个算法
公元前330年,被人们称为“几何之父”的欧几里得出生了。在欧几里得生活的那个时期,几何学存在一个很大的缺点和不足,就是缺乏系统性。
这一时期的古希腊几何学,大多数是片断、零碎的知识,公理与公理之间、证明与证明之间并没有什么很强的联系性,更不要说对公式和定理进行严格的逻辑论证和说明。
于是欧几里得下定决心,要在有生之年完成对几何学的系统化理论化。由此,经过无数个日夜的撰写,人类史上第一个算法——欧几里得算法诞生了!
对现在的计算机行业来说,欧几里得算法是目前最经典的几大算法之一。
历史上的第一个算法程序
19世纪80年代,“软件之母”Ada Byron为巴贝奇分析机编写了求解伯努利方程的程序。这是人类史上的第一个算法程序。
巴贝奇分析机
Ada关于算法的研究实现了计算机科学的本质性飞跃。在她去世一百年之后的1953年,她之前所翻译《分析机概论》留下的笔记被重新公布,再一次震惊了世人。人们因此认为,Ada对现代计算机与软件工程造成了重大影响。
从现在的观点来看,Ada首先为了计算制作了“算法”,然后制作了“程序设计流程图”,这个珍贵的计划被认为是“第一件计算机程序”。
“软件之母”Ada Byron
作为世界上的第一位程序员,Ada为编程的发展做出了极大的贡献。
第一次解决算法定义的难题
进入20世纪,算法得到了进一步的巨大发展。这个世纪,英国数学家图灵提出了著名的图灵论题,并提出一种假想的计算机的抽象模型,这个模型被称为图灵机。
图灵机的构造
所谓的图灵机就是指一个抽象的机器,它有一条无限长的纸带,纸带分成了一个一个的小方格,每个方格有不同的颜色,有一个机器头在纸带上移来移去。
机器头有一组内部状态,还有一些固定的程序。每个时刻,机器头都要从纸带上读入一个方格信息,然后结合内部状态查找程序表,再根据程序输出信息到纸带方格上,并转换自己的内部状态进行移动。
虽然图灵机十分地简单,但它可以用来模拟任何算法。图灵机对人们使用纸笔进行数学计算的过程进行了抽象,实现了用机器代替人类进行数学计算。图灵机的出现,解决了算法定义的难题。
算法是计算机程序的灵魂,掌握了算法,就可以离开发出优秀的程序更近一步。
2
“算法+数据结构=程序”
说到算法与编程的关系,异步君就必须向大家介绍一位传奇人物:Nicklaus Wirth。
作为编程界的“Pascal之父”,Nicklaus Wirth有一句在计算机领域人尽皆知的名言:“算法+数据结构=程序”。
凭借着这句名言,Nicklaus Wirth在1984年拿到了图灵奖的奖项。因为这个公式对计算机科学的影响程度,足以类似物理学中爱因斯坦的“E=MC^2”——仅用一个公式就展示了程序的本质。
Nicklaus Wirth
Nicklaus Wirth于1934年在瑞士北部的温特图尔出生,其父瓦尔特是一位地理学教授。Wirth小时候就喜欢动手动脑,他的最大爱好就是组装飞机模型。
1960年,在加拿大莱维大学深造的Wirth获得了硕士学位。取得硕士学位的他并不满足,随后便进入加州大学伯克利分校,于1963年获得博士学位。
在斯坦福大学成功的开发出Algol W以及PL360后,爱国心极强的Nicklaus Wirth于1967年回到祖国瑞士,第二年在他的母校苏黎世工学院,他创建与实现了Pascal语言——当时世界上最受欢迎的语言之一。
Pascal语言算得上是一种经典的算法语言。而算法的主要目的在于为人们提供阅读了解所执行的工作流程与步骤。那么,什么样的算法才算是“好”的算法?异步君在这里提炼了几个性质:
(1)正确性:正确性是指算法能够满足具体问题的需求,程序运行正常,无语法错误,能够通过典型的软件测试,达到预期的需求。
(2)易读性:算法遵循标识符命名规则,简洁易懂,注释语句恰当适量,方便自己和他人阅读,便于后期调试和修改。
(3)健壮性:算法对非法数据及操作有较好的反应和处理。例如,在学生信息管理系统中登记学生年龄时,若将21岁误输入为210岁,系统应该提示出错。
(4)高效性:高效性是指算法运行效率高,即算法运行所消耗的时间短。算法时间复杂度就是算法运行需要的时间。
好的算法,可以让我们开发程序达到事半功倍的效果。那么我们应该如何学好算法呢?
3
如何学好算法
随着科技的发展,算法已经逐渐渗透在各行业内,是一个有着优秀前景的专业领域。
怎样学好算法?异步君在这里为大家准备了一些学习算法的入门路径:
算法工程师必备技能
1.至少懂一门语言:C/C++/java/python/R;
2. 熟练运用各种常用算法和数据结构,有独立的实现能力;
3.熟悉数据挖掘算法;
4.熟悉机器学习相关知识理论。
加分项:具有较为丰富的项目实践经验。
大家看到这里,肯定带一个疑惑:是应该直接学习算法吗?
万丈高楼平地起,任何高深的算法都要从基础算法学起,不可能一口吃个胖子。
所以,初入门的你学习算法还是要从基础开始:
算法的基础学习步骤
1.首先学习一门语言
例如 C/C++/Java/python,初学者学 C++比较普遍。
2.学数据结构
数据结构书有很多,但是有些教材晦涩难懂,建议看图解多,通俗易懂的书,推荐《趣学数据结构》。
3.学算法
不要直接看《算法导论》,大量证明会让你崩溃。
推荐《趣学算法》,有问题分析,完美图解,伪码详解,实战演练,适合初学者快速掌握经典算法。
程序的灵魂是算法。软件开发中,选择算法可以更快更好地实现功能。因此,程序员唯有掌握算法,才能轻松地驾驭程序开发。
也可以加一下老胡的微信 围观朋友圈~~~
推荐阅读
(点击标题可跳转阅读)
老铁,三连支持一下,好吗?↓↓↓