程序员如何在TopCoder或其他比赛中测试他们的算法？

Question

在TopCoder或ACM ICPC的竞赛中编写中等到较高难度的程序的优秀程序员必须在提交之前确保其算法的正确性.

虽然它们提供了一些示例测试用例以确保正确的输出,但它如何保证程序正常运行？他们可以编写自己的一些测试用例,但在所有情况下都不可能通过手动计算知道正确的答案.他们是如何做到的呢？

更新:看起来,鉴于竞争环境的严格限制,分析和保证算法的结果是不可能的.但是,如果在解决这些问题时有任何手册,更常见的特征 - 应该足以回答这个问题.最好的做法..

Answer 1

在竞赛中,顶级程序员有足够的经验来阅读问题,并考虑一些应该抓住大部分输入可能性的测试用例.
它通常会捕获大部分错误 - 但它并非100%安全.

然而,在现实生活中的关键应用(例如飞机或核反应堆上的关键系统)中,有一些方法可以证明某些代码可以完成它应该做的事情.

这是形式验证的领域- 在竞赛期间完成这一过程太复杂和耗时,但对于某些系统而言,它是被使用的,因为错误是不能容忍的.

一些附加信息:
正式验证基本上由两部分组成:

1. 手动验证 - 在这里我们使用证明系统,如Hoare逻辑,并手动证明程序完成了我们想要它做的事情.
2. 自动模型检查 - 将问题建模为状态机,并使用模型检查工具验证模块是否执行了应该执行的操作(或者不执行"坏"操作).
   指定"它应该做什么"通常用时间逻辑来完成.
   这通常用于验证硬件模型的正确性.例如,英特尔使用它来确保它们不会再次获得浮点错误.