问是否有可能编写一个验证器来检查给定的程序是否实现了给定的算法？
EN

Stack Overflow用户

提问于 2013-02-24 22:40:23

回答 2查看 162关注 0票数 5

给定一个用C++编写的程序P，我可以编写一个算法来检查程序P是否实现了特定的算法吗？有没有什么算法可以解决这个问题。这个问题是可以解决的吗？

例如，我要求一个人实现快速排序算法，现在如果我想确保这个人确实实现了快速排序算法。这个人实际上可以实现一些其他的排序算法，它将产生正确的输出并通过所有测试用例(黑盒测试)。我可以这样做的一种方法是查看源代码。我希望避免这种手动工作，并希望编写一个可以完成这项工作的程序。问题是“这可能吗？”

回答已采纳

发布于 2013-02-24 23:08:50

在Rice's Theorem中，通常甚至不能通过检查代码来决定一段代码是否为排序函数。当然，您可以通过使用这些输入运行它并检查结果，来确定它是否具有对某些有限输入集进行排序的效果。

您可以针对给定目标排序算法的特定情况执行某些操作，方法是检查在排序过程中排序的数组，检查目标算法特有的不变量。例如，递归快速排序实现中的每个调用都将导致一个子数组被排序。

=================================================================

在评论之后，我建议看看Ahmad Taherkhani's home page。他继续在这一领域进行研究，包括2012年关于该主题的一篇论文。

票数 5

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/15052791

复制

相似问题

问是否有可能编写一个验证器来检查给定的程序是否实现了给定的算法？EN