blocks|key|4940650|text|您没有提供太多细节，但有一个数学家社区(数学知识管理MKM)，他们已经开发了支持数学的计算机证明的工具。例如，请参阅：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4940651|http://imps.mcmaster.ca/|offset|length|4940652|最新的会议|4940653|http://www.orcca.on.ca/conferences/cicm09/mkm09/|4940654|entityMap|0|LINK|mutability|MUTABLE|url|1^0|0|0|O|0|0|0|0|1C|1|0^^$0|@$1|2|3|4|5|6|7|R|8|@]|9|@]|A|$]]|$1|B|3|C|5|6|7|S|8|@]|9|@$D|T|E|U|1|V]]|A|$]]|$1|F|3|G|5|6|7|W|8|@]|9|@]|A|$]]|$1|H|3|I|5|6|7|X|8|@]|9|@$D|Y|E|Z|1|10]]|A|$]]|$1|J|3|-4|5|6|7|11|8|@]|9|@]|A|$]]]|K|$L|$5|M|N|O|A|$P|C]]|Q|$5|M|N|O|A|$P|I]]]]

You don't give many details but there is a community of mathematicians (Mathematical Knowledge Management MKM) who have developed tools to support computer proofs of mathematics. See, for example:

<a href="http://imps.mcmaster.ca/" rel="nofollow noreferrer">http://imps.mcmaster.ca/</a>

and the latest conference 

<a href="http://www.orcca.on.ca/conferences/cicm09/mkm09/" rel="nofollow noreferrer">http://www.orcca.on.ca/conferences/cicm09/mkm09/</a>

blocks|key|4940691|text|我所处的位置是证明素数和Kruskals+--我如何才能将这些算法转换成类似上面的数学形式，这样我就可以继续证明|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4940692|blockquote|4940693|4940694|4940695|我不认为你可以直接。相反，证明两者都生成MST，然后证明任意两个MST相等(或者等价，因为某些图可以有多个MST+)。如果两种算法生成的MST被证明是等价的，那么这两种算法是等价的。|4940696|entityMap^0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|J|8|@]|9|@]|A|$]]|$1|B|3|-4|5|C|7|K|8|@]|9|@]|A|$]]|$1|D|3|-4|5|6|7|L|8|@]|9|@]|A|$]]|$1|E|3|-4|5|6|7|M|8|@]|9|@]|A|$]]|$1|F|3|G|5|6|7|N|8|@]|9|@]|A|$]]|$1|H|3|-4|5|6|7|O|8|@]|9|@]|A|$]]]|I|$]]

<blockquote>
 Where i am stuck is proving prims and Kruskals - how can i get these algorithms in to a form like the mathmatical one above so i can proceed to prove
</blockquote>

I don't think you can directly. Instead, prove that both generate a MST, then prove that any two MST are equal ( or equivalent, since you can have more than one MST for some graphs ). If both algorithms generate MSTs which are shown to be equivalent, then the algorithms are equivalent.

blocks|key|2029369|text|从我在Uni大学的数学课上，我(依稀)记得证明了Prims和Kruskals算法--你不能用数学形式来攻击它。取而代之的是，您可以将经过验证的图理论结合起来，例如http://en.wikipedia.org/wiki/Prim%2527s_algorithm#Proof_of_correctness来构建证明。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|2029370|如果你想证明复杂性，那么简单地通过算法的工作，它是O(n%5E2)。对于图是稀疏的这种特殊情况，有一些优化可以将其减少到O(nlogn)。|2029371|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Prim%2527s_algorithm#Proof_of_correctness^0|29|1W|0|0|0^^$0|@$1|2|3|4|5|6|7|N|8|@]|9|@$A|O|B|P|1|Q]]|C|$]]|$1|D|3|E|5|6|7|R|8|@]|9|@]|C|$]]|$1|F|3|-4|5|6|7|S|8|@]|9|@]|C|$]]]|G|$H|$5|I|J|K|C|$L|M]]]]

From my maths classes at Uni I (vaguely) remember proving Prims and Kruskals algorithms - and you don't attack it by writing it in a mathematical form. Instead, you take proven theories for Graphs and combine them e.g. <a href="http://en.wikipedia.org/wiki/Prim%27s_algorithm#Proof_of_correctness" rel="nofollow noreferrer">http://en.wikipedia.org/wiki/Prim%27s_algorithm#Proof_of_correctness</a> to build the proof. 

If your looking to prove the complexity, then simply by the working of the algorithm it's O(n^2). There are some optimisations for the special case where the graph is sparse which can reduce this to O(nlogn).

blocks|key|124763|text|大多数情况下，证据取决于你手中的问题。简单的参数有时就足够了，有时你可能需要严格的证明()。我曾经用一个推论和已证明定理的证明来证明我的算法是正确的。但那是为了一个大学项目。|type|unstyled|depth|inlineStyleRanges|entityRanges|data|124764|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|D|8|@]|9|@]|A|$]]|$1|B|3|-4|5|6|7|E|8|@]|9|@]|A|$]]]|C|$]]

