이론 컴퓨터 과학에서 알고리즘은 지정된 대로 동작하는 경우 사양과 관련하여 정확하다. 가장 잘 탐구되는 것은 기능적 정확성(correctness)이다. 이는 알고리즘의 입력-출력 동작을 나타낸다(즉, 각 입력에 대해 사양을 충족하는 출력을 생성한다).[1]

후자의 개념 내에서, 대답이 반환되면 그것이 정확할 것을 요구하는 부분 정확성은 결국 대답이 반환되어야 하는, 즉 알고리즘이 종료되어야 하는 전체 정확성과 구별된다. 따라서 프로그램의 전체 정확성을 입증하려면 부분 정확성과 종료를 입증하는 것으로 충분하다.[2] 후자 종류의 증명(종료 증명)은 정지 문제를 결정할 수 없기 때문에 완전히 자동화될 수 없다.

같이 보기

편집

출처

편집

각주

편집
  1. Dunlop, Douglas D.; Basili, Victor R. (June 1982). “A Comparative Analysis of Functional Correctness”. 《Communications of the ACM14 (2): 229–244. doi:10.1145/356876.356881. S2CID 18627112. 
  2. Manna, Zohar; Pnueli, Amir (September 1974). “Axiomatic approach to total correctness of programs”. 《Acta Informatica3 (3): 243–263. doi:10.1007/BF00288637. S2CID 2988073.