알고리즘

(1)

2019 년 봄학기 강원대학교 컴퓨터과학전공 문양세

알고리즘 (Algorithm)

 필요한 수학의 복습

(2)

수학 ~ 머리 아파 ~

그래서 ~, 어려운 것 빼고 ~

고등학교 시절에 , 이산수학 과목에서 , 아주 쉬운 것으로만 복습

복습 내용

표기법 ( 가 머야 ?)

함수

수학적 귀납법

정리 , 보조정리

로그

집합

순열과 조합

확률

필요한 수학의 복습

(3)

표기법

올림함수 (ceiling function)

x: 주어진 실수 x 보다 크거나 같은 가장 작은 정수

예 : 9/2 = 5, 3.3 = 4, 7 = 7, -3.3 = -3

내림함수 (floor function)

x: 주어진 실수 x 보다 작거나 같은 가장 큰 정수

예 : 9/2 = 4, 3.3 = 3, 7 = 7, -3.3 = -4

시그마를 사용한 합의 표현

100

1

1 2 100

i

i i



   



1

( 1)

1 2 2

n i

i i n n n



     



100 2 2 2 2 2

1

1 2 100

i

i i



   



² ² ² ² ²

1

1 2

( 1)(2 1)

n i

i i n

n n n



   

 





4 ⁱ

ij  ?



(4)

함수 (function)

함수 f 는 변수 x 를 유일한 값 f(x) 로 연관 짓는 규칙 또는 법칙이다 . 함수는 튜플 (tuple, ordered pair) 을 결정하며 , 이들 튜플을 좌표에 그 리면 그래프가 된다 .

정의역 : x 값의 범위 (domain)

공변역 ( 변역 , 공역 ): 함수 f 가 정의되는 값의 범위 (codomain)

치역 : 정의역이 함수 f 에 의해 매핑된 범위 (range)

( )

2

f x  x

y x 

2

(5)

수학적 귀납법 (mathematical induction) (1/2)

어떤 등식이 모든 n 에 대해서 성립함을 보이기 위해서 , 가능한 모든 n 을 등식에 대입하여 증명할 수는 없다 .

수학적 귀납법 :

주어진 등식이 n=1 일 때 성립함을 증명하고 , n 일 때 성립한다고 가정한 후 , n+1 일 때 성립함을 증명한다 .

그러면 , 도미노의 원리와 같이 모든 n 에 대해서 성립하는 것이다 .

(6)

수학적 귀납법 (mathematical induction) (2/2)

수학적 귀납법을 이용한 증명 과정

귀납 기본 (Induction base):

n=1(

혹은 n=0) 에 대해 등식이 성립함을 증명한다 .

귀납 가정 (Induction hypothesis):

임의의 n 에 대해 등식이 성립한다고 가정한다 .

귀납 단계 (Induction step):

등식이 n+1 에 대해서도 성립함을 증명한다 .

(7)

수학적 귀납법 예제 (1/2)

모든 양의 정수 n 에 대해서 다음 등식이 성립함을 증명하라 .

증명

Induction base: n=1 일 때 성립한다 .

Induction hypothesis: n 일 때 성립한다고 가정한다 .

Induction step: 다음 과정에 의해 n+1 일 때 역시 성립한다 .

1

( 1) 2

n

i

i n n



 



1

1(1 1) 2 1

i



  



 

1

1 1

2

( 1) 2 2 ( 1)

2 2

( 1) ( 1) 1 ( 1)( 2)

3 2

2 2 2

n n

i i

n n n

i i n

n n



 

 

    

  

 

  

 

(8)

수학적 귀납법 예제 (2/2)

모든 음이 아닌 정수 n 에 대해서 다음 등식이 성립함을 증명하라 .

증명

Induction base: n=0 일 때 성립한다 .

Induction hypothesis: n 일 때 성립한다고 가정한다 .

Induction step: 다음 과정에 의해 n+1 일 때 역시 성립한다 .

1 0

2 2 1

n i n

i





 



0 0 0 1

0

2 2

ⁱ

1 2 1

i





   



1 1 1 1

0 0

( 1) 1

1 2

2 2 2 2 1 2

2 2 1 2 1 2 1

n n

i i n n n

i i

n

n n

   

 

 

    

      

 

(9)

정리 (Theorem) 와 보조정리 (Lemma) (1/3)

정리 (theorem)

정리란 참 (true) 으로 밝혀진 명제이다 .

A statement that has been proven to be true.

공리 (axiom, postulates)

증명된 정리 혹은 증명하고자 하는 정리의 가정이다 .

Assumptions (often unproven) defining the structures about which we are reasoning.

(10)

정리 (Theorem) 와 보조정리 (Lemma) (2/3)

보조정리 (lemma)

 다른 정리를 증명하는데 사용하는 간단한 정리이다 .

 A minor theorem used as a stepping-stone to proving a major theorem.

“ 복잡한 내용이 정리이고 , 간단한 내용이 보조정리”를 의미하는 것은 아님 !

따름정리 (corollary)

 어떤 정리가 증명되면 , 이에 의하여 자연스럽게 증명되는 정리이다 .

 A minor theorem proved as an easy consequence of a major theorem.

(11)

정리 (Theorem) 와 보조정리 (Lemma) (3/3)

가설 (conjecture)

증명되지는 않았지만 참으로 믿어지는 명제이다 .

