알고리즘

(1)

알고리즘 (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)

Recurrence Relations ( 점화 관계 )

수열 {a_n} 에 대한 점화 관계란 a_n 을 이전의 항들인 a₀, …, a_n−1 들을 사용하여 표 시하는 등식이다 .  대표적인 예가 피보나치 수열

특정 수열이 주어진 점화 관계를 만족하면 해당 수열을 그 점화 관계의 해라 한 다 .

주어진 점화 관계는 하나 이상의 많은 해를 가질 수 있다 . 점화 관계 ( 점화식 ) 예제 :

Consider the recurrence relation

a

_n = 2a_n−1 − a_n−2 (n≥2).

Which of the following are solutions?

a

_n = 3n

a

_n = 2ⁿ

a

_n = 5

Yes

Yes No

(22)

이자율 계산 예제 (1/2)

Recurrence relation for growth of a bank account with P%

interest per given period: ⁽ 이자율이 P% 일 때 , 총액 계산 )

M _n = M _n−1 + (P/100)M _n−1

 M_n: 이번 달의 총액

 M_n−1: 지난 달의 총액

 (P/100)M_n−1: 지난 달의 이자

M

_n

= M

_n−1

+ (P/100)M

_n−1

= (1 + P/100) M

_n−1

= r M

_n−1

( let r = 1 + P/100)

= r (r M

_n−2

)

= r·r·(r M ) …and so on to…

(23)

이자율 계산 예제 (2/2) 예제 :

원금이 10,000 달러이고 , 1 년 이자가 11% 일 때 , 복리로 계산하면 30 년 후 계좌 잔고는 ?

 M_n = M_n−1 + (11/100)M_n−1= (1.11)M_n−1

 M₁ = (1.11)M₀

 M₂ = (1.11)M₁= (1.11)²

M

₀

 M₃ = (1.11)M₂= (1.11)³

M

₀

 _…

 M_n = (1.11)M_n-1= (1.11)ⁿ

M

₀

 M₃₀ = (1.11)³⁰

M

₀= (1.11)³⁰

x 10,000 = $228,922.97 // M

₀ = 10,000

(24)

피보나치 수열의 예제

주어진 ( 생물 , 미생물 ) 개체는 태어난 지 2 주기 이후에는 매 주기마다 하나의 새로운 개체를 생산한다 .

P _n = P _n−1 + P _n−2 (Fibonacci relation)

 P_n: 현재 (n 번째 ) 주기의 개체 수

 P_n−1: 바로 이전 주기에 있었던 개체의 수

 P_n−2: 새로 태어난 개체의 수 (2 주기 이후에 새로운 개체를 생산하므로 )

(25)

하노이 탑 예제 (1/3)

문제 : 말뚝 1 에 있는 모든 디스크를 말뚝 2 로 옮긴다 .

 한 번에 한 개의 디스크만 옮길 수 있다 .

 작은 디스크 위에 큰 디스크를 올려 놓을 수는 없다 .

말뚝 1 말뚝 2 말뚝 3

(26)

하노이 탑 예제 (2/3)

H

_n

= n 개 디스크 스택을 옮기는 데 필요한 디스크의 이동 횟수 최적의 전략 :

 상위 (n−1) 개 디스크를 여분 말뚝에 옮긴다 . (H

_n−1

moves)

 맨 아래 디스크를 옮긴다 . (1 move)

 여분 말뚝의 (n−1) 개 디스크를 옮긴다 .. (H

_n−1

moves)

Note: H _n = 2H _n−1 + 1

(27)

하노이 탑 예제 (3/3) H _n = 2 H _n−1 + 1

= 2 (2 H _n−2 + 1) + 1 = 2 ² H _n−2 + 2 + 1

= 2 ² (2 H _n−3 + 1) + 2 + 1 = 2 ³ H _n−3 + 2 ² + 2 + 1 …

= 2 ⁿ⁻¹ H ₁ + 2 ⁿ⁻² + … + 2 + 1

= 2 ⁿ⁻¹ + 2 ⁿ⁻² + … + 2 + 1 (since H ₁ = 1) =

= 2 ⁿ − 1

 ^

 1 0

2 n i

i

1

0

( 1)

, 1 ( 1)

n n

k k

ar a r r

r





  

 

(28)

분할 정보 (Divide & Conquer) 의 점화식

Consider a function f(n) that, for all n=b ^k for all kZ ⁺ ,

satisfies the recurrence relation: ^(n=b

^k

일 때 , 다음 점화 관계가 성립하면 )

with a≥1, integer b>1, real c>0, d≥0. Then:

log

O( ) if ( ) O( log ) if O( ^b ) if

d d

a d

n a b

f n n n a b

n a b

 

   

 



       

( ) n ^d

f n af cn

b

(29)

생판 처음 본 것이라고요 ?

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

혹 어렵다고 생각되시면 ,

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