20世纪最好的十个算法z

大狗

1.1946.Los Alamos的Von Neumann,Stan Vlam,Nick Metropolis编的 Metropolis算法,即M
onte Carlo方法
2.1947兰德公司的Grorge Dantzig创造的线性规划的单纯性算法
3.1950.美国国家标准局数值分析所的Magnus Hestenes,Edward Stiefel,Cornelius Lancz
os的Krylovz空间迭代法
4.1951 橡树岭国家实验室的Alston Householder矩阵计算的分解方法
5.1951 John Backus在IBM领导的小组研制的Fortron最优编译程序
6.1959-61 伦敦的Ferranti Ltd的J.G.F.Francis的称为QR的算法的计算机本征值的稳定的
方法
7.1962London的Elliot Brothers Ltd的Tony Hoare提出的快速(按大小)分类法
8.1965 IBM的Cooley与Princeton及Bell的Turkey的FFT算法
9.1977 Brighham Young大学的Helaman Ferguson和Rodney Forcede的整数关系侦察算法
10.1987 Yale的Leslie Greengard和Vladinimir Rokhlin发明的快速多级算法

大狗

算法设计策略
这里介绍了一般的算法设计策略，阐述各方法的理论基础、主要思想及其适用范围。同时针对一些具体问题来讲述如何用这些一般的理论以及各种抽象数据类型对问题进行抽象描述，并用最有效的方式设计出解决问题的高效算法。它们将生动地再现计算机程序设计方法学的理论、抽象和设计三个过程，而且，通过对算法正确性的证明和复杂性的分析，深化对大问题的复杂性、概念和形式模型、效率和抽象的层次、折衷和结论等在计算机学科中重复出现的概念的理解。

必须强调指出，对于某些问题(如NP--完全问题)而言，用这里的方法和任何已知的方法都不可能设计出有效的算法。对于这种问题，人们常常考虑利用具体输入的某些特点来设计有效算法或设计求问题近似解的有效算法。这一部分内容我们将在高级专题中讨论。

在对有关算法进行形式描述时我们采用类Pascal的伪代码，并作了一些简化，略去不言而喻的一些说明，如函数、形参、变量等类型说明。

这里主要讨论的算法设计策略有：

递归技术 —— 最常用的算法设计思想，体现于许多优秀算法之中
分治法 —— 分而制之的算法思想，体现了一分为二的哲学思想
模拟法 —— 用计算机模拟实际场景，经常用于与概率有关的问题
贪心算法 —— 采用贪心策略的算法设计
状态空间搜索法 —— 被称为"万能算法"的算法设计策略
随机算法 —— 利用随机选择自适应地决定优先搜索的方向
动态规划 —— 常用的最优化问题解决方法

大狗

数学研究的对象是数量和空间的关系，我觉得数学是一种用来表达人类对自然的认识，
并互相交流这种认识的语言（这是我的看法，当然每个人对数学都有自己的理解）。而
算法，就是一种机械地解决问题的方法，根据算法解决问题时不需要任何智慧(这里可能
用词不当，因为强人工智能学派认为智慧就是一种复杂的算法)，只要照着做就可以了，
所以现在的计算机能够执行算法而且也只能执行算法。发明创造各种算法是为了让我们
研究数学的时候不需要总是依据他的客观物理含义，比如我们做1987+1234567的时候，
通常使用的是按位计算，这是按照一定的规则（算法）一步一步做下去的，而不是考虑
它的物理含义：有1987个苹果，然后又拿来了1234567个，一共是多少个，但是小孩子刚
学加法的时候要扳着手指头计算，从这点还可以看出加法的本来物理意义。
  所以我觉得，数学是上帝创造的，它表现了一种客观实在；而算法是人类创造的，它是
方便人类研究数学这种客观实在的工具。
  算法的发展和形式系统是分不开的，数学发展到20世纪初的时候，数学家开始研究数学
