• Set: 중복을 허용하지 않는 정렬되지 않은 집합 Defining set

  • Roster Method S = {a,b,c, …}
  • Set-Builder Notatoin S = {x|P(x)}

  Properties

  • Set Equality A=B ↔ ∀x(x∈A⇔x ∈B) ↔ ∀x((x∈A → x ∈B) Λ (x∈B → x ∈A)) ↔ (A ⊆ B) Λ (B ⊆ A)
  • Subset(부분집합) A ⊆ B
  • Proper Subset(진부분집합) A ⊆ B, A ≠ B ↔ ∀x((x∈A → x ∈B) Λ ∃(x∈B Λ ㄱ(x ∈A))) : B에 있고 A에 없는게 있다
  • Cardinality: number of DISTINCT elements |{1,2,2,3}| = 3 |Φ| = 0 |{Φ}| =1
  • |AUB| = |A|+|B| - |A∩B|
  • Power Set(멱집합): 모든 부분집합의 집합 ex) P({1,2}) = { Φ, {1}, {2}, {1,2}}
  • Tuple: ordered n-tuple (a1,a2,…,an)
  • pair: 2-tuple (a,b)
  • Cartesian Product AxB : Set of ordered pair {(a,b) | a ∈B, b∈ B}
  • Truth Set(진리집합) : { x∈Domain | P(x)}

  Operations

  : 논리에서의 연산과 동일(T를 U로, F를 Φ로, V를∪, Λ를 ∩, ㄱ를 윗줄로) *A - B = A ∩ B^c

• Function : f:A→B, one element in A → one element in B, f(a) = b

  • Terminology

    • A = Domain(정의역)
    • B = Codomain(공역)
    • f(A) = Range(치역)
    • f(a) = b: image(상), a: preimage(원상)

  • category

    injective	surjective	bijective
    one to one, 단사	onto, 전사	one to one correpondance, 전단사
    정의역의 모든 원소 사용	공역의 모든 원소 사용	정의역과 공역의 원소 전부 사용
    f(a)=f(b) ↔ a=b	∀b ∈B, ∃a ∈A s.t f(a)=b	f(a)≠ f(b) ↔ a≠b

    proof:

    injective: show f(a) exists for all a in domain surjective: show for all b, a exists s.t f(a) = b

  • Inverse function f-1 f should be bijection

  • Graph of f(x): {(a,b)|a∈A, b=f(a)}

  • Composition f*g(x) = f(g(x))

• Set Cardinality

  • Equality, inequality |A| = |B|: bijection exists |A| ≤ |B|: injection exists
  • Contable set(가산집합): 자연수 집합으로의 단사 함수 존재 Cardinality = “Aleph Null” = |N| = |Z| = |Q|
  • thm) all infinite set contains Countable infinite subset pf) pick a0 from S, a1 from S-{a0}, a2 from S-{a0,a1}, … since S is infinite, S-{a0,a1,…} is infinite therefore ai is infinite, countable ■
  • thm) for countable A,B: AUB is countable
  • thm) |A|≤|B|, |B|≤|A| →|A|=|B| *how to proof two sets have same cardinality: find injective func from A to B, B to A

• Matrix (skip basic concept of matrices)

  • zero-one matrices: contain only 1 and 0
    join: A V B = [a11Vb11, a12Vb12, …] meet A Λ B = [a11Λb11, a12Λb12,…] boolean product A ⊙ B : 행렬 곱할때, 곱하기를 AND로 더하기를 OR로 취급해서 불 연산함. i.e. cij = (ai1 Λ b1j) V (ai2 Λ b2j) V …

• Algorithms Algorithm is a finite set of precise instructions for solving problem

  • Searching problems Linear search algorithm BST
  • Sorting problems bubble, insertion, selection
  • Greedy algorithm : 매 단계마다 최선의 선택
  • prove greedy is best: proof by contradiction; 더 좋은 해를 가정, 모순
  • Halt problem(정지 문제) : 프로그램이 특정 입력에 언제 종료하는지 결정할 수 있는가? 정답: NO 풀리지 않는다 자세한 증명은 찾아보기

• Algorithm complexity (consider time complexity)

  • Big-O notation: upper bound def) for some C, k, if |f(x)|≤C|g(x)| for x>k then f(x) ∈ O(g(x))
  • f is O(g), g is O(f) →same order
  • Big-Ω notation: lower bound, |f(x)|≥C|g(x)|
  • BIg-Θ notation: f(x) ∈ O(g(x)), f(x) ∈ Ω(g(x))

Big-O examples 1<log n < n^a (a<1) < n < nlog n < n^b (b>1) < a^n (a>1) < n! < n^n (log n)^c < n^d n^a < b^n

Complexity analysis

• write pseudocode
• count total step of algorithm in worst case(O), avg case(Θ), best case(Ω)