2. 수학적 귀납법과
Invariant를 통한 증명 [1-2주차]
2024년
1월 9일 화요일
오후 10:48
<수학적 귀납법>
수학적 귀납법의
기본형 : P(1)[Base]이
참이고, P(n-1)->P(n)[Step]이 참이면, P(n)은 모든 자연수 n에 대해서 참이다.
P(n-1)->P(n)을 증명할 때 P(n-1)이 참이라고 ‘가정’하고 P(n)임을 증명한다.
수학적 귀납법의 강한 형태 : P(1)이 참이고, P(1)∧P(2)∧…∧P(n-1)->P(n)이 참이면 P(n)은 모든 자연수 n에 대해서 참이다.
(∧는 and, &&를
의미하는 수학 기호)
<명제 P->Q의 의미>
P(n) : n이 등장하는 문장
명제 : 객관적으로 참, 거짓을 판단할 수 있는 문장. 아래의 4개 문장은 명제이다.
조건 : 그 자체로는 명제가 아니지만, 변수값에 따라 참, 거짓을 판단할 수 있는 문장. 아래에서 P와 Q는 조건이다.
- P가 참, Q가 참 -> 전체는 참
- P가 참, Q가 거짓 -> 전체는 거짓
- P가 거짓, Q가 참 -> 전체는 참
- P가 거짓, Q가 거짓 -> 전체는 참
예전에는 3, 4번째 경우를 vacuous(공허한)이라고 했다.
그러나 이
경우를 true라고 하는 것이 더 편리하기에 지금은 참이라고 한다.
ex1) 자연수 n에 대해 3<n -> 10<n2
- 위 명제는 참인가?
- n = 1일 때, 위 명제는 참. (거짓->거짓)
ex2) 자연수 n에 대해 1<n -> 10<n2
**n=1, n=4일 때는 참이 되지만, n=2일 때는 거짓이 된다.**
<간단한 재귀함수증명>
unsigned int sum(unsigned int x)
{
if(x <= 0) return 0;
return x + sum(x – 1);
}
위 함수가
항상 0+1+2+…+x 를 리턴한다는 것을 증명해 보자.
S(3)->S(2)->S(1)->S(0)->0->1->3->6 처럼 따라
들어가는 식으로 생각하면 복잡한 함수에서 증명하기 어렵다. 수학적 귀납법을 이용해 증명하자.
- P(1)이 참이다 : “sum(1)이 리턴하는 값은 1이다”를 증명하면 됨. 실제 코드에 1을 대입하면 1을
리턴함을 알 수 있음.
- P(x-1) -> P(x) 가 참이다 : “sum(x-1)이 1+2+…+(x-1)을
리턴하면 sum(x)는 1+2+…+x를 리턴한다”를 증명하면 됨.
- 코드를 보면 sum(x)는 x+sum(x-1)의
값을 리턴함. sum(x-1)의 리턴 값은 1+2+…+(x-1)과 같다고 가정했으므로 sum(x)는 1+2+…+(x-1)+x를 리턴함을 확인할 수 있음
<루프 불변성(Invariant)>
루프 불변성 : 반복문이 실행되는 동안 변하지 않는 성질
ex) 삽입 정렬에서 인덱스j 원소를 뽑아 정렬하는 경우
for (j=1; j<array.length; j++)
"array[0..j-1]은 for문이 반복을 시작할 때마다
정렬된 상태이다." -> 루프 불변성
루프 불변성을
보이려면 다음 세 가지를 만족해야 한다.
1. 초기조건 : 루프가 첫 번째 반복을 시작하기 전에 루프 불변성이 참이어야
한다.
2. 유지조건 : 루프의 반복이 시작되기 전에 루프 불변성이 참이었다고 가정하면, 다음 반복이 시작되기 전까지도 계속 참이여야 한다.
3. 종료조건 : 루프가 종료될 때 그 불변식이 알고리즘의 타당성을 보이는 데 유용한
특성을 가져야 한다.
종료조건 예) 위 삽입 정렬에서 for문이 종료될 때 j = length 이다. 이를 루프 불변성에 대입하면 "array[0..length-1]은 정렬된 상태이다"가
된다. 배열 전체가 정렬되었으며 이는 알고리즘이 타당함을 의미한다.
<Binary Search 증명>
int search(int a[], int n, int x)
{
int l, r, m;
l = 0; r = n-1;
while(l <= r) {
m = (l+r) / 2; // l<=m<=r 이다.
if(a[m] == x) return m;
else if (a[m] > x) r
= m-1;
else l = m+1;
}
return -1;
}
(a는 정렬된 배열, n은 배열 크기, x는
찾을 값, m은 인덱스)
* Proof by Invariant
Invariant : 만약 어떤 i에 대해서 a[i] = x라면, l<=i<=r이 항상성립한다.
(1) 초기조건 : l은 인덱스의 시작, r은 인덱스의 끝이므로 l<=i<=r가 성립.
(2) 유지조건 : a[m]>x라면 m>i, r=m-1>i-1, r>=i.
a[m]<x라면 m<i, l=m+1<i+1,
l<=i.
invariant가 깨질 수 있는 코드가 없다.
(3) 종료조건 : l과 r의 차이가 계속 줄어들기 때문에, 적어도 l=i=r이 될 때 i를 리턴하게 된다.
* a[i] = x인 i가 없다면,
l과 r의 차이가 계속 줄어들기 때문에, 루프는
반드시 끝나고 -1이 리턴 됨
<Binary Search 증명(재귀)>
int search(int a[], int n, int x)
{
int m;
if(n<=0) return -1;
m = n/2;
if(a[m] == x) return m;
else if(a[m] > x) return
search(a, m, x);
else {
r = search(a+m+1, n-m-1,
x);
if(r = -1) return -1;
else return r+m+1;
}
}
재귀 호출이
반복될수록 감소하는 값 n을 기준으로, 수학적 귀납법을 적용한다.
주장 : 만약 어떤 i에 대해서 a[i]
= x라면, 위 함수는 i를 리턴한다.
Base : n = 0인 경우 “어떤 i에 대해서 a[i] = x”가 성립할 방법이 없고, 함수는 항상 -1을 리턴한다.
Step : n=0, n=1, n=2, …, n = k-1인 경우 주장이 참(a[i]
= x를 만족하는 i가 없거나, 있다면 i를 리턴)이라 가정하면, n = k인 경우 주장이 참이 됨을 보이면 된다.
n = k일 때,
- Case 1 : a[m] = x인 경우 m을 리턴하므로 주장이
성립
- Case 2 : a[m] > x인 경우 a[m], a[m+1], …, a[n] 중에서는 x와 같은 값이 없다. 따라서 a[i] = x인 경우가 있다면 i는 0, 1, …, m-1중
하나이다. 위에서, n=0, n=1, …, n=k-1인 경우 주장이 참이 된다고 가정하였다. 따라서 n=m일 경우, 주장이
참이 된다. 즉, search(a, m, x)는 정확하게 작동하여 i를 리턴한다. search(a, k, x)는 i를 그대로 리턴하게 되므로, n=k일 때 주장은 참이 된다.
- Case 3 : a[m] < x인 경우, a[i] = x인 경우가
있다면 i는 m+1, m+2, …, k 중 하나이다. search(a+m+1, k-m-1, x)는 n=0, …, n=k-1인 경우 중 하나이므로, 위 가정에 따르면 정확하게 작동하여 i를 리턴한다. 그러나 a에 a+m+1을
입력했기 때문에, 재귀 호출된 함수에서의 i는 호출한 함수
기준으로는 i-m-1가 된다. 이를 고려하여 m+1을 더해 리턴하므로, n=k일 때 주장은 참이 된다.
* Case1, 2, 3에서 a[i] = x를
만족하는 i가 있다고 가정하였다. a[i] = x를 만족하는 i가 없는 경우, 주장은 무조건 성립하므로, 그러한 가정을 해도 문제가 없다. (만족하는 i가 없는 경우는 고려하지 않아도 된다.)
<Selection Sort의 증명>
int sort(int a[], int n)
{
int i, j, m, t;
for(i=0; i<n; i++) {
// find minimum
m = i;
for (j=i; j<n; j++)
if (a[m] > a[j]) m =
j;
// swap
t = a[i]; a[i] = a[m]; a[m]
= t;
}
return;
}
Sorting이 됐다는 증명을 어떻게 할 것인가?
입력 : a[0], a[1], …, a[n-1] <- (정수) 집합
Sorting이 완료된 후 다음이 만족되어야 함
- 구분을 위해, Sorting이 끝난 후 배열에 저장된 값들을 b[0], b[1], …,b[n-1]라고 부르자
- 조건 1: {a[0], a[1], …, a[n-1]} = {b[0], b[1], …, b[n-1]} 집합으로 같음
- 조건 2: b[0] < b[1] < … < b[n-1] (편의상
같은 값은 없다고 가정)
Proof by Invariant
- 배열 요소를 교환만 하므로, 집합 조건을 깰 수 있는 코드는 없음
- Invariant: k번째 루프가 끝난 후에
(1) a[0] < a[1] < … < a[k-1]
-> k=n인 경우 a[0] < a[1]< … < a[n-1]
(2) a[k-1] < a[x] if x
> k-1
- 이제 수학적 귀납법을 통해 invariant를 증명하자
Base : k = 0
(1): a[0]부터 a[-1]까지? 아무것도 없음. 이는
아무말도 하지 않은 것(null condition). 아무말도 하지 않으면 true.
(2): a[-1]은 말이 안 됨. null condition 이므로 true.
Step : k번째 루프가 끝났을 때 Invariant가 성립한다면, k+1번째 루프가 끝났을 때도 Invariant가 성립하는가?
(1): a[0] < a[1] < … < a[k-1] < a[k]
a[0] < … < a[k-1]은 k번째 루프의 (1)에 의해 성립
a[k-1] < a[k] 는 k번째 루프의 (2)에 의해 성립.
a[k]가 a[x]중 무엇이였든간에 a[k-1] 보다
크다.
(2): a[k] < a[x] if x
> k
a[k], …, a[n-1]중 최소값을 a[k]로 옮겼으므로 성립
<Selection Sort 재귀호출 증명>
int sort(int a[], int n)
{
if (n<=1) return;
int j, m, t;
m = 0;
for(j=0; j<n; j++) {
if (a[m] > a[j]) m = j;
}
// swap
t = a[0]; a[0] = a[m]; a[m] = t;
sort(a+1, n-1);
return;
}
조건 1: {a[0], a[1], …, a[n-1]} = {b[0], b[1], …, b[n-1]} 집합으로 같음
조건 2: b[0] < b[1] < … < b[n-1] (편의상
같은 값은 없다고 가정)
이번에도 조건1을 깰 수 있는 코드는 없음.
Base : n = 1일 때, 할 일이 없음.
Step : n-1일 때 sort() 함수가 성공한다면 (즉, 재귀 호출이 끝난 후 a[1]<a[2]<…<a[n-1] 이라면)
n일 때 sort() 함수가 성공하는가? (함수가
끝날 때 a[0]<a[1]<…<a[n-1]이
성립하는가?)
- 재귀호출 전 : 최소값을 a[0]에 저장하므로 a[0]<a[1], a[0]<a[2], …,
a[0]<a[n-1]이 성립한다.
- 재귀호출 이후 : 가정에 따라, a[1]<a[2]<…<a[n-1]이
성립한다. 최소값을 a[0]에 저장했으므로, a[0]<a[1]이다. 따라서 n일 때 sort()함수가
성공한다.
OneNote에서 작성되었습니다.