的本质（其实早就开始了，不过20世纪初是鼎盛时期），大家发现，我们的数学体系完
全是基于一种符号的演算体系，所有数学体系都变成了"由几个基本公理奠基，然后规
定几个规则，按照这些规则推导出来所有的定理"这种公理化体系。这就是形式系统。
形式系统中的推导过程就是一个个的算法。比如求积分的方法，开根号的方法，加法，
乘法，...etc。大家就提出疑问，是否存在一种算法，可以证明一个命题是对是错，如
果存在的话，我们只要找到这种算法就一劳永逸了。这个问题是由希尔伯特在1900年巴
黎国际数学家会议上提出的希尔伯特第十问题。但是可惜的是，天才的图灵证明了这种
一劳永逸的算法是不存在的，这说明了算法不是一切，也不能够解决一切！后来大家又
发现很多不可计算问题，这些问题根本不能用算法来解决。比如Pi的小数点后面是否存
在1000个连续的7，要回答这个问题，必须不停地计算Pi,但是Pi是无限不循环小数，如
果算到某一位发现了1000个连续的7，我们可以说命题成立；关键是，如果该命题确实不
成立，我们却无法通过计算证明该命题不成立，还必须永远的算下去！这是一个很奇怪
的现象，如果单纯靠算法，我们居然无法知道某个命题是否成立！后来大家又发现很多
这类不可计算问题，这时候我们才知道，原来算法可以解决的只是自然中极少数的一部
分问题，就像牛顿力学和相对论的关系一样，牛顿力学解决的完全是特殊的现象，算法
解决的也是特殊的一类问题！更槽糕的是，伟大而"可恶"的天才哥德尔出现了，他在
25岁就提出了一个震惊世界的定理：哥德尔不完备性定理。这个定理说明，任何的形式
系统，要么存在着矛盾，要么存在着不可被证明是对还是错的命题，而这种不可证明性
是可以证明的！！这就表明了我们从欧几里德时代开始建立起的公理化数学体系有着先
天的缺陷！这个发现令数学家们想用数学和算法来描述世界的构想化为泡影。所以人类
其实是很可笑的，企图接近上帝，但是上帝创造人类的时候就注定了让人类永远无法认
清这个世界。顺便提一下，本世纪初的另一个伟大的而且是令人类沮丧的发现是物理中
的不确定性，它和哥德尔的不完备性有点类似，说明了我们永远无法真正预测一个粒子
的行为，原来物理学的重要意义之一就是"知道某个物体在某时刻的状态，并且知道他
所受的所有力。根据运动方程，就能预测下个时刻他的位置"，但是不确定性却告诉我
们这是不可能的，物理世界中也存在着人类永远无法认识的东西。数学上和物理上的双
重打击令后来的纯理论科学家们低调了很多，更多的人开始研究具有实用价值的东西，
而很少有人再幻想通过纯理论的研究找到一劳永逸的方法了。

大狗

基本算法

1.数论算法
求两数的最大公约数
function gcd(a,b:integer):integer;
begin
if b=0 then gcd:=a
else gcd:=gcd (b,a mod b);
end ;

求两数的最小公倍数
function lcm(a,b:integer):integer;
begin
if a< b then swap(a,b);
lcm:=a;
while lcm mod b >0 do inc(lcm,a);
end;

素数的求法
A.小范围内判断一个数是否为质数：
function prime (n: integer): Boolean;
var I: integer;
begin
for I:=2 to trunc(sqrt(n)) do
if n mod I=0 then
begin
prime:=false; exit;
end;
prime:=true;
end;

B.判断longint范围内的数是否为素数（包含求50000以内的素数表）：
procedure getprime;
var
i,j:longint;
p:array[1..50000] of boolean;
begin
fillchar(p,sizeof(p),true);
p[1]:=false;
i:=2;
while i< 50000 do
begin
if p then
begin
j:=i*2;
while j< 50000 do
begin
p[j]:=false;
inc(j,i);
end;
end;
inc(i);
end;
l:=0;
for i:=1 to 50000 do
if p then
begin
inc(l);
pr[l]:=i;
end;
end;{getprime}

function prime(x:longint):integer;
var i:integer;
begin
prime:=false;
for i:=1 to l do
if pr >=x then break
else if x mod pr=0 then exit;
prime:=true;
end;{prime}

2．

3．


