자료구조를 위한 수학적 기초

Relation(관계)

• 관계는 두 집합의 데카르트 곱의 부분집합. 집합 ( A )와 ( B )에 대해 관계 ( R )은 다음과 같이 정의됨: [ R \subseteq A \times B ] 여기서 ( A \times B = { (a, b) \mid a \in A, b \in B } )

관계의 성질

1. Reflexive: ( R )이 reflexive이려면 ( \forall a \in A, (a, a) \in R )
   • 예시:
     관계 $R$이 $\leq$(작거나 같다)일때, 모든 수 $a$에 대해 $a\leq a$가 참 - reflexive
2. Symmetric: ( R )이 Symmetric이려면 ( \forall a, b \in A, (a, b) \in R \implies (b, a) \in R )
   • 예시:
     관계 ( R )이 “a는 b의 친구”일 때, ( a = b )이면 ( b = a )가 항상 참이므로 symmetric.
3. Antisymmetric: ( R )이 antisymmetric이려면 ( \forall a, b \in A, (a, b) \in R \land (b, a) \in R \implies a = b )
   • 예시:
     관계 ( R )이 $\leq$(작거나 같다)일 때, ( (a, b) \in R )이고 ( (b, a) \in R )이면 ( a = b )가 되어야 하므로 antisymmetric.
4. Transitive: ( R )이 transitive이려면 ( \forall a, b, c \in A, (a, b) \in R \land (b, c) \in R \implies (a, c) \in R )
   • 예시:
     관계 ( R )이 “a는 b의 조상”일 때, ( a )가 ( b )의 조상이고 ( b )가 ( c )의 조상이라면 ( a )는 ( c )의 조상이므로 transitive.

관계의 종류

1. Equivalence Relation (동치 관계):
   • Reflexive, Symmetric, Transitive 성질을 모두 만족하는 관계.

   • 관계 ( R )이 “같다”일 때, ( a = a ) (Reflexive), ( a = b \implies b = a ) (Symmetric), ( a = b \land b = c \implies a = c ) (Transitive).

   • 예시
     • mod equivalene: ( a \equiv b \pmod{n} )는 ( n )으로 나눈 나머지가 같을 때 성립.
       • Reflexive: ( a \equiv a \pmod{n} )
       • Symmetric: ( a \equiv b \pmod{n} \implies b \equiv a \pmod{n} )
       • Transitive: ( a \equiv b \pmod{n} \land b \equiv c \pmod{n} \implies a \equiv c \pmod{n} )
2. Partial Order (부분 순서):
   • Antisymmetric, Transitive 성질을 만족하는 관계.
   • 예시:

     • “작거나 같다” 관계 ( R )이 “작거나 같다”일 때, ( a \leq b \land b \leq a \implies a = b ) (Antisymmetric), ( a \leq b \land b \leq c \implies a \leq c ) (Transitive).

     • “키가 더 크고 몸무게가 더 많다”

       • Antisymmetric: ( a )의 키와 몸무게가 ( b )의 키와 몸무게와 같다면, ( a )와 ( b )는 동일한 사람이어야 함.
       • Transitive: ( a )가 ( b )보다 키가 크고 몸무게가 많으며, ( b )가 ( c )보다 키가 크고 몸무게가 많다면, ( a )는 ( c )보다 키가 크고 몸무게가 많음.
3. Total Order:
   • Partial Order의 모든 성질을 만족하며, 추가로 모든 ( a, b \in A )에 대해 ( a \leq b ) 또는 ( b \leq a )가 성립하는 관계.
   • 예시:
     관계 ( R )이 “작거나 같다”일 때, ( a \leq b ) 또는 ( b \leq a )가 항상 성립하므로 Total Order.
     • “키가 더 크고 몸무게가 더 많다” 는 어떤 관계에 대해서는 성립하지 않을 수 있기 때문에 total order가 아님(키만 더 크거나, 몸무게만 더 많은 경우 존재)

Recursive Relation (재귀적 관계)

• 재귀적 관계는 자기 자신을 활용하여 정의되는 함수.
• 예시:
  • 피보나치 수열 관계: [ T(n) = \begin{cases} 0 & \text{if } n = 0
    1 & \text{if } n = 1
    T(n-1) + T(n-2) & \text{if } n > 1 \end{cases} ]
  • 자연수의 팩토리얼 관계: [ T(n) = \begin{cases} 1 & \text{if } n = 0
    n \cdot T(n-1) & \text{if } n > 0 \end{cases} ]
