《程序员》杂志的一位作者
本刊记者：什么是最早的算法？
高德纳：我想，第一个“真正的”算法可以追溯到大约4000年前，它们以楔型文字记载在粘土板上。我在文章“史前巴比伦算法”中对此有过讨论（我将其翻译为现代注记方式），这篇文章也重印为我的书《计算机科学论文精选》的第十一章。
当然，这些早期的算法并不是很精巧。它们解释了如何以计算的方式解决这些问题，但后来发现使用代数方法能更好地解决它们。最早的“有意义的”算法,它对于今天的程序员们仍然很重要,是最大公约数的求解。其中一个算法被称为欧几里德算法，它被记载于欧几里德几何原本上,尽管它来自于欧多克索斯和其它一些更早期的人物。这种算法基于辗转相除法。另一个算法仅需要除以二，因此非常适合当前的二进制计算机。这个算法可能发源于2000年前的中国——这要取决于我们如何理解经典的《九章算术》中一些句子的隐藏的含义（我在我的书《半数值算法》的340到341页和中文版的309页讨论了这个问题）。
本刊记者：奥运会今年夏天在中国举行，这是对于中国来说是一件很重要的事情，因为它有一些特殊的含义，也许是一个符号，表示中国人能像接受希腊火炬一样接受西方文化。希腊先哲毕达哥拉斯说过“我喜欢作为奥运会的观众胜过成为一个运动员或商人”。现在很多中国人也成为了奥运会观众，我来问个问题：为什么希腊人发现的数学对于人类文明（包括计算机科学）如此重要？
高德纳： 希腊数学家发明的最伟大的东西是严格证明的概念。这个概念将数学与其它知识区别开来，其它知识往往是基于事实的累计、由老师传授给学生的并由社会共识所评 估（举个例子，物理中，并不知道一个假设的真假，而只能等着所谓专家们的想法越来越趋于统一。但是在数学中，很多事情都是无可辩驳的，或者说不存在不同的 观点），纵观人类历史，那些没有遵从希腊方式理解数学的文明把数学认为是应该记忆的规则而不是可以由逻辑推演而来的事实。在这些文明（例如古代中国、日 本、印度和哥伦布发现之前的美洲等）中，人们发现了很多重要的数学原理但是也犯了很多错误，因为学生否决老师是不明智的！这也是为什么我如此感激史前的希 腊数学家教会其他人如何真正的证明问题。
另一方面，我希望澄清一点，我相信所有文明之间都是相互学习的。我为计算机科学这个全世界成千上万的人的共同成果而庆祝，每个人都为此贡献了他们从经验中而来的重要观点。
本刊记者：如何看待数学和计算机科学之间的关系，特别是数学和算法学习之间的关系？
高德纳：你可以参照我对第二个问题的回答，我认为数学对于程序员最重要的意义在于它告诉我们如何证明我们的程序将会在所有情况下正常工作。若非如此，我们就得为此担心，尽管我们的程序通过了已有的所有测试，但或许明天它在处理另外一些新数据时就会出错。
当然，仅仅知道程序能正常工作这一点并不够。有了数学，我们可以证明一个程序比另一个程序快成千上万倍。某些时候，我们甚至能证明程序是“最好的”（best possible）——根据某些标准，没有其它程序会比它好。
本刊记者：这个问题是关于您的书《计算机编程艺术（The Art of Computer Programming）》，写这本书的主要目的是什么呢？您是否试图构建一个算法体系？您是如何选择主题呢？
高德纳：我写《计算机编程艺术》的主要目地是组织和理解一些广泛被各种程序使用的最基础的想法。只要可能，我使用数学给出对于每种基础的方法的对于精 确效率的计量的理解。此外，我尽量叙述每一种方法的历史，因为理解这些方法是如何被发现的有助于我们在现时和今后发明新的方法。
但是，书的主题是1962年 选定的，这时计算机科学还没发展到一个作者无法掌握的规模。因此，没有像操作系统、并行处理、分布式处理之类的资料。此外，我更多地使用整数而不是浮点 数。我把高级数学主题，例如数值分析、计算几何留给别人讨论。我关注的是程序员与机器间的低层次接口，为支持高级应用程序而用于构建库和工具的基础的子程 序。然而，尽管将主题列表做了如此多限制，我这个关于计算科学的一小部分仍旧是一个如此巨大的主题，我需要为剩下的内容工作20年！所以，我希望一直保持健康。
本刊记者：我的很多朋友都尝试过阅读《计算机编程艺术》，但是他们发现这非常困难。我听说一个小说家——詹姆斯乔伊斯（James Joyce），《尤利西斯》（Ulysses）的作者——有人为他的小说写了本书，名字叫《乔伊斯小说指导》，我不知道有没有针对《计算机编程艺术》的类似书籍，比如 《计算机编程导论阅读指导》。您能给《计算机编程艺术》的读者一些建议吗？
高德纳：《计算机编程艺术》不是为所有人写的。大约每50个人中就有一个能发展出独特的看问题的方式，这使他们成为真正的程序员。像你我这样的人，倾向于将知识用特殊的形式在脑中组织以便于更好地利用电脑。每50人中的另外49人不该从事编程这一行，尽管他们可以使用计算机完成一些不需要编程的任务。
对程序员来说，拥有非程序员的朋友是非常重要的，所以对于你所说的你有朋友阅读《计算机编程艺术》非常困难，我并不觉得奇怪。当然，你的朋友也许不应该阅读你看过的所有书籍，你也不应期待能轻易看懂他们的书籍！最好的方法是团队合作，用天分和技巧作为补充。
本刊记者：您认为对最近一些年来说，计算机科学最需要解决的问题是什么?
高德纳：我在所有地方都看到很大的发展的潜能。所以，从这些同样精彩的候选者中我无法选择。机器人、加密、制图（mapping）、动态规划、大量文本或大量DNA序列的搜索等等，都亟待提高。
总 的来说，我认为我期待的主要进步来自于程序员和非程序员的合作。比如，人类能更好地理解动作。我相信很多针对医生、化学家、物理学家、生物学家等的将数据 以动画形式表现出来的工具应该被开发出来。要实现它们，需要优秀的程序员实现动画，与能够理解人类视觉能力的优秀的图形设计师一起工作，与知道哪些数据需 要被理解的优秀的医生、化学家、物理学家和生物学家一起工作。
本刊记者：我听说狄克斯特拉（Edsger W. Dijkstra）曾经试图解决这样的问题：什么是正确的程序？所谓的形式证明？现在在软件工业中，我们主要依靠测试而编写正确的程序。有没有可能在理论上找到一种方法让我们知道程序是否正确，尤其是对大规模的程序？
高德纳：在我回答第二个问题的时候，我提到使用数学去证明（不是重复地测试直到你找不到错误）的重要性。狄克斯特拉和其他人都发展了验证正确性方法，这些方法可以放大,以验证“大”程序。但是，如你指出的，软件工业界并没有真正遵从他们的建议。部分的问题在于——“大”的含义一直在变：当我们有一个可以工作的大程序，人们常常就想写一个更大的，这也就更加难以验证。验证技术从没有跟上人们对于代码体积越来越大的胃口。
我将会试着同时从理论和实践上解释我的态度。拿我的程序TeX做例子，它按照今天的标准来说并不“大”，它只有500页的代码。我并没有完成对于TeX完全的形式化的正确性证明，尽管我非常喜欢数学证明。但是，我已经非常熟悉验证的基础，我知道如何非形式化地使用它们——大体上我知道如何证明正确性，如果我有时间去研究每一个琐碎的细节（grind through the gory details）。
没有这些基础知识，我的程序可能会经常崩溃，像你我知道的一些商业软件一样。有了这些知识，我就能写出非常稳定和好用程序，但也仅是在我测试了它之后！
让我从另一个不同角度再说一遍：没有理论，我不知道程序可被证明的正确是什么意思，我挣扎前进（flounder）。但是尽管有了理论，我也不能确定我的程序是好的，除非我进行了广泛的测试！
为什么？因为在现实中，没有程序能被真正被证明是正确的：假定的“证明”可能包含错误。如果某人给我看一个经过形式化证明的程序，我不得不检查一下验证过程有没有错误。验证过程也许由机器完成，但是机器逻辑也许是错误的，如此这般。这是一个永无终点的循环。
数学展示给我们理想，我们可以检查证明，直到我们认为它们是合理的。但是只有不会犯错的超人能真正得出证明是正确的结论。
进一步来说，证明程序是否满足它的规格说明（specification）的想法也是值得怀疑的，因为规格说明本身可能是不正确的。实际上TeX并没有精确的规格说明，如果有，我也认为它完全没有用处！（不是每个人同意我这个观点，但他们应该设计并实现一个完美排版软件，在我已完成了TeX这个排版软件的时候。）
总之，我认为将“形式证明”和“测试”分裂开来是危险的。最好的做法是正确地同时使用两种方法。我在我的著作《Literal Programming》的第十章和第十一章详细地讨论了TeX的调试（在《Digital Typography》的第三十四章中讨论了后续开发）。
本刊记者：我们的杂志名字叫《程序员》，所以我的最后一个问题是：什么是程序员，您如何看待程序员？
高德纳：程序员选取一个抽象的算法，并将其转化为以某种定义良好的语言写成的程序中的具体形式，程序才可以被机器执行。
“算法”之于“程序”就类似于“信息”之于“数据”： 信息是理想化的抽象的概念，它或多或少可以由某种精确的方法将其编码为数据，以完美地表达。一个算法是一种理想化的可计算的为某些任务服务的过程，它或多 或少可以由某种精确的方法将其编码为程序，以完美地表达。但是程序员事实上不仅仅是写程序的人。真正的任务是编写可以被人们阅读的程序，而不仅仅是编写可 以被机器分析的程序，因为人们会需要验证它（非形式化的）、修改它和维护它。这就是为什么我坚信“作文式程序设计（literate programming）”——像文学创作那样写程序，写出自己的风格，为他人所欣赏。
原文：http://blog.csdn.net/programmer_editor/archive/2008/12/11/3501111.aspx