A statement whose truth values has not been proven.

(A conjecture may be widely believed to be true, regardless.)

이론 (theory)

주어진 공리 (axiom) 으로부터 증명이 가능한 모든 정리 (theorem) 의 집합이 다 .

The set of all theorems that can be proven from a given set of axioms.

(12)

로그 (Logarithm) (1/2)

상용로그 (common logarithm): 밑이 10 인 로그

로그의 주요 특성 [ 위키 ]

log10 1  log10,000 log10 

⁴

 4

log

log log

1. log 1 0 2.

3. log ( ) log log 4. log log log 5. log log

6.

a

a a

a x

a a a

y

a a

y x

a x

xy x y

x x y

y

x y x

x y



 

   

   



x

log

y a    x

a

y

(13)

로그 (Logarithm) (2/2)

자연로그 (natural logarithm): 밑이 e 인 로그 ( 위키 )

밑이 자연대수 e(= 2.718281828459…) 인 로그

예 :

적분을 사용한 자연로그 개념 :

함수 1/x 에서 , ln x 는 1 과 x 사이의 면적을 나타낸다 .

log 10 ln10 2.3025851

_e

 

1

1 ln a  

^a

x

5 1

1 ln5   x

(14)

집합 (Set) (1/2)

집합 (set) 이란 순서를 고려하지 않고 중복을 고려하지 않는 객체 ( 원소 , 멤버 ) 들의 모임이다 .

집합의 표현 방법 : 원소 나열법 , 조건 제시법

원소 나열법 ( 예 : {…, -3, -2, -1, 0, 1, 2, 3, …})

조건 제시법 ( 예 : {x | x is integers})

집합의 항등 : 동일한 원소들로 이루어진 두 집합은 동일하다 . 주요 표기법 :

xS: x 는 집합 S 의 원소이다 .

: 공집합 (empty set) ( 원소가 하나도 없는 유일한 집합 )

(15)

집합 (Set) (2/2)

합집합 : AB = {x | xA  xB}

{2,3,5}{3,5,7} = {2,3,5,3,5,7} ={2,3,5,7}

교집합 : AB = {x | xA  xB}.

{2,4,6}{3,4,5} = {4}

차집합 : A  B = x  xA  xB

{1, 2, 3, 4, 5, 6}  {2, 3, 5, 7, 11} = {1, 4, 6}

(16)

순열과 조합 (1/3)

순열 (Permutation):

주어진 n 개 물체 중에서 k 개를 선택하여 나열하는 방법의 수

조합 (Combination):

주어진 n 개 물체 중에서 k 개를 선택하는 방법의 수

( , ) ( 1) ( 1) !

( )!

P n k n n n k n

        n k



( , ) !/ ( )! !

( , )

( , ) ! !( )!

n P n k n n k n

C n k

P k k k k n k

k

  

        

(17)

순열과 조합 (2/3)

조합의 예제 : 10 명으로 구성된 팀에서 경기에 나갈 선수 5 명을 선발하 는 방법은 모두 몇 가지인가 ?

10 명 중에서 5 명을 선발하되 , 5 명의 순서는 고려할 필요가 없으므로 ,

10 개의 원소 집합에서 5- 조합의 수를 구하는 문제임

결국 , 252 가지 이다 .

10! 10!

(10,5) 252

5!(10 5)! 5! 5!

C   

 

(18)

순열과 조합 (3/3)

순열의 예제 : 100 명이 참여한 경품 행사에서 , 1 등 , 2 등 , 3 등을 한 명 씩 선발하는 방법은 모두 몇 가지 인가 ?

3 등을 선발하는 방법 = 100 가지

결국 , 100 x 99 x 88 = 970,220 가지 이다 .

순열을 활용하면… .

100 명 중에서 세 명을 뽑아서 순서대로 나열하는 방법…

결국 , P(100,3) = 970,220 가지 이다 .

(19)

확률 (Probability) (1/2)

표본공간 (sample space) 혹은 모집단 (population):

가능한 모든 결과의 집합 ( 예 : 주사위의 경우 , 1, 2, 3, …, 6) 사건 (event): 표본 공간의 부분집합

( 주사위에서 짝수가 나오는 사건의 집합 )

원소사건 : 단지 하나의 원소만 가지는 부분집합 ( 주사위에서 1 이 나오는 사건 )

(20)

확률 (Probability) (2/2)

정의 : 표본공간이 n 개의 다른 결과를 가진 {e

₁

, e

₂

, ..., e

_n

} 이라 하자 . 각 사건 S 에 실수 p(S) 를 지정하는 함수가 다음 조건을 만족하면 ,

이를 확률함수 (probability function) 라 한다 .

1  i  n 에 대해서 , 0  p(

e

_i)  1 이다 .

p(

e

₁) + p(

e

₂) + … + p(

e

_n)  1 이다 .

사건 S 에 대한 p(S) 는 S 에 속하는 원소사건들의 확률의 합이다 . ( 예 : p(S) = p(

e

₁) + p(

e

₂) + p(

e

₇) if S = {

e

₁,

e

₂,

e

₇})

(21)

생판 처음 본 것이라고요 ?

고등학교 문과 수학의 일부분에 해당하는 쉬운 내용입니다 .

혹 어렵다고 생각되시면 ,

고등학교 참고서를 들춰보세요 ~