计算机科学中最重要的32个算法.doc

计算机科学中最重要的32个算法.doc计算机科学中最重要的32个算法
奥地利符号计算研究所(Research Institute for Symbolic Computation,
简称RISC)做了一个调查，投票选出32个最重要的算法：
A*搜索算法——图形搜索算法，从给定起点到给定终点计算出路
径。其中使用了一种启发式的估算，为每个节点估算通过该节点的最佳路 径，并以之为各个地点排定次序。算法以得到的次序访问这些节点。因此, A*搜索算法是最佳优先搜索的范例。
集束搜索(又名定向搜索，Beam Search) 最佳优先搜索算法
的优化。使用启发式函数评估它检查的每个节点的能力。不过，集束搜索 只能在每个深度中发现最前面的m个最符合条件的节点，m是固定数字一 —集束的宽度。
二分查找(Binary Search) 一 线性数组中找特定值的算法，每 个步骤去掉一半不符合要求的数据。
分支界定算法(Branch and Bound) 在多种最优化问题中寻找
特定最优化解决方案的算法，特别是针对离散、组合的最优化。
Buchberger算法 一种数学算法，可将其视为针对单变量最大公
约数求解的欧几里得算法和线性系统中高斯消元法的泛化。
数据压缩一采取特定编码方案，使用更少的字节数(或是其他信
息承载单元)对信息编码的过程，又叫来源编码。
Diffie-Hellman密钥交换算法——一种加密协议，允许双方在事先不 了解对方的情况下，在不安全的通信信道中，共同建立共享密钥。该密钥 以后可与一个对称密码一起，加密后续通讯。
Dijkstra算法 t对没有负值权重边的有向图，计算其中的单一起
点最短算法。
离散微分算法(Discrete differentiation)
动态规划算法(Dynamic Programming) 展示互相覆盖的子问
题和最优子架构算法
欧几里得算法(Euclidean algorithm) 计算两个整数的最大公
约数。最古老的算法之一，出现在公元前300前欧几里得的《几何原本》。
期望-最大算法(Expectation-maximization algorithm,又名 EM-Tr
aining)——在统计计算中，期望-最大算法在概率模型中寻找可能性最大 的参数估算值，其中模型依赖于未发现的潜在变量。EM在两个步骤中交 替计算，第一步是计算期望，利用对隐藏变量的现有估计值，计算其最大 可能估计值；第二步是最大化，最大化在第一步上求得的最大可能值来计 算参数的值。
快速傅里叶变换(Fast Fourier transform, FFT) 计算离散的傅
里叶变换(DFT)及其反转。该算法应用范围很广，从数字信号处理到解 决偏微分方程，到快速计算大整数乘积。
梯度下降(Gradient descent) 一种数学上的最优化算法。
哈希算法(Hashing)
堆排序(2即$)
Karatsuba乘法——要完成上千位整数的乘法的系统中使用，比如 计算机代数系统和大数程序库，如果使用长乘法，速度太慢。该算法发现 于1962年。
LLL算法(Lenstra-Lenstra-Lovasz lattice reduction) 以格规约
(lattice)基数为输入，输出短正交向量基数。LLL算法在以下公共密钥加
密