プログラマーはTopCoderやその他の競技でどのようにアルゴリズムをテストしますか？

Question

TopCoderまたはACM ICPCの競技で中程度から高い難易度のプログラムを書く良いプログラマは、提出する前にアルゴリズムの正確性を確保しなければなりません。

正しい出力を保証するためのサンプルテストケースがいくつか用意されていますが、プログラムが正しく動作することをどのように保証しますか？彼らは自分でいくつかのテストケースを書くことができますが、すべてのケースで手動計算による正解を知ることはできません。どうやってやっているの？

更新：それはそうと、競争環境の厳しい制約を与えられたアルゴリズムの結果を分析し、保証ことは可能ではありません。しかし、そのような問題を解決する際に採用される、より一般的な手作業の特徴があれば、その質問に答えるだけで十分です。ベストプラクティスのようなもの..

Answer 1

大会では、トッププログラマーは質問を読んで十分な経験があり、入力の可能性をほとんど取り込むテストケースを考えます。
これはほとんどのバグをキャッチしますが、100％安全ではありません。

しかし、実際の生活に欠かせないアプリケーション（航空機や原子炉などの重要なシステム）では、コードが何をするのかを証明する方法があります。

これはformal verificationのフィールドです。これはあまりにも複雑で時間がかかりますが、いくつかのシステムでは間違いが許されないために使用されます。

---

いくつかの追加情報：
フォーマル検証は基本的に2つの部分から構成されています

1. マニュアル検証 - ここで私たちは、このようなHoare logicとして証明システムを使用して、手動プログラムは、我々が何を望んでい証明それを行う。
2. 自動model checking - 問題をステートマシンとしてモデリングし、モデルチェックツールを使用して、モジュールが想定していることを実行しているかどうかを確認します。
   「何をすべきか」を指定するのは通常temporal logicです。
   これは、ハードウェアモデルの正確性を検証するためによく使用されます。たとえば、インテルはそれを使ってfloating point bugが再び届かないようにします。

Answer 2

トップコーダーには時間要素があるため、その制約内のすべての組み合わせをテストすることはできません。彼らはおそらく最善を尽くし、実生活と同じように残りの経験に頼っているでしょう。重要なコードが永遠にエラーフリーであることを保証することはこれまでに可能であるとは知らない。

Answer 3

ピクチャーこれ、あなたはアルゴリズムの束を知っているとthem.Youが問題のneeds.Youに合うように、既に知られているアルゴリズムを変更する方法を知って実装しながら、よく考えて考えていないだろうトップprogrammer.Meaningある想像時間と複雑さを見積もることで強く、最悪の場合、あなたの調整されたアルゴリズムが時間とメモリの制約内で実行されることを期待しています。
このレベルでは、コードを開始する前に、スクラッチパッドを約5〜10分間思考して使用し、非常に明確なアルゴリズムを持っています。コーディングが終了すると、コンパイルされ、通常はコンパイルエラーは発生しません。コードは直感的です。 使用されているアルゴリズムと使用されているデータ構造に基づいて、 が次のいずれかの問題の可能性があります。

1. コーナーケース
2. オーバーフローの問題

コーナーケースは、N = 1は、答えはothers.So異なっていると言うしかしとき、あなたは一般的なケースのためにコード化されているよう基本的にですあなたは一般的にそれを特別なケースとして書いています。 オーバーフローは、中間値または結果がデータ型の制限をオーバーフローする場合です。

この時点で発生している問題をメモし、このデータをチャレンジフェーズ（TopCoderのように）で使用します。
これらの2つを確認したら、[送信]を押します。