algorithm - 是否可以编写一个验证程序来检查给定程序是否实现给定算法?

标签 algorithm automation

给定一个用 C++ 编写的程序 P,我能否编写一个算法来确定程序 P 是否实现了特定算法?有没有解决这个问题的算法。这个问题可以解决吗?

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

最佳答案

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

您可以针对给定目标排序算法的特定情况做一些事情,方法是检查排序期间正在排序的数组,检查目标算法的特征不变量。例如,递归快速排序实现中的每次调用都会导致子数组排序。

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

根据评论,我建议查看 Ahmad Taherkhani's home page .他一直在这一领域进行研究,包括 2012 年关于该主题的论文。

关于algorithm - 是否可以编写一个验证程序来检查给定程序是否实现给定算法?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15052791/

相关文章:

powershell - 为什么我的PowerShell脚本不遵守步骤顺序?

Excel:签署 Excel 宏以防止 "Enable Macros"弹出

testing - Testcafe 无法在启用了 SIP 的 MacOS 镜像上运行这一事实是否有任何解决方案?

java - 如何使用光学字符识别解析数字 4

C++在未排序的数组中找到第一个缺失的正值

algorithm - 您如何看待为这个酒店问题开发算法?

java - 确定给定字符串是否为 k 回文

database - 这是功能同步算法吗?

java - Selenium 不会单击页面上的第一个复选框

batch-file - 批处理 - 搜索零件/确切名称并将行从文本文件复制到批处理中作为 var