|
|---|
|
|
|
|
|
|
a********e
发帖数: 16 | 1 四.艾兹赫尔·W·戴克斯彻（Edsger W. Dijkstra）。
1)理论物理学家转入计算机编程。
2)1956年左右，思考出最短路径算法，修改后为最短子分支树算法，发表于《数字数学
》。当时数学界几乎全在研究连续统和无穷大问题，无人关注。
3)针对资源共用问题，提出“互斥”方法，基于铁路信号系统的P（荷兰语“通过”）
、V（荷兰语“释放”）操作。
4)“哲学家的晚餐”，体现死锁问题。之后几年最成熟计算机系统MULTIX却并没有考虑
死锁问题。
5)前往美国布劳斯公司，推行编程的可验证性，提出“GOTO语句是有害的”，却阻碍了
一些程序员所喜欢的程序不确定性。
6)《程序与证明的形式开发》，拉近数学与计算机科学的距离。
7)对人工智能说不。
五.迈克尔·O·拉宾（Michael Oser Rabin）。
1)德国犹太人拉比家族（观察思考产生智慧的阶层）。
2)能够猜想的计算机：考虑有限状态机，证明非确定性有限状态机与确定性有限状态机
之间的转换关系。
2+)图灵于1935年定义“计算”的逻辑基础，设计图灵机。借助哥德尔不可判定原理，
设计停机问题，挑战希尔伯特判定性问题。
3)对计算固有难度的研究，证明匹斯伯格算术系统（只包含自然数和加运算的数学系统
中，对状态真伪判断是可用图灵机计算的）的固有难度。
4)考虑黎曼猜想，将所有与某数字不互素的数均作为其“见证者”，可证明对于合数n
来说，从1到n之间至少有3/4数字为“见证者”，可“见证”n是合数。为验证大整数是
否为素数提供了高性能、不确定的方法。
5)随机化方法，广泛应用于密码学。
六.高德纳（Donald Ervin Knuth）。
1)数学专业。1956年接触计算机IBM 650。
2)1962年，为Addison-Wesley出版社编写关于编译器的书稿，到1966年写了3000页草稿
，定下7卷丛书《计算机程序设计艺术》的计划。
3)编译器研究中，发明LR(k)分析法。将属性规则与文法规则结合，形成语法树。
4)精确分析算法复杂度。
5)KMP（Knuth-Morris-Pratt）字符串查找算法。
6)排版工具TEX，字体工具METAFONT。
7)“我学编程的时候，一天能摸5分钟计算机就不错了。想让程序跑起来，就必须写得
没有错误。所以编程就像在石头上雕刻一样，必须小心翼翼。我就是这样学编程的。”
七.罗伯特·E·陶尔扬（Robert Endre Tarjan）。
1)平面图判别问题，1930年库拉托夫斯基的算法为O(N6)，陶尔扬采用深度优先搜索发
现线性算法。
2)并查集，时间复杂度为反阿克曼函数。
3)最大网络流，发明动态树、伸展树。
4)证明“最近使用LRU”算法较优。
5)持久性数据结构。
八.莱斯利·兰伯特（Leslie Lamport）。
1)1972年，在麻省计算机协会（COMPASS）为ILLLIAC IV计算机编写Fortran编译器，计
算机拥有64个处理器。
2)面包店算法：戴克斯彻解决互斥问题的讨论，戴克斯彻改进和高德纳改进都假设计算
机存储器读写为“原子级的”， 兰伯特提出面包店算法，无需信号灯、原子性寄存器
等。
3)兰伯特时钟，基于狭义相对论灵感，确定分布式系统时间关系。
4)拜占庭将军问题。斯坦福国际研究所“软件实施的容错多处理器”项目。引入数字签
名。
5)软件形式化验证。层级结构证明。
6)发明LATEX，“La”代表法语“the”、姓氏“Lamport”，Latex又有“乳胶”意思。
九.史提芬·古克（Stephen Arthur Cook）和利奥尼德·列文（Leonid Anatolievich
Levin）。
1)巡回推销员问题。“难解易验”——NP完全问题，1971年。
2)古克：于哈佛师从自动定理证明研究的王浩（曾师从逻辑学家金岳霖），研究命题演
算可满足性。
2.1)1971年在ACM研讨会上发表论文《定理证明过程的复杂性》，定义非确定性多项式
（Nondeterministic polynomial）问题，即NP问题，猜测部分是非确定的，检验部分
是多项式的。可满足性问题是NP中最难问题，即NP完全问题。
2.2)理查德·卡普证明另外21个问题也是NP完全问题，“可约简性”——它们同样难度。
2.3)90年代末，伦纳德·阿德曼用DNA链算法解决巡回推销员问题，但耗费分子数同样
很大。
3)列文：因物理奥赛而进入基辅大学物理数学寄宿学校，接触到科尔莫戈罗夫，之后成
为列氏门生，但最终因为政治原因无法获得博士学位而移民。
3.1)在20世纪50年代末到60年代初，苏联举国上下都对科学抱有极大的热忱。奥林匹克
竞赛非常热门，全国绝大多数青少年都会参加。如果你获胜，同时又不是犹太人，那么
还有机会参加国际奥林匹克竞赛。
3.2)科尔莫戈罗夫对小列文提出的问题：将所有字母序列分为合理、不合理，那么对于
任意无限长字母序列是否都可以拆分成有限长的序列，使所有序列属于同一类别（第一
个序列可除外）？
3.3)20世纪50年代初的苏联，禁止讨论计算机科学，可能因为维纳的控制论。到了60年
代开始全面推广计算机科学。
3.4)研究科尔莫戈罗夫复杂性。发现编写能简单、快速生成给定字符串的程序固有难度
与其他问题是同等难度。
4)列夫参与合作开发了“透明”证明理论，该证明方法如存在某问题，则对证明的任一
小部分进行数学检验，都能以同样概率发现该错误。
5)NP是否=P？ |
|
|
|
|
|
|
