二十世纪十大算法(运筹学)(2).pdf资源-CSDN文库

版权申诉

189 浏览量 2023-03-06 20:28:51 上传评论收藏 358KB PDF 举报

资源推荐

资源详情

资源评论

二十世纪十大算法

摘要:二十世纪十大算法。下面的内容是对“二十世纪十大算法”的罗列和简

要的描述，这些算法是由《计算机科学与工程》 (简称 CISE) 杂志的编辑选出来

的，这是他们 2000 年一月至二月刊的主要话题。这十大算法是 20 世纪在科学与

工程的发展和实践方面最有影响力的算法，并且应该是 20 世纪数值数学和计算

科学发展的一个摘要。对于这样的一种选择，我们可以持赞同或者反对的态度，

但至少不应该低估它们，因为它们是发达国家具备很高素质的计算机科学家们的

观点。编辑们向该杂志的读者们征询他们对于这个选择的看法和感受。在随后的

几期 CISE 中得到的反馈结果是，关于这个选择只有赞成而没有分歧。因此可以

得出结论，CISE 作出的选择很好并且得到了国际科学界的认可。

整数关系探测法（简称 IRD）

多年来，研究人员都梦想着能有这样一种设备，这种设备可以让他们识别满

足数学公式的数值常量。随着高效的 IRD 算法的出现，这一时代到来了。令为

x  (

x

1

,

x

2

,...,

x

n

)

一个实数或者复数向量。如果存在不为零的整数

i

，x 就拥

a

有这样一个整数关系，使得

a

1

x

1



a

2

x

2

...

a

n

x

n

 0

。一个整

数关系算法是一种实用的计算方案，它可以恢复整数向量（若存在），或者可以

a

i

产生不存在整数关系的范围。这些都是计算数论的行为。对 IRD 而言，最有效

的算法是 Ferguson 最近发现的 PSLQ 算法。作为一个例子，下面是 PSLQ 1997

发现的一个公式，使我们能够计算



的第 n 位 16 进制数。







k  0



1



4 2 1 1



  

k

 

16



8k  1 8k  4 8k  5 8k  6



另一个例子是定义一个常数

B

3

 3.54409035955...

，它是数理逻辑图

x

i 1



rx

i



1x

i



里的第三个分叉点，这表现出了在混沌出现之前周期缩短了一

倍。为了保证精确，B

3

是参数 r 的最小取值，这样逐次迭代

x

就具有 8 个周期

i

而不是 4 个周期。可以类似地来定义常数 B

2

和 B

1

。使用了 PSLQ 前身算法的计

算发现 B

3

是如下方程的根

t



12 t



48 t



40 t



193 t



392 t



44 t



8t



977 t



604 t



2108 t



4913  0

6 5 4 3 2

12 11 10 9 8 7

使用了 IRD 后，研究人员在数学和物理方面有了许多新的发现，而这些发现又

相应的产生了有价值的新见解。这个过程常常被称为“实验数学”，即利用现代

计算机发现新的数学原理，我们期望它在 21 世纪的纯数学和应用数学里扮演一

本内容试读结束，登录后可阅读更多

下载后可阅读完整内容，剩余5页未读，立即下载

内容反馈

版权申诉

春哥111

粉丝: 1w+
资源: 6万+

最新资源

资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！点击此处反馈

feedback-tip