알고리즘의 정당성(correctness)
# 알고리즘의 정당성(correctness)
조건 1 : 답을 출력할 때는 반드시 그 답이 정확할 것
조건 2 : 어떤 입력 데이터에 대해서도 유한 시간 내에 답을 낼 것
# 알고리즘의 정당성을 증명하는 방법
1. 테스팅법(testing method)
> 테스팅법으로 정당성을 증명할 경우에는 그 문제의 조건에 맞는 임의의 데이터를 입력했을 때 그 데이터에 대한 컴퓨터의 계산 결과를 미리 알고 있는 정답과 비교한다.
> 그러나
> 이 방법은 비용이 너무 많이 들고 시간이 너무 걸리며 매우 번거롭기 때문에 이 방법만으로는 알고리즘의 정당성을 검증하기에는 부적합하다. 왜냐하면, 알고리즘의 정당성에 관한 모든 의문을 없애기 위해서는 먼저 그 알고리즘을 정당한 컴퓨터 프로그램으로 구현해야 할 뿐만 아니라, 가능한 모든 데이터에 대해 이러한 검증을 해야 한다. 그러나 모든 데이터에 대한 결과를 미리 알고 있다면 프로그램을 작성하는 의미가 없을 뿐 아니라, 실제 문제에 있어서는 이와 같이 프로그램을 모든 경우에 대해 테스트하는 것은 거의 불가능하다.
2. 이론적 증명
> 따라서 일반적으로 알고리즘이 제대로 실행된다는 정당성을 증명하기 위해서 앞서 말한 두 가지 조건이 각각 성립한다는 것을 이론적으로 증명한다.
조건 1을 증명하기 위해서는 알고리즘 혹은 프로그램의 각 문장에 있는 변수가 갖는 값 사이에 성립하는 어떤 조건식을 증명하면 된다. 그리고 이 조건이 반복문이 실행되는 중에도 충족되는지 보면된다.
귀납법 : 앞에서 일어난 결과가 뒤에서도 일어날 것이라는 것을 증명하는 방법
# 귀납법 증명 3단계
1. 단계 나누기 : 증명하고 싶은 사실을 여러 단계로 나눔
2. 첫 단계 증명 : 첫 단계에서 증명하고 싶은 내용이 성립함을 보임
3. 귀납 증명 : 한 단계에서 증명하고 싶은 내용이 성립한다면, 다음 단계에서도 성립함을 보임
# 반복문 불변식(loop invariant)
귀납법 알고리즘의 정당성을 증명하기 위해 자주 쓰이는 방법.
과정들이 결과까지 잘 가고 있는가?
1. 초기 조건 : 초기에 만든 조건이 충족하는가?
2. 유지 조건 : 초기에 만든 조건이 반복문이 실행되는 중에도 충족하는가?
조건 1 : 답을 출력할 때는 반드시 그 답이 정확할 것
조건 2 : 어떤 입력 데이터에 대해서도 유한 시간 내에 답을 낼 것
# 알고리즘의 정당성을 증명하는 방법
1. 테스팅법(testing method)
> 테스팅법으로 정당성을 증명할 경우에는 그 문제의 조건에 맞는 임의의 데이터를 입력했을 때 그 데이터에 대한 컴퓨터의 계산 결과를 미리 알고 있는 정답과 비교한다.
> 그러나
> 이 방법은 비용이 너무 많이 들고 시간이 너무 걸리며 매우 번거롭기 때문에 이 방법만으로는 알고리즘의 정당성을 검증하기에는 부적합하다. 왜냐하면, 알고리즘의 정당성에 관한 모든 의문을 없애기 위해서는 먼저 그 알고리즘을 정당한 컴퓨터 프로그램으로 구현해야 할 뿐만 아니라, 가능한 모든 데이터에 대해 이러한 검증을 해야 한다. 그러나 모든 데이터에 대한 결과를 미리 알고 있다면 프로그램을 작성하는 의미가 없을 뿐 아니라, 실제 문제에 있어서는 이와 같이 프로그램을 모든 경우에 대해 테스트하는 것은 거의 불가능하다.
2. 이론적 증명
> 따라서 일반적으로 알고리즘이 제대로 실행된다는 정당성을 증명하기 위해서 앞서 말한 두 가지 조건이 각각 성립한다는 것을 이론적으로 증명한다.
조건 1을 증명하기 위해서는 알고리즘 혹은 프로그램의 각 문장에 있는 변수가 갖는 값 사이에 성립하는 어떤 조건식을 증명하면 된다. 그리고 이 조건이 반복문이 실행되는 중에도 충족되는지 보면된다.
귀납법 : 앞에서 일어난 결과가 뒤에서도 일어날 것이라는 것을 증명하는 방법
# 귀납법 증명 3단계
1. 단계 나누기 : 증명하고 싶은 사실을 여러 단계로 나눔
2. 첫 단계 증명 : 첫 단계에서 증명하고 싶은 내용이 성립함을 보임
3. 귀납 증명 : 한 단계에서 증명하고 싶은 내용이 성립한다면, 다음 단계에서도 성립함을 보임
# 반복문 불변식(loop invariant)
귀납법 알고리즘의 정당성을 증명하기 위해 자주 쓰이는 방법.
과정들이 결과까지 잘 가고 있는가?
1. 초기 조건 : 초기에 만든 조건이 충족하는가?
2. 유지 조건 : 초기에 만든 조건이 반복문이 실행되는 중에도 충족하는가?