正当性 (計算機科学)
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/04/18 02:32 UTC 版)
ナビゲーションに移動 検索に移動計算機科学における正当性（Correctness）とは、アルゴリズムがその仕様に照らして正しいことを意味する。「機能的」正当性とは、アルゴリズムの入出力動作に関する正当性である（すなわち、各入力に対して正しく出力を生成すること）。形式的検証を参照されたい。
完全正当性（Total Correctness）は、アルゴリズムが常に停止することも要求される。一方、部分正当性（Partial Correctness）は単に返ってくる答えが正しいことのみを要求する（常に答えが返ってくるとは限らない）。停止問題には汎用的解法はないので、完全正当性はより深い問題をはらんでいる。
例えば、整数を 1 から順に調べて奇数の完全数を探すとした場合、部分正当性を備えたプログラムを書くのは極めて簡単である（素因数分解を行って n が完全数かどうかを調べる）。しかし、そのプログラムが完全正当性を備えているとするには数論において未知の知識を必要とする。
正当性の証明は数学的証明でなければならず、アルゴリズムもその仕様記述も形式的に与えられなければならない（形式的仕様記述）。特にその証明は、そのアルゴリズムを特定のマシン上でプログラムとして実装したものについて正当性を意味するものではない。その場合メモリ量の限界を考慮する必要がある。
証明論におけるカリー・ハワード対応は、直観主義論理における機能的正当性の証明がラムダ計算における特定プログラムに対応するとしている。このような証明の変換を「プログラム抽出; program extraction」と呼ぶ。
関連項目
「正当性 (計算機科学)」の例文・使い方・用例・文例
- 請求の正当性を立証する
- 正当性は幾つかの実験によって承認された。
- 私たちは提案された方法を発展させ、その正当性を議論する予定です。
- 要求の正当性を実証する.
- 活力、体力、または正当性が、磨いたり浄化したりして衰える、あるいは弱まる
- 数学者は推測の正当性を示した
- 正当性または承認を欠いている
- あなたの意見の正当性についての堅くユーモアのない考えによって特徴づけられる
- 不変の正当性の原則
- 正当性および妥当性の美的基準との適合
- 正規の法規に従うことによる正当性
- 裁判官は私の主張の正当性を認めた
- 彼の要求の正当性
- 死刑に対する正当性
- 考えまたは信条での正当性の欠如
- 何か他のものの正当性または効果に基づくという仮定
- 純粋性または正当性（特に言語で）の綿密なまたは誇張された主張
- 勝利の正当性が争われている勝者（レース、選挙など）
- ある物の正当性、現実、または真性を肯定あるいは保証する人
- 何かの正当性を確かめる人
Weblio日本語例文用例辞書はプログラムで機械的に例文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
- 正当性_(計算機科学)のページへのリンク
