점화와 응용 (Recurrence and Its Applications)

Slides:



Advertisements
Similar presentations
2016 년 봄학기 강원대학교 컴퓨터과학전공 문양세 이산수학 (Discrete Mathematics) 알고리즘과 복잡도 (Algorithms and Complexity)
Advertisements

Lesson 11 What’s Your Type? 여러분의 유형은 무엇인가요 ?. What job do you want to have in the future? 여러분은 미래에 어떤 직업을 갖고 싶은가 ? p.218.
15 장. 알고리즘의 설계 알고리즘 설계 학습목표 기본 패턴 패턴의 한계점 일곱 가지 패턴의 알고리즘 설계 기법을 이해한다.
A: Could you tell me how to make a call from this phone
ALL IN ONE WORKING HOLIDAY!
Lecture 9 프로그램 실행의 비용 computation cost – 시간 time, 메모리 memory – tractable vs intractable problems.
이산수학(Discrete Mathematics)
(Mathematical Induction)
Sources of the Magnetic Field
Multiple features Linear Regression with multiple variables (다변량 선형회귀)
Chapter 7 ARP and RARP.
6.9 Redundant Structures and the Unit Load Method
Activation Records & Recursion
Internet Computing KUT Youn-Hee Han
어떤 과정으로 쓰면 될까.
Chaper 2 ~ chaper 3 허승현 제어시스템 설계.
축산 인식개선을 위한 농협의 추진 사례 ( ) 농협중앙회 축산지원단장 박인희.
정 의 학습의 일반적 정의 기계학습(Machine Learning)의 정의
알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 1 강원대학교 컴퓨터과학전공 문양세.
REINFORCEMENT LEARNING
Discrete Math II Howon Kim
On the computation of multidimensional Aggregates
제 34 장 금융정책과 재정정책이 총수요에 미치는 효과 1.
Ch. 5 : Analog Transmission
제 5장. Context-Free Languages
이산수학(Discrete Mathematics) 수학적 귀납법 (Mathematical Induction)
Genetic Algorithm 신희성.
Dynamic Programming.
Ch. 10 Algorithm Efficiency & Sorting
Ch. 10 Algorithm Efficiency & Sorting
Internet Computing KUT Youn-Hee Han
고대수학 1. 바빌로니아 이집트 그리스 인도 아랍 중국 미대륙.
제 14 장 거시경제학의 개관 PowerPoint® Slides by Can Erbil
After You Read, Talk and Talk
Chapter 2. Finite Automata Exercises
점화와 응용 (Recurrence and Its Applications)
계수와 응용 (Counting and Its Applications)
이산수학(Discrete Mathematics)
adopted from KNK C Programming : A Modern Approach
이산수학(Discrete Mathematics)  증명 전략 (Proof Strategy)
Talk and talk Could you…? 영어 7-b
Ch.02 Divide and Conquer (분할정복)
알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 년 봄학기
이산수학(Discrete Mathematics)
Dynamic Programming.
9. Do You Have a Scientific Mind?
Insight Deep MininG 건강을 위한 마이너스, 무첨가 식품 인사이트코리아/식품음료신문 공동 기획 기사
6.1 점화 관계 (Recurrence Relations)
제 1 장. 자료구조와 알고리즘.
Discrete Math II Howon Kim
합병정렬(Merge Sort) (1/2) 문제: n개의 정수를 (비내림차순으로) 정렬하시오.
CHAP 1:자료구조와 알고리즘.
이산수학(Discrete Mathematics) 비둘기 집 원리 (The Pigeonhole Principle)
3장. 탐색.
이산수학(Discrete Mathematics)
Internet Computing KUT Youn-Hee Han
7. Quicksort.
알고리즘 강의 슬라이드 2 분할정복 제 2 장 분할정복 도경구역, 알고리즘, 사이텍미디어, 1999.
창 병 모 숙명여대 전산학과 자바 언어를 위한 CFA 창 병 모 숙명여대 전산학과
자동제어공학 4. 과도 응답 정 우 용.
2.7 행렬 (Matrices] 이산수학 (Discrete Mathematics) Matrix Reloaded
이산수학(Discrete Mathematics)
알고리즘(Algorithm) – Divide and Conquer (분할정복)
이산수학(Discrete Mathematics)  증명 전략 (Proof Strategy)
이산수학(Discrete Mathematics) 수열과 합 (Sequences and Summations)
[CPA340] Algorithms and Practice Youn-Hee Han
빈칸에 알맞은 것을 [보기]에서 골라 문장을 완성하시오
Chapter 4. Energy and Potential
Chapter 7: Deadlocks.
Sawasdee ka.
Presentation transcript:

점화와 응용 (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 a1 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 = 10243+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 kZ+, 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)