알고리즘의 정당성 증명이란

알고리즘이 정말 맞는 알고리즘이라는 것을 증명하는 것이다.

수학적 귀납법(Mathematical Induction)

귀납: 歸 돌아갈 귀, 納 들일 납
앞에서 일어난 결과가 뒤에서도 일어날 것이라는 것을 증명하는 방법
예)반복적인 일

귀납법 증명 3단계

1. 단계 나누기: 반복적인 일 중에 하나.
2. 첫 단계 증명: 그 하나의 일이 문제를 해결하는 과정안에 있는가?
3. 귀납 증명: 첫 단계 증명에 따라 나머지도 똑같이 동작할 것이다.

반복문 불변식(Loop Invariant)

귀납법 알고리즘의 정당성을 증명하기 위해 자주 쓰이는 방법.
과정들이 결과까지 잘가고 있는가?

1. 초기 조건: 초기에 만든 조건이 충족하는가?
2. 유지 조건: 초기에 만든 조건이 반복문이 실행되는 중에도 충족하는가?

삽입 정렬을 반복문 불변식을 이용해 귀납법 증명 하기

+ (NSArray *)insertionSortWithUnsortedArray:(NSArray *)array { 
	NSMutableArray *mutableArray = [array mutableCopy]; 
	//불변식 1: mutableArray[0..i - 1]은 이미 정렬되어 있다. 
	for (NSInteger i = 0; i < mutableArray.count; i++) { 
	NSInteger j = i; while (j > 0 && [mutableArray[j - 1] integerValue] > [mutableArray[j] integerValue]) {
		//불변식 2: mutableArray[j]를 제외한 mutableArray[0..i]은 정렬되어 있다.
	 	[mutableArray exchangeObjectAtIndex:j - 1 withObjectAtIndex:j]; 
	 	j -= 1; 
	 	} 
	 } 
	 return [mutableArray copy]; 
 }

귀류법(Reduction To The Absurd)

귀류: 歸 돌아갈 귀, 謬 그르칠 류
비교하고자 하는 알고리즘을 부정하고 부정한 것을 증명하다 보니 부정한 것이 틀렸고 비교하고자 하는 알고리즘이 틀리지 않음을 증명하는 방법.

비둘기집의 원리(Pigeonhole Principle)

n마리 비둘기가 n - 1개의 비둘기집에 다 들어갔다면 한 비둘기의 집에 적어도 2마리의 비둘기가 들어가 있다는 것을 알 수 있는 원리.

구성적 증명(Pigeonhole Principle)

구성적: 構 얽을 구, 成 이룰 성, 的 과녁 적
답을 가져와 답이 존재하고 있다는 것을 증명한다. 비구성적 증명은 어떠한 이유 때문에 답이 존재할 것이라는 것 을 증명한다.

참고: Algorithmic Problem Solving Strategies

_{잘못된 부분이 있다면 알려주시면 바로 수정하겠습니다.}