Skip to content

0914_ComputationalThinking.md

Latest commit

 

History

History
261 lines (162 loc) · 9.19 KB

0914_ComputationalThinking.md

File metadata and controls

261 lines (162 loc) · 9.19 KB
Raw

Computational Thinking

프로그래밍과 논리/수학

정확하게 확인하는 과정을 수많은 세월 동안 정리해 둔 것이 “증명” 기법이다.

프로그래밍의 어려운 점

  • Hard Logic 논리

  • Hard vs. Soft Logic

    • 직관은 논리적인 느낌을 주는 것

    • 직관의 장점은 (익숙한 상황에서) 빠르다는 것

    • 직관의 단점은 정확하지 않다는 것 (가끔은 익숙한 상황에서도 틀림)

    • 또 다른 단점은 강한 착각을 일으킨다는 것

  • 일상 생활에서는 Soft Logic이 빠르기 때문에 유용

    • 논리적으로 부정확한 표현을 사용하지만, 어떤 의미인지 모든 사람이 이미 알고 있다는 가정이 존재

  • 프로그래밍은 Hard Logic을 사용

    • 프로그래밍 언어의 표현들이 모두 논리학에서 나온 것
    • 사용되는 수많은 알고리즘들을 이해하기 위해서는 Hard Logic이 필요

  • 오해의 근원

    • Soft Logic으로 알고리즘을 이해하려고 하는 것
    • 알고리즘 설명을 봐도 이해가 안 되는 것은 증명을 안 봤기 때문
    • 증명을 봐도 이해가 안되는 것은 직관으로 이해하려고 하기 때문
    • 가끔 직관적으로 이해되는 알고리즘이 있지만 조금만 어려워지면 직관으로 완전한 이해를 얻는 것은 사실상 불가능

[참고]

  • 명제

    • 참이나 거짓을 알 수 있는 식이나 문장.

    • p, q, r, …로 표현.

  • 진릿값

    • 참이나 거짓을 표현.

    • T, F 또는 1, 0

[연산 (결합)]

  • 부정 NOT
    • p가 명제일 때, 명제의 진릿값이 반대
    • ~p 또는 ┐p로 표기 (not p 또는 p의 부정으로 읽음)
  • 논리곱 AND
    • p, q가 명제일 때, p, q 모두 참일 때만 참이 되는 명제
    • p ^ q (p and q, p 그리고 q)
  • 논리합 OR
    • p, q가 명제일 때, p, q 모두 거짓일 때만 거짓이 되는 명제
    • p V q (p or q, p 또는 q)
  • 배타적 논리합 XOR
    • p, q가 명제일 때, p, q 중 하나만 참일 때 참이 되는 명제
    • p ⊕ q (p xor q)

[합성]

  • 연산자 우선 순위

    • ┐ > V, ^ > ->, <->

  • 항진명제 : 진릿값이 항상 참

  • 모순명제 : 진릿값이 항상 거짓

  • 사건명제 : 항진명제도 모순명제도 아닌 명제

  • 조건명제

    • p, q가 명제일 때, 명제 p가 조건(또는 원인), q가 결론(또는 결과)로 제시되는 명제

    • p -> q (p이면 q이다.)

      p q p -> q
      T T T
      T F F
      F T T
      F F T

  • 쌍방조건명제

    • p, q가 명제일 때, 명제 p와 q가 모두 조건이면서 결론인 명제
    • p <-> q (p면 q고, q면 p다.)

  • 조건명제의 역, 이, 대우

    • 역 : q -> p

    • 이 : ┐p -> ┐q

    • 대우 : ┐q -> ┐p

      p q p -> q q -> p ┐p -> ┐q ┐q -> ┐p
      T T T T T T
      T F F T T F
      F T T F F F
      F F T T T T

증명

  • 증명은 정확한 명제식으로 표현할 수 있는 것이라야 함
  • 보통은 정확한 명제식까지 쓰지는 않으나 근본적으로는 명제식으로 바꿀 수 있음
  • 증명에 대한 수많은 오해가 p->q를 p<->q와 혼동하는 것에서 일어남

수학적 귀납법과 증명의 수준

  • 수학적 귀납법의 기본형: P(1)이 참이고, P(n)->P(n+1)이 참이면 P(n)은 모든 자연수 n에 대해서 참이다.
  • 수학적 귀납법의 강한 형태: P(1)이 참이고, P(1) ^ P(2) ^ … ^ P(n) -> P(n+1)이 참이면 P(n)은 모든 자연수 n에 대해서 참이다.

Trivial Proof, Vacuous Proof

1. logic and proof

  • ~ (~p ^ q) V q

  • (~p V q) ^ (p ^ ~q)

  • p ^ (p V q)

  • (p ^ ~q) V (p ^ q)

  • (p ^ ~q) -> r

  • ∀x ∈ R, x**2 >= x

  • ∃x ∈ R, x**2 < x

  • n이 짝수이면, 3n + 5는 홀수

  • m이 짝수이고 n이 홀수이면, 2m + 3n은 홀수

  • n**2이 짝수이면, n은 짝수

  • n**2이 3의 배수이면, n은 3의 배수

2. number and expression

컴퓨터는 0/1을 표현할 수 있는 비트들을 모아 수를 표현

k개의 비트를 사용하면 어떤 경우든 최대 2^k 가지의 값을 표현하는 것이 가능

10진수로 k자리를 쓰면 0부터 10**(k-1)까지 표현이 가능한 것과 완전히 동일한 과정

