Computational Thinking
2019. 03. 11 (Mon)
I. 증명
정확한 명제식으로 표현할 수 잇는 것이어야 함
수학적 귀납법에서 필요한 것은 P(n) -> P(n+1)이 참인것을 보이기만 하면 되므로 P(n)이 참인것은 가정으로 한다.
귀납법
명제를 참이라 가정하고 접근. P(1)이 참이고, P(n) -> P(n+1)이 참임을 증명
귀류법
명제를 거짓이라 가정하고 접근
수식이나 논리를 증명이 가능한 명제로 만들어야 함
바로 증명하기가 힘들면 대우를 사용
혹은 경우에 따라 나눠서 증명
II. 수의 표현
k를 표현하기 위해 컴퓨터에서 1+logk 만큼의 bit가 필요
####log n 이란
- 2의 몇 승이 n이 되는가
- n을 표현하는데 몇 비트가 필요한가
- 1로 시작해서 두 배를 몇 번 하면 n이 되는가
- n을 2로 나눌 때 몇 번 나눠야 1이 되는가
컴퓨터 분야에서 log의 base는 항상 2
병합정렬: n log n
이진탐색: log n
III. 집합과 조합론
두 집합 A가 B의 부분집합임을 증명: A의 임의의 원소가 B에 포함됨을 보이면 된다.
두 집합 A와 B가 같다는 것을 증명: A가 B의 부분집합이며, B가 A의 부분집합임을 보이면 된다.
(1) 조합
순서가 없으면서 겹치지 않는 집합
n개의 원소의 집합에서 k개의 원소를 추출하는 방법
(2) 이항 계수
1. 논리 전개
3군데 에서 3개의 x 추출, 3군데에서 0개의 y 추출
3군데 에서 2개의 x 추출, 3군데에서 1개의 y 추출
…
2. 의미
각 항의 계수가 n개의 원소의 집합에서 k개의 원소를 추출하는 논리와 같다
점화식: nCr = n-1Cr + n-1Cr-1
- n-1Cr-1: 첫번째를 포함한다 치고 나머지 n-1에서 r-1개를 뽑아내는 경우
- n-1Cr: 첫번째를 포함하지 않는다 치고 나머지 n-1에서 r개를 뽑아내는 경우
또한 각 항을 모두 더하면 2^n: n개의 원소를 가진 집합의 부분 집합 갯수
파스칼의 삼각형…