为算法编写证明

Question

嗨,大家好我想比较2个算法,并认为我可以尝试为他们写一个证明!(我的数学很糟糕因此问题)

通常在去年的数学课上我们会遇到类似的问题

证明:(2r + 3)= n(n + 4)

那么我会做所需的4个阶段并在最后得到答案

我被困的地方是证明prims和Kruskals - 我怎样才能将这些算法变成上面的数学形式所以我可以继续证明

注意:我不是要求别人为我回答 - 只是帮我把它放到一个我可以自己去的地方

谢谢

Answer 1

为了证明算法的正确性,您通常必须显示(a)它终止,以及(b)其输出满足您要执行的操作的规范.这两个证明与你在问题中提到的代数证明有很大的不同.您需要的关键概念是数学归纳.(这是证明的递归.)

我们以quicksort为例.

为了证明快速排序总是终止,你首先会显示它终止于长度为1的输入.(这很简单.)然后显示如果它终止输入长度最多为n,那么它将终止输入长度为n +1.感谢归纳,这足以证明算法终止所有输入.

要证明快速排序是正确的,您必须将比较排序规范转换为精确的数学语言.我们所要的输出是一个置换的输入,使得如果我 ≤ Ĵ再一个_我 ≤ 一_Ĵ.证明快速排序的输出是输入的排列很容易,因为它从输入开始,只是交换元素.证明第二个属性有点棘手,但你可以再次使用归纳法.

Answer 2

您没有提供太多细节，但有一个数学家社区（数学知识管理 MKM）开发了支持计算机数学证明的工具。例如，参见：

以及最新的会议