课程主页: https://www.coursera.org/learn/what-is-a-proof
课程概述
在计算机科学的各个领域，数学思维都是至关重要的：无论是算法、生物信息学、计算机图形学、数据科学还是机器学习等方向。在这门课程中，我们将学习离散数学中最重要的工具：归纳法、递归、逻辑、不变量、例子和最优性。我们将运用这些工具回答一些典型的编程问题，例如：如何确保解决方案的存在？我如何确保我的程序计算出了最优答案？这些对象是否满足给定的条件？
课程大纲
建立有说服力的论点
为什么有些论点具有说服力而有些则不然？什么使得论点具有说服力？如何以一种没有怀疑余地的方式建立你的论点？数学思维如何帮助我们做到这一点？在这一部分，我们将开始探讨这些问题。我们的目标是通过例子学习如何理解证明，如何独立发现证明，如何解释证明，最后也是最重要的，如何享受证明：我们会看到一个小的评论或简单的观察如何将一个看似微妙的问题变成一个明显的问题。
如何寻找例子？
我们如何确定一个具有某些要求的对象存在？一种方式是遍历所有对象，检查是否至少有一个符合要求。然而，在许多情况下，搜索空间巨大。计算机可能会帮助，但一些缩小搜索空间的推理对计算机的搜索和“徒手工作”都非常重要。在这一模块中，我们将学习各种技巧，以证明一个对象存在并且该对象在所有其他对象中是最优的。我们将通过解决许多互动难题来进行实践。同时，我们还将展示一些帮助我们构造例子的计算机程序。
递归和归纳
我们将发现递归和归纳这两种强大的定义对象、证明概念和实现程序的方法。这两种方法在离散数学和计算机科学中得到了广泛应用。特别是在分析算法的正确性和运行时间以及实现高效解决方案时，您将经常看到它们。有些计算问题（如探索网络）的递归解决方案是最自然的。递归和归纳的主要思想是将给定的问题分解为相同类型的更小问题。能够看到这样的分解是数学和编程中一项重要的技能。我们将通过共同解决各种问题来锤炼这项技能。
逻辑
数学逻辑在建立有说服力的论点中起着至关重要的作用。我们在编写代码、推理和决策、使用计算机程序时都会使用数学逻辑的规则和语言。本周我们将学习数学逻辑的基础知识，并练习一些看似反直觉但却是逻辑上合理的数学校面。这将帮助我们编写可读和精确的代码，并以严谨和简洁的方式表达我们的想法。
不变量
“有些东西是永恒不变的。”除了是一个哲学声明，这句话在离散数学和计算机科学中也是一个重要的理念。一个在过程中保持不变的属性被称为不变量。在分析算法、程序和其他过程中，不变量被大量使用。找到正确的不变量的能力是我们将在这一模块中共同培养的重要技能。
解决15-puzzle
在这一模块中，我们考虑一个著名的15块拼图，需要在一个方框中恢复15个方块的顺序。事实证明，这个拼图的行为由美丽的数学决定：当且仅当对应的排列是偶数时，它是可解的。为了理解这意味着什么以及为什么是真的，我们将学习偶排列和奇排列的基本属性——在代数和离散数学中一个重要的概念。接着，我们将实现一些处理排列的简单方法，然后使用它们作为构建块，来实现一个能迅速解决此游戏任意配置的程序！
课程主页: https://www.coursera.org/learn/what-is-a-proof