7

TopCoder または ACM ICPC のコンテストで難易度が中程度から高いプログラムを作成する優れたプログラマーは、提出前にアルゴリズムの正確性を確認する必要があります。

正しい出力を保証するためにいくつかのサンプル テスト ケースが提供されていますが、プログラムが正しく動作することはどのように保証されるのでしょうか? 独自のテスト ケースを作成することはできますが、すべてのケースで手計算で正しい答えを知ることはできません。どうやってやっているの？

更新:どうやら、競争環境の厳しい制約が与えられた場合、アルゴリズムの結果を分析して保証することはまったく不可能です。ただし、そのような問題を解決する際に採用されるマニュアル、より一般的な特性があれば、質問に答えるのに十分なはずです。ベストプラクティスのようなもの..

4

3 に答える 3

8

コンテストでは、トップ プログラマーは質問を読み、入力の可能性のほとんどを捉えるいくつかのテスト ケースを考えるのに十分な経験を持っています。
通常、ほとんどのバグをキャッチしますが、100% 安全というわけではありません。

ただし、実際の重要なアプリケーション (飛行機や原子炉の重要なシステムなど) では、コードの一部が本来の動作を行うことを証明する方法があります。

これは正式な検証の分野です。これは複雑すぎてコンテスト中に行うには時間がかかりますが、一部のシステムではミスが許されないため使用されます。

追加情報:
正式な検証は、基本的に 2 つの部分で構成されます。

  1. 手動検証 - ここでは、Hoare ロジックなどの証明システムを使用して、プログラムがやりたいことを実行していることを手動で証明します。
  2. 自動モデル チェック- 問題をステート マシンとしてモデル化し、モデル チェック ツールを使用して、モジュールが本来の動作を行っている (または「悪い」ことをしていない) ことを確認します。
    「何をすべきか」を指定することは、通常、時相論理で行われます。
    これは、ハードウェア モデルの正確性を検証するためにもよく使用されます。たとえば、インテルはこれを使用して、浮動小数点バグが再び発生しないようにします。
于 2013-07-11T09:18:16.613 に答える
3

これを想像してみてください。あなたがトップ プログラマーであると想像してください。つまり、あなたはたくさんのアルゴリズムを知っており、それらを実装する際によく考えません。問題のニーズに合わせて既知のアルゴリズムを変更する方法を知っています。時間の見積もりと複雑であり、最悪の場合、調整したアルゴリズムは時間とメモリの制約内で実行されると予想されます。
このレベルでは、スクラッチパッドを 5 ～ 10 分ほど考えて使用するだけで、コーディングを開始する前に非常に明確なアルゴリズムが得られます。コーディングが完了したら、コンパイルを実行します。通常、コンパイル エラーは発生しません。コードが非常に直感的であるためです。あなたへ。次に、使用されるアルゴリズムと使用されるデータ構造に基づいて、次のいずれかの問題が発生する可能性があると予想します。

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

コーナーケースは、基本的には一般的なケースをコーディングしたようなものですが、N = 1と言うと、答えが他とは異なるため、通常は特殊なケースとして記述します。オーバーフローとは、中間値または結果がデータ型の制限を超える場合です。

この時点で発生する問題を書き留め、このデータをチャレンジ フェーズで使用します (TopCoder の場合と同様)。
これら 2 つを確認したら、[送信] をクリックします。

于 2013-07-11T14:56:49.053 に答える
2

Top Coder には時間要素があるため、その制約内ですべての組み合わせをテストすることはできません。彼らはおそらく、実生活で行うのと同じように、できる限り最善を尽くし、残りは経験に頼っています。コードの重要な部分に永遠にエラーがないことを保証できるかどうかはわかりません。

于 2013-07-11T09:15:45.443 に答える