[이산 수학] - Discrete Mathematics (9) 썸네일형 리스트형 One to One, Onto definition Chapter 4.3 Exercise Find a theta notation 1. for i =1 to n 2. for j = 1 to i 3. x = x+1 → i = 1 : 1 time → i = 2 : 2 times → i = 3 : 3 times ... → i = n : n times ∴ 1 + 2 + 3 + ... + n = n(n+1)/2 = theta(n^2) 1. i = n 2. while (i>=1) { 3. x = x+1 4. i = floor | i/2 | 5. } → n = 8 = 2^3 : 1 → n = 4 : 1 → n = 2 : 1 → n = 1 : 1 (end) 4 times → If n = 16 = 2^4 : total 5 times ∴ 2^(k-1) Chapter 4.3 lg n denotes log2(n) 1) O(g(n)) - upper bound | f (n) | = ceiling| (6+1)/2 | + ... + 6 = 4 + 5 +6 >= ceiling| (6+1)/2 | + ceiling| (6+1)/2 | + ceiling| (6+1)/2 | → 1+2+3+...+n >= ceiling| (n+1)/2 | + ... + (n-1) + n >= ceiling| (n+1)/2 | + ... + ceiling| (n+1)/2 | = ceiling| (n/2) | * ceiling | (n+1)/2 | >= (n/2) * (n/2) = (n^2)/4 → 1+2+3+...+n = Ω(n^2) ∴ 1+2+3+...+n = theta(n^2) 1^k + 2^k + 3^k.. Chapter 4.1 ~ 2 Algorithms 2+2+...+2 = 200 vs 2*100 = 200 Pseudocode i) let = denote the assignment operator. x = y means "copy the value of y into x" x = y is executed, the value of y is unchanged. ii) Example if(y>x) z = x y = z if(y==x) z = x y = z if(y ㄱ= x) y = x else z = x a = z if(y large).. Chapter2. Proof (2.4) 2.4.3 Use induction to show that n! >= 2^(n-1) for all n>=1. (i) Basic Step (n=1) We must show that n! >= 2^(n-1) is true if n = 1. 1 ! = 1 >= 1 = 2^(1-1) (ii) Inductive Step We assume that the inequality is true for n >= 1 n! >= 2^(n-1) is true. We must then prove that the inequality is true for n+1 (n+1)! >= 2^n is true. (n+1)! = (n+1)n! Now (n+1)! = (n+1)n! >= (n+1)*2^(n-1) ( Because of n! >=.. Chapter2. Proofs (2.2) 2.2.1 We will give a proof by contradiction of the following statement : For every n ∈ Z, if n^2 is even, then n is even. Proof. We give a proof by contradiction. Thus we assume the hypothesis n^2 is even and that the conclusion is false n is odd. Since n is odd, there exists an integer k such that n = 2k+1. Now n^2 = (2k+1)^2 = 4k^2+4k+1 = 2(2k^2+2k)+1. Thus n^2 is odd, which contradicts the hy.. Chapter2. Proofs (2.1) 2.1.10 Give a direct proof of the following statement. For all integers m and n, if m is odd and n is even, then m+n is odd. Proof. Let m and n be arbitrary integers, and suppose that m is odd and n is even. We prove that m + n is odd. By definition, since m is odd, there exists k1 such that m = 2k1 + 1. Also, by definition, since n is even, there exists an integer k2 such that n = 2k2. Now the .. [이산수학] - Chapter1. Sets and Logic (2) 1.2 Propositions - A sentence that is either true or false conjunction p ∧ q (p and q) disjunction p ∨ q (p or q == inclusive-or) exclusive-or p exor q p q p exor q T T F T F T F T T F F F 1.3 Conditional Propositions & Logical Equivalence p → q p는 q이기 위한 충분조건 q는 p이기 위한 필요조건 P Q P → Q T T T T F F F T T F F T p if and only if q p if and only if q means that p if q ( q → p ) and p only if ( p → q .. [이산수학] - Chapter1. Sets and Logic (1) 목차 1.1 Sets - 집합 1.2 Propositions - 명제 1.3 Conditional Propositions and Logical Equivalence - 조건 명제와 논리적 동치 1.4 Arguments and Rules of Inference 1.5 Quantifiers - 한정사 1.6 Nested Quantifiers 1.1 Sets 집합이란? 간단히 말해 objects의 collection이다. 이 object는 elements or members가 될 수 있다. 너무 이해하기 어렵다면 집합이란 A = {1,2,3,4} 이다. (four elements) Z = integers Set Q = rational numbers Set R = real numbers Set X가 유한한 집합.. 이전 1 다음