4.求最小生成树
A.Prim算法：
procedure prim(v0:integer);
var
lowcost,closest:array[1..maxn] of integer;
i,j,k,min:integer;
begin
for i:=1 to n do
begin
lowcost:=cost[v0,i];
closest:=v0;
end;
for i:=1 to n-1 do
begin
{寻找离生成树最近的未加入顶点k}
min:=maxlongint;
for j:=1 to n do
if (lowcost[j]< min) and (lowcost[j]< >0) then
begin
min:=lowcost[j];
k:=j;
end;
lowcost[k]:=0; {将顶点k加入生成树}
{生成树中增加一条新的边k到closest[k]}
{修正各点的lowcost和closest值}
for j:=1 to n do
if cost[k,j]< lwocost[j] then
begin
lowcost[j]:=cost[k,j];
closest[j]:=k;
end;
end;
end;{prim}

B.Kruskal算法：(贪心)
按权值递增顺序删去图中的边，若不形成回路则将此边加入最小生成树。
function find(v:integer):integer; {返回顶点v所在的集合}
var i:integer;
begin
i:=1;
while (i< =n) and (not v in vset) do inc(i);
if i< =n then find:=i
else find:=0;
end;

procedure kruskal;
var
tot,i,j:integer;
begin
for i:=1 to n do vset:=;{初始化定义n个集合，第I个集合包含一个元素I}
p:=n-1; q:=1; tot:=0; {p为尚待加入的边数，q为边集指针}
sort;
{对所有边按权值递增排序，存于e中，e.v1与e.v2为边I所连接的两个顶点的序号，e.len为第I条边的长度}
while p >0 do
begin
i:=find(e[q].v1);j:=find(e[q].v2);
if i< >j then
begin
inc(tot,e[q].len);
vset:=vset+vset[j];vset[j]:=[];
dec(p);
end;
inc(q);
end;
writeln(tot);
end;

大狗

ElGamal算法


作者:fnlq
【声明】

一．本文实用于初学者，目的在于帮助大家熟悉一些系统底层的知识。
二．本文只是为了让广大网友共同提高一些基础知识，本人决无卖弄之意，只供需要这方面知识的读者阅读，如果你是高手，或者不需要这方面知识，请跳过。
三．本文是一篇翻译文章，如有雷同，敬请谅解。
四．本文欢迎传抄转载，但是不要用于任何商业用途。请尊重作者劳动，也欢迎来信交流 fnlq@263.net


=======================================================================

【正文】

ElGamal算法既能用于数据加密也能用于数字签名，其安全性依赖于计算有限域上离散对数这一难题。密钥对产生办法。首先选择一个素数p，两个随机数, g 和x，g, x < p, 计算 y = g^x ( mod p )，则其公钥为 y, g 和p。私钥是x。g和p可由一组用户共享。ElGamal用于数字签名。被签信息为M，首先选择一个随机数k, k与 p - 1互质，计算

a = g^k ( mod p )
再用扩展 Euclidean 算法对下面方程求解b：

M = xa + kb ( mod p - 1 )

签名就是( a, b )。随机数k须丢弃。验证时要验证下式：

y^a * a^b ( mod p ) = g^M ( mod p )

同时一定要检验是否满足1<= a < p。否则签名容易伪造。ElGamal用于加密。被加密信息为M，首先选择一个随机数k，k与 p - 1互质，计算

a = g^k ( mod p )，b = y^k M ( mod p )


( a, b )为密文，是明文的两倍长。解密时计算

M = b / a^x ( mod p )

ElGamal签名的安全性依赖于乘法群(IFp)* 上的离散对数计算。素数p必须足够大，且p-1至少包含一个大素数。因子以抵抗Pohlig & Hellman算法的攻击。M一般都应采用信息的HASH值(如SHA算法)。ElGamal的安全性主要依赖于p和g，若选取不当则签名容易伪造，应保证g对于p-1的大素数因子不可约。D.Bleichenbache“GeneratingElGamal Signatures Without Knowing the Secret Key”中提到了一些攻击方法和对策。ElGamal的一个不足之处是它的密文成倍扩张。

美国的DSS(Digital Signature Standard)的DSA(Digital Signature Algorithm)算法是经ElGamal算法演变而来。