기본 개념 실험(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$..