【www.9778.com】大数据等最核心的关键技术:32个算法

www.9778.com 1

大数据等最核心的关键技术:32个算法

www.9778.com ,奥地利符号计算研究所(Research Institute for Symbolic
Computation,简称RISC)的Christoph
Koutschan博士在自己的页面上发布了一篇文章,提到他做了一个调查,参与者大多数是计算机科学家,他请这些科学家投票选出最重要的算法,以下是这次调查的结果,按照英文名称字母顺序排序。

 

1、A*
搜索算法
——图形搜索算法,从给定起点到给定终点计算出路径。其中使用了一种启发式的估算,为每个节点估算通过该节点的最佳路径,并以之为各个地点排定次序。算法以得到的次序访问这些节点。因此,A*搜索算法是最佳优先搜索的范例。

 

2、集束搜索(又名定向搜索,Beam
Search)——最佳优先搜索算法的优化。使用启发式函数评估它检查的每个节点的能力。不过,集束搜索只能在每个深度中发现最前面的m个最符合条件的节点,m是固定数字——集束的宽度。

 

3、二分查找(Binary
Search)——在线性数组中找特定值的算法,每个步骤去掉一半不符合要求的数据。

 

4、分支界定算法(Branch and
Bound)——在多种最优化问题中寻找特定最优化解决方案的算法,特别是针对离散、组合的最优化。

 

5、Buchberger算法——一种数学算法,可将其视为针对单变量最大公约数求解的欧几里得算法和线性系统中高斯消元法的泛化。

 

6、数据压缩——采取特定编码方案,使用更少的字节数(或是其他信息承载单元)对信息编码的过程,又叫来源编码。

 

7、Diffie-Hellman密钥交换算法——一种加密协议,允许双方在事先不了解对方的情况下,在不安全的通信信道中,共同建立共享密钥。该密钥以后可与一个对称密码一起,加密后续通讯。

 

8、Dijkstra算法——针对没有负值权重边的有向图,计算其中的单一起点最短算法。

 

9、离散微分算法(Discrete differentiation)。

 

10、动态规划算法(Dynamic
Programming)——展示互相覆盖的子问题和最优子架构算法

 

11、欧几里得算法(Euclidean
algorithm)——计算两个整数的最大公约数。最古老的算法之一,出现在公元前300前欧几里得的《几何原本》。

 

12、期望-最大算法(Expectation-maximization
algorithm,又名EM-Training)——在统计计算中,期望-最大算法在概率模型中寻找可能性最大的参数估算值,其中模型依赖于未发现的潜在变量。EM在两个步骤中交替计算,第一步是计算期望,利用对隐藏变量的现有估计值,计算其最大可能估计值;第二步是最大化,最大化在第一步上求得的最大可能值来计算参数的值。

 

13、快速傅里叶变换(Fast Fourier
transform,FFT)——计算离散的傅里叶变换(DFT)及其反转。该算法应用范围很广,从数字信号处理到解决偏微分方程,到快速计算大整数乘积。

 

14、梯度下降(Gradient descent)——一种数学上的最优化算法。

 

15、哈希算法(Hashing)。

 

16、堆排序(Heaps)。

 

17、Karatsuba乘法——需要完成上千位整数的乘法的系统中使用,比如计算机代数系统和大数程序库,如果使用长乘法,速度太慢。该算法发现于1962年。

 

18、LLL算法(Lenstra-Lenstra-Lovasz  lattice
reduction)——以格规约(lattice)基数为输入,输出短正交向量基数。LLL算法在以下公共密钥加密方法中有大量使用:背包加密系统(knapsack)、有特定设置的RSA加密等等。

 

19、最大流量算法(Maximum
flow)——该算法试图从一个流量网络中找到最大的流。它优势被定义为找到这样一个流的值。最大流问题可以看作更复杂的网络流问题的特定情况。最大流与网络中的界面有关,这就是最大流-最小截定理(Max-flow
min-cut theorem)。Ford-Fulkerson 能找到一个流网络中的最大流。

 

20、合并排序(Merge Sort)。

 

21、牛顿法(Newton’s
method)——求非线性方程(组)零点的一种重要的迭代法。

 

22、Q-learning学习算法——这是一种通过学习动作值函数(action-value
function)完成的强化学习算法,函数采取在给定状态的给定动作,并计算出期望的效用价值,在此后遵循固定的策略。Q-leanring的优势是,在不需要环境模型的情况下,可以对比可采纳行动的期望效用。

 

