[Algorithm] 1-2. Mathematical Background

저번 시간에는 알고리즘을 설계하고 분석하는 방법에 배웠다.

이번 시간에는 알고리즘에 자주 사용되는 수학적 지식에 대해 간단하게 살펴보도록 하겠다.

 

 

 

 

● Mathematics

1. Series

- 급수를 뜻하고, 수열의 합을 말한다.

- 기하급수, 무한급수 등이 있겠다.

 

 

2. Arithmetic series

- 산술 급수를 뜻하고, 연속된 정수의 합을 나타낸다.

 

3. Polynomial Series

- 제곱들의 합이다.

 

 

4. Power of 2

 

 

5. Arithmetic-Geometric Series

 

 

 

● Logic

- Logic은 자연어로 적힌 문제들을 공식화해서 우리가 더 정확하게 이성적으로 사고할 수 있도록 도와준다.

 

1.

 

 

2. 

 

 

3.

 

 

* 드모르간의 법칙

- 논리곱의 전체 부정은 각각의 부정의 논리합이다.

- 논리합의 전체 부정은 각각의 부정의 논리곱이다.

 

 

 

● Proof

① Counterexample (반례)

- 어떤 명제가 참이 아님을 증명하는 방법.

- 이것으로 참이 아님을 증명할 수 있는 잘 알려진 명제

- 예: 모든 소수는 홀수이다

  → 반례 : 2는 짝수인 소수이다.

 

 

② Contraposition (대우)

 

 

 

③ Contradiction (모순)

- 모순을 이용한 증명법

- 귀류법 p → q가 주어졌을 때, p → ~q라고 가정하고 논리를 계속 펼쳐보면 ~p가 나온다.

  그럼 p와 ~p는 양립할 수 없는 모순이므로 p → q이다. ~p →~q와 같아서 본질적으로는 대우와 같은 증명방법이다.

 

 

④ Mathematical Induction (수학적 귀납법)

- 수학에서 어떤 명제나 식들을 증명할 때 많이 쓴다.

위 식을 증명할 때 수학적 귀납법을 쓰는 것을 예로 보겠다.

i) 맨 먼저 i = 1일 때 (좌변) = 1, (우변) = 1 x 2 / 2 = 1이어서 성립한다.

ii) n = k일 때 성립한다고 가정하자.

iii) n = k + 1일 때

iv) 따라서 모든 자연수에 대하여 성립한다.

 

 

 

 

다음 시간에는 알고리즘 문제를 분석하는 방법에 대해 자세히 알아보도록 하겠다.