증명 수학적 귀납법 직접 증명법 간접 증명법 재귀법 프로그램 검증
수학적 귀납법과 이를 이용한 증명 과정을 이해한다. 여러 가지 증명 방법들의 증명 과정을 익힌다. 재귀법을 이용한 정의와 과정을 이해한다. 재귀 알고리즘을 작성하고 검증한다. 프로그램을 검증하는 목적과 방법을 살펴본다.
제 2 수학적 귀납법 / 강귀납법 자연수 n 에 관한 명제 p(n)에 대하여 다음 두 조건이 성립한다고 하자. (2) 임의의 자연수 k ≥1에 대해 p(1)∧p(2)∧…∧ p(k) 참이면 p(k+1)도 참이다. 이 때 모든 자연수 n에 대하여 p(n)은 참이다.
직접증명법(direct proof) 명제의 함축 p→q 가 참이 됨을 증명하는 방법
간접증명법(indirect proof) 증명하고자 하는 명제를 논리에 어긋나지 않는 범위에서 증명하기 쉬운 명제로 변환하여 증명하는 방법 유형 대우증명법 모순증명법 반례증명법
대우증명법(proof by contraposition) 명제의 함축 p→q 이 참이면 그 대우인 q→ p 도 참이고 두 명제가 서로 동치인 것을 이용 주어진 명제의 대우명제가 참임을 증명함으로써 증명하고자 하는 명제도 참임을 증명하는 방법
모순증명법(proof by contradiction) 주어진 명제를 부정한 뒤 그 식을 전개함에 있어서 결론이 모순됨을 보여 결국 명제가 참임을 증명하는 방법 함축 p→q 와 (p∧q)가 동치인 것을 이용하여 증명하는 방법 (p∧q)가 참이라고 한 뒤 그 결과가 모순되면 (p∧q) 가 참이 되고 이와 동치인 함축 p→q 도 참이 됨을 이용
반례에 의한 증명법(proof by counter-example) 주어진 명제에 모순되는 간단한 예를 하나 보임으로써 명제를 증명하는 방법 다른 증명 방법으로 증명하기 어려운 예제들을 증명할 때 유용
재귀법(recursion) 하나의 문제를 그보다 값이 작은 동일한 문제로 계속 단순화시켜 해결하고자 하는 방법 하나의 문제를 그보다 값이 작은 동일한 문제로 계속 단순화시켜 해결하고자 하는 방법 재귀법 문제해결을 위해 규칙필요 초기조건(initial condition) 재귀조건(recursion condition)
재귀 알고리즘 재귀법을 이용한 프로그램 알고리즘 재귀 알고리즘을 이용하여 복잡한 연산을 쉽게 해결 대부분의 프로그램 언어에서 재귀 알고리즘 지원
하노이 탑(tower of Hanoi) 3개의 기둥 중 제일 왼쪽 기둥에 크기가 큰 것이 제일 아래에 있게 원판들이 쌓여있을 때 제일 오른쪽 기둥으로 원판을 옮기는 데 소요되는 최소 이동 횟수를 구하는 문제 추가조건 원판은 한 번에 하나씩만 옮길 수 있다. 원판을 기둥과 기둥으로만 옮길 수 있다. (즉, 바닥에 내려놓을 수 없다.) 크기가 큰 원판은 작은 원판 위에 올 수 없다.
원판이 3개인 하노이 탑의 풀이 원리
프로그램 명령문 순서문 조건문 반복문 명령들을 순서대로 실행 주어진 조건이 참인지 거짓인지에 따라 명령문을 선택하여 실행 조건이 참인 동안 명령문을 반복 실행
프로그램 명령문