23、两次筛法(Quadratic
Sieve)——现代整数因子分解算法,在实践中,是目前已知第二快的此类算法(仅次于数域筛法Number
Field
Sieve)。对于110位以下的十位整数,它仍是最快的,而且都认为它比数域筛法更简单。

 

24、RANSAC——是“RANdom SAmple
Consensus”的缩写。该算法根据一系列观察得到的数据,数据中包含异常值,估算一个数学模型的参数值。其基本假设是:数据包含非异化值,也就是能够通过某些模型参数解释的值,异化值就是那些不符合模型的数据点。

 

25、RSA——公钥加密算法。首个适用于以签名作为加密的算法。RSA在电商行业中仍大规模使用,大家也相信它有足够安全长度的公钥。

 

26、Schönhage-Strassen算法——在数学中,Schönhage-Strassen算法是用来完成大整数的乘法的快速渐近算法。其算法复杂度为:O(N
log(N) log(log(N))),该算法使用了傅里叶变换。

 

27、单纯型算法(Simplex
Algorithm)——在数学的优化理论中,单纯型算法是常用的技术,用来找到线性规划问题的数值解。线性规划问题包括在一组实变量上的一系列线性不等式组,以及一个等待最大化(或最小化)的固定线性函数。

 

28、奇异值分解(Singular value
decomposition,简称SVD)——在线性代数中,SVD是重要的实数或复数矩阵的分解方法,在信号处理和统计中有多种应用,比如计算矩阵的伪逆矩阵(以求解最小二乘法问题)、解决超定线性系统(overdetermined
linear systems)、矩阵逼近、数值天气预报等等。

 

29、求解线性方程组(Solving a system of linear
equations)——线性方程组是数学中最古老的问题,它们有很多应用,比如在数字信号处理、线性规划中的估算和预测、数值分析中的非线性问题逼近等等。求解线性方程组,可以使用高斯—约当消去法(Gauss-Jordan
elimination),或是柯列斯基分解( Cholesky decomposition)。

 

30、Strukturtensor算法——应用于模式识别领域,为所有像素找出一种计算方法,看看该像素是否处于同质区域(
homogenous region),看看它是否属于边缘,还是是一个顶点。

 

31、合并查找算法(Union-find)——给定一组元素,该算法常常用来把这些元素分为多个分离的、彼此不重合的组。不相交集(disjoint-set)的数据结构可以跟踪这样的切分方法。合并查找算法可以在此种数据结构上完成两个有用的操作:

  •   查找:判断某特定元素属于哪个组。

  •   合并:联合或合并两个组为一个组。

 

32、维特比算法(Viterbi
algorithm)——寻找隐藏状态最有可能序列的动态规划算法,这种序列被称为维特比路径,其结果是一系列可以观察到的事件,特别是在隐藏的Markov模型中。

 

以上就是Christoph博士对于最重要的算法的调查结果。你们熟悉哪些算法?又有哪些算法是你们经常使用的?

