5장 알고리즘의 정당성 증명

알고리즘이 존재가능한 모든 입력에 대해 정확하게 동작한다는 사실을 증명할 수 없다. 따라서 알고리즘의 정확한 증명은 각종 수학적인 기법을 기반으로 되야한다.

수학적 귀납법과 반복문 불변식

---

수학적 귀납법은 반복적인 구조를 갖는 명제들을 증명하는 데 유용하게 사용되는 증명 기법.

귀납법은 크게 3가지로 나뉜다.

• 단계 나누기 = 증명하고 싶은 사실을 여러 단계로 나눈다.
  
  
• 첫 단계 증명 = 첫 단계에서 증명하고 싶은 내용이 성립함을 보인다. 
  
  
• 귀납 증명 = 첫 단계에서 증명하고 싶은 내용이 성립하면, 다음 단계에서도 성립함을 보인다.

알고리즘은 어떠한 형태로든 반복적인 요소를 가지고 있기 때문에, 귀납법은 알고리즘의 정당성을 증명할 때 가장 유용하게 사용되는 기법.

반복문 불변식 = 반복문의 내용이 한 번 실행될 때마다 중간 결과가 우리가 원하는 답으로 가는지..

불변식을 이용한 반복문의 정당성은 다음과 같이 증명한다

• 반복문 진입시에 불변식이 성립함을 보인다.
  
  
• 반복문 내용이 불변식을 깨뜨리지 않음 보인다. 시작할 때 불변식이 성립하면, 끝에서도 성립한다
  
  
• 반복문 종료시에 불변식이 성립하면 항상 우리가 정답을 구했음 보인다.

*불변식이 깨졌을 때 프로그램을 강제 종료함으로써 알고리즘에 문제가 있는지 없는지를 판단할 수 있다. 다만 엄청나게 많이 실행되는 반복문 안에 단정문을 배치하는 것은 삼가는 것이 좋다.

귀류법

---

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

알고리즘의 결과가 최선임을 보이기 위해 각 단계에서 최선의 선택을 함을 귀류법으로 증명하고, 각 단계에서 최선의 선택을 한다면 다음 단계에서도 최선의 선택을 할 수 있음을 귀납법으로 증명한다.

비둘기집의 원리

---

10마리의 비둘기가 9개의 비둘기집에 모두 들어갔다면, 2마리 이상이 들어간 비둘기집이 반드시 하나는 있게 마련이다.