通过提供一个反例证明算法是否正确

Question

我正在学习算法课程，经常会要求我们证明算法是否正确。我们想要这样做的方式是提供一些算法将要采用的数据集，并给我们提供不正确的结果。这听起来很简单，但我比我更愿意承认这一点。但我想变得更好，因此我在这里。

我正在寻找关于如何解决这些问题的提示和建议。我们需要考虑哪些事情才能想出能够有效“打破”算法的数据？我意识到这是一个相当广泛的问题，但我想象大多数问题的思维过程都非常相似。

让我们用下面的例子：

我们有一个算法，将提供非加权区间调度问题的最佳解决方案。也就是说，我们采取较早的整理间隔，删除重叠间隔，并重复，直到没有间隔。

我们有另一个问题，安排所有间隔。我们有这样的想法：我们可以使用我们的初始算法来选择第一组间隔，从剩余的组中去除选定的间隔，再次对剩余的间隔应用初始算法以获得第二组，并且重复直到没有剩余的间隔。这是否会产生最少数量的非重叠区间？

你会如何解决这个问题？通过你的思考过程走过我。

Answer 1

你必须寻找一些边缘情况。对于您的问题，请检查算法是否仍然在未加权的时间间隔集合上工作。检查它是否在所有等间隔的集合上工作。检查是否给出所有不相交的间隔，然后将这些间隔返回给你（如果这是你所期望的）。所以，你是对的 - 证明某些不起作用通常涉及到一个例子（通常是一个奇怪的例子）。

您可能还想问问计算机科学堆栈交换站点。