下面是一些比较重要的算法,原文罗列了32个,但我觉得有很多是数论里的,和计算机的不相干,所以没有选取。下面的这些,有的我们经常在用,有的基本不用。有的很常见,有的很偏。不过了解一下也是好事。也欢迎你留下你觉得有意义的算法。A*搜寻算法俗称A星算法。这是一种在图形平面上,有多个节点的路径,求出最低通过成本的算法。常用于游戏中的NPC的移动计算,或线上游戏的BOT的移动计算上。该算法像Dijkstra算法一样,可以找到一条最短路径;也像BFS一样,进行启发式的搜索。BeamSearch束搜索(beamsearch)方法是解决优化问题的一种启发式方法,它是在分枝定界方法基础上发展起来的,它使用启发式方法估计k个最好的路径,仅从这k个路径出发向下搜索,即每一层只有满意的结点会被保留,其它的结点则被永久抛弃,从而比分枝定界法能大大节省运行时间。束搜索于20世纪70年代中期首先被应用于人工智能领域,1976年Lowerre在其称为HARPY的语音识别系统中第一次使用了束搜索方法,他的目标是并行地搜索几个潜在的最优决策路径以减少回溯,并快速地获得一个解。二分取中查找算法一种在有序数组中查找某一特定元素的搜索算法。搜素过程从数组的中间元素开始,如果中间元素正好是要查找的元素,则搜素过程结束;如果某一特定元素大于或者小于中间元素,则在数组大于或小于中间元素的那一半中查找,而且跟开始一样从中间元素开始比较。这种搜索算法每一次比较都使搜索范围缩小一半。Branchandbound分支定界(branchandbound)算法是一种在问题的解空间树上搜索问题的解的方法。但与回溯算法不同,分支定界算法采用广度优先或最小耗费优先的方法搜索解空间树,并且,在分支定界算法中,每一个活结点只有一次机会成为扩展结点。数据压缩数据压缩是通过减少计算机中所存储数据或者通信传播中数据的冗余度,达到增大数据密度,最终使数据的存储空间减少的技术。数据压缩在文件存储和分布式系统领域有着十分广泛的应用。数据压缩也代表着尺寸媒介容量的增大和网络带宽的扩展。Diffie–Hellman密钥协商Diffie–Hellmankeyexchange,简称“D–H”,是一种安全协议。它可以让双方在完全没有对方任何预先信息的条件下通过不安全信道建立起一个密钥。这个密钥可以在后续的通讯中作为对称密钥来加密通讯内容。Dijkstra’s算法迪科斯彻算法是由荷兰计算机科学家艾兹格·迪科斯彻发明的。算法解决的是有向图中单个源点到其他顶点的最短路径问题。举例来说,如果图中的顶点表示城市,而边上的权重表示著城市间开车行经的距离,迪科斯彻算法可以用来找到两个城市之间的最短路径。动态规划动态规划是一种在数学和计算机科学中使用的,用于求解包含重叠子问题的最优化问题的方法。其基本思想是,将原问题分解为相似的子问题,在求解的过程中通过子问题的解求出原问题的解。动态规划的思想是多种算法的基础,被广泛应用于计算机科学和工程领域。比较著名的应用实例有:求解最短路径问题,背包问题,项目管理,网络流优化等。这里也有一篇文章说得比较详细。欧几里得算法在数学中,辗转相除法,又称欧几里得算法,是求最大公约数的算法。辗转相除法首次出现于欧几里得的《几何原本》中,而在中国则可以追溯至东汉出现的《九章算术》。最大期望算法在统计计算中,最大期望算法是在概率模型中寻找参数最大似然估计的算法,其中概率模型依赖于无法观测的隐藏变量。最大期望经常用在机器学习和计算机视觉的数据聚类领域。最大期望算法经过两个步骤交替进行计算,第一步是计算期望,利用对隐藏变量的现有估计值,计算其最大似然估计值;第二步是最大化,最大化在E步上求得的最大似然值来计算参数的值。M步上找到的参数估计值被用于下一个E步计算中,这个过程不断交替进行。快速傅里叶变换(FFT)快速傅里叶变换,是离散傅里叶变换的快速算法,也可用于计算离散傅里叶变换的逆变换。快速傅里叶变换有广泛的应用,如数字信号处理、计算大整数乘法、求解偏微分方程等等。本条目只描述各种快速算法,对于离散傅里叶变换的性质和应用,请参见离散傅里叶变换。哈希函数HashFunction是一种从任何一种数据中创建小的数字“指纹”的方法。该函数将数据打乱混合,重新创建一个叫做散列值的指纹。散列值通常用来代表一个短的随机字母和数字组成的字符串。好的散列函数在输入域中很少出现散列冲突。在散列表和数据处理中,不抑制冲突来区别数据,会使得数据库记录更难找到。堆排序Heapsort是指利用堆积树这种数据结构所设计的一种排序算法。堆积树是一个近似完全二叉树的结构,并同时满足堆积属性:即子结点的键值或索引总是小于它的父结点。归并排序Mergesort是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用。RANSAC算法RANSAC是”RANdomSAmpleConsensus”的缩写。该算法是用于从一组观测数据中估计数学模型参数的迭代方法,由FischlerandBolles在1981提出,它是一种非确定性算法,因为它只能以一定的概率得到合理的结果,随着迭代次数的增加,这种概率是增加的。该算法的基本假设是观测数据集中存在”inliers”和”outliers”,并且这组观测数据受到噪声影响。RANSAC假设给定一组”inliers”数据就能够得到最优的符合这组点的模型。RSA加密演算法这是一个公钥加密算法,也是世界上第一个适合用来做签名的算法。今天的RSA已经专利失效,其被广泛地用于电子商务加密,大家都相信,只要密钥足够长,这个算法就会是安全的并查集Union-find并查集是一种树型的数据结构,用于处理一些不相交集合的合并及查询问题。常常在使用中以森林来表示。Viterbialgorithm寻找最可能的隐藏状态序列(Findingmostprobablesequenceofhiddenstates)
BTY:关于这个世界上的算法,你可以看看Wikipedia的这个网页:_of_algorithms关于排序算法,你可以看看本站的这几篇文章《一个显示排序过程的Python脚本》、《一个排序算法比较的网站》觉得不错,有兴趣的同学随便看看。_1287562702v26b.jpg