Mathematics/Discrete Mathematics

기본 개념 실험(experimant)은 결과 도출 과정, 사건(event)은 실험 결과, 표본 공간(sample space)은 가능한 모든 실험 결과 집합이다.유한한 표본공간 $ S $ 에서 모든 결과가 동등하게(equally likely) 일어난다 가정할 때 사건 $ E $ 의 발생 확률 $ P(E) $ 은 $ P(E) = | E | / | S | $ 이다. 만약 가능한 결과가 $ n $ 개 라면 각 결과가 나올 확률은 $ 1/n $ 이다. 그러나 일반적으로 결과는 동등하게 일어나지 않는다.함수 $ P $ 를 확률 함수라 하면 표본공간 $ S $ 의 원소로서 각 결과 $ x \in S $ 에 대해 $ [0, 1] $ 의 수를 할당한다. 이때 할당된 수가 확률이며 $ \sum_{x \in S} P(x) ..

경우의 수 곱셈의 원리어떤 시행이 연속된 $ t $ 단계로 구성되고, 각 단계가 $ n_1, n_2, \cdots, n_t $ 가지 방법으로 이뤄져 있을 때 서로 다른 시행의 가능한 모든 경우의 수는 다음과 같다.$$ n_1 \times n_2 \times \cdots \times n_t $$요약하면 객체들이 연속적인 단계로 구성되면 곱셈 원리를 사용한다. 덧셈의 원리$ X_1, X_2, \cdots , X_t $ 가 집합이고 $ i $ 번째 집합 $ X_i $ 가 $ n_i $ 개의 원소를 가지고 있다 가정하자. 만약 $ \{ X_1, X_2, \cdots, X_t \} $ 가 서로소, 즉 $ i \neq j $ 일 때 $ X_i \cap X_j = \emptyset $ 이라 할 때 $ X_1 $ 또는..

공개키 암호 시스템 발신자와 수신자가 메시지를 외부에 노출하지 않으려면, 메시지를 은밀하게 보내는 방법도 사용할 수 있겠지만, 남들이 보더라도 무슨 말인지 알 수 없게 암호화하여 메시지를 보낼 수도 있을 것이다. 이때 발신자는 메시지를 암호화(encrypt)하여 수신자에게 보내야 할 것이고, 수신자는 받은 메시지를 복호화(decrypt)하여 확인해야 할 것이다.이러한 암호 시스템 중 하나가 공개키 암호 시스템인데, 개인키를 숨김으로써 메시지를 아무나 복호화할 수 없도록 하고, 공개키를 통해 암호화를 한다. 즉 절차는 다음과 같다.먼저 수신자가 공개키와 개인키를 만들어 발신자에게 공개키를 보낸다. 이때 개인키는 공개되지 않도록 하며 수신자만 확인할 수 있어야 한다.발신자는 수신자가 보낸 공개키를 이용하여 ..

