Mathematics Review for Algorithm [CPA340] Algorithms and Practice Youn-Hee Han http://link.kut.ac.kr

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

올림(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 규칙

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

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

순열(Arithmetic Sequence)과 합(Series) (2/14)

순열(Arithmetic Sequence)과 합(Series) (3/14) We wanted to work out the sum of: 1 + 2 + 3 + ….. + 98 + 99 + 100 100 + 99 + 98 + ….. + 3 + 2 + 1 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

순열(Arithmetic Sequence)과 합(Series) (4/14) 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)

순열(Arithmetic Sequence)과 합(Series) (5/14) 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 )

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

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

순열(Arithmetic Sequence)과 합(Series) (8/14) Given Arithmetic Series Calculate Note that So,

순열(Arithmetic Sequence)과 합(Series) (9/14) Problem 1 Problem 2

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

순열(Arithmetic Sequence)과 합(Series) (11/14) Problem 1 Problem 2

순열(Arithmetic Sequence)과 합(Series) (12/14) Telescoping Sum

순열(Arithmetic Sequence)과 합(Series) (13/14) Example 1: Note:

순열(Arithmetic Sequence)과 합(Series) (14/14) 시그마의 성질

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

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

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

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

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

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

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

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

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

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

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

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

집합 (Set) (1/2) 집합(set)이란 순서를 고려하지 않고 중복을 고려하지 않는 객체(원소, 멤버)들의 모임이다. 집합의 표현 방법: 원소 나열법, 조건 제시법 원소 나열법 (예: {…, -3, -2, -1, 0, 1, 2, 3, …}) 조건 제시법 (예: {x | x is integers}) 집합의 항등: 동일한 원소들로 이루어진 두 집합은 동일하다. 주요 표기법: xS: x는 집합 S의 원소이다. : 공집합(empty set) (원소가 하나도 없는 유일한 집합) S  T: 집합 S는 집합 T 의 부분집합(subset)이다. S  T: 집합 S는 집합 T 의 진부분집합(proper subset)이다.

집합 (Set) (2/2) 합집합: AB = {x | xA  xB} 교집합: 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}

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

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

순열과 조합 (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가지 이다.

확률 (Probability) (1/2) 표본공간(sample space) 혹은 모집단(population): 가능한 모든 결과의 집합 (예: 주사위의 경우, 1, 2, 3, …, 6) 사건(event): 표본 공간의 부분집합 (주사위에서 짝수가 나오는 사건의 집합) 원소사건: 단지 하나의 원소만 가지는 부분집합 (주사위에서 1이 나오는 사건)

확률 (Probability) (2/2) 정의: 표본공간이 n개의 다른 결과를 가진 {e1, e2, ..., en}이라 하자. 각 사건 ei 에 실수 p(ei )를 지정하는 함수가 다음 조건을 만족하면, 이를 확률함수(probability function)라 한다. 1  i  n에 대해서, 0  p(ei)  1이다. p(e1) + p(e2) + … + p(en)  1 이다. 사건 S에 대한 p(S)는 S에 속하는 원소사건들의 확률의 합이다. (예: p(S) = p(e1) + p(e2) + p(e7) if S = {e1, e2, e7})