计算机科学中32个常用的基础算法

奥地利符号计算研究所(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博士对于最重要的算法的调查结果,这些算法有着广泛的应用,虽然说是计算机算法,其实其中不少条目都是一门数学课程,或者某课程中的重要章节,广泛地涉及基础数学、计算数学等课程,比如数值计算,信息论,矩阵论等。

(0)

相关推荐

  • 计算机科学中32个常用的基础算法

    奥地利符号计算研究所(Research Institute for Symbolic Computation,简称RISC)的Christoph Koutschan博士在自己的页面上发布了一篇文章,提到他做的一个调查,参与者大多数是计算机科学家,他请这些科学家投票选出最重要的算法,以下是这次调查的结果,按照英文名称字母顺序排序: 1.A* 搜索算法--图形搜索算法,从给定起点到给定终点计算出路径.其中使用了一种启发式的估算,为每个节点估算通过该节点的最佳路径,并以之为各个地点排定次序.算法以得到

  • javascript中数组的常用算法深入分析

    前言 Array是Javascript构成的一个重要的部分,它可以用来存储字符串.对象.函数.Number,它是非常强大的.因此深入了解Array是前端必修的功课.本文将给大家详细介绍了javascript中数组的常用算法,下面话不多说了,来一起看看详细的介绍吧 一.不改变原数组,返回新数组(字符串) 1.concat()   连接两个或者多个数组,两边的原始数组都不会变化,返回的是被连接数组的一个副本. 2.join()  把数组中所有的元素放入到一个字符串中,返回字符串 var a = [1

  • C++ STL中五个常用算法使用教程及实例讲解

    目录 前言 sort()排序 常用遍历算法for_each() 常用遍历算法 搬运transform() 查找算法find 删除操作erase() 实例应用 前言 在C++中使用STL算法都要包含一个算法头文件 #include<algorithm> 这样我们才能使用这个STL算法函数 sort()排序 Sort函数包含在头文件为#include<algorithm>的c++标准库中,是一个专门用来排序的高效的函数,我们在解决问题时可以方便快捷的排列顺序. sort()函数中有三个

  • C++中STL的常用算法总结

    目录 1.常用遍历算法 1.1 for_each 1.2 transform 2.常用查找算法 2.1 find 2.2 find_if 2.3 adjacent_find 2.4 binary_search 2.5 count 2.6 count_if 3.常用排序算法 3.1 sort 3.2 random_shuffe 3.3 merge 3.4 reverse 4.常用拷贝和替换算法 4.1 copy 4.2 replace 4.3 replace_if 4.4 swap 5.常用算术生

  • php四种基础算法代码实例

    php四种基础算法:冒泡,选择,插入和快速排序法许多人都说 算法是程序的核心,一个程序的好于差,关键是这个程序算法的优劣.作为一个初级phper,虽然很少接触到算法方面的东西 .但是对于冒泡排序,插入排序,选择排序,快速排序四种基本算法,我想还是要掌握的.下面是我按自己的理解,将四个方法分析一遍.需求:分别用 冒泡排序法,快速排序法,选择排序法,插入排序法将下面数组中 的值按照从小到的顺序进行排序. $arr(1,43,54,62,21,66,32,78,36,76,39); 1. 冒泡排序法

  • C#中的那些常用加密算法

    前言 本文主要讲解一下C#常用的那些加密算法. 本文源码 本文所用源码均以为大家整理完毕,大家使用以下方式获取 需要的小伙伴,请关注微信公众号: 程序员零距离, 或者扫描下方公众号二维码,回复关键字:加密算法 , 即可获取本文所用的所有源码资源. 关注上方公众号,回复 加密算法获取 MD5加密 MD5加密是最常见的加密方式,因为MD5是不可逆的,所以很多系统的密码都是用MD5加密保存的. 虽然MD5是不可以解码的,但因为MD5加密的字符串是固定的,所以,理论上只需要建立一个庞大的数据库,把所有的

  • Python机器学习之Kmeans基础算法

    一.K-means基础算法简介 k-means算法是一种聚类算法,所谓聚类,即根据相似性原则,将具有较高相似度的数据对象划分至同一类簇,将具有较高相异度的数据对象划分至不同类簇.聚类与分类最大的区别在于,聚类过程为无监督过程,即待处理数据对象没有任何先验知识,而分类过程为有监督过程,即存在有先验知识的训练数据集. 二.算法过程 K-means中心思想:事先确定常数K,常数K意味着最终的聚类(或者叫簇)类别数,首先随机选定初始点为质心,并通过计算每一个样本与质心之间的相似度(这里为欧式距离),将样

  • java中几种常见的排序算法总结

    目录 本节目标: [插入排序] [优化版] [希尔排序] [选择排序] [堆排序]  [冒泡排序] 介绍一个冒泡排序的优化方法:  [快速排序] [归并排序] [正文] [代码简介:]  [排序总结] 本节目标: :分析常见的比较排序算法基本原理及实现 :分析排序算法的性能分析 :分析Java中常用排序方法 1 排序 排序,就是使一串记录,按照其中某个或某些关键字的大小,递增或递减排列的操作. 平时的上下文中,提到排序 通常指排升序. 2 稳定性 两个相同的数据,如果经过排序后,排序算法能保证其

  • golang常用加密解密算法总结(AES、DES、RSA、Sha1、MD5)

    目录 关于加密解密 AES DES RSA MD5 Sha1 Base64 在项目开发过程中,当操作一些用户的隐私信息,诸如密码.帐户密钥等数据时,往往需要加密后可以在网上传输.这时,需要一些高效地.简单易用的加密算法加密数据,然后把加密后的数据存入数据库或进行其他操作:当需要读取数据时,把加密后的数据取出来,再通过算法解密. 关于加密解密 当前我们项目中常用的加解密的方式无非三种. 对称加密, 加解密都使用的是同一个密钥, 其中的代表就是AES.DES 非对加解密, 加解密使用不同的密钥, 其

  • Java实现八个常用的排序算法:插入排序、冒泡排序、选择排序、希尔排序等

    本文实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 .快速排序.归并排序.堆排序和LST基数排序 首先是EightAlgorithms.java文件,代码如下: import java.util.Arrays; /* * 实现了八个常用的排序算法:插入排序.冒泡排序.选择排序.希尔排序 * 以及快速排序.归并排序.堆排序和LST基数排序 * @author gkh178 */ public class EightAlgorithms { //插入排序:时间复杂度o(n^2) p

随机推荐