점화와 응용 (Recurrence and Its Applications) 이산수학(Discrete Mathematics) 점화와 응용 (Recurrence and Its Applications) 2016년 봄학기 강원대학교 컴퓨터과학전공 문양세
점화 관계(Recurrence Relations) 분할과 정복(Divide and Conquer) 강의 내용 Recurrence and Its Applications 점화 관계(Recurrence Relations) 분할과 정복(Divide and Conquer)
Recurrence Relations Recurrence Relations A recurrence relation (R.R., or just recurrence) for a sequence {an} is an equation that expresses an in terms of one or more previous elements a0, …, an−1 of the sequence, for all n≥n0. (수열 {an}에 대한 점화 관계란 an을 이전의 항들인 a0, …, an−1들을 사용하여 표시하는 등식이다. 대표적인 예가 피보나치 수열) A particular sequence is said to solve the given recurrence relation if it is consistent with the definition of the recurrence. (특정한 수열이 주어진 점화 관계를 만족하면 해당 수열을 주어진 점화 관계의 해라 한다. 다음 페이지의 예를 참조) A given recurrence relation may have many solutions. (주어진 점화 관계는 하나 이상의 많은 해를 가질 수 있다.)
Recurrence Relation Example Recurrence Relations Consider the recurrence relation an = 2an−1 − an−2 (n≥2). Which of the following are solutions? an = 3n an = 2n an = 5 Yes No Yes
이자율 계산 예제 (1/3) Recurrence Relations Recurrence relation for growth of a bank account with P% interest per given period: (이자율이 P%일 때, 총액 계산) Mn = Mn−1 + (P/100)Mn−1 Mn: 이번 달의 총액 Mn−1: 지난 달의 총액 (P/100)Mn−1: 지난 달의 이자
= r·r·(r Mn−3) …and so on to… = rn M0 이자율 계산 예제 (2/3) Recurrence Relations Mn = Mn−1 + (P/100)Mn−1 = (1 + P/100) Mn−1 = r Mn−1 (let r = 1 + P/100) = r (r Mn−2) = r·r·(r Mn−3) …and so on to… = rn M0
예제: 원금이 10,000 달러이고, 1년 이자가 11%일 때, 복리로 계산하면 30년 후 계좌 잔고는? 이자율 계산 예제 (3/3) Recurrence Relations 예제: 원금이 10,000 달러이고, 1년 이자가 11%일 때, 복리로 계산하면 30년 후 계좌 잔고는? Mn = Mn−1 + (11/100)Mn−1 = (1.11)Mn−1 M1 = (1.11)M0 M2 = (1.11)M1 = (1.11)2M0 M3 = (1.11)M2 = (1.11)3M0 … Mn = (1.11)Mn-1 = (1.11)nM0 M30 = (1.11)30M0 = (1.11)30 x 10,000 = $228,922.97 // M0 = 10,000
Pn = Pn−1 + Pn−2 (Fibonacci relation) 피보나치 수열의 예제 Recurrence Relations Growth of a population in which each organism yields 1 new one every period starting 2 periods after its birth. (예제 4: 주어진 (생물, 미생물) 개체는 태어난 지 2주기 이후에는 매 주기마다 하나의 새로운 개체를 생산한다… ) Pn = Pn−1 + Pn−2 (Fibonacci relation) Pn: 현재(n 번째) 주기의 개체 수 Pn−1: 바로 이전 주기에 있었던 개체의 수 Pn−2: 새로 태어난 개체의 수 (2주기 이후에 새로운 개체를 생산하므로)
하노이 탑 예제 (1/3) Recurrence Relations Problem: Get all disks from peg 1 to peg 2. (말뚝 1에 있는 모든 디스크를 말뚝 2로 옮긴다.) Only move 1 disk at a time. (한 번에 한 개의 디스크만 옮길 수 있다.) Never set a larger disk on a smaller one. (작은 디스크 위에 큰 디스크를 올려 놓을 수는 없다.) Peg #1 Peg #2 Peg #3
하노이 탑 예제 (2/3) Recurrence Relations Let Hn = # of moves for a stack of n disks. (Hn을 n개의 디스크 스택을 옮기는 데 필요한 디스크의 이동 횟수라 하자.) Optimal strategy: Move top n−1 disks to spare peg. (Hn−1 moves) Move bottom disk. (1 move) Move top n−1 to bottom disk. (Hn−1 moves) Note: Hn = 2Hn−1 + 1
하노이 탑 예제 (3/3) Hn = 2 Hn−1 + 1 = 2 (2 Hn−2 + 1) + 1 = 22 Hn−2 + 2 + 1 Recurrence Relations Hn = 2 Hn−1 + 1 = 2 (2 Hn−2 + 1) + 1 = 22 Hn−2 + 2 + 1 = 22(2 Hn−3 + 1) + 2 + 1 = 23 Hn−3 + 22 + 2 + 1 … = 2n−1 H1 + 2n−2 + … + 2 + 1 = 2n−1 + 2n−2 + … + 2 + 1 (since H1 = 1) = = 2n − 1
More Examples (1/2) Recurrence Relations 예제 (비트 스트링 문제): 두 개의 연속적인 0들을 갖지 않는(0이 연달아 2개 나오지 않는) 길이 n의 비트 스트링 개수에 대한 점화 관계와 초기 조건을 제시하라. # of bit strings of length n with no two consecutive 0s: End with a 1: Any bit string of length n – 1 with no two consecutive 0s 1 an-1 an-2 End with a 0: Any bit string of length n – 2 with no two consecutive 0s 1 0 an = an-1 + an-2 Total: 점화 관계: an = an-1 + an-2 초기 조건: a1 = 2 = |{0, 1}|, a2 = 3 = |{01, 10, 11}|
More Examples (2/2) Recurrence Relations 예제 (코드 워드 나열): 짝수 개의 0을 포함하는 십진수는 유효한 코드 워드(예: 1230407869는 유효하고, 120987045608은 유효하지 않다)라 하고, an을 n자리 코드 워드의 개수라 할 때, an의 점화 관계를 구하라. 한 자리 스트링(0, 1, 2, .., 9) 중 0은 유효치 않으므로, a1 = 9. an에 대해서는 다음 두 가지 경우의 합으로 나타난다. Case 1: (n–1)자리 유효한 스트링에 0이 아닌 수를 더한 스트링의 개수 = 9an-1 Case 2: (n-1)자리 유효하지 않은 스트링에 0을 더한 스트링의 개수 = (10n-1 - an-1) ( (n-1)자리 스트링은 10n-1개이고 이중 an-1이 유효한 스트링 이므로) an = 9an-1 + (10n-1 - an-1) = 8an-1 + 10n-1
점화 관계(Recurrence Relations) 분할과 정복(Divide and Conquer) 강의 내용 Recurrence and Its Applications 점화 관계(Recurrence Relations) 분할과 정복(Divide and Conquer)
Time for each sub-problem Divide & Conquer Recurrence Relations Divide and Conquer Main points so far: Many types of problems are solvable by reducing a problem of size n into some number a of independent sub-problems, each of size n/b, where a1 and b>1. (많은 경우에 있어서, 크기 n의 문제를 a개의 크기 n/b의 작은 문제로 바꾸어 처리할 수 있다.) The time complexity to solve such problems is given by a recurrence relation: T(n) = a·T(n/b) + g(n) (이런 경우의 시간 복잡도는 T(n)의 점화 관계로 나타낼 수 있다.) Time for each sub-problem Time to break problem up into sub-problems
Divide & Conquer Examples Divide and Conquer Binary search: Break list into 1 sub-problem (smaller list) (so a=1) of size n/2 (so b=2). So T(n) = T(n/2)+c (g(n)=c constant) Merge sort: Break list of length n into 2 sub-lists (a=2), each of size n/2 (so b=2), then merge them, in g(n) = (n) time. So T(n) = 2T(n/2) + cn (roughly, for some c)
Fast Multiplication Example (1/3) Divide and Conquer The ordinary grade-school algorithm takes (n2) steps to multiply two n-digit numbers. (학교에서 배운 방법에 따르면, n자리인 두 수의 곱은 (n2) 스텝이 필요하다.) This seems like too much work! So, let’s find a faster multiplication algorithm! To find the product cd of two 2n-digit base-b numbers, c=(c2n-1c2n-2…c0)b and d=(d2n-1d2n-2…d0)b, first, we break c and d in half: c=bnC1+C0, d=bnD1+D0, (e.g., 4321 = 10243+21) and then... (see next slide)
Fast Multiplication Example (2/3) Divide and Conquer Zero Three multiplications, each with n-digit numbers (Factor last polynomial)
Fast Multiplication Example (3/3) Divide and Conquer Notice that the time complexity T(n) of the fast multiplication algorithm obeys the recurrence: T(2n)=3T(n)+(n) i.e., T(n)=3T(n/2)+(n) So a=3, b=2. ( The order will be reduced …) Time to do the needed adds & subtracts of n-digit and 2n-digit numbers
with a≥1, integer b>1, real c>0, d≥0. Then: The Master Theorem Divide and Conquer Consider a function f(n) that, for all n=bk for all kZ+, satisfies the recurrence relation: (n=bk 일 때, 다음 점화 관계가 성립하면) f(n) = af(n/b) + cnd with a≥1, integer b>1, real c>0, d≥0. Then: Proof of the theorem is …. omitted.
Master Theorem Examples (1/3) Divide and Conquer Recall that complexity of fast multiplication was: T(n)=3T(n/2)+(n) Thus, a=3, b=2, d=1. So a > bd, so case 3 of the master theorem applies, so: which is O(n1.58…), so the new algorithm is strictly faster than ordinary (n2) multiply!
Master Theorem Examples (2/3) Divide and Conquer 예제(Binary Search): 이진 탐색의 복잡도는 얼마인가(비교 수를 추정하라)? 이진 탐색의 점화 관계: T(n) = T(n/2)+c (n 이 짝수라 가정) 매스터 정리로 보면, a = 1, b = 2, d = 0으로서, a = 1 = bd인 두 번째 경우에 해당한다. 결국, 다음과 같은 과정에 의해 O(logn)이 된다.
Master Theorem Examples (3/3) Divide and Conquer 예제(Merge Sort): 합병 정렬의 복잡도는 얼마인가(비교 수를 추정하라)? 이진 탐색의 점화 관계: T(n) = 2T(n/2)+cn (n 이 짝수라 가정) 매스터 정리로 보면, a = 2, b = 2, d = 1로서, a = 2 = bd인 두 번째 경우에 해당한다. 결국, 다음과 같은 과정에 의해 O(nlogn)이 된다.
점화 관계(Recurrence Relations) 분할과 정복(Divide and Conquer) 강의 내용 Recurrence and Its Applications 점화 관계(Recurrence Relations) 분할과 정복(Divide and Conquer)