Mathematics Review for Algorithm

Presentation on theme: "Mathematics Review for Algorithm"— Presentation transcript:

1 Mathematics Review for Algorithm
[CPA340] Algorithms and Practice Youn-Hee Han

2 수업 내용 복습 내용 올림과 내림 순열과 합 수학적 귀납법 정리, 보조정리 로그 집합 순열과 조합 확률

3 올림(Ceiling)과 내림(Floor) (1/2)
올림함수(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 규칙

4 올림(Ceiling)과 내림(Floor) (2/2)
다음 빈칸을 채우시오

5 등차순열(Arithmetic Sequence)과 합(Series) (1/9)
시그마를 사용한 합의 표현 How many cans are there in this pyramid. How many cans are there in a pyramid with 100 cans on the bottom row?

6 등차순열(Arithmetic Sequence)과 합(Series) (2/9)

7 We wanted to work out the sum of:
등차순열(Arithmetic Sequence)과 합(Series) (3/9) We wanted to work out the sum of: … … If we write it out in reverse we get…. 101 + 101 + 101 +….. How many times do we add 101 together? 101 x 100 = 10100 What do we need to do to this answer? 10100 / 2 = 5050

8 등차순열(Arithmetic Sequence)과 합(Series) (4/9)
a = first term l = last term d = common difference a (a + d) + (a + 2d) (a + 3d) (l - 2d) (l - d) l (l - 3d) …. l (l - d) + (l - 2d) (l - 3d) (a + 2d) (a + d) a (a + 3d) …. There are n pairs of numbers that add up to (a + l) Arithmetic Series = ½ n (a + l)

9 등차순열(Arithmetic Sequence)과 합(Series) (5/9)
a = first term l = last term d = common difference Arithmetic Series = ½ n (a + l) From last lesson, we know that the nth term (last term) is given by: l = a + (n – 1) d Arithmetic Series = ½ n (2a + (n – 1) d )

10 등차순열(Arithmetic Sequence)과 합(Series) (6/9)
a = first term l = last term d = common difference Arithmetic Series = ½ n (a + l) Arithmetic Series = ½ n (2a + (n – 1) d )

11 Find the sum of the arithmetic series: 11 + 15 + 19 + … + 107
등차순열(Arithmetic Sequence)과 합(Series) (7/9) Find the sum of the arithmetic series: … + 107 a = 11 d = 4 l = 107 l = a + (n – 1)d From last lesson… 107 = (n – 1) Sub values in… n = 25 Solving… Sum = ½ n (a + l) Using formula… Sum = ½ 25 ( ) Sub values in… Sum = 1475

12 등차순열(Arithmetic Sequence)과 합(Series) (8/9)
Given Arithmetic Series Calculate Note that So,

13 등차순열(Arithmetic Sequence)과 합(Series) (9/9)
Problem 1 Problem 2

14 등비순열(Geometric Sequence)과 합(Series) (1/14)
Given Geometric Series Don’t use it when r = 1 Infinite Geometric Series for r < 1

15 등비순열(Geometric Sequence)과 합(Series) (2/4)
Problem 1 Problem 2

16 등비순열(Geometric Sequence)과 합(Series) (3/4)
Telescoping Sum

17 등비순열(Geometric Sequence)과 합(Series) (3/4)
Example 1: Note:

18 시그마의 성질 시그마의 성질

19 함수 (Function) 함수 f 는 변수 x를 유일한 값 f(x)로 관계를 형성하는 규칙 또는 법칙이다.
함수는 튜플(tuple, ordered pair)을 결정하며, 이들 튜플을 좌표에 그리면 그래프가 된다. 정의역: x값의 범위 (domain) 공변역(변역, 공역): 함수 f가 정의되는 값의 범위 (codomain) 치역: 정의역이 함수 f에 의해 매핑된 범위 (range)

20 수학적 귀납법 (mathematical induction) (1/2)
어떤 등식이 모든 n에 대해서 성립함을 보이기 위해서, 가능한 모든 n을 등식에 대입하여 증명할 수는 없다. 수학적 귀납법: 주어진 등식이 n=1일 때 성립함을 증명하고, n일 때 성립한다고 가정한 후, n+1일 때 성립함을 증명한다. 그러면, 도미노의 원리와 같이 모든 n에 대해서 성립하는 것이다.

21 수학적 귀납법 (mathematical induction) (2/2)
수학적 귀납법을 이용한 증명 과정 귀납 기본(Induction base): n=1(혹은 n=0)에 대해 등식이 성립함을 증명한다. 귀납 가정(Induction hypothesis): 임의의 n에 대해 등식이 성립한다고 가정한다. 귀납 단계(Induction step): 등식이 n+1에 대해서도 성립함을 증명한다.

22 수학적 귀납법 예제 (1/3) 모든 양의 정수 n에 대해서 다음 등식이 성립함을 증명하라. 증명
Induction base: n=1일 때 성립한다. Induction hypothesis: n일 때 성립한다고 가정한다. 즉, Induction step: 다음 과정에 의해 n+1일 때 역시 성립한다.

23 수학적 귀납법 예제 (2/3) 모든 음이 아닌 정수 n에 대해서 다음 등식이 성립함을 증명하라. 증명
Induction base: n=0일 때 성립한다. Induction hypothesis: n일 때 성립한다고 가정한다. 즉, Induction step: 다음 과정에 의해 n+1일 때 역시 성립한다.

24 수학적 귀납법 예제 (3/3) 모든 음이 아닌 정수 n에 대해서 다음 등식이 성립함을 증명하라. 증명 (Self-test)
Induction base: n=1일 때 성립한다. Induction hypothesis: n일 때 성립한다고 가정한다. Induction step: 다음 과정에 의해 n+1일 때 역시 성립한다.

25 정리(Theorem)와 보조정리(Lemma) (1/3)
정리란 참(true)으로 밝혀진 명제이다 (A statement that has been proven to be true.) 반드시 Proof 필요 보조정리(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.

26 정리(Theorem)와 보조정리(Lemma) (2/3)
공리(axiom, postulates) 증명된 정리 혹은 증명하고자 하는 정리의 가정이다. Assumptions (often unproven) defining the structures about which we are reasoning. Proof 필요 없이 가정하는 것 추론 규칙(rules of inference) 논리적으로 유효한 주장(logically valid deductions)을 사용하여 임의의 가정을 결론까지 이끌어가는 증명의 과정이다. Patterns of logically valid deductions from hypotheses to conclusions.

27 정리(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.

28 지수(exponent)와 로그 (Logarithm) (1/3)
임의의 실수 에 대하여 예제

29 지수(exponent)와 로그 (Logarithm) (2/3)
상용로그 (common logarithm): 밑이 10인 로그 로그의 주요 특성

30 지수(exponent)와 로그 (Logarithm) (3/3)
자연로그 (natural logarithm): 밑이 e인 로그 밑이 e(= …)인 로그 예: 적분을 사용한 자연로그 개념: 함수 1/x 에서, ln x는 1과 x 사이의 면적을 나타낸다.

31 순열과 조합 (1/3) 순열(Permutation): 주어진 n개 물체 중에서 k개를 선택하여 나열하는 방법의 수
조합(Combination): 주어진 n개 물체 중에서 k개를 선택하는 방법의 수

32 순열과 조합 (2/3) 조합의 예제: 10명으로 구성된 팀에서 경기에 나갈 선수 5명을 선발하는 방법은 모두 몇 가지인가?
10명 중에서 5명을 선발하되, 5명의 순서는 고려할 필요가 없으므로, 10개의 원소 집합에서 5-조합의 수를 구하는 문제임

33 순열과 조합 (3/3) 순열의 예제: 100명이 참여한 경품 행사에서, 1등, 2등, 3등을 한 명씩 선발하는 방법은 모두 몇 가지 인가? 3등을 선발하는 방법 = 100가지 2등을 선발하는 방법 = 99가지 1등을 선발하는 방법 = 98가지 결국, 100 x 99 x 88 = 970,220가지 이다. 순열을 활용하면…. 100명 중에서 세 명을 뽑아서 순서대로 나열하는 방법… 결국, P(100,3) = 970,220가지 이다.