어떤 값 n을 표현하기 위해서는 몇 개의 비트가 필요할까?

2k - 1 >= n 이 성립해야 함 -> 즉, 2k >= n + 1

k >= log(n+1) -> 약 log n 비트가 필요

x = log n 과 2**x = n 은 같은 말

log n 이란

  1. 2의 몇 승이 n이 되느냐의 답
  2. n을 표현하는 데 몇 비트가 필요한가의 답
  3. 1로 시작해서 계속 두 배를 할 때 몇 번 하면 n이 되느냐의 답
  4. n을 2로 계속 나눌 때 몇 번 나누면 거의 1이 되느냐에 대한 답

x = log n 일 때 x와 n을 비교하면 x가 더 작고, n이 커질수록 엄청나게 달라진다

컴퓨터 분야에서 로그의 밑은 항상 2

32비트 컴퓨터의 주소공간은 2**32

  • 2진수 표현에서 log n 비트로 표현할 수 있는 숫자 범위
  • n이 충분히 큰 값일 때 다음 중 어느 값이 더 큰가?
    • 2n ( ) n**2
    • 2**(n log n ) ( ) n!
  • x = log_a(yz)일 때 x를 2를 밑으로 하는 로그들로 표현하시오.
  • 역함수를 구하시오
    • f(x) = log(x - 3) - 5

3. Set and Combination theory

두 집합 A와 B에 대해 A가 B의 부분집합임을 증명한다는 것은 A의 임의의 원소가 B에 포함됨을 보이는 것과 같다.

두 집합 A와 B가 같다는 것을 증명하기 위해서는 A가 B의 부분집합이고 B가 A의 부분집합임을 증명하면 된다.

조합론은 경우의 수를 따지는 문제들을 보통 말한다

조합은 개수는 C를 이용하여 표현하기도 하지만 괄호 표현을 더 많이 쓴다.

  • nCk + nC(k-1) = (n+1)Ck
  • 귀류법을 이용하여 (A - B) ∩ (B - A) = ∅임을 증명하라
    • 명제의 참을 증명
    • 그 명제의 부정을 참이라 가정하고, 모순, 거짓임을 보임
    • ┐(p -> q) :F
    • p -> q : T
  • 8 x 8 체스 판에 말 두개를 놓으려고 한다. 아무 곳에나 놓아도 되지만 한 칸에 두개가 들어가지는 못한다. 가능한 방법은 모두 몇가지인가?
  • 비밀번호를 0부터 9까지의 숫자만 가지고 만든다고 하자. 4개 이상 6개 이하의 숫자를 쓸 수 있다고 할 때 가능한 비밀번호의 가지수는 얼마인가?
  • 52개의 카드를 이용해서 만들 수 있는 5개 카드의 조합은 몇가지인가?
  • 52개의 카드를 이용해서 만들 수 있는 5개 카드 조합 중 같은 무늬의 카드가 정확히 3개인 경우는 몇가지인가?
  • 52개 카드에서 5개 카드 조합을 만들 때, 숫자가 같은 카드가 한 쌍도 없는 경우는 몇가지인가?

4. basic formula

알고리즘의 시간 복잡도를 표현할 수 있는 다양한 수식들이 존재한다.

풀이법을 익혀 두어야 알고리즘의 시간 복잡도를 계산할 수 있고, 알고리즘이 시간이 얼마나 걸릴지 예측할 수 있다.

  • T(n) = T(n - 1) + 1, T(0) = 1
  • T(n) = T(n - 1) + n, T(0) = 1
  • T(n) = T(n - 1) + log n, T(0) = 1
  • T(n) = T(n/2) + 1, T(1) = 1
  • T(n) = T(n/2) + n, T(1) = 1
  • T(n) = 3T(n/2) + n, T(1) = 1
  • T(n) = T(n - 1) + (1/n), T(1) = 1

5. Recursion

재귀란 자기 자신을 호출하는 함수, 그럼 끝날 수가 있는가?

함수는 입력이 있으며, 자기 자신의 입력과 동일한 입력으로 자기 자신을 호출하면 당연히 끝나지 않음

하지만, 다른 입력으로 호출하면 끝날 수 있음

함수란 어떤 문제를 해결하는 방법을 코딩한 것

함수가 어떤 문제의 단 한 케이스만을 해결하는 것이 아님

제대로 코딩 된 것이라면 해결하는 문제의 모든 케이스들을 해결해야 함

수학적 귀납법 증명 사용 가능

  1. n이 0일 때 문제를 풀 수 있음
  2. n-1 에서 문제를 풀 수 있으면 n 에서도 문제를 풀 수 있다

위 두 가지가 사실이면 모든 가능한 n에 대해 문제를 풀 수 있다는 것이 사실

  • 피보나치 수열: F(n) = F(n-1) + F(n-2), F(1)= F(2) = 1

6. DP

간단하게 설명하면 재귀 함수에서 동일한 입력의 함수 호출이 반복적으로 일어날 때 그 결과 값을 저장해 두고 불러 쓰는 것이다. (Memoization)

최초 입력에서 파생되는 모든 가능한 입력에 대한 답을 모두 저장할 수 있는 메모리가 있어야 한다.

단순히 재귀에서 저장된 값을 찾아보는 것으로도 가능하지만, 결과 값을 순서를 정해서 계산할 수도 있다. (Dynamic Programming)

  • Memoization 피보나치 수열: F(n) = F(n-1) + F(n-2), F(1)= F(2) = 1

  • Dynamic Programming 피보나치 수열 : F(n) = F(n-1) + F(n-2)