algorithm - 当谈到证明时，你如何“得到它”？

Question

当我们开始进入算法设计和更多离散的计算机科学主题时，我们最终不得不一直证明事情。每次我看到有人问如何真正擅长证明时，常见的（可能是懒惰的）答案是“练习”。

如果您掌握了基础知识，练习一切都很好，但是您如何进入数学证明的思维定势？感应何时点击？哪些资源最适合教授这些主题？在沉迷于证明写作之前应该研究哪些基础主题？

score 9 · Accepted Answer

他们不是懒惰，实践是唯一的方法。参加你必须做证明的课程，并在网上查找课堂笔记和旧测试以及其他大学的答案，这些答案经过证明。

score 8 · Accepted Answer

我首先要承认，作为一名 CS 学生，我很难掌握一种正式的思维方式，而且这绝非易事，除非你有这方面的天赋。

恐怕没有比实践和学习更好的答案了。

一种正式的数学和算法思维和视觉问题的方式是一种技能，首先需要对你正在处理的主题有非常深刻的理解。其次，它要求您对现有证明有很好的了解。试着把自己想象成一些伟大的科学家，他们提出了你正在研究的算法。了解您将如何尝试解决该特定问题。然后看看他们如何证明他们的算法的正确性。

我只能推荐这门学科中最好的教科书，即CLRS 的 Intro to Algorithms。如果你从头到尾经历它，包括每一个练习，你将提高你的技能。

score 6 · Accepted Answer

实践确实是唯一的方法，但它也可以通过阅读证明来帮助。我不会涉及实践，因为其他回答者已经涵盖了我能想到的所有内容，所以我将仅谈谈我所说的阅读的意思。

教科书非常喜欢写出“重要”的证明。它非常好，因为它们经常证明非常强大的陈述，并且真的很花哨。但正如你不应该从第一天起就通过模仿奥运选手来学习成为世界级的体操运动员（比如，你可能会折断你的脊椎），你也不应该阅读任何真正大的证明（一开始）。我发现阅读较小的校样很有帮助，通常来自返还的家庭作业（我假设你是学生），或者偶尔从一本可以提高智慧的教科书上阅读。

我认为阅读校样有帮助的原因是因为有一小部分“技巧”或“想法”构成了巨大的功课校样，甚至是更高级的。数据结构质量和递归关系通常涉及与归纳证明相关的思考，涉及有限状态机可计算性的证明有时使用鸽笼原理，很少使用对角化的想法（很少见，不用担心）。当然，几乎所有其他证明都使用反证法。我敢肯定还有其他方便的工具让我忘记了，但我希望你能明白。

弄清楚何时、如何以及为什么用一种或另一种特定方法解决问题需要实践和经验。我建议在练习之外阅读证明，因为它通常可以向您展示使用您已经遇到的证明方法的创造性方法。

最后一点，试着记住你第一次学习编程的时间。你是怎么变得更好的？在我看来，证明事物和编程事物并没有太大的不同。:)

score 3 · Accepted Answer

通过成为一名数学家，你进入了做数学证明的思维定势。我并不是说最后一个陈述以重言式的方式，而是要意识到，发表在数学杂志上的数学证明是某种修辞的产物。即，它是一个证明，因为一群数学家同意它是一个证明。理想情况下，证明中的论点都可以简化为符号逻辑，但在实践中并非如此。计算机生成的证明完全无法进行有价值的数学运算为此提供了一些证据。

我通过做证明并让其他数学家接受它们来进入思维定势。我同意其他人的观点，即“实践”是必不可少的。除非您尝试，尝试和尝试，否则您不会做证明。通常，曙光慢慢地破晓。

最好的资源当然是其他数学家和阅读证明。很少有（如果有的话）能够在不加入数学社区的情况下进行真正的数学证明。

score 2 · Accepted Answer

恐怕“实践”真的是这里最好的答案。

它与编程非常相似：一旦你掌握了窍门，你就会发现能够很好地解决问题的模式，并且你可以创建一个你以前从未实现过的新颖系统的高级设计图。然而，新手程序员并没有意识到模式：他们对代码进行破解，直到他们不小心偶然发现了一些似乎“有效”的解决方案。

当您遇到要证明的问题时，您通常可以识别属性（“我有一组不同的对象吗？”、“我是否正在生成排列？”、“我是否希望最小化/最大化某个值？”等）。迟早，证明会聚集到一个模糊相似的组中，用于解决一个问题的技术可以很容易地应用于新的变体。

algorithm - 当谈到证明时，你如何“得到它”？

7 回答 7

Related

Reference