• Closed Form
  • Closed Form는 재귀적 관계를 명시적으로 표현한 형태로, 반복적인 계산 없이 결과를 구할 수 있음.
  • 예시:
    • (T(n) = T(n-1) + n; \ T(1)=1)
  • Closed Form: ( T(n) = \frac{n(n+1)}{2} )

Tower of Hanoi 문제

• 정의:
  • Tower of Hanoi는 ( n )개의 원판을 한 기둥에서 다른 기둥으로 옮기는 문제로, 다음 규칙을 따름:
    1. 한 번에 하나의 원판만 옮길 수 있음.
    2. 더 큰 원판이 더 작은 원판 위에 놓일 수 없음.
    3. 원판은 항상 세 개의 기둥 중 하나에 있어야 함.
• 재귀적 관계:

  • 하노이 타워 문제는, ( n - 1 )개의 원판을 경유하는 기둥에 옮기고, 가장 큰 원판을 목적 기둥에 옮긴 다음 다시 ( n - 1 )개의 원판을 목적 기둥에 옮기는 문제로 표현할 수 있음(Recursive)

  • ( T(n) )은 ( n )개의 원판을 옮기는 데 필요한 최소 이동 횟수: [ T(n) = T(n-1) + 1 + T(n-1) = 2T(n-1) + 1 ]

• Closed Form:
  • ( T(n) = 2^n - 1 )

Mathmatical Proof

Deduction

• Deduction은 일반적인 원리나 법칙에서 특정한 결론을 도출하는 논리적 추론 방법.
• $P \Rightarrow Q$, $Q \Rightarrow R$, then $P\Rightarrow Q$
• 예시:
  • ( P )가 “모든 사람은 죽는다”이고, ( Q )가 “소크라테스는 사람이다”일 때, ( P \land Q )가 참이면 ( R )이 “소크라테스는 죽는다”가 참임을 보일 수 있음.

Contradiction

• Contradiction은 어떤 명제가 참임을 보이기 위해 그 명제가 거짓이라고 가정한 후, 논리적 모순을 도출하는 방법.
• 예시:
  • ( \sqrt{2} )가 무리수임을 증명:
    1. ( \sqrt{2} )가 유리수라고 가정. 즉, ( \sqrt{2} = \frac{p}{q} )이며, ( p )와 ( q )는 서로소 정수.
    2. 양변을 제곱하면 ( 2 = \frac{p^2}{q^2} ), 즉 ( p^2 = 2q^2 ).
    3. ( p^2 )는 2의 배수이므로 ( p )도 2의 배수. 따라서 ( p = 2k )로 표현 가능.
    4. ( p^2 = 4k^2 )를 ( 2q^2 )에 대입하면 ( 2q^2 = 4k^2 ), 즉 ( q^2 = 2k^2 ).
    5. ( q^2 )도 2의 배수이므로 ( q )도 2의 배수.
    6. ( p )와 ( q )가 모두 2의 배수이므로 서로소가 아니라는 모순 발생.
    7. 따라서 ( \sqrt{2} )는 무리수임이 증명됨.

Mathematical Induction

• Mathematical Induction(수학적 귀납법) 은 특정한 사례들로부터 일반적인 결론을 도출하는 논리적 추론 방법.
• 수학적 귀납법은 다음 두 단계를 통해 증명함:
  1. 기초 단계(Base Case): 명제가 특정 단계에서 참임을 보임.
  2. 귀납 단계(Inductive Step): ( n = k )에서 명제가 참이라고 가정하고, ( n = k + 1 )에서도 참임을 보임.
• 예시:
  • ( 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} ) 증명:
    1. 기초 단계: ( n = 1 )일 때, ( 1 = \frac{1(1+1)}{2} )이므로 참.
    2. 귀납 단계: ( n = k )에서 ( 1 + 2 + \cdots + k = \frac{k(k+1)}{2} )라고 가정.
       ( n = k + 1 )일 때: [ 1 + 2 + \cdots + k + (k+1) = \frac{k(k+1)}{2} + (k+1) ] [ = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2} ] 따라서 ( n = k + 1 )에서도 참임을 보였으므로, 수학적 귀납법에 의해 명제가 성립.

---

해당 포스트는 서울대학교 컴퓨터공학부 강유 교수님의 자료구조 25-1학기 강의를 정리한 내용입니다.