알고리즘의 정당성 증명

1.      수학적 귀납법

2.      반복문 불변식(?)

3.      귀류법

4.      비둘기집 원리(?)

5.      구성적 증명

 

수학적 귀납법

단계나누기

첫단계 증명

귀납 증명

K=1일 때 증명하고 k=n일때를 증명하는 과정

귀류법

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

구성적 증명

è 우리가 원하는 답이 존재한 다는 것을 실제 예를 들거나 답을 만드는 방법으로 제시하는 증명

                

예) 안정적 결혼 문제

                 여자와 남자 커플을 만들 때 서로 선호하는 이성을 찾는 방법

1.      여성이 먼저 1순위로 마음에 드는 이성에게 간다.

2.      그 중 퇴짜를 맞은 여성들은 상대에게 짝이 있는것과 관계없이 다음으로 마음에 드는 이성에게 간다.

3.      남성들은 만약 더 마음에 드는 이성이 다가왔다면 지금의 파트너에게 퇴짜를 놓고 새 이성에게 넘어간다.

4.      더 프로포즈 할 여성이 없을 때까지 2번을 반복한다.