[알고리즘] 알고리즘의 정당성 증명

수학적 귀납법

---

"반복적인 구조를 갖는 명제를 증명하는 데 유용하게 사용되는 증명 기법"

 

귀납법 증명은 크게 세 단계로 나누어진다.

(1) 단계 나누기 : 증명하고 싶은 사실을 여러 단계로 나눈다.

(2) 첫 단계 증명 : 그중 첫번째 단계에서 증명하고 싶은 내용이 성립함을 보인다. 

(3) 귀납 증명 : 첫번째 단계에서 증명하고 싶은 내용이 성립한다면, 다음 단계에서도 성립함을 보인다.

반복문 불변식

귀납법을 통해 알고리즘의 정당성을 증명할 때, 가장 유용하게 사용되는 개념이다. 

반복문 불변식이란 반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는 길 위에 잘 있는지를 명시하는 조건이다. 반복문이 마지막 정답을 계산하기 위해서는 항상 이 식이 변하지 않고 성립해야 하는 것이다.

 

반복문 불변식은 크게 세 단계로 나누어진다.

(1) 반복문 진입시에 불변식이 성립함을 보인다.

(2) 반복문 내용이 불변식을 깨드리지 않음을 보인다. 즉, 반복문 내용이 시작할 때 불변식이 성립했다면 끝날 때도 성립함을 보인다.

(3) 반복문 종료시에 불변식이 성립하면 정답이다.

 

귀류법

---

우리가 원하는 바와 반대되는 상황을 가정하고 논리를 전개해서 결론이 잘못됐음을 찾아내는 증명 기법 

어떠한 선택이 항상 최선임을 증명하고자 할 때 많이 이용된다. 즉, 우리가 선택한 답보다 좋은 답이 있다고 가정한 후에 그것이 아님을 보이면 우리가 최선의 선택했음을 보일 수 있게 된다.

비둘기집의 원리

---

"10마리의 비둘기가 9개의 비둘기집에 모두 들어갔더라면, 2마리 이상이 들어간 비둘기집이 반드시 하나 이상 존재한다."

 

만약 머리숱이 적을수록 세금을 적게 부과하는 탈모자 위로 법안이 통과되어, 머리털 수를 센다고 해보자. 

그렇다면 이때 머리털 수가 같은 사람의 수는 최소 몇명 이상일까? 

만약 머리털이 제일 많은 사람이 100만 가닥이 있다고 가정하고, 서울의 인구수가 천만명이라고 가정한다면 

머리털 수가 같은 사람은 최소 두 사람은 반드시 존재한다. 이것이 바로 비둘기집의 원리이다.

 

구성적 증명

---

구성적 증명이란 어떠한 답이 있음을 증명하기 위해 사용하는 증명 방법이다. 즉, 구성적 증명은 답의 실제 예를 들거나 답을 만드는 방법을 실제로 제시하는 증명이다. 

즉, 보통은 알고리즘을 제시함으로써 증명을 하게 된다.