正しさ(コンピューターサイエンス)

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

理論計算機科学では、アルゴリズムが指定どおりに動作する場合、 そのアルゴリズム仕様に関して正しいものです。最もよく調べられるのは、アルゴリズムの入出力動作を参照する機能の正確さです(つまり、入力ごとに、仕様を満たす出力を生成します)。[1]

後者の概念では、回答が返された場合にそれが正しいことを要求する部分的正当性は、最終的に回答返されること、つまりアルゴリズムが終了することをさらに要求する完全な正当性とは区別されます。同様に、プログラムの完全な正当性を証明するには、その部分的な正当性とその終了を証明するだけで十分です。[2]停止問題決定不可能であるため、 後者の種類の証明(終了証明)を完全に自動化することはできません

最も奇数の完全数を見つけるために部分的に正しいCプログラム、その全体的な正確さは2021年の時点で不明です


// nの適切な除数の合計を返しますstaticint divisorSum int n {    
   int i sum = 0 ;    
   for i = 1 ; i < n ; ++ i    
      if n i == 0      
         合計+ = i ;  
   合計を返す; 
}
//最小の奇数の完全数を返し
ますintleastPerfectNumber void {  
   int n ; 
   for n = 1 ;; n + = 2    
      if n == divisorSum n ))   
         nを返す; 
}

たとえば、整数1、2、3、…を連続して検索して、ある現象の例(たとえば、奇数の完全数)を見つけることができるかどうかを確認すると、部分的に正しいプログラムを作成するのは非常に簡単です(ボックスを参照)。しかし、このプログラムが完全に正しいと言うことは、数論では現在知られていない何かを主張することです。

アルゴリズムと仕様の両方が正式に与えられていると仮定すると、証明は数学的な証明でなければなりません。特に、特定のマシンにアルゴリズムを実装する特定のプログラムの正当性アサーションであるとは期待されていません。これには、コンピュータのメモリの制限などの考慮事項が含まれます

証明論深い結果あるカリーハワード対応は、建設的論理における機能的正当性の証明がラムダ計算の特定のプログラムに対応することを示しています。この方法で証明を変換することをプログラム抽出と呼びます。

ホーア論理は、コンピュータプログラムの正確さについて厳密に推論するための特定の正式なシステムです。[3]公理的手法を使用して、プログラミング言語のセマンティクスを定義し、ホーアトリプルと呼ばれるアサーションを通じてプログラムの正確性について議論します。

ソフトウェアテストは、プログラムまたはシステムの属性または機能を評価し、それが必要な結果を満たしているかどうかを判断することを目的としたアクティビティです。ソフトウェアの品質にとって重要であり、プログラマーやテスターに​​よって広く展開されていますが、ソフトウェアの原理についての理解が限られているため、ソフトウェアテストは依然として芸術です。ソフトウェアテストの難しさは、ソフトウェアの複雑さに起因します。中程度の複雑さのプログラムを完全にテストすることはできません。テストは単なるデバッグ以上のものです。テストの目的は、品質保証、検証と妥当性確認、または信頼性の見積もりです。テストは、一般的なメトリックとしても使用できます。正当性テストと信頼性テストは、テストの2つの主要な領域です。ソフトウェアテストは、予算、時間、品質の間のトレードオフです。[4]

も参照してください

メモ

  1. ^ ダンロップ、ダグラスD。; バシリ、ビクターR.(1982年6月)。「機能的正当性の比較分析」ACMの通信14(2):229–244。土井10.1145 /356876.356881
  2. ^ マンナ、ゾハル; プヌーリ、アミール(1974年9月)。「プログラムの完全な正しさへの公理的アプローチ」。ActaInformatica3(3):243–263。土井10.1007 / BF00288637
  3. ^ Hoare、CAR(1969年10月)。「コンピュータプログラミングの公理的基礎」(PDF)ACMの通信12(10):576–580。CiteSeerX10.1.1.116.2392_ 土井10.1145 /363235.3632592016年3月4日にオリジナル(PDF)からアーカイブされました。  
  4. ^ Pan、Jiantao(1999年春)。「ソフトウェアテスト」(コースワーク)。カーネギーメロン大学2017年11月21日取得

参考文献