Most of the times the proof depends on the problem you have in your hand. Simple argument can be suffice at times, at some other times you might need rigorous proof. I once used a corollary and proof of already proved theorem to justify my algorithm is right. But that is for a college project.

blocks|key|124771|text|也许你想尝试一种半自动的证明方法。例如，如果您有Prim和Kruskal算法的Java规范，并且以最佳方式构建在相同的图模型上，则可以使用KeY+Prover来证明算法的等价性。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|124772|关键部分是在Dynamic+Logic中形式化您的证明义务(这是一阶逻辑的扩展，具有Java程序符号执行的类型和方法)。要证明的公式可以匹配以下(粗略的)模式：|124773|\forall+Graph+g.+\exists+Tree+t.
++++(<{KRUSKAL_CODE_HERE}>resultVar1=t)+<->+(<{PRIM_CODE_HERE}>resultVar2=t)|code-block|syntax|javascript|124774|这表明对于所有的图，两种算法都会终止，并且结果是相同的树。|124775|如果你很幸运，并且你的公式(和算法实现)是正确的，那么KeY可以自动为你证明。如果不是，您可能需要实例化一些量化的变量，这使得有必要检查前面的证明树。|124776|在用KeY证明了这件事之后，你可以为学到的东西感到高兴，也可以尝试从KeY证明中重建一个手动证明-这可能是一项乏味的任务，因为KeY知道许多不容易理解的特定于KeY的规则。然而，也许你可以做一些事情，比如从KeY用来实例化证明中序列右侧的存在量词的术语中提取赫布兰德析取。|124777|嗯，我认为KeY是一个有趣的工具，更多的人应该习惯于使用这样的工具来证明关键的Java代码;)|124778|entityMap|0|LINK|mutability|MUTABLE|url|http://www.key-project.org/^0|1X|A|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|10|8|@]|9|@$A|11|B|12|1|13]]|C|$]]|$1|D|3|E|5|6|7|14|8|@]|9|@]|C|$]]|$1|F|3|G|5|H|7|15|8|@]|9|@]|C|$I|J]]|$1|K|3|L|5|6|7|16|8|@]|9|@]|C|$]]|$1|M|3|N|5|6|7|17|8|@]|9|@]|C|$]]|$1|O|3|P|5|6|7|18|8|@]|9|@]|C|$]]|$1|Q|3|R|5|6|7|19|8|@]|9|@]|C|$]]|$1|S|3|-4|5|6|7|1A|8|@]|9|@]|C|$]]]|T|$U|$5|V|W|X|C|$Y|Z]]]]

Maybe you want to try out a semi-automatic proof method. Just to go for something different ;) For example, if you have a Java specification of Prim's and Kruskal's algorithms, optimally building upon the same graph model, you can use the <a href="http://www.key-project.org/" rel="nofollow">KeY Prover</a> to prove the equivalence of the algorithm.

The crucial part is to formalize your proof obligation in Dynamic Logic (this is an extension of first-order logic with types and means of symbolic execution of Java programs). The formula to prove could match the following (sketchy) pattern:

<pre><code>\forall Graph g. \exists Tree t.
 (&lt;{KRUSKAL_CODE_HERE}&gt;resultVar1=t) &lt;-&gt; (&lt;{PRIM_CODE_HERE}&gt;resultVar2=t)
</code></pre>

This expresses that for all graphs, both algorithms terminate and the result is the same tree.

If you're lucky and your formula (and algorithm implementations) are right, then KeY can prove it automatically for you. If not, you might need to instantiate some quantified variables which makes it necessary to inspect the previous proof tree.

After having proven the thing with KeY, you can either be happy about having learned something or try to reconstruct a manual proof from the KeY proof - this can be a tedious task since KeY knows a lot of rules specific to Java which are not easy to comprehend. However, maybe you can do something like extracting an Herbrand disjunction from the terms that KeY used to instantiate existential quantifiers at the right-hand side of sequents in the proof.

Well, I think that KeY is an interesting tool and more people should get used to prove critical Java code using tools like that ;)

I am trying to compare 2 algorithms. I thought I may try and write a proof for them. (My math sucks, so hence the question.)
Normally in our math lesson last year we would be given a question like &lt;can't use symbols in here so left them out&gt;.
Prove: (2r + 3) = n (n + 4)
Then I would do the needed 4 stages and get the answer at the end.
Where I am stuck is proving prims and Kruskals - how can I get these algorithms in to a form like the mathmatical one above, so I can proceed to prove?
Note: I am not asking people to answer it for me - just help me get it in to a form where I can have a go myself.

Writing a proof for an algorithm

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

EdgeOne AI 安全实战专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

我正在尝试比较两种算法。我想我可以试着为他们写一份证明。(我的数学很烂，所以就有了这个问题。)通常，在去年的数学课上，我们会遇到这样的问题：“can‘t use symbols in here，so left out>。证明：(2r + 3) =n (n + 4)然后我会做所需的4个阶段，并在最后得到答案。我被困在证明素数和Kruskals的地方--我如何才能将这些算法转化为类似上面数学形式的算法

问为算法编写证明
EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问为算法编写证明EN

回答 5

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问为算法编写证明
EN