Mathematical Preliminaries

1. Set Concepts and Notation

set notation => 중학교 때 배운 것..아재요..

powerset => 한 집합의 가능한 모든 부분 집합(subset)들의 집합

multiset => set 내부의 복제품을 가진 것 (ex. {a, a, b}, {a, a, b, b, b})

 

2. Relation

2-1. 정의

relation R over a set S는 S로부터 만들어진 R의 규칙으로 정렬된 pair들.

$R \times R \subseteq$ relation R over a set S

 

ex)

S = {1, 2, 3}

<의 관계 = {(1, 2), (1, 3), (2, 3)}

=의 관계 = {(1, 1), (2, 2), (3, 3)}

 

2-2. Properties

 

relation 특징

 

만약 모든 S에 속하는 a에게 aRa라면 reflexive다.

만약 모든 S에 속하는 a, b에게 aRb일 때, bRa라면 symmetric이다.

만약 모든 S에 속하는 a, b에게 aRb, bRa일 때, a=b라면 antisymmetric이다.

만약 모든S에 속하는 a, b, c에게 aRb, bRc일 때, aRc라면 transitive이다.

 

ex)

 

"<"

Reflexive : a<a (x)

Symmetric : a<b일 때, b<a? (x)

Antisymmetric : a<b, b<a이면 a=b(o), 왜냐면 충분조건이 거짓이라 명제는 무조건 참

Transitive : a<b, b<c이면 a<c(o)

 

"<="

Reflexive : a<=a (o)

Symmetric : a<=b일 때, b<=a? (x)

Antisymmetric : a<=b, b<=a이면 a=b(o)

Transitive : a<=b, b<=c이면 a<c(o)

 

"="

Reflexive : a=a (o)

Symmetric : a=b일 때, b=a? (o)

Antisymmetric : a=b, b=a이면 a=b(o)

Transitive : a=b, b=c이면 a=c(o)

 

"Friend of"

 

Reflexive : aFa (x)

Symmetric : aFb일 때, bFa? (o)

Antisymmetric : aFb, bFa이면 a=b(x)

Transitive : aFb, bFc이면 aFc(x) (not Always)

 

2-3. Equivalence relation

Equivalence relation : reflexive, symmetric, and transitive

 

ex) =, under modulo operation

Def if n = qm + r, then n = r(mod m)

x = x(mod m) -> x = 0*m + x

if x = y(mod m) -> y = x(mod m) : x = q*m + y -> y = -q*m + x

if x = y(mod m) and y = z(mod m) then x = z(mod m) : x = q*m + y, y = q'*m + z => x  (q + q') * m + z

 

2-4. Partial Order & Total Order

 

Partial order : antisymmetric and transitive

 

ex <, <=

 

Total order : Partial order && all pairs with distict elements are comparable!

 

comparable : 모든 순서쌍에 의해 relation의 참, 거짓 여부가 정해지는 것

 

3. Notation for Numbers

b : bit, B : byte

KB : killobyte(1000byte ~ $2^{10}$byte)

MB : megabyte($10^{6}$byte~$2^{20}$byte)

GB : gigabyte($10^{9}$byte~$2^{30}$byte)

TB : terabyte($10^{12}$byte~$2^{40}$byte)

PB : petabyte($10^{15}$byte~$2^{50}$byte)

 

=> 각각 2의 10승의 제곱으로 어림 가능

 

ex) 4GB = $2^{32}$byte

3-1. Big Numbers - Exercises

1) Assume you want to assign unique numerical ids to 50 milion people. How many bits are required to express the ids?

=> $\log_2 50million$이 어떤 것인지 대충 알아야 함

=> 1 million $\approx 2^{20}$

 

2) What is the amount of memory memory required to load 1000 images at once?

1000*1000 size의 image라고 가정할 때, 1 pixel의 크기를 4 byte라고 가정.

4byte * 1million $\approx 2^{22} byte$

$2^{22} byte$ * 1000 $\approx 2^{32} byte$

 

3) How much disk storage is required to save 1000 images for each of 50 million people?

$2^{32}$ * 50 * $2^{20}$byte

3-2. Miscellaneous Notation

ms: milisecond

Factorial n! = n * (n-1) * (n-2) ...

Permutation of a sequence S : S를 어떠한 순서로 배열한 것

Random permutation: permutation in a random order

Flooring(x) : 버림

Ceiling(x) : 올림

 

4. Logarithm

4-1. properties

 

log(nm) = logn+ logm

log(n/m) = logn - logm

log(n**r) = rlogn

loga(n) = logb(n)/logb(a)

 

loglog(n) = log(log(n))

log**2n = (logn)**2

 

5. Summation

$$\sum_{i=1}^n i = \frac{n(n+1)}{2}$$

 

$$\sum_{i=1}^n i^2 = \frac{2n^3 + 3n ^2 + n}{6} = \frac{n(2n+1)(n+1)}{6}$$

 

$$\sum_{i=1}^{\log n} n = n \log n$$

 

$$\sum_{i=1}^{\infty} a^i = \frac{1}{1-a} for \ 0 \lt a \lt 1$$

 

$$\sum_{i=1}^{n} a^i = \frac{a^{n+1} - 1}{a - 1} \ for \ a \neq 1$$

 

$$\sum_{i=1}^{n} \frac{i}{2^i} = 2 - \frac{n + 2}{2^n}$$

 

6. Recursion

6-1. Recurrence Relation

Recurrence relation : 함수가 자기 자신의 함수로 규정되는 경우

ex) fibonacci function : f(n) = f(n-1) + f(n-2), f(1)=f(2)=1

 

6-2. Closed Form

Closed form solution : 재귀를 쓰지 않고 함수를 규정하는 경우

ex) facorial = n! = n*(n-1)! = n * n-1 * n-2 * ... * 1(Closed form)

 

6-3. Recursion

Recursion : 자기 자신을 호출해서 답을 구하는 algorithm

ex) compute n!

Hanoi puzzle => HW1 참고

 

7. Mathematical Proof

7-1. Deduction

- 만약에 P -> R을 증명하고 싶다면, P->Q, Q->R을 차례로 증명하는 것

- P = Q를 증명하고 싶다면, P->Q and Q->P를 차례로 증명

 

7-2. Proof by contradiction

- 가장 간단한 방식으로 이론을 증명하는 기법

- P -> ~Q가 false임을 보여서, P->Q를 증명하는 기법

ex) No integer is the largest 

 

7-3. Proof by mathematical induction

- theorem X가 n>=c인 모두 정수에 대해서 true임을 보이는 기법

- Base case ; X가 c일 때 true임을 보임

- x가 n-1일 때 true라고 가정하고, X가 n일 때 true임을 보임.

 

7-4. Estimation Techniques

order of magnitude(지수함수로 커지는 scale)을 이용해서 값을 추론하는 기법