历史上的今天:算法分析之父出生;史上最失败的世纪并购;含冤 50 年的计算机先驱
1938 年 1 月 10 日:算法分析之父 Donald Knuth 出生
高德纳(Donald Knuth)出生于 1938 年 1 月 10 日,他是现代计算机科学先驱,算法大师,1974 年图灵奖得主。高德纳开拓了算法分析领域,为数个理论计算机科学的分支做出了基石性贡献。高德纳属于全才式科学家,在多个领域均有卓越贡献,高德纳所写的《计算机程序设计艺术》(The Art of Computer Programming,通常被称为 TAOCP 系列)是计算机科学界最受高度敬重的参考书籍之一。TAOCP 系列是对经典计算机科学的权威论述,是科学史上最重要的著作之一,与相对论、博弈论、量子力学等比肩。高德纳也是排版软件 TEX 和字体设计系统 Metafont 的发明人。此外,他还曾提出文学编程的概念,并创造了 WEB 与 CWEB 软件,作为文学编程开发工具。高德纳还是个音乐大师,不光自己编曲、设计乐器,还用信息论分析音乐的复杂度。
1918 年 1 月 10 日,俄罗斯计算机科学家 Alexander L’vovich Brudno 出生,他是世界上首个发现并全面描述 Alpha-beta 剪枝算法的人,Alpha-beta 剪枝是一种对抗性搜索算法,通常用以减少极小化极大算法(Minimax 算法)搜索树的节点数。该算法是一种对抗性搜索算法,主要应用于机器游玩的二人游戏(如井字棋、象棋、围棋);当算法评估出某策略的后续走法比之前策略的还差时,就会停止计算该策略的后续发展。该算法和极小化极大算法所得结论相同,但剪去了不影响最终决定的分枝,故得名剪枝。
1952 年,Brudno 为在苏联俄罗斯科学院能源研究所的克日扎诺夫斯基实验室建造的 M-2 计算机开发了“数学/机器接口”。他和挚友 Alexander Kronrod 在 1959 年组织了一个研讨会,专门介绍系统编程、国际象棋编程和人工智能领域的不同作品。在研讨会后,Brudno 关于 Alpha-beta 剪枝算法的研究于 1963 年以俄语和英语出版发表;该算法被用于弗拉基米尔·阿拉萨罗夫(Vladimir Arlazarov)和理论与实验物理研究所的其他人编写的计算机象棋程序。该算法后来在 1974 年被世界计算机国际象棋冠军