유클리드 호제법 유클리드 호제법유클리드 호제법은 두 정수의 최대공약수를 찾기 위한 효율적인 알고리즘이다.$ a $ 가 음이 아닌 정수, $ b $ 가 양의 정수, $ r = a \bmod b $ 라면 $ \gcd(a, b) = \gcd(b, r) $ 이다. 이를 이용하여 $ a $ 에 $ b $ 를, $ b $ 에 $ r $ 을 대입하며 반복하다가 $ r $ 이 $ 0 $ 이 나온다면, $ b $ 가 최대공약수이다.이는 $ a $ 와 $ b $ 의 공약수의 집합이 $ b $ 와 $ r $ 의 공약수의 집합과 같다는 것을 보임으로써 증명 가능하다.몫과 나머지 정리에 의해 $ a = bq + r $ $ (0 \leq r (참고 링크). $ c \mid a $ 이고 $ c \mid bq $ 이므로 $ c \m..

정수 표현 흔히 정수를 십진법으로 표현한다. 이는 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 를 사용하여 정수를 표현하는 방법으로 기호의 위치에 따라 10의 n 제곱을 곱한다. 예를 들어 $ 179 = 1 \times 10^2 + 7 \times 10^1 + 9 \times 10^0 $ 와 같이 나타내는 것이다.수를 나타내는 진법이 근거로 하는 수, 즉 십진법의 십과 같은 수를 그 진법의 기수(base)라 한다.이진법(binary number system)에서 정수를 표현할 때는 0 과 1 만이 필요하다. 예를 들어 $ 101101_2 = 1 \times 2^5 + 0 \times 2^4 + 1 \times 2^3 + 1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 ..

약수 (Divisor) 정수 $ n $ 과 $ d $ 가 $ d \neq 0 $ 일 때, $ n = dq $ 를 만족하는 정수 $ q $ 가 존재하면 $ d $ 가 $ n $ 을 나눈다(divide)고 정의한다. 이때 $ q $ 를 몫(quotient), $ d $ 를 $ n $ 의 약수 또는 인수(factor)라 한다. 만약 $ d $ 가 $ n $ 을 나누면 $ d \mid n $ 으로 표기하고, 나누지 못한다면 $ d \nmid n $ 으로 표기한다.양의 정수 $ n $ 과 $ d $ 가 $ d \mid n $ 이면 $ d \leq n $ 이다. 왜냐하면 $ d \mid n $ 이면 $ n = dq $ 인 양의 정수 $ q $ 가 존재하며 따라서 $ d \leq dq = n $ 이기 때문이다.몫-나..

알고리즘 (Algorithms) 알고리즘은 어떤 문제를 해결하기 위한 단계별 방법이며, 다음의 특성을 가진다.입력 (Input) : 알고리즘은 입력을 받는다.출력 (Output) : 알고리즘은 출력을 생성한다.정밀성 (Precision) : 각 단계가 명확하게 기술되어 있다.결정성 (Determinism) : 실행 과정에서 각 단계의 결과는 유일하며, 입력과 이전 단계의 결과에 의해 결정된다.유한성 (Finiteness) : 알고리즘은 유한한 수의 명령어가 실행된 후 종료된다.정확성 (Correctness) : 알고리즘이 생성한 출력은 문제를 정확하게 해결한다.일반성 (Generality) : 알고리즘은 일련의 입력에 대해 적용된다. 의사코드 (Pseudo-code) 영어를 그대로 읽어서 슈도코드라고도 ..

이항 관계 (Binary Relation) 어떤 집합에서 다른 집합으로의 관계(relation)는 첫 번째 집합의 요소들이 두 번째 집합의 어떤 요소들과 관련되어 있는지로 확인할 수 있다. 예를 들어 자연수의 영역에서 정의된 항등함수를 생각하면, $ \{(1, 1), (2, 2), \cdots, (n, n) \} $ 으로 나타낼 수 있을 것이다.즉 집합 $ X $ 에서 집합 $ Y $ 로의 관계(여기서는 두 집합의 관계이므로 이항관계) $ R $ 은 $ X \times Y $ 의 부분집합이다. 만약 $ (x, y) \in R $ 이면, $ x \text{ } R \text{ } y $ 라 쓰고 $ x $ 가 $ y $ 와 관계있다고 말한다. 이 후 관계라 하면 이항 관계를 말한다.이때 관계 $ R $ 의..

수열 (Sequence) 수열 $ s $ 는 정의역 $ D $ 가 정수의 부분집합인 함수이다. $ s(n) $ 대신 $ s_n $ 표기법을 사용하며, 이때 $ n $ 을 수열의 인덱스(index)라 한다. $ D $ 가 유한 집합인 수열을 유한 수열, 그렇지 않으면 무한 수열이라 한다. 수열은 $ s $ 으로 표기하고, 수열의 단일 원소는 인덱스를 붙여 $ s_n $ 으로 나타낸다.무한 수열은 다음과 같은 수열을 고려해 확인해볼 수 있다. 수열 $ s : 2, 4, 6, \dots , 2n , \dots $ 을 고려하면 $ n $ 번째 원소는 $ 2n $ 이다. 만약 정의역이 양의 정수 집합 $ \mathbb{Z}^+ $ 라면 $ s_1 = 2, s_2 = 4, \dots , s_n = 2n, \dots..

함수의 정의 함수는 어떤 집합의 각 원소를 다른 어떤 집합의 각 원소에 유일하게 대응시키는 관계를 말한다. 예를 들어 $ X $ 와 $ Y $ 가 집합일 때 $ X $ 에서 $ Y $ 로의 함수 $ f $ 는 $ f : X \to Y $ 로 나타낸다. 이는 카테시안 곱 $ X \times Y $ 의 부분집합으로 정의되며 카테시안 곱은 $ \{ (x,y) \mid x \in X, y \in Y \} $ 이다. 각 $ x \in X $ 에 대해 정확히 하나의 $ y \in Y $ 가 존재하여 $ (x,y) \in f $ 를 만족하는 성질을 가진다. 이를 $ f(x) = y $ 라 표기한다.이때 집합 $ X $ 를 정의역(domain)이라 하고, 집합 $ Y $ 를 공역(codomain)이라 한다. $ f $..