프로그래밍과 논리/수학
(1) 논리와 증명
직관 : 익숙한 상황에서 빠를 수 있지만, 틀리거나 착각을 일으킬 수 있음
프로그래밍에는 직관이 아닌 "논리"가 중요하다.
soft logic, 직관으로 알고리즘을 이해하고자 한다면 오해가 생기고 이해가 어려워질 수 있음.
hard logic으로 프로그래밍을 해야 한다!
♧ 'p이면 q이다' 라는 명제에서 p가 거짓이면 이 명제는 항상 참이다.
"증명"은 정확한 명제식으로 표현할 수 있는 것이어야 함.
p→q, p↔q를 혼동하지 않도록 주의하기!
♣ 수학적 귀납법
=> P(n)이 참인 것은 중요하지 않음. P(n)이 참일 때 P(n+1)이 참인 그 관계를 증명하는 것이 목적이다.
=> 어떤 상황에 대해 수학적 귀납법을 쓰고자 하면, 우선 증명이 가능한 명제를 만들고 그 명제에 대해 적용.
기본형 : P(1)이 참이고, P(n) → P(n+1)이 참이면 P(n)은 모든 자연수 n에 대해서 참이다.
강한 형태 : P(1)이 참이고, P(1)∧P(2)∧...∧P(n) → P(n+1)이 참이면 P(n)은 모든 자연수 n에 대해서 참이다.
e.g. sum(x)가 수의 합을 계산한 결과를 낸다는 사실을 증명하고자 한다.
① 명제 : "sum(x)가 리턴하는 값은 1+2+...+x의 값과 항상 같다"
② P(1)이 참이다 : "sum(1)이 리턴하는 값은 1이다" 증명.
③ P(x) → P(x+1)이 참이다 : "sum(x-1)이 1+2+...+(x-1)을 리턴하면, sum(x)는 1+2+...+x를 리턴한다" 증명
(2) 수와 표현
(3) 집합과 조합론
(4) 기초 수식
(5) 재귀
(6) 동적 프로그래밍
(7) 조합론 프로그램 과제
(8) 기초 알고리즘 프로그램 과제
---공부ing---
