[Computational Thinking] 프로그래밍과 논리/수학

■당신이...

        - Problem Solving 문제들을 봤는데 어떻게 풀어야 하는지 전혀 감이 오지 않는다.

        - 도구나 라이브러리는 잘 쓰는데 프로그램 처음부터 짜려면 막막하다. 

        - 어떻게 프로그램을 짜면 더 빠른지, 더 느린지 전혀 감이 없다.

        - Problem Solving 자료를 보고 시간을 들여도 발전이 없다.

---

■ 하나라도 일치하는 상황이 있다면..., 어쩌면 ...

       - Problem Solving을 본격적으로 공부할 준비가 안된 것일 수 있다.

 

※ 필요한 것

        - 논리적으로 전확하게 확인하는 과정 연습

              ☞ 되는 것 같다 or 공식 외우기 말고 정확하게 확인해 본적이 있는지?

              ☞ 코드 작성 전에, 정확한 결과가 나올 것인지, 얼마나 빠를 것인지 미리 알 수 있는지?

              ☞ 정확히 확인하는 훈련이 되어 있지 않으면, 단순 작업 이상의 코드를 작성하기 어렵고,

                   다른 사람의 코드를 고치는 것도 매우 어렵다.

        - 증명 기법은 딱딱한 것이 아닌 기발한 아이디어들의 집합이고 "이해하면 재미있는 그림"들과 같다.

 

---

■ 프로그래밍의 어려운 점 두가지

        - 프로그래밍 언어 문법과 라이브러리 사용

        - 논리(Hard logic)

 

 

문법과 라이브러리 사용은 정확하게 이해할 수 있어야 하고

 

다양하게 알고 활용할 줄 알아야 코드 작성이 수월해진다.

 

최초로 배울 때에는 다소 어려움이 있지만 훈련에 비례하여 실력이 느는 경향이 있다고 한다.

 

 

 

 

∴ Hard vs. Soft Logic

 

Soft Logic : 선 후행 관계를 때에 따라 바꿀 수 있는 관계

 

직관적으로 판단되는 것과 비슷한 맥락이라고 생각한다.

 

그저 논리적인 느낌을 주는 것이며 빠르게 판단할 수 있지만 정확하지 않다.

 

또 다른 단점은 강한 착각을 일으킨다.

 

 

Hard Logic : 물리적으로 선 후행 관계를 바꿀 수 없는 관계

 

프로그래밍은 Hard Logic을 사용한다.

 

프로그래밍 언어의 표현들이 모두 논리학에서 나왔으며,

 

사용되는 수많은 알고리즘들을 이해하기 위해선 Hard Logic이 필요하다.

 

증명을 봐도 이해가 안되는 것은 직관(Soft Logic)으로 이해하려고 하기 때문이며,

 

직관으로 이해되는 알고리즘도 있긴 하지만 조금만 어려워져도 완전한 이해를 얻는것은 사실상 불가능해

 

Hard Logic을 통하여 이해하려는 태도가 필요하다.

---

■ 명제

 

p(가정) → q(결론) 라는 명제가 있을 때,

 

- 역 : q → p / 가정과 결론을 바꾸어 놓은 명제

- 이 : ~p → ~q / 가정과 결론에 각각 부정을 취한 명제

- 대우 : ~q → ~p / 결론의 부정을 가정으로 하고, 가정의 부정을 결론으로 하는 명제

 

명제가 참이면 대우 또한 참이다.

 

명제에서 p(가정)가 거짓이면 명제는 항상 참이다. (Vacuous Proof)

 

강의에서 들은 예로 설명하자면,

 

p : 시험에 통과하면 -> q : 치킨을 사주겟다고 약속을 했다.

 

p가 거짓 즉, 시험에 통과하지 못했을 때 치킨을 사주지 않는 것은 약속을 지킨 것(참)이다.

 

또한, 시험에 통과하지 못했는데 치킨을 사주는것 또한 약속을 어기지는 않았으니 참이다. 

 

그리고 명제의 q(결론)가 항상 참이면 명제는 참이다. (Trivial Proof)

---

■ 수학적 귀납법

        - 기본형 : P(1)이 참이고, P(n) → P(n+1)이 참이면 P(n)은 모든 자연수 n에 대해서 참이다.

        - 강한 형태 : P(1)이 참이고, P(1) ∧ P(2) ∧ ··· ∧ P(n) → P(n+1)이 참이면 P(n)은 모든 자연수 n에 대해서 참이다.

 

마찬가지로 강의에서 들었던 예로

int sum(int x){
	if(x <= 0) return 0;
	return x + sum(x-1);
}

위와 같은 재귀함수가 있다고 가정을 하자.

 

직관적으로 이해할 수 있을 정도로 간단한 코드이다.

 

x가 0 또는 음수이면 0을 반환하고, 그 이상이면 1부터 x까지 모두 더하는 함수이다.

 

하지만, 증명을 하라고 하면, 그저 "답이 맞는것이 당연하다"라고 말하는 것으로는 충분하지 않다.

 

 

증명을 하기 위해서는 증명이 가능한 명제를 만들어야 한다.

 

"sum(x)가 리턴하는 값은 1 + 2 + ··· + x 의 값과 항상 같다" 라고 명제를 세우면

 

이제 수학적 귀납법을 적용할 수 있다.

 

P(1) : "sum(1)의 리턴값은 1이다"를 증명하면 되는데, 그냥 코드에 1을 대입하면 1을 리턴함을 알 수 있으므로 참이다.

 

P(n) → P(n+1) : P(n)이 참이라고 가정하면 P(n)은 sum(n)이고 이는 1 + 2 + ··· + n와 항상 같다.

 

                    P(n+1)은 n+1 + sum(n)을 리턴한다. 즉, (n+1) + 1 + 2 + ··· + n 이므로 

 

                    P(n)이 참이면 P(n+1)도 참이므로 수학적 귀납법에 의해 명제는 참이 된다.

 

---

[참고] : https://swexpertacademy.com/main/learn/course/subjectList.do?courseId=AVuPCwCKAAPw5UW6