6.1 점화 관계 (Recurrence Relations) 이산수학 (Discrete Mathematics) 6.1 점화 관계 (Recurrence Relations) 2006년 봄학기 문양세 강원대학교 컴퓨터과학과

We will cover … in Chapter 6. 6.1 Recurrence Relations $6.1 Recurrence Relations (점화 관계) $6.3 Divide-and-Conquer (분할 정복) $6.5 Inclusion-Exclusion (포함-배제)

Recurrence Relations 6.1 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 6.1 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) 6.1 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) 6.1 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

예제 3: 원금이 10,000 달러이고, 1년 이자가 11%일 때, 복리로 계산하면 30년 후 계좌 잔고는? 이자율 계산 예제 (3/3) 6.1 Recurrence Relations 예제 3: 원금이 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) 피보나치 수열의 예제 6.1 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) 6.1 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) 6.1 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 6.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) 6.1 Recurrence Relations 예제 6 (비트 스트링 문제): 두 개의 연속적인 0들을 갖지 않는 길이 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) 6.1 Recurrence Relations 예제 7 (코드 워드 나열): 짝수 개의 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) an = 9an-1 + (10n-1 - an-1) = 8an-1 + 10n-1

모든 점화 관계식을 (단순하게) 해결할 수는 없다. 주요 점화 관계식에 대한 풀이는 $6.2를 참조한다. 점화 관계식 풀기 6.1 Recurrence Relations 모든 점화 관계식을 (단순하게) 해결할 수는 없다. 주요 점화 관계식에 대한 풀이는 $6.2를 참조한다.