ACM通信
部门
数学迷了?
我10岁的时候，我的数学老师成立了一个数学俱乐部。这门课的流行程度不超过几周，但足以让我学习矩阵和行列式。当我回到家时，母亲问我俱乐部过得怎么样。“很漂亮。”我回答。“你是说‘有趣’吗?”她问道。“不，”我说，“美极了!”虽然有些人觉得数学令人困惑，但也有人觉得它优雅而美丽。数学家保罗·厄兹(Paul Erds)经常提到“圣经”(The Book)，上帝在书中保存了每个数学定理的最美丽的证明。哲学家伯特兰·罗素说过:“如果正确地看待数学，它不仅拥有真理，而且拥有至高的美。”美可以是引人注目的; something so beautiful must be true!
但数学之美的诱惑力量最近受到了批评。在迷上数学在今年早些时候出版的一本书中，理论物理学家萨宾·侯赛因菲尔德(Sabine Hossenfelder)断言，数学的优雅使物理学误入歧途。具体来说，她认为物理学的几个分支，包括弦理论和量子引力，在缺乏实验数据来证实或反驳这些理论的情况下，已经开始把数学之美视为真理的标准。她认为，在数学之美的引诱下，理论物理学界正成为群体思维和认知偏见的受害者。大约10年前，在2008年金融危机之后，诺贝尔经济学奖得主保罗·克鲁格曼在一篇题为《经济学家是如何错得这么离谱的?》的文章中，就经济学和数学提出了同样的观点。他的主要回答是:把数学之美误认为真理。“在我看来，”克鲁格曼写道，“经济学专业误入歧途，因为经济学家作为一个群体，把披着令人印象深刻的数学外衣的美误认为真理。”
因此，可以说，物理学和经济学都被数学淹没了。计算机科学怎么样?具体来说，理论计算机科学(TCS)怎么样?TCS无疑拥有数学之美。很久以前，作为一名研究生，正是数学之美吸引了我来到TCS，并继续领导我的研究多年。我发现了计算复杂性理论(或简称复杂性理论)，它有它的定理(例如，时间层次和空间层次定理)和它的开放问题(例如，PvsNP)，才能美丽得令人难以忘怀。美,是的,但真相呢?
物理理论描述了物质世界，通过它们的“真理”，我们指的是它们描述这个世界的忠实程度。经济理论描述了经济体系，但我们所说的“真理”，不仅指它们描述这些体系时的忠实程度，还指它们为商界人士和政策制定者提供的指导质量。我认为复杂性理论与经济学理论在这方面是相似的。它不仅应该为我们研究算法的性能提供一个理论框架，而且还应该为使用算法的算法设计者和系统开发人员提供良好的指导。那么从这个角度来看，复杂性理论有多好呢?
衡量一个特定算法的性能是很清楚的一个在一个特定的问题实例上我。但复杂性理论旨在描述的性能一个在空间上所有问题实例，它通过从单个问题实例中抽象化来做到这一点。我们进行这种抽象的典型方法是通过考虑所有长度的问题实例n，并要求算法性能的上下限(通常与时间和内存利用率有关)作为函数n。这种方法称为最坏的方法，因为它专注于每个长度中最具挑战性的问题实例n。如果我们能证明的上限是一个慢增长函数，例如，Cn log n，取一个小常数c，那么我们就有了良好性能的保证所有问题实例。但是，一般来说，大多数上界和下界都没有那么有用。例如，指数下界只是说明一些问题实例很难，但并没有说明这些实例的实际意义。
在之前的专栏中，我已经讨论了在特定情况下理论和实践之间的差距。正如我所指出的，程序终止可能在理论上是无法解决的，但在实践中是可以解决的，一个而布尔可满足性在理论上可能难以解决，但在实践中是可以处理的。b在这两种情况下，最坏情况的方法都太悲观了，而且告诉我们的算法在实践中的性能太少。美并不一定意味着真理。超越最坏情况复杂性是复杂性理论的一个关键挑战，也是当前许多研究的主题。(见Tim Roughgarden的评论文章第88页)。
脚注
一个。//www.eqigeno.com/magazines/2011/7/109895-solving-the-unsolvable/fulltext
b。//www.eqigeno.com/magazines/2014/3/172516-boolean-satisfiability/fulltext
数字图书馆是由计算机协会出版的。版权所有©2019 ACM, Inc.
评论
蒂莫西·戴维斯
代码之美是否与数学之美不同?
数学上$x=A^{-1}b$很漂亮，但它是求解线性系统的糟糕方法。在大多数情况下，它在密集情况下是不准确的，在稀疏情况下是O(n^3)时间，而一个好的稀疏求解器可以在相同的矩阵上花费O(n)时间。所以我会说，虽然在MATLAB中x=inv(A)*b看起来很漂亮，但实际上它真的很丑。真正漂亮的是MATLAB表达式x=A\b。
我把这种情况称为“MATLAB inv滥用”，尽管MATLAB代码分析器警告过这种情况，但这种情况却非常普遍。根据我的统计，MATLAB Central中6%的用户使用inv(A)，几乎所有的用户都是“inv滥用”，我敢冒险猜测，这些代码的作者被美丽的数学语句$x=A^{-1}b$所误导，写出了丑陋的“x=inv(A)*b”。
然而代码中的美是很重要的。我会说，当代码写得很好，文档记录得很好，当逻辑清晰，当代码没有bug，当软件所体现的算法既优雅又“快速”(在理论上或实际问题上的实践中，或者理想情况下两者都是)，那么计算机科学家就会说它真的很漂亮。
这是漂亮代码的一个好的工作定义吗?这是一个开放的问题;我可能错过了一些重要的东西。
数学是美丽的，如果它是优雅的和表达的(在证明)。如果一个猜想a的证明需要一个强大的定理B，这个定理B有一个长而难读的证明，那也没关系。事实上，这可以使A的证明更加简洁。
但这不适用于代码。x=inv(A)*b调用强大的大锤inv(…)，当A是稀疏的时候，这是非常可怕的。
当代码不仅看起来漂亮(容易写，容易读，像乐高玩具一样容易玩)，而且行为也很漂亮时，它是美丽的吗?
贡纳狼
这是我经常在课堂上和我的学生讨论的话题，我们所追求的“美”的数量决定了我们学习计算的哪个分支。我在墨西哥最大的大学UNAM的工程学院教授操作系统(本科)，在介绍了死锁预防、规避和检测/恢复的策略后，我提出了这一点:
如果我作为一个数学家，作为一个强硬的计算机科学家来看待这个话题，死锁的存在本身就是一个丑陋的错误，所以我必须解决它!如果存在已知的解决方案(并且存在有待改进的地方)，那么我的职业职责就是致力于解决这些问题。
但工程是理想科学与现实世界相遇的地方。理想的科学自然是美丽的。工程是混乱和油腻的。我们必须平衡解决方案的可行性与现实世界的成本，权衡错误的概率，根据大多数计算机(并非所有人都会设计需要遵循硬实时保证或类似内容的系统)的实际情况调整我们的观察结果。
有几个讨论点，我们可以为理想，为美好争论，或者我们可以动手去处理现实世界。这塑造了我们对世界的看法和看法。是的，我们都知道最流行的死锁解决方案(通常被称为“鸵鸟算法”)是一个明显的信号，在我们的领域，美并不总是赢家。
显示所有2评论