알고리즘 정당성 증명

Nov 24, 2022

• 알고리즘 정당성 증명
  • 수학적 귀납법(mathematical induction)
  • 귀류법
  • 비둘기 집의 원리
  • 구성적 증명

알고리즘 정당성 증명

많은 경우 단위 테스트를 통해 프로그램을 증명하지만, 이는 완벽한 방법이 아니다.

알고리즘을 정확히 증명하기 위해서는 다양한 수확적 기법을 이용하여야 하며, 이를 통해 알고리즘 구현 시의 통찰과 구조를 완벽히 이해할 수 있다.

무조건 하나의 증명법만 이용되는 것이 아니라, 두 증명법을 섞어 쓰기도 한다.
예를 들어, 구한 답이 최선의 답임을 귀류법으로 증명하고, 귀납법을 이용해 다음 루프에서도 최선임을 증명한다.

수학적 귀납법(mathematical induction)

루프 불변성 에도 사용되는 증명방법
즉 주로 반복적인 구조를 갖는 명제에서 사용된다.

마치, 도미노가 쓰러지듯, 다음 단계를 연쇄적으로 증명하여 최종 결과를 증명하는 방식이며, 세 단계로 나뉨

1. 단계 나누기 : 증명하고 싶은 사실을 여러 단계로 나눔
2. 첫 단계 증명 : 첫 단계에 증명하고 싶은 내용이 성립함을 보임
3. 귀납 증명 : 다음 단계들에서도 연속적으로 성립하는지 보임

🧾️ 예시 문제: “사다리 게임은 언제나 위 선택지와 아래 결과가 1:1 대응되는가?”

1. 단계 나누기: 가로줄이 하나도 없는 N개의 새로줄이 존재할 때, 이때 가로줄을 하나 씩 긋는 것을 한 단계로 본다.
2. 첫 단계 증명: 가로줄이 하나도 없는 N개의 세로줄은 항상 1:1 대응이 된다.
3. 귀납 증명: 가로줄을 특정 두 세로줄 사이에 추가하면, 두 세로줄은 서로의 결과를 뒤바꾸므로, 1:1 대응이 변하지 않음.

가로줄을 아무리 많이 추가해도 1:1 대응은 변하지 않음.

귀류법

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

주로, 어떤 선택이 항상 최선임을 증명하고자 할 때 사용, 즉 이보다 나은 답은 없다를 증명하기 위해 이용

🧾️ 예시 문제: “최대한 많은 회의가 진행되도록 회의실의 회의 스케쥴을 지정하는 문제”

최선의 답: 가장 빨리 끝나는 회의를 순서로 배정하면 최대한 많은 회의를 진행할 수 있음

• 최선의 예정된 회의 집단을 $A$라고 하자
• $A$에서 회의 하나인 원소 $b$를 빼고 시간이 겹치지만 더욱 늦게 끝나 넣지 못했던 회의 $b’$를 넣어도 A 내부 원소의 수는 동일하다.
• 따라서 가장 빨리 끝나는 회의 순으로 진행하면 최소한 공동으로 최선의 답을 구할 수 있다.

비둘기 집의 원리

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

순환 소수 판별 등에 사용 가능

구성적 증명

기존 상단의 비구성적 증명과 달리, 실제 답을 만드는 방법을 제시하는 방법

알고리즘을 만들어낸 후, 해당 알고리즘의 결과를 다른 증명법을 통해 증명하